logologo

Popular Boards

1 Mentions
Ronald L. Rivest, Adi Shamir, Leonard M. Adleman | Communications of the ACM | (1978)
Primary Link DOI Openalex Full text (OA)

Abstract

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n , of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n .

Tags

Key Takeaways

Referenced In

StarTalk

Season 17, Episode 1: Why Do Quantum Computers Break Cryptography

Hey StarTalkers! In Neil and Chuck’s discussion with Professor John Martinis in the first episode of Season 17, they touch briefly on the issue of cryptography in the coming age of quantum computers.

An Interview with the Winner of the 2025 Nobel Prize in Physics, John Martinis

Professor Martinis gives a brief explanation of the problem in this clip: a common form of encryption called RSA will be made obsolete by a quantum computing algorithm called Shor’s algorithm. In a way, physicists around the world are working hard on something that could put your data at risk.

But the scary predictions miss some important detail. So let’s look at what Shor’s algorithm actually does, and how things are likely to change in future.

Why Will Quantum Computing Break RSA Encryption?

RSA encryption uses two large prime factors of a very big number. The paper it was proposed in recommends multiplying two 100-digit prime numbers to end up with a 200 digit key. This 200 digit number is public, but the prime factors are crucial secret information.

The encryption system works because finding prime factors of very large numbers is really difficult. It would have taken billions of years to crack when it was proposed in the late 70s, but still a year or two with modern technology.

But in 1997, Peter Shor proved that quantum computers could make short work of the task. Quantum computers can use a superposition of different possibilities – rather than just one at a time – to search more efficiently.

Shor’s algorithm uses the repetition inherent in modular arithmetic alongside quantum Fourier transformations to find the prime factors. Think of it this way: each original prime p and q is the wavelength of a wave, and the points n where they are completely in phase are the ones that can be factored into p and q.

So Should We Be Worried?

The good news is that quantum-proof cryptography is basically ready-to-go.

It’s also pretty difficult to make a quantum computer that can actually handle Shor’s algorithm. There is progress, but nothing can break current systems yet.  

So physicists really are working on something that will put your data at risk, but luckily, security experts are working even faster.

Read Full Post
5