In the comment below, user Imperishable Night suggests an alternative method which should be at least conceptually easier to understand. The algorithm is essentially a careful elaboration of Henno Brandsma's answer to this very question. You can find these chapters online for free download here. You can find a good description of one such algorithm in the Handbook of Applied Cryptography, Chapter 8, section 8.2.2. There are various fast algorithms to solve the problem of factoring n given n, e, and d.
If you'd like to see a real example of how HTTPS uses RSA under the covers with a 617-digit n and an e of 65537, see my blog post " The First Few Milliseconds of an HTTPS Connection." In the "Real World", n is obviously much larger. (Note that "e" should be much larger in practice because for small values of "m" you don't even exceed n)Īnyways, now we have "c" and can reverse it with "d" m = c^d mod n This will give me the following ciphertext: c = m^e mod n This is important because if you have a plaintext message m then the ciphertext is c = m^e mod nĪnd you decrypt it by m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)įor example, I can "encrypt" the message 123456789 using your teacher's public key: m = 123456789 Why is this important? It's because d is a special number such that d = e^-1 mod phi(n) The easiest way is probably to check all odd numbers starting just below the square root of n: Floor] = 100711415 You can "break" RSA by knowing how to factor "n" into its "p" and "q" prime factors: n = p * q Where d is the decryption exponent that should remain secret.
Where n is the modulus and e is the public exponent.
0 kommentar(er)
