Question

Is there a way(cryptanalysis) to break the RSA algorithm?

Answer 1

There is in fact one way I've come across in which one can get individual messages without breaking the cryptosystem. In terms of actually breaking it and getting the key, I have not heard of any ways other than factoring \(N\).

Answer 2

There are a few different ways to factor \(N\), such as straight factoring, finding \(\phi(N)\), or finding \(p+q\) (where \(pq=N\)). All of these will allow you to factor \(N\).

Answer 3

If you're interested in seeing the way obtain an individual message, let me know. As fair warning, it is somewhat mathematically intense.

Answer 4

The only way I've heard was just to factor N and then taking the result and subtracting 1 from each to find ϕ(N) and then just using that to find the key. The other way I found was by using the lattice method, but I don't really understand most of it, so I skipped it. What's your way called?

Answer 5

I don't know if it has a name or not. Like I said previously, I do not believe the method I am mentioning actually cracks the system.

Answer 6

You could try explaining it to me and see if I understand it ^^

Answer 7

As far as I can tell, it's a form of chosen-ciphertext attack. For the real simple explanation of what it is, look at the fourth bullet point here: http://en.wikipedia.org/wiki/RSA_(algorithm)#Attacks_against_plain_RSA

Answer 8

Here's the full explanation that I have. Suppose Alice is sending a message to Bob, and Eve wants to read it. Alice sends \(c\equiv m^e \pmod{N}\) to Bob. Eve intercepts this. Now, Eve chooses \(k\) such that \(\gcd(k, N)=1\). Using this, Eve encrypts \(c'\equiv k^e\cdot c\pmod{N}\) and sends this to Bob, asking Bob to decrypt it to make sure everything is working just fine.

Bob decrypts \(c'\) getting\[m'\equiv (c')^d\equiv(k^e\cdot m^e)^d\pmod{N}\]Simplifying this, \[m'\equiv (k^{ed}\cdot m^{ed})\equiv k\cdot m\pmod{N}\]Now Bob sends this back to Eve.

Recall that Eve knows, \(k\), and can quickly find \(k^{-1}\pmod{N}\). Finally, Eve multiplies \[k^{-1}\cdot m'\equiv k{-1}\cdot k\cdot m\equiv m\pmod{N}\]Obtaining the original message.

Answer 9

That's intense.

Answer 10

Once you take the explanation apart and look at each piece, it's not too bad.

Answer 11

But to do this, you'd have to interact with the owner of the private key.

Answer 12

Correct. You would be acting under the guise of someone that wants to exchange messages, and is testing the key holder's encryption.

Answer 13

Have you tried this? xD

Answer 14

I've done one or two small examples by hand. This is just something we were taught in my cryptography course.