Crypto 101

Secret key: Diffie–Hellman, 
Two parties don't know each other can establish a secret key

Alice				Bob
Secret	Public	Calculates	Sends	Calculates	Public	Secret
a	p, g		p,g			b
a	p, g, A	ga mod p = A	A		p, g	b
a	p, g, A		B	gb mod p = B	p, g, A, B	b
a, s	p, g, A, B	Ba mod p = s		Ab mod p = s	p, g, A, B	b, s

Public-private key: RSA

https://www.cs.utexas.edu/~mitra/honors/soln.html

RSA Algorithm Example

• Choose p = 3 and q = 11
• Compute n = p * q = 3 * 11 = 33
• Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
• Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
• Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]
• Public key is (e, n) => (7, 33)
• Private key is (d, n) => (3, 33)
• The encryption of m = 2 is c = 2⁷ % 33 = 29
• The decryption of c = 29 is m = 29³ % 33 = 2