Repeated primes endanger internet codes

InternetEvery day across the internet, millions of secret messages are sent. Some might be messages from spies, but they aren’t the only people who keep secrets. For example, banks and online stores need to communicate without people stealing account details. Recently, a group of researchers discovered a problem with a popular encryption system. So what was the problem, and should we be worried?

If you want people to send you secret messages over the internet, you could make yourself an RSA key pair. RSA keys require two large prime numbers – these are usually several hundred digits long. You then multiply them together, and put this product on the internet for everyone to see. People can use this ‘public key’ to encode messages to send to you, but they can’t use it to decode those messages.

In order to decode messages, you use the prime numbers to make a ‘private key’. As long as you keep your prime numbers secret, no one should be able to read messages encoded with your public key. However, if someone takes the public key and works out which prime numbers you used, they can break the code.

No one has found a quick way to break public keys without a clue. However, if two public keys share a prime, those keys can break each other. This shouldn’t happen very often, because there are so many prime numbers to choose from.

Researchers from a Swiss university took lots of public keys from the internet and looked for shared primes. Around two in every thousand keys they checked shared a prime and were broken by the researchers. The problem was not in the maths of RSA, but how some software generated prime numbers. This flawed software sometimes generated the same prime numbers for different people.

This research doesn’t mean that internet security is completely broken. Only a very small proportion of keys can be broken in this way. However, it just goes to show that what works on paper doesn’t always work as well in the real world.