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.

### 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.