SUNY Geneseo Department of Mathematics
Wednesday, December 8
INTD 105 17
Fall 2021
Prof. Doug Baldwin
(No.)
How would you break an RSA cryptosystem?
Figure out p and q, from n = pq, in other words, factor n.
Once you know p and q, you can calculate (p-1)(q-1). Then, since you already know e, you can basically do what you’d do to create the system in the first place to find d such that ed / (p-1)(q-1) has remainder 1.
Now you know the target cryptosystem’s private key!
For example, break a system with n = 35723 and e = 11:
Thanks to an online factoring tool, we found that n = 35723 = 139 × 257
p = 139
q = 257
(p-1)(q-1) = 138 × 256 = 35328
5 × 11 × 41 × 47 = 105985, which has remainder 1 when divided by 35328 (105985 = 3 × 35328 + 1)
So since e = 11, d must be 5 × 41 × 47 = 9635.
So if a class can break an RSA cryptosystem in the 15 minutes or so it took us to do this example, RSA doesn’t seem very secure at all. But it actually is, and the reason is that factoring is much more time-consuming than it looked in this example. We only factored a 5-digit number; remember that RSA works with numbers with hundreds of digits. As far as anyone knows, the time it takes to factor a number grows roughly proportionally to 10 to the power of half the number of digits, which is an astronomically long time when the number of digits is in the hundreds. So RSA is probably very secure as long as you use it with large p and q values.
But note the “probably.” While computer scientists believe that factoring takes as long as I said, no-one has actually proven it. So beware if you wake up some morning and see a headline “MIT student invents fast factoring algorithm.”
How do you know a public key comes from who it claims to? Why can’t some hacker set up a server that, in effect, broadcasts to the Internet “I’m SUNY Geneseo, and I’ve just changed my public key to such-and-such, so please use that with your credit card number for future payments.”
The answer is that Geneseo (along with all other secure servers) doesn’t say “my public key is such-and-such,” it says “the ’certificate’ for my public key is such-and-such.”
A “certificate” is a digital document from a trusted organization called a “certificate authority,” which vouches for public keys. A certificate authority might be a big financial firm (or a spin-off of such a firm) which has and needs to maintain a reputation for trustworthiness, and which knows how to verify identities. Then when someone, say Geneseo, wants a new public key, they take that key to a certificate authority, prove that they really are Geneseo, and receive a digital document from the certificate authority that says, in effect, “I, such-and-such a certificate authority, vouch that the following is Geneseo’s public key: …. This document is digitally signed by the certificate authority, and constitutes the certificate. Now when some wants to send secure information to Geneseo, they get a certificate from a server claiming to be Geneseo, verify that it is signed by a certificate authority they trust, and, if so, get the public key from it.
This system of certificates is why sometimes when you connect to something on the Internet, you get a message in your browser to the effect of ”certificate has expired.“ (Certificates are often only good for a limited time, and this message means that the place you tried to connect to identified itself with an expired certificate. Usually that just means the site administrators haven’t gotten around to renewing their certificate quite as quickly as they should have, but potentially it indicates that someone is trying to masquerade as the site in question and not quite doing a good enough job of it.)
One of the last important linguistic approaches to cryptography: the Navajo code-talkers.