SUNY Geneseo Department of Computer Science

Cryptography Examples

Previous Lecture

End-of-Semester

CS Dept. holiday party

• Wed. Dec. 10, 3:00 PM
• South 309
• Sign up in Dept. office

SOFIs in class next Monday (12/8)

• Need a czar/czaritza

Final

• Monday, Dec. 15, 8:00 AM
• Comprehensive but biased towards material since exam 2
• Same format and rules as hour exams
• Designed for 2 hours, 3 available
• Donuts & cider
• Sample questions will be on the Web

Questions?

RSA Cryptography

To create a public/private key pair:

1. Pick two prime numbers, p & q, such that p mod 4 = q mod 4 = 3
• e.g., 11, 19, 23, 31, 43, 47
2. Compute n = p*q
3. Choose e such that e is relatively prime to n
• (e = 3 is popular)
4. Find d such that e * d mod (p-1)(q-1) = 1
   • e.g., suppose p = 5, q = 7
   • (p-1)(q-1) = 4 * 6 = 24
   • Suppose e = 3
   • Want 3d mod 24 = 1
   • Oops, not solvable

The public key is the pair (e,n)

The private key is the pair (d,n)

Encrypt a numeric message x as y = x^e mod n

Decrypt y as x = y^d mod n

Demonstration:

• Messages = letters
  • A = 2
  • B = 3
  • C = 4
  • ...
  • Z = 27
• Simple symmetric key scheme
  • Pick key, k, as an integer
  • Encode x: y = x * k
  • Decode: x = y / k
• Contrast to RSA public-key scheme

To simplify exponentiations mod n

• x^e = (x²)^e/2 if e is even
  • = x x^e-1 if e is odd
• Any multiplication can be done and taken mod n at any time in evaluating these
  • e.g., 7¹⁶ mod 10
  • = (7²)⁸ mod 10
  • = 49⁸ mod 10
  • = (49 mod 10)⁸ mod 10
  • = 9⁸ mod 10
  • (Because (a*b) mod n = [(a mod n) * (b mod n)] mod n

Next Lecture