Most of us use and rely on SSL everyday. The mathematical workings of the RSA [Rivest, Shamir, Adleman] algorithm are not overly complex but mapping everything back to what happens in reality requires detailed understanding. Skipping over the need for SSL (for confidential and authenticated exchange of a symmetric key over and insecure medium) I will review the mathematical workings then how they are applied in real world examples.
There are also details in previous posts – RSA1, RSA2
Mathematics
Step |
Components |
|---|---|
| 1. | public key – e |
| standard practice to choose: 65537 | |
| 2. | random primes p,q |
| Let’s use:
579810099525248565010050509754571001027, 6989752565699505597485398979958574481969 |
|
| 3. | key modulus – n |
| n = pq:
4052729130775091849638047446256554071699019514021047339267026030072286291982163 |
|
| 4. | φ(n) = (p – 1)(q – 1) |
| φ(n):
4052729130775091849638047446256554071691449951355822585104530580582573146499168 |
|
| 5. | find e that is co-prime with φ(n) |
| already using a prime,which will be co- prime.. – e = 65537 (in binary 10000000000000001) | |
| 6. | (ed) mod φ(n) = 1d = e–1 mod φ(n) – Modular multiplicative inverseMore than one answer |
| using Extended Euclidean algorithm:
944402082567056818708092537028397604145319798848072425038015030084640082599681, 4997131213342148668346139983284951675836769750203895010142545610667213229098849, ..+ 2φ(n), +3φ(n)) |
|
| 7. | private key – d |
| d = e–1 mod φ(n):
944402082567056818708092537028397604145319798848072425038015030084640082599681 |
With a public key (e), a key modulus (n) and a private key (d) we can apply the RSA algorithm.
Message (mess) = 911
RSA encrypt -> mess ^ e mod n = 911 ^65537 mod 4052729130775091849638047446256554071699019514021047339267026030072286291982163
RSA encrypted message (ciph) = 3095021178047041558314072884014000324030086129008597834642883051983162360819331
RSA decrypt -> ciph ^ d mod n = 3095021178047041558314072884014000324030086129008597834642883051983162360819331 ^ 944402082567056818708092537028397604145319798848072425038015030084640082599681 mod
4052729130775091849638047446256554071699019514021047339267026030072286291982163
= 911
How is that secure?
When Alice encrypts using Bob’s public key (e) along with the key modulus (n) the output is a protected cipher.
An eavesdropper does not know the private key so decryption is very difficult:
Attacker must solve:
(unknown val, x) ^ e mod n = ciph
x ^65537 mod 4052729130775091849638047446256554071699019514021047339267026030072286291982163 = 3095021178047041558314072884014000324030086129008597834642883051983162360819331
OR, easier – try to determine the private key:
The attacker knows e and n (which = pq). When we created the private key (step 6 above) we conducted: e–1 mod φ(n) – Modular multiplicative inverse which is relatively fast for us to calculate.
The attacked does not know e–1 mod φ(n) though. φ(n) = (p – 1)(q – 1). The attacker knows that n is a composite prime = pq (where p and q are both primes).
So… if the attacker can solve p * q = n (where they know n) then RSA is insecure.
Thankfully the process of Integer factorization is so much harder than the process of creating p,q,n, φ(n), e and d that online business and confidentiality can be maintained to acceptable levels.
Threats to RSA
It would be extremely valuable to malicious individuals/groups and (more importantly) intelligence organizations make large integer factorization efficient enough to break RSA.
However the theoretical aspects of RSA are not generally recognized as the main source of vulnerability