A Short Course in Cryptography, January 2004

Day 2: PublicKey Cryptography
How well can this work in Alice and Bob have never met before?
PublicKey Cryptography
We need to use different keys for encrypting and decrypting. That way, Alice can send Bob a message without needing to set up a secret key first. All she needs to know if Bob's public key. Anyone else can know Bob's public key, but that isn't enough to decrypt the message.This means we need a problem that is:
Finding prime factors!
 Hard to do in one direction (decryption)
 Easy to do in the other direction (encryption)
 Given a big number, it is hard to find its prime factors.
 But, it is easy to multiple any two numbers together.
Modular Exponentiation
We can calculate any number mod n by just subtracting multiples of n until we get to a number less than n. So,5 mod 7 = 5 5 is already less than 7 8 mod 7 = 1 since 8  7 = 1 17 mod 7 = 3 since 17  (2 * 7) = 3Questions1. 9 mod 7
2. 2 mod 3
3. 3 mod 2
4. 100 mod 11
5. 1024 mod 1022
Modular exponentiation is like modular arithmetic, except the numbers are much bigger. But, because it is modulo it is actually easier to calculate.
5^{3} = 5 * 5 * 5 = 125 125 mod 7 = 6But, it is easier to calculate:5^{3} mod 7 = 5 * 5 * 5 mod 7 = (5 * 5 mod 7) * 5 mod 7 = (25 mod 7) * 5 mod 7 = 4 * 5 mod 7 = 20 mod 7 = 6Questions6. 3^{2} mod 7
7. 3^{3} mod 7
8. 3^{3} mod 15
9. 3^{7} mod 15
RSA Algorithm
SetupEncryption
 Bob chooses two secret prime numbers. We will call them p and q. To be secure, the numbers must be very big (at least 100 digits).
 Bob calculates n = p * q.
 Bob finds a number e where the greatest common divisor of e and (p  1) * (q  1) is 1.
 Bob finds a number d where d * e = 1 mod ((p  1) * (q  1)).
 Bob publishes n and e as the public key. He keeps d secret and destroys p and q.
Ciphertext = M^{e} mod n
Decryption Message = C^{d} mod n
Questions
 Select two secret prime numbers: p = 3, q = 5.
 Calculate n = p * q = __________________
 Select e such that the greatest common divisor of e and (p  1) * (q  1) is 1:
GCD (e, 8) = 1Which one of these would be a possible choice for e:
 2
 4
 6
 7
 Select d such that d * e = 1 mod ((p  1) * (q  1)). Which one of these would be a possible choice for d:
Encryption Encrypt the message M = 3.
 4
 6
 7
 8
C = M ^{e} mod n
Decryption Decrypt the ciphertext C = 12.M = C ^{d} mod n