RSA Flashcards
What is the key generation for RSA?
- Pick two large prime numbers p and q
- Let n = pq (the modulus)
- Compute (p-1)(q-1)
- Find a number e which is coprime/relatively prime with (p-1)(q-1). e is also called the public exponent.
- Compute the multiplicative inverse d of e modulo (p-1)(q-1). d is also called the private exponent.
How do you encrypt a message (m) using RSA?
m^e mod n
Where:
m = message
e = public exponent
n = the modulus
How do you decrypt a ciphertext (c) using RSA?
c^d mod n
Where:
d = private exponent
n = the modulus
If x is the multiplicative inverse of y then:
x * y = 1
If x is y’s multiplicative inverse modulo n if:
(x * y) mod n = 1
Is RSA secure?
Brute force attacks are infeasible for large numbers.
The most efficient way to attack RSA is by factoring n the modulus as this would get you p and q and allow you to calculate everything else. However factoring integers is intracteable
Define relatively prime for x and y:
Two integers x and y are relatively prime if their greatest common divisor is 1
What are the two types of MACs for hashing?
- Combine hashing with a secret key. Constructed with help from a hashing function
- Build the MAC from a block cipher