So we can try values of k in a small range around e and there should be only one integer solution to the quadratic, the solution for the correct k. Of the form ax 2 + bx + c = 0 and we can solve for x using the quadratic formula.
Now setting x=p, and therefore n/x=q, multiplying both sides by x and rearranging terms we have We know that ed = 1 mod phi(n), or equivalentlyĮd - 1 = k * (p-1)*(q-1). To proceed, lets set x=p and solve for x, just to stick with convention.
In the case that e is small you can develop a quadratic equation in the unknown prime p and thus easily solve for it using e.g. 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)
