The RSA method is an asymmetric public key cryptographic algorithm. The user must independently generate two keys: one public and accessible to all that can be used by another user to encrypt the message to be sent, a private one known only by the user which is used to decrypt the message received.
Math behind RSA:
We choose two prime numbers p and q and define n = pq which we will call module. We also compute the euler function of n:
where the various
but as n is defined, we simply have:
We choose a number such that it is coprime with phi(n), that is GCD (e, phi(n)) = 1.
Now we are searching for a number d such that ed = 1 mod((p-1)(q-1)). To find d we use the Extended Euclidean algorithm which, in this case, states that:
Since e and phi (n) are coprime integers we have that x is the multiplicative inverse of e module phi (n) and y is the multiplicative inverse of phi (n) modulo e, so x=d.
If we have an 'm' message the encrypted message will be:
and to decipher it
we show that it is actually decrypted as mentioned:
From the last equation we obtain, by definition of phi (n):
Using, then, Fermat's little theorem we get:
We observe now that p and q are different prime numbers so we can use Chinese remainder theorem obtaining that:
The power of the algorithm lies in the unproven assumption that deciphering the message without knowing the factors of n is computationally intractable (the factoring of a number is an operation with a sub exponential trend):
The fastest known algorithm to date is called General Number Field Sieve, with a complexity in the order of:
Where b is the size (in bits) of the number from factorize.