RSA explained

2014-10-13

3 minute read

Refresh myself with RSA A trapdoor function which means that a hard problem could be easy if you provide some “trapdoor” information which can “open the door” easily. RSA is just a kind of trapdoor function.

Basic Problems

Factoring

Factoring is to find prime factors of a composite number, and we want this can be solved in polynomial time. However, even for a easy case, say just two primes, this problem is still very hard. See this wiki You could say that we can increase computation power to make it faster since they are growing everyday, but the solution would be much easier that we just simply increase the size of the prime factors.

RSA Assumption

RSA needs a modulo as \(N=pq\), while \(p\) and \(q\) are \(n\)-bit primes.

Before looking into RSA, we need to introduce Phi function or Euler’s totient \(\phi(n)\). This function gives the number of positive integers less or equal to \(n\) that are relatively prime to \(n\). I hope every reader knows what is co-prime. It may be hard to calculate how many co-prime in a randomly given very large \(n\). However, if \(n\) is a prime, then we can say \(\phi(n) = n-1 \) because all the other integers less or equal to \(n\) are \(n\)’s co-prime. Also this phi function is multiplicative that \(\phi(mn)=\phi(m)\phi(n)\) as long as they are co-prime. Back to the case of RSA where \(N=pq\), then \(\phi(N) = \phi(p)\phi(q) = (p-1)(q-1)\).

In RSA, we need to find a integer \(e\) such that \(\gcd(e, \phi(N)) = 1\) and a integer \(d\) such that \(ed = 1 \mod \phi(N) \). Since \(d\) can be written like this \(d = e^{-1} \mod \phi(N) \), this is called multiplicative inverse of \(e \mod \phi(N)\). In RSA, \(e\) will be released as the public key and \(d\) will be released as the private key. In the key generation phase, we can calculate \(d\) using extended Euclidean algorithm. Originally, Euclidean algorithm is used to find greatest common divisor. extended Euclidean algorithm is an extension, by outputting the greatest common divisor of \(a,b\) in a form as \(ax+by\).

So how this extended Euclidean algorithm is related to the multiplicative inverse of modulo? For example, we have \((e,N)\) and we want to get \(d\), we can just run \(\text{exEuclidean}(e,\phi(N)) = ae+y\phi(N) = 1 \). Do a modulo \(\phi(N)\) at both side, we can get \(ae \equiv 1 \mod \phi(N)\). We set \(d = a\).

RSA is based on factoring because if the factoring problem is easy to solve then we can solve RSA problem easily. That is if we know that the two primes in \(N\), then we can calculate the \(\phi(N)\) using equation above, then we can compute the inverse \(d\) of \(e\) modulo \(\phi(N)\) using algorithm such as extended Euclidean. Since \(d\) is the private key, which mean the owner of \(d\) can just decipher the cipher text.

Encryption and Decryption

KeyGen

Generate two prime and get \(N=pq\), select a public key \(e\), and calculate \(d\). Then the public key is \((N,e)\) and private key is \((N,d)\)

Enc

Say we have a message \(m\). We encrypt it as \(c = m^d \mod N\)

Dec

Say we have a ciphertext \(c\). We decrypt it as \[m = c^e \mod N = m^{de \mod \phi(N)} \mod N = m \]

Basic Problems

Factoring

RSA Assumption

Encryption and Decryption

KeyGen

Enc

Dec

Reference