Chris Spackman – Cryptography

Public-Private Key Pair Generation

This demonstration shows how public and private key pairs are created. Users can put in their own numbers to see the results, or just use the defaults. (The button is below Step 2.)

The system shown here is RSA. Ron Rivest, Adi Shamir and Leonard Adleman published it in 1977, and it is named from their initials. Clifford Cocks, a mathematician at GCHQ, the British signals-intelligence agency, had found an equivalent system in 1973, but his work stayed secret until 1997.

The Padlock Analogy

Imagine Alice buys 100 identical padlocks that all open with the same key. She keeps the key (her private key) and sends open padlocks to everyone she knows. When Bob wants to send Alice a secret message, he puts it in a box and snaps one of Alice's padlocks shut. Now only Alice can open it, because only she has the key. That is basically how public-key encryption works: the padlock is the public key (anyone can lock with it), and the key is the private key (only Alice can unlock).

Step 1: Input Values

Use the defaults, or enter your own values for the two prime numbers p and q. p and q MUST be prime numbers.

Try it small (p=61, q=53, e=17) — use these small values to follow along with a calculator. The numbers are small enough to check by hand!

Here, we use 17 and 65537 for e because these meet some mathematical requirements and are frequently used.

Also, please note that the default values for p and q might look big but are actually too small for real security and are used for demonstration purposes only.

Step 2: Results

After doing the math (button below), the results will show:

• The modulus (n): The product of the two primes (p and q).
• The totient — phi(φ): This counts how many numbers from 1 to n are coprime with n (share no factors with it). When n is the product of two primes, the formula is simple: φ(n) = (p−1) × (q−1). This number is used to create the private key.
• A couple of math checks: For security, software checks that e, p, q, and n meet some requirements.
• The decryption key (d): A secret number paired with the encryption key (e). It is the modular inverse of e mod φ(n): the number d with e × d ≡ 1 (mod φ(n)). Whatever (e) locks, (d) unlocks.
• The public key: Alice can share this key with anyone and everyone. Other people can use it to send messages that only Alice can read.
• The private key: Alice must keep this key secret. She will use it to read messages sent using her public key. She can also use her private key to "sign" messages. Signing proves that the message came from Alice and that it has not been changed.

Perform Key Pair Generation

Why This Works

The public key and private key are like a pair of linked locks. The public key is used to "lock" (encrypt) messages, and only the private key can "unlock" (decrypt) them. Similarly, the private key can "lock" (sign) messages, and the public key can verify the signature.

This connection between the public and private keys is based on some advanced math. Even if someone has the public key, it's nearly impossible to figure out the private key unless they know the two secret prime numbers (p and q) that were used to create the keys. Trying to find them by brute force would take millions of years.

Things to Try

• Click "Try it small" and generate keys with p=61, q=53, e=17. Can you follow the math with a calculator?
• What happens if you pick two primes that are very close together (like p=101, q=103)? Is that a good idea for security? (No: when p and q are close, n is almost a perfect square, and √n lies between them. A factoring trick Pierre de Fermat described in 1643 starts at √n and finds both primes in a few steps.)
• What if p or q is not actually prime? Try it and see what error you get.
• Why not use the same prime twice (p = q)? Try it and read the error. Hint: what is the square root of n?
• Try switching the value of e between 17 and 65537. How does d change?

In The Real World

In real-world key pair generation, the numbers used are much larger than what we use here, for security reasons:

p and q

These are very, very large prime numbers. Today's keys use an n of 2048 to 4096 bits, so p and q are each about 300 to 600 digits long. Best practice is for them to be roughly the same length (but not close in value; see "Things to Try").

n

The product of p and q. A gigantic number with only 2 factors, aside from itself and 1. Even knowing that it is the product of two primes, for well-chosen primes, it would take millions of years to brute force factor n.

FAQ

Why prime numbers?

The math on this page only works when p and q are prime. The shortcut φ(n) = (p−1)×(q−1) is true only for two distinct primes, and that φ(n) is what makes d undo e: because e × d ≡ 1 (mod φ(n)), raising a message to the e and then the d gives the message back. With a non-prime p or q, the page's φ(n) is wrong and the keys would not undo each other. The security then comes from n: the only known way to get d from the public key is to factor n back into p and q.

Why large numbers?

The larger the numbers, the harder it is for an attacker to figure out the private key from the public key.

How do they find large primes to use?

Turns out, it is a lot easier to check if a number is prime or not than it is to try to actually factor a similarly large number. So, computers randomly come up with a huge number, and check if it is prime. If it is, great! If not, they can tweak the number and check again. The software continues until it has a number it is fairly certain is prime.

• For example, if you have the number 212, you know it is not prime because it is obviously divisible by 2. So, just add 1 to it, and then check if 213 is prime. It isn't (3 and 71), and you know that 215 won't be prime (because ends in 5), so check 217 (nope). Continue until you find one that is prime — it would be a couple more tries in our example to get to 223, which is prime.
• Obviously, modern computers are using much, much, much, much bigger numbers, and probably doing a bit more advanced math on the numbers. But, maybe not — adding a small number and checking again might be faster than generating an entirely new very-large candidate prime.

Where does the decryption key (d) come from?

It's created as part of the math that connects the public and private keys. It is like the partner to the encryption key (e). The (slightly complicated) math ensures that they work together.

Why can't someone figure out the private key from the public key?

The private key depends on the secret prime numbers (p and q) that were used to create the public key. Without knowing these primes, the math to find the private key would take so long that even the fastest computers couldn't do it.

Can I use the public / private keys from this page for real encryption?

NO!!!!!!
Okay, technically, maybe, but there is a lot more to creating real keys than we show here. This page demonstrates the math behind the keys. Real keys use much larger primes, are stored in standard formats, and are usually wrapped in a certificate that also includes information about the owner, when the key should expire, who vouches for it, and much more.

Related

See also: Diffie-Hellman Key Exchange — how two people can agree on a shared secret over an insecure channel, using similar math.

Or step back to the classical methods that came first: Traditional Cryptography · Early Modern Cryptanalysis.