Chapter 3: Public-key Cryptography

Chapter 3: Public-key Cryptography#

Imagine you have a magical mailbox. Anyone can put a letter in it, but only you can open it and read the messages. That’s the basic idea behind public-key cryptography!

How Public-key Cryptography Works#

  1. You create two keys: a public key (like your mailbox) and a private key (like your mailbox key).

  2. You share your public key with everyone. It’s like leaving your mailbox out in the open.

  3. Anyone can use your public key to encrypt a message for you (like putting a letter in your mailbox).

  4. Only you, with your private key, can decrypt and read these messages (like opening your mailbox).

It solves the big problem of symmetric encryption: how to securely share the key. With public-key cryptography, you don’t need to share any secret key!

A Simple Example: RSA#

One of the most famous public-key systems is RSA (named after its inventors: Rivest, Shamir, and Adleman). Here’s a simplified version of how it works:

  1. Choose two prime numbers (let’s call them p and q).

  2. Multiply them to get n (n = p * q).

  3. Choose a public exponent e.

  4. Calculate a private exponent d.

  5. Your public key is (n, e), and your private key is (n, d).

Let’s see a simple (but not secure) implementation:

import random

def is_prime(n):
  if n < 2:
      return False
  for i in range(2, int(n ** 0.5) + 1):
      if n % i == 0:
          return False
  return True

def generate_keypair(p, q):
  if not (is_prime(p) and is_prime(q)):
      raise ValueError('Both numbers must be prime.')
  elif p == q:
      raise ValueError('p and q cannot be equal')
  
  n = p * q
  phi = (p-1) * (q-1)

  e = random.randrange(1, phi)
  g = gcd(e, phi)
  while g != 1:
      e = random.randrange(1, phi)
      g = gcd(e, phi)

  d = multiplicative_inverse(e, phi)
  
  return ((e, n), (d, n))

def gcd(a, b):
  while b != 0:
      a, b = b, a % b
  return a

def multiplicative_inverse(e, phi):
  d = 0
  x1 = 0
  x2 = 1
  y1 = 1
  temp_phi = phi
  
  while e > 0:
      temp1 = temp_phi // e
      temp2 = temp_phi - temp1 * e
      temp_phi = e
      e = temp2
      
      x = x2 - temp1 * x1
      y = d - temp1 * y1
      
      x2 = x1
      x1 = x
      d = y1
      y1 = y
  
  if temp_phi == 1:
      return d + phi

def encrypt(pk, plaintext):
  key, n = pk
  cipher = [pow(ord(char), key, n) for char in plaintext]
  return cipher

def decrypt(pk, ciphertext):
  key, n = pk
  plain = [chr(pow(char, key, n)) for char in ciphertext]
  return ''.join(plain)

# Let's try it out!
p = 61
q = 53
public, private = generate_keypair(p, q)
message = "Hello, RSA!"

encrypted_msg = encrypt(public, message)
decrypted_msg = decrypt(private, encrypted_msg)

print(f"Original: {message}")
print(f"Encrypted: {encrypted_msg}")
print(f"Decrypted: {decrypted_msg}")

Original: Hello, RSA!
Encrypted: [3183, 1557, 867, 867, 1941, 3057, 2907, 1310, 2680, 899, 2768]
Decrypted: Hello, RSA!

This is a simplified version of RSA. Real-world implementations use much larger prime numbers and additional security measures.

Digital Signatures#

Public-key cryptography also enables digital signatures. It’s like signing a document, but with math!

  1. You create a hash of your message.

  2. You encrypt this hash with your private key.

  3. Anyone can verify the signature using your public key.

This proves that you (the owner of the private key) really sent the message and that it hasn’t been tampered with.

Pros and Cons of Public-key Cryptography#

Pros:

  1. Solves the key distribution problem of symmetric encryption.

  2. Enables secure communication without pre-shared secrets.

  3. Makes digital signatures possible.

Cons:

  1. Much slower than symmetric encryption.

  2. Requires longer key lengths for equivalent security.

  3. More computationally intensive.

Real-world Applications#

  1. Secure websites (HTTPS) use public-key cryptography to establish a secure connection.

  2. Secure email systems like PGP use public-key cryptography.

  3. Bitcoin and other cryptocurrencies use public-key cryptography for digital signatures.

What We Learned#

  • Public-key cryptography uses two keys: a public key for encryption and a private key for decryption.

  • It’s like a magical mailbox that anyone can put messages into, but only you can open.

  • RSA is a famous public-key algorithm.

  • Digital signatures are possible with public-key cryptography.

  • It solves the key distribution problem but is slower than symmetric encryption.

Quick Check: Did You Get It?#

Let’s see if you caught the main ideas:

  1. In public-key cryptography, which key can be freely shared? (Hint: It’s not private)

  2. What’s the name of the famous public-key algorithm we discussed? (Hint: It’s three letters)

  3. What do we call the math-based equivalent of a handwritten signature? (Hint: It starts with ‘Digital’)

Think about your answers, then check below!

Click to see the answers

  1. Public key

  2. RSA

  3. Digital signature

Great job if you got them all!

Contents