Talk:RSA cryptosystem

As I understand it, efficiently factoring large numbers => RSA broken, but it has not been proven that efficiently factoring large numbers is the only way to break RSA. -- The Anome

I agree with that. Thanks for making the distinction. -- CYD

I'm curious about how much the fact that it's known that two "large prime numbers" are used to construct a product eases the factoring. i.e., since only prime numbers within a certain size range need to be considered as factoring candidates -- hagedis.

From memory of previous discussions elsewhere, not very much. If one factor is very big, then the other is smaller, so the small factor is a soft target. Both numbers approximately the same size (in terms of bit length) represents a harder, not an easier problem. -- The Anome

there are factoring algorithms which specifically target factoring a number which has two factors that are roughly the same size. (and it gets faster the closer together they are.) sorry, no reference off the top of my head.

That's for a different definition of "same size". If P and Q are both 1024 bits (both have a 1 in the most significant bit) and were each chosen randomly (and uniformly, and independently), then they are about the same size, but factoring P*Q is hard. On the other hand, if |P-Q|<100, then they are about the same size, and factoring P*Q is trivial. When cryptographers talk about factors being the same size, they usually mean the bit length, not the difference. -LC

Seems I was wrong about the complexity of factoring :-P Can someone who knows this stuff add information about which complexity class factoring falls into (or is suspected of falling into)? -- CYD

OK, I've added that. --LC

This sentence was added to the article:

Like all public key algorithms, RSA is susceptible to the [man-in-the-middle attack]?.

I'm not sure what the author intended to say here. If Alice and Bob know each other's public keys, then there's no MITM attack. If they don't, then this is a key-distribution problem, which is a problem for all cryptography (not just public key). In what way is public-key crypto more susceptible to MITM than symmetric crypto? --LC

In public key crypto, you have to be really sure that the public key you use does indeed belong to the person you want to send a message too; you can't just look up the public key in an (untrusted) phone book or internet database. I don't think this issue even arises with secret key cryptography. You can't attack secret key cryptography by seeding a public key database with bogus public keys. I also don't think that the term "man-in-the-middle attack" is even used in the context of secret key cryptography. --AxelBoldt

The term is frequently used in both forms of crypto (c.f. [1]). You've noted one case: key distribution. To prevent MITM, Alice must send the key securely to Bob. That's a problem for both public-key and symmetric. For symmetric, it must be secure against both eavesdropping and tampering; for public-key, it only needs to be secure against tampering. People often discuss MITM for stream ciphers, since a MITM might change known bytes if there is no MAC. It's often discussed for block cipher modes, since some modes would allow a MITM to change known blocks in the middle of the message, if there's no MAC. It's discussed in more complex protocols such as Kerberos, which uses only symmetric algorithms to distribute symmetric keys. Such protocols have to be carefully designed to avoid MITM attacks. Most cryptographers would say that MITM attacks are an issue related to protocols above the level of the cipher (e.g. key distribution, block modes, MACs, etc.) and aren't really an issue related to the cipher itself. --LC

about the complexity of factoring (or its decision problem variant):

"It is suspected to be outside of P and NP-Complete and Co-NP-Complete."

This is probably true if you parse that as (outside P) and (outside NP-complete) and (outside Co-NP-complete). I think the text is a bit confusing as it is.

I thought it was clear before, but I've reworded it now. Maybe that's less confusing. --LC

Thanks, much better.

Note that "It is suspected to be" is probably true. A lot of experts suspect it, but certainly not all. My own guess is that it is probably in P, though there are no known algorithms that work in P so far. It's almost certainly not NP-complete, and almost certainly not Co-NP-complete. It has been proven that if it is one of those, then P is the same as NP.

No. If it's in NP-complete, then NP-Complete = Co-NP-Complete. That would be a very surprising result, but it wouldn't necessarily mean that P=NP. --LC

Yes it would. If there is any problem that is both in NP-complete and also in Co-NP, then P=NP. I don't have a citation handy, but i think this is mentioned in Garey and Johnson, with a cite to the original paper.

No. See Garey and Johnson's theorem 7.2. If a problem is both in NP-complete and also in co-NP, then NP=co-NP, which implies NP-complete=co-NP-complete. They don't say it would imply P=NP. --LC

Ok, i'll have to dig my copy out of the mess and look at this again. It's been a couple of years. Until i figure it out, or someone knowlegeable finds a cite, please leave the last few paragraphs here as a reminder.

The best currently known algorithm (assuming two prime factors of approx equal size, composite is bigger than 450 bits and has no particular special form) is the General Number Field sieve, which is asymptotically much slower than polynomial but much faster than exponential.

Yes. In fact I corrected an error on that point earlier today, and mentioned the exact bound here. --LC

Some of the decision problem variants of factoring belong to a complexity class called lamba-complete.

I'm not familiar with lambda-complete. It would be great if you could write an article on it. If you do, go ahead and add a link to it in the table in computational complexity theory. --LC

I wonder if it is good advice to choose e small. That might induce people to simply choose the smallest e possible, in that way giving away some information about φ(N) which could conceivably be exploited in cracking. --AxelBoldt

In practice, people often use e=3 or e=65537, because they allow faster encryption, and it's generally considered safe. The latter is sometimes preferred because there is an attack if you encrypt the same message e different times to different people. However, in a typical hybrid system the "message" is actually a random symmetric key, so that isn't a concern. --LC