Introduction to Public Key Cryptography I

In this page, we're introducing the concept of public key crypto, building from the key distribution problem all the way towards how minor mishandling of RSA can end up making it vulnerable.

Why Public Key Crypto?

The Key Distribution Problem: A Cryptography Tale

Imagine it’s the 1950s, and people are starting to use codes to send secret messages over long distances. These codes work like a locked box: you use a key to lock (encrypt) the message, and you need the same key to unlock (decrypt) it. This is called symmetric encryption.

But there’s a big problem. How do you share the key with the person on the other side? If someone intercepts the key while you’re sending it, they can unlock all your secrets. That’s like sending a treasure chest and the key to the same thief!

As more people start using these secret messages, the problem becomes worse. If you’re a spy or a businessperson, you’d need to share a different key with every person you talk to. Imagine keeping track of a pile of keys for all your friends and co-workers! Plus, every time you need to exchange a key, you’d have to meet in person or send it through a trusted courier. It’s slow, expensive, and risky.

By the 1970s, this key problem was a huge headache. The world was getting more connected, and people needed a better way to send secrets securely. Cryptographers were desperate to find a solution.

A Solution!

One day, two clever cryptographers, Whitfield Diffie and Martin Hellman, had a wild idea. What if there was a way to send secrets without needing to share a secret key first? It seemed impossible—like magic. But they figured out a way to do it using math.

Their idea was this:

1. Everyone would have two keys: one public key and one private key.

2. The public key could be shared with anyone, like your email address. No need to keep it secret.

3. The private key would stay with you and never be shared, like your diary’s lock.

Here’s the magic: anything locked with the public key can only be unlocked with the private key. And vice versa. So, you could send someone your public key, they could use it to lock (encrypt) a message, and only you could unlock (decrypt) it with your private key. No need to meet or send secret keys through risky channels!

The Birth of RSA

Just a year later, three brilliant mathematicians—Rivest, Shamir, and Adleman—came up with an easy-to-use system called RSA. It made this public and private key idea practical for the real world. Suddenly, people had a way to exchange secrets securely without worrying about stolen keys.

This new way of encrypting messages, called public key cryptography, solved the key-sharing problem. Now:

• You could send secrets to anyone in the world without needing to meet them first.

• The internet became a safer place, allowing things like online shopping, secure emails, and private chats.

• Managing secrets got way easier—you only needed one private key for yourself and could share your public key freely.

Why It Matters

Before public key cryptography, sharing secrets was like whispering across a crowded room and hoping no one overheard. After public key cryptography, it’s like sending a locked box with a key only you can use.

Today, every time you see a little padlock in your web browser, public key cryptography is working behind the scenes to keep your secrets safe. It all started with a simple, but powerful, idea: share a lock, not a key.

Let’s Talk RSA

How we think of the math behind RSA

I'm gonna include this section for a small proof on why RSA works in a mathematical sense.

$$a^1 = a \newline \therefore a^1 \equiv a \pmod m \newline a^0 \times a^1 \equiv a \pmod m \newline a^{\phi_m} \times a^1 \equiv a \pmod m \newline a^{\phi_m + 1} \equiv a \pmod m \newline \text {in general:} \newline a^{k\phi_m + 1} \equiv a \pmod m \text { where k is any integer.} \newline \text {suppose that we rewrite it so that} \newline e \times d = k\phi_m + 1 \newline \therefore e \times d \equiv 1 \pmod {\phi_m}$$

We have four main steps:

1. Key Generation

2. Key Distribution

3. Encryption

4. Decryption

[1] Key Generation:

Step 1: Alice chooses two large prime numbers p and q

Step 2: Alice calculates N and phi N = p.q phi = (p-1).(q-1)

Step 3: Alice Selects encryption exponent e: e is relatively prime to n.

Step 4: Alice calculates decryption exponent d: $𝑑 \times 𝑒 ≡ 1 \pmod {phi}$ Which is same as: $d = e^{-1} \mod phi$

Step 5: The keys are as follows:

Alice($K_{PUBLIC}$) = (e,N) Alice($K_{PRIVATE}$) = (d,N)

Note that Alice also keeps private, p, q and n. Bob Repeats the above steps to generate his public and private keys.

Key Generation Example:

Alice generates her key as follows:

1. p= 5 and q=11

2. N = 5 x 11 = 55

3. phi = 4 x 10 = 40

4. e = 7

5. $d = 7^{-1} \mod 40 = 23$

6. $K_{PUBLIC}$ = (7,55) $K_{PRIVATE}$ = (23,55)

P = 17
q = 23
e = 0x10001
N = p*q
phi = (p - 1) * (q - 1)
d = pow(e,-1,phi)
# Key generation sucessful

[2] Key Distribution:

Alice and Bob share their public keys over an insecure channel.

[3] Encryption:

If Bob wants to send X to Alice: $𝑦 = 𝑥 ^ 𝑒 \mod N$ 1 < 𝑥 < N

Encryption Example:

If Bob wants to send 'N' (N = No) to Alice. Assume that we are using the same keys generated in the previous example.

x = 'N' = 13 (the base is the English alphabet)

$𝑦 = 13^7 \mod 55 → 𝑦 = 7$

Note that we are using e and m from the public key of Alice.

[4] Decryption:

If Alice receives Y from Bob, she can decrypt using: $𝑥 = 𝑦 ^ 𝑑 \mod N \space \space 1 < 𝑥 < N$

Decryption Example:

Using the above example:

y = 7 $𝑥 = 7 ^ {23} \mod 55 → 𝑥 = 13$ Note that we are using d and N from the Private key of Alice.

Uses of RSA (or PKC in general)

Encryption: Keeping Information Private

Encryption with RSA ensures that only the person you want to share information with can read it. Here's how it works:

• Each person has a public key (which can be shared) and a private key (kept secret).

• If you want to send someone a private message, you use their public key to encrypt it.

• Only they can decrypt it using their private key.

This method is used in things like secure websites (HTTPS) to protect sensitive data like passwords and credit card numbers.

Digital Signing: Verifying Identity and Authenticity

RSA digital signatures let people verify that a message really came from you and wasn’t changed. Here's how it works:

• You use your private key to create a digital signature for a message.

• The recipient uses your public key to check the signature and confirm it’s from you.

This is like sealing a letter with a personal stamp that can’t be copied. It ensures:

• Authenticity: The message is really from you.

• Integrity: The message hasn’t been tampered with.

• Non-repudiation: You can’t deny sending the message.

RSA helps make online communications safe and trustworthy, powering tools like secure email, electronic payments, and digital certificates.

Assume we have a public key, how can we break RSA?

Easy, we have N and we know N = p.q so we just factorize N into p and q and find phi = (p-1)(q-1) and extract d thus breaking RSA.

Well…its easier said than done, this is exactly what we call The Factorization Problem!

Which happens to be one of those problems in the science of algorithms where if p and q were large enough (along with other properties) wasn’t proven to have an efficient solution.

This drives us into the next section of our notes.

More On FP

The factorization problem is the math puzzle behind some public key cryptography systems, like RSA. It’s based on this idea:

• It’s easy to multiply two large prime numbers together.

• But it’s extremely hard to take a big number and figure out which two prime numbers were multiplied to get it.

For example, multiplying 47 and 59 is simple: 47×59=2773. But if someone just gave you 2773, figuring out it came from 47 and 59 would take a lot more effort.

This “one-way” difficulty is what makes RSA secure. Even if someone knows your public key (based on a big number), they can’t easily figure out the private key unless they can solve this factorization puzzle—something that takes too long, even for powerful computers.

Breaking RSA

RSA is a powerful cryptographic system, but its security depends not just on the math but also on how it’s implemented. If RSA is handled carelessly, it can be vulnerable to attacks.

Even a small mistake in how RSA is used can weaken the system and allow attackers to break it—often much faster than the math suggests. This is why secure implementation practices are just as critical as the algorithm itself.

Alright then, let’s look at those mishandles in more detail…

Problems with the factors and modulus p,q,N:

N is Prime

it’s less complex to determine if a number is prime than to factor a number, phi would be equal to N - 1 and the entire cipher is broken

N is a Square

it’s also less complex to determine if a number is a perfect square than to factor a number, phi would be equal to p*(p-1) and the entire cipher is broken

P and Q are Close to Each Other (Fermat factoring)

Fermat's factorization method, also known as Fermat's factorization theorem, is one of the methods used to factorize integers. It's particularly effective when the difference between p and q is small. The basic idea behind Fermat's factorization method is to express 𝑁N as the difference of two squares:

𝑁=𝑎2−𝑏2=(𝑎+𝑏)(𝑎−𝑏)

If 𝑁N can be expressed in this form, then 𝑝p and 𝑞q can be found by computing the greatest common divisor (GCD) of 𝑁 with (𝑎+𝑏) and (𝑎−𝑏).

Therefore, if 𝑝 and 𝑞 are close to each other, an attacker can find them more easily using Fermat's factorization method or other similar techniques.

N Has Many Factors Not Just 2

THEORETICALLY, If 𝑁 in RSA has many factors, not just two, it would complicate the factorization process and potentially enhance the security of the RSA encryption.

Surpisingly, that’s not really the case…

A fairly naive algorithm for factoring N is the following:

while N > 1:
  for p in increasing_primes:
    while p divides N:
      N = N / p
      factors.add(p)

With this algorithm,

340 282 366 920 938 463 463 374 607 431 768 211 456 can be factored in exactly 128 iterations of the innermost while. (The number, of course, is 2128)

The more prime factors a composite number has, the smaller those factors have to be. For example, 919⋅677=622 163. With the naive algorithm, this takes 157+1=158 iterations to factor. A number of roughly the same size comprised of three factors, 73⋅89⋅97=630 209, only takes 25+2=27 iterations to factor.

Similarly, a 1000-digit number composed of two roughly equally-sized factors will take about 10497 iterations to factor. A 1000-digit number composed of 100 roughly equally-sized factors will take about 434 294 481+99≈10**9 iterations. And a 1000-digit number composed of 1000 roughly equally-sized factors will take about 4+999≈103 iterations.

Reused Primes:

Assume we do reuse primes, where N1 = pq1, N2 = pq2

if we find gcd(N1,N2) it’ll be equal to p, breaking the entire cipher

Problems with Exponents e and d:

Small e

when e is too small, breaking RSA is as simple as finding the e-th root to the enciphered message, especially when the enciphered message isn’t subject to the modulus.

Large e

when e is too large, the encryption is usually vulnerable to 2 different attacks

1. Wieners attack

2. you find the other one ;)

e Isn’t Coprime with phi(n)

This results in all sorts of mess, in some cases the message is gone for good and can’t be decrypted, in other we can break the cipher using modular square root.

Problems with the messages M

Short Message

If our message is too short, it takes us to a similar problem as having a small e, take this as a rule of thumb to identify this issue

m # message
e # exponent
n # modulus
assert m**e > n

if this assertion fails then we have a vulnerable cipher

Bad Padding

When it comes to bad padding, attacks like Coppersmiths’ and Franklin Reiter attacks are the most common, we’ll explain further as we solve challenges

Message Reuse

Message reuse leaves us with good old CRT attacks, can you prove why?