Contents | Announcements | Exams | Literature | Pictures, videos, and slides |
Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room MF 6.104B
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
Netherlands
Phone: +31 (0) 40 247 4764
The easiest ways to reach me wherever I am:
e-mail:tanja@hyperelliptic.org
Some of the lectures will be given by Chloe Martindale.
Contents
Note that one of the course requirements is algebra. I will not repeat basic background on groups, rings and fields in class. If you don't have the necessary background, take the summer and work through the "Number Theory and Algebra" script.
It is not necessary to purchase a book to follow the course.
Previous versions of this course used
Henk van Tilborg's "Fundamentals of Cryptology", Kluwer academic
Publishers, Boston, 2000. But the book is out of print.
A preliminary author's copy by Henk can be downloaded in pdf form
here
and as a mathematica worksheet here.
Other books you might find useful
The exam will be an open-book exam, meaning that you can use any book
or notes that you have on paper.
You may use a programmable calculator and I expect you to be able
to use it for modular exponentiation and inversion.
I will also bring a laptop with
access to the course page incl. blackboard pictures and scripts, but
you may not use it to surf the internet. There will be a termnal
to run GP-Pari; sage is not available on the laptop.
For 2MMC10, the first exam will take place October 31, 2017, 13:30 - 16:30. The retake exam will take place January 23, 2018, 18:00 - 21:00. Rooms will be announced. For Mastermath the exam will take place on January 8, 2018, 14:00 - 17:00. We plan to merge the retake with the 2MMC10 retake, this means that you need to come to TU/e on Jan 23.
For 2MMC10 you can earn up to 1P for the final mark through the homework. Please hand in your solutions in groups of 2 or 3, we do not have the capacity for individual corrections. Please make sure to register for the exam in time. For TRU/e students from Nijmegen, this means that you need to register at TU/e as well and get a student number etc.
For students from Mastermath, please register on their site.
You can earn up to 1P for the final mark through the homework.
The bonus point only counts if the grade for the exam is at least
5.0, so even if you score a full bonus point in the homework but
only a 4.5 in the test you do not pass. Please
hand in your solutions in groups of 2 or 3, we do not have the
capacity for individual corrections. Please submit your solution
on time by email to the address below.
For all students:
Gustavo Banegas and
Manos Doulgerakis are
the teaching assistants for this course. You can reach them
at crypto.course (at) tue.nl.
Do not send me your homework but submit it
on paper before the Thursday lectures. If there is a programming
component to the exercises email the solution to the TAs.
If an assignment is unclear and you have questions about the
homeworks, contact me in class or by email.
05 Sep 2017
General introduction to cryptography; concepts public key,
symmetric key cryptography, and hash functions.
Pictures of blackboards are here.
Videos will come as soon as I have better internet.
If you want to try your skills at some cryptosystems visit http://www.mysterytwisterc3.org/.
As an example we attacked the
"Perfect Code Public Key System" by Fellows and Koblitz. Attention,
this was never proposed for cryptography but only as a teaching tool.
Here are the slides in pdf for the perfect code
system.
07 Sep 2017
Recap on Fermat's little theorem, Euler phi function and its computation,
Lagrange's theorem,
Chinese Remainder Theorem (CRT).
RSA encryption (KeyGen, Encrypt, Decrypt), exponentiation via square
and multiply, use of RSA in hybrid encryption (use RSA to encrypt a
key for symmetric crypto, use the latter to encrypt the message.
choolbook RSA is homomorphic, avoid this structure
by using a padding scheme; we covered
RSA OAEP.
RSA signatures (KeyGen, Sign, Verify).
Note that RSA is exceptional in that signing and encrypting are
so closely related.
Faster decryption/signing via CRT-RSA incl. estimates on
improvement (look up Karatsuba multiplication).
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 14 Sep, at 10:45.
To submit, please bring your homework on paper to the
lecture on Thursday and hand it before the lecture to the
lecturer.
For MasterMath, homework is due Thursday, 28 Sep, at 10:45 by email.
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The exercise sheet is here.
For the RSA exercise you can assume a
caclulator with very large precision, i.e. you should use the
square-and-multiply method.
12 Sep 2017
Factorization techniques for integers: trial division, Pollard's
rho method including explanation why it works when it works and
Floyd's cycle-finding algorithm; Pollard's p-1 method including
why it works.
Start of explanation of how to factore RSA numbers; e.g. how to
factor if p and q ar too close.
Pictures of blackboards and videos are here.
14 Sep 2017
Factorization using Dixon's method/method of random squares.
The initial example didn't work as well as I expected and I
couldn't connect with my laptop. Thanks for helping out
with laptop and typing!
We used the computer algebra system Pari-gp for the examples
and I wrote some of the commands on the board (also at the
beginning of the second lecture). See the beginning of the
second lecture (= 4th picture)
for a working example of factoring 323.
Q-sieve, quadratic sieve, some comments about the number-field
sieve and running times.
You can find examples and code snippets for these methods and
those from the previous lecture on http://facthacks.cr.yp.to.
The slides I used are here.
Primality testing methods: Fermat test and Carmichael numbers;
Miller-Rabin test. These tests are 100% correct when they output
'not prime'; otherwise they say 'maybe prime'. If you want to
be sure that a number is prime, you need to use a primality
proof. Read up on Pocklington's test.
Pictures of blackboards and videos are here.
For 2MMC0, homework is due next Thursday, 21 Sep, at 10:45.
To submit, please bring your homework on paper to the
lecture on Thursday and hand it before the lecture to the
lecturer.
For MasterMath, homework is due Thursday, 12 Oct, at 10:45 by email.
Please submit in groups of size 2
or 3; we do not have the correction capacity for handling
singletons. The exercise sheet is here.
Note that you do not need to write anything for exercise 6.
The next lectures will be given by Chloe Martindale and Joan Daemen. While I'm offline you can find photos and videos on Chloe's homepage.
HomeworkOld exams by me: