ELEC3506

Topics

Network SecurityLecture 12 PDF20 min

Public-key cryptography and RSA

Why two separate keys remove the need to share a secret, the pros and cons of public-key encryption, the RSA key generation steps, encryption and decryption, the p=5 q=7 worked example, the commutative property and why RSA is hard to break.

By the end of this page you should be able to

  • Explain which key encrypts and which decrypts in public-key confidentiality
  • List the lecture's pros and cons of public-key encryption
  • Generate an RSA key pair from small primes following the five steps
  • Encrypt and decrypt a number with RSA using modular reduction
  • State why knowing the public key does not reveal the private key

The idea

Symmetric encryption has a chicken-and-egg problem. To send a secret message you first need a shared secret, and to share a secret you need a secure channel.

Public-key encryption breaks the loop with two keys. Bob publishes one and keeps the other. Anyone can use the published key to lock a message for Bob, but only Bob’s private key opens it. Alice and Bob never have to meet. The price is speed, which is why the lecture lists a set of cons next to the pros.

How it works

Two keys instead of one

The lecture states the idea directly.

  • No key sharing is needed.
  • There are two separate keys: one private and one public.
  • The public key, exposed to the public domain, is used for encryption.
  • The private key, private to the user, is used for decryption.
  • The public key locks the message and the private key opens it.

The figure on the confidentiality slide did not extract. The text above is all the lecture’s wording that survives.

Pros

  • No need for secret key sharing.
  • It is computationally infeasible to compute the private key given the cryptographic algorithm and the public key.
  • Used for authentication, digital signatures and secret-key exchanges.

Cons

  • Relatively long mathematical calculations using relatively long keys.
  • Much slower than symmetric-key encryption.
  • Inefficient for long messages.
  • The public key must be distributed via a trusted third party.

How it works

RSA: the algorithm in outline

RSA is named for Rivest, Shamir and Adleman and was developed in 1978 at MIT. The lecture calls it the de-facto standard for data transmission on the Internet. It uses two exponents, e and d, where e is public and d is private. If P is the plaintext and C the ciphertext, Alice uses C = P^e mod n to encrypt and Bob uses P = C^d mod n to recover the plaintext. The modulus n, a very large number, is created during key generation.

Before any of that, the lecture notes a message is just a bit pattern, and a bit pattern is uniquely a number. For example m = 10010001 is 2^7 + 2^4 + 2^0 = 128 + 16 + 1 = 145. Encrypting the message means encrypting that number, which gives a new number, the ciphertext.

How it works

RSA: creating a public and private key pair

  1. Choose two large prime numbers p and q, for example 1024 bits each.
  2. Compute n = pq and z = (p-1)(q-1).
  3. Choose e with e < n that has no common factors with z. That is, e and z are relatively prime.
  4. Choose d such that ed - 1 is exactly divisible by z. In other words ed mod z = 1.
  5. The public key is (n, e) and the private key is (n, d).
RSA key generation
n=pq,z=(p−1)(q−1),ed mod z=1n = pq, \quad z = (p-1)(q-1), \quad ed \bmod z = 1
p, q
Two large primes
n
Modulus, pq
z
(p-1)(q-1)
e
Public exponent, no common factor with z
d
Private exponent, ed mod z = 1

How it works

RSA: encryption and decryption

Given (n, e) and (n, d) as above, with the message as a number m < n:

  1. To encrypt, compute c = m^e mod n.
  2. To decrypt the received bit pattern c, compute m = c^d mod n.
RSA encryption and decryption
c=me mod n,m=cd mod nc = m^{e} \bmod n, \qquad m = c^{d} \bmod n
m
Message as a number, less than n
c
Ciphertext as a number

How it works

The lecture's worked example

Worked example

Bob chooses p = 5 and q = 7, encrypting the 8-bit message 00001100

  1. Modulus: n = pq = 5 x 7 = 35.

  2. z: (5-1)(7-1) = 4 x 6 = 24.

  3. Choose e: the lecture takes e = 5. The factors of 5 are 1 and 5, and the factors of 24 include 2, 3, 4, 6, 8, 12. The only common factor is 1, so e and z are relatively prime, and 5 < 35.

  4. Choose d: the lecture takes d = 29. Check: e x d = 5 x 29 = 145, and 145 - 1 = 144 = 6 x 24. So ed - 1 is exactly divisible by z, and ed mod 24 = 1.

  5. Keys: public (35, 5), private (35, 29).

  6. Message: 00001100 in binary is 8 + 4 = 12, so m = 12, and 12 < 35.

  7. Encrypt: c = 12^5 mod 35. Directly, 12^5 = 248832. Since 35 x 7109 = 248815, the remainder is 248832 - 248815 = 17. By reducing at each stage: 12^2 = 144, 144 mod 35 = 4. Then 12^4 = 4^2 = 16. Then 12^5 = 16 x 12 = 192, and 192 mod 35 = 17. So c = 17.

  8. Decrypt: m = 17^29 mod 35. Using repeated squaring: 17^2 = 289, 289 mod 35 = 9. 17^4 = 9^2 = 81, 81 mod 35 = 11. 17^8 = 11^2 = 121, 121 mod 35 = 16. 17^16 = 16^2 = 256, 256 mod 35 = 11. Since 29 = 16 + 8 + 4 + 1, multiply 17^16 x 17^8 x 17^4 x 17^1 mod 35: 11 x 16 = 176, 176 mod 35 = 1. Then 1 x 11 = 11. Then 11 x 17 = 187, 187 mod 35 = 12. So m = 12.

AnswerPublic key (35, 5), private key (35, 29). The message 12 encrypts to 17 and decrypts back to 12.

The slide prints m^e as 24832 and c^d as 481968572106750915091411825223071697. The second number is exactly 17^29. The first is one digit short, since 12^5 is 248832. The ciphertext 17 and the recovered message 12 are both right, so the slide’s printed value is a typo and the answers stand.

How it works

Another important property

The lecture states that encrypting then decrypting, in either order, returns the message.

K_B^-(K_B^+(m)) = m = K_B^+(K_B^-(m))

Using the public key first and then the private key gives m. Using the private key first and then the public key also gives m. The result is the same.

This matters in the signature topic, where the private key is applied first on purpose. The lecture says the property “will be very useful later”.

How it works

Why is RSA secure?

Suppose you know Bob’s public key (n, e). To determine d you essentially need to find the factors of n without knowing the two factors p and q. The lecture’s fact is that factoring a big number is hard.

With the toy numbers, n = 35 factors by inspection as 5 x 7, so the example is not secure. Real keys use primes of around 1024 bits each.

Where marks get lost

The public key does not decrypt

In confidentiality the public key encrypts and the private key decrypts. Mixing them up is the commonest slip. In the signature topic the roles reverse, with the private key applied first, which is why the commutative property is stated.

In the exam

  • Be able to carry out the five key-generation steps for small p and q, showing n, z, a valid e, and a check of ed mod z = 1.
  • Encrypt with m^e mod n, reducing at each stage, and decrypt with c^d mod n.
  • The lecture’s numbers: p = 5, q = 7, n = 35, z = 24, e = 5, d = 29, m = 12, c = 17.
  • Know all four pros and cons.
  • The security argument is the difficulty of factoring n.

Aside

Flagged: the printed power

The lecture slide shows 12^5 as 24832. The correct value is 248832. The slide’s ciphertext 17 is right regardless, and that is the answer the exam marks.

Check yourself

  • Public key encrypts, private key decrypts. Nothing secret is shared in advance.
  • The cost is speed, so RSA suits short messages such as keys.
  • n = pq, z = (p-1)(q-1), e relatively prime to z, ed mod z = 1.
  • c = m^e mod n and m = c^d mod n. With the lecture’s keys, 12 becomes 17 and back.
  • RSA is secure because factoring n is hard.

Check yourself

  1. In RSA with p = 5 and q = 7, what is z?
  2. Which of these satisfies the lecture's condition for d when e = 5 and z = 24?
  3. Using the lecture's key (n = 35, e = 5), what is the ciphertext of m = 12?
  4. Why is a long message normally not encrypted directly with RSA?
  5. What is the hard problem that protects the RSA private key?