Franz Lemmermeyer

Introduction To Cryptography

Schedule

  Mo 13:40 - 15:30, SAZ 19
  We 15:40 - 17:30, SAZ 19

Topics

RSA
Complexity of basic algorithms
Primality Tests
Factorization Methods
Other Cryptographic Protocols (key exchange, authorization, . . . )
DLP
Elliptic Curves
Algebraic Tori

RSA-129

When Rivest, Shamir and Adleman published their public key scheme, they challenged the readers to decrypt the following message. It was encoded with the public key (N,e), where

N = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541

was later called RSA-129 because it has 129 digits, and where e = 9007. The factorization of N was achieved in 1994. Given the prime factor

p = 3490529510847650949147849619903898133417764638493387843990820577

use pari (and cut & paste; right-click the blue frame at the top of the pari window) to find q, compute d, and decrypt the message

c = 96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154

Homework

Homework is always due one week after hand-out except when stated otherwise. Solutions will be posted after all students have turned their homework in.

Th 13.09.06 problems; due next Tuesday since I forgot to give you the message m.
Th 28.09.06 problems; solutions
Th 06.10.06 problems; solutions
Th 06.10.06 problems; solutions
Tu 14.11.06 The 4 problems at the end of Chapter 8.

What I did in class

Tu 12.09.06: Cryptograms.
Th 14.09.06: RSA.
Tu 19.09.06: complexity of algorithms
Th 21.09.06: primality tests.
Tu 26.09.06: PRIMES IS IN P (AKS)
Th 28.09.06: complexity of AKS; factoring algorithms
Tu 03.10.06: factoring algorithms (Lehman, p-1)
Th 05.10.06: Pollard's rho method
Tu 10.10.06: Modern factorization methods; security of RSA
Th 12.10.06: 3:40-5:30 Discrete Logarithms
Tu 17.10.06:
Th 19.10.06: NO CLASS, moved to 11.10.06
Tu 24.20.06 no class
Th 26.10.06 no class
Tu 31.10.06 Diffie-Hellman etc.
Th 02.11.06 review
Tu 07.11.06 Midterm 1, SBZ 10 Here are the exam and the solutions. The average was 70.5
Th 09.11.06 3:40-5:30 midterm solutions
Tu 14.11.06 Finite fields.
Th 16.11.06 no class; moved to 09.11.06
Tu 21.11.06 Pell conics
Th 23.11.06 Pell conics, p+1 method
Tu 28.11.06 primality tests based on p+1, Pell cryptography
Th 30.11.06 No class.
Tu 05.12.06 Elliptic curves; ECM
Th 07.12.06 ECPP
Tu 12.12.06 ECC
Th 14.12.06 Cryptography based on tori and Braid Groups
Tu 19.12.06 Midterm 2 solutions. Average 72/100
Th 21.12.06 No class

Here's the take-home final. You can use the following numbers to cut and paste them into pari:

     n = 10861745462990897534907816853010793219571
     m = 3141592653589793238462643383          
     r = 69844585193681467109
     s = 87124120179688940726
     p =  556988536090052377769

Jan. 08, 2007 Final, 9:30 - 11:30, AZ25. Please finish the take home final until Monday.

Here are the updated notes.