RSA explained
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
Before looking into RSA, we need to introduce Phi function or Euler’s totient
In RSA, we need to find a integer
So how this extended Euclidean algorithm is related to the multiplicative inverse of modulo? For example, we have
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
Encryption and Decryption
KeyGen
Generate two prime and get
Enc
Say we have a message
Dec
Say we have a ciphertext
Reference
- http://en.wikipedia.org/wiki/Coprime_integers
- http://en.wikipedia.org/wiki/Euler's_totient_function
- http://en.wikipedia.org/wiki/Integer_factorization
- http://en.wikipedia.org/wiki/Euclidean_algorithm
- http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
- http://en.wikipedia.org/wiki/RSA_(cryptosystem)