Warning! The directory is not yet complete and will be amended until the beginning of the term.
250085 VU Topics in Algebra: Cryptography (2019W)
Continuous assessment of course work
Labels
The oral video exam will take place on May 14, 2020. Please contact Prof. Arzhantseva by email for the registration, the assignment of the exact time and further instructions.
Details
max. 25 participants
Language: English
Lecturers
Classes (iCal) - next class is marked with N
The oral presence exam will take place on October 7, 2020 in the Besprechungszimmer 2nd floor. This is the last possibility for the exam on this course. Please contact Prof. Arzhantseva by email for the registration, the assignment of the exact time and further instructions.
- Tuesday 08.10. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 09.10. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 15.10. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 16.10. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 22.10. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 23.10. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 29.10. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 30.10. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 05.11. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
-
Wednesday
06.11.
09:45 - 11:15
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock - Tuesday 12.11. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 13.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 19.11. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 20.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 26.11. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 27.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 03.12. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 04.12. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 10.12. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 11.12. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 17.12. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 07.01. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 08.01. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 14.01. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 15.01. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 21.01. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 22.01. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 28.01. 09:45 - 13:00 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 29.01. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
- Thursday 30.01. 13:15 - 18:15 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
- Friday 31.01. 08:00 - 13:15 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
- Wednesday 11.03. 08:00 - 13:00 Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
Information
Aims, contents and method of the course
This introductory course is on selected chapters of modern cryptography. We discuss both classical and rather recent cryptographic topics. These include currently the most popular RSA (= Rivest-Shamir-Adleman) and ECC (= Elliptic Curve Cryptography) public-key cryptosystems as well as the use of cryptography in blockchain technology. Theoretical results are supported by exercises and concrete real-life examples such as the discussion on security issues in WhatsApp and in the design of Bitcoin.
Assessment and permitted materials
Oral exam or written manuscript.
Minimum requirements and assessment criteria
The knowledge of the following fundamental concepts is required: groups, vector spaces, linear transformations, basics in number theory and probability.
Examination topics
Content of the lectures and exercises.Exam questions:
(1) Cryptography principles: definitions, (non) examples. Basic cryptography concepts (primitive, protocol, cover time, etc.). Basic model for secrecy: (none)- examples. Cryptosystem for secrecy: definition, examples. Symmetric versus asymmetric cryptosystems.
(2) Main attacks on encryption algorithms. Passive versus active attacks. Keys: length, size. Brute-force attack: assumptions, estimates on key lengths.
(3) Examples of symmetric cryptosystems: Caesar and Substitution ciphers. The letter frequency analysis. Monoalphabetic and polyalphabetic ciphers. Vigenère cipher. If the given key of a Vigenère Cipher has repeated letters, does it make it any easier to break?
(4) The computational complexity of basic mathematical operations and of the exhaustive key search attack. Complexity classes of algorithms.
(5) Three types of security. Perfect secrecy: definition, examples, equivalent formulations (with proof). Perfect secrecy: Shannon’s Theorem (with proof).
(6) RSA cryptosystem: definition, examples, correctness (encryption and decryption are inverse operations). Parameter generation, its complexity. Main attacks.
(7) One-way function, with a trapdoor. Theorem: RSA keys vs Factoring (formulation and sketch of proof).
(8) Hash function: definition, types of resistance, (non)-examples. Optimal asymmetric encryption padding.
(9) Discrete logarithm problem. The DLP assumption. The DLP in (Z/(p-1)Z, +) Is breaking the ECC cryptosystem equivalent to solving the DLP?
(10) ElGamal cryptosystem and parameter generation: definition, correctness (encryption and decryption are inverse operations). Theorem: ElGamal keys versus DLP (with proof).
(11) Elliptic curve: definition, singularities, normal forms, tangents. Theorem: the intersection of E with a projective line (with proof).
(12) Group structure on the elliptic curve over the algebraic closure, geometrically: definition and theorem (with proof).
(13) Cayley-Bacharach’s theorem (with proof).
(14) Associativity (sketch of proof).
(15) Elliptic curves over finite fields: theorems (without proof) and examples. Check that for a prime q, each natural number in the Hasse interval occurs as the order of the elliptic curve group over the field of q elements.
(16) Diffie-Hellman key agreement: protocol, attacks. The DHP problem. The ECDHE.
(17) Digital Signature Scheme. RSA signature algorithm. Attacks: definitions and examples.
(18) DSS with hashing. Hash functions from block ciphers: definition and example, with proof (the example where (x,y)àaxby).
(19) DSS and Public-key cryptosystem: sign-then-encrypt versus encrypt-versus- sign.
(20) ElGamal variant of DSS: definition and correctness. Security assumptions. Example of misuse (with proof).
(21) ElGamal variant of DSS: example of misuse (with proof). ECDSA: definition and correctness.
(22) Digital currency: definition and security requirements. Distributed ledgers. Blockchain. Security assumptions underlying the generation of the bitcoin address.
(23) Bitcoin transaction and its verification. Merkle tree. Bitcoin mining.
(24) Bit generator. Linear feedback shift register: definition, periods, security. RSA bit generator.
(25) Distinguisher. Next bit predictor. Yao’s theorem (sketch of proof).
(26) Error-correcting codes and expander graphs.
(27) Describe the probabilistic pigeonhole principle and explain, with examples, why it is relevant in cryptography (i.e hash functions, birthday paradox, etc).
(28) Describe a variety of attacks that rely on structural weaknesses in respective cryptosystems (for instance, known message attacks for multiplicative systems, or weaknesses of El Gamal under weak random choices).
(29) Describe Shanks algorithm, give examples of its use and outline how to use Shanks Algorithm to compute the order of an elliptic curve of prime order in combination with Hasse’s bound.
(1) Cryptography principles: definitions, (non) examples. Basic cryptography concepts (primitive, protocol, cover time, etc.). Basic model for secrecy: (none)- examples. Cryptosystem for secrecy: definition, examples. Symmetric versus asymmetric cryptosystems.
(2) Main attacks on encryption algorithms. Passive versus active attacks. Keys: length, size. Brute-force attack: assumptions, estimates on key lengths.
(3) Examples of symmetric cryptosystems: Caesar and Substitution ciphers. The letter frequency analysis. Monoalphabetic and polyalphabetic ciphers. Vigenère cipher. If the given key of a Vigenère Cipher has repeated letters, does it make it any easier to break?
(4) The computational complexity of basic mathematical operations and of the exhaustive key search attack. Complexity classes of algorithms.
(5) Three types of security. Perfect secrecy: definition, examples, equivalent formulations (with proof). Perfect secrecy: Shannon’s Theorem (with proof).
(6) RSA cryptosystem: definition, examples, correctness (encryption and decryption are inverse operations). Parameter generation, its complexity. Main attacks.
(7) One-way function, with a trapdoor. Theorem: RSA keys vs Factoring (formulation and sketch of proof).
(8) Hash function: definition, types of resistance, (non)-examples. Optimal asymmetric encryption padding.
(9) Discrete logarithm problem. The DLP assumption. The DLP in (Z/(p-1)Z, +) Is breaking the ECC cryptosystem equivalent to solving the DLP?
(10) ElGamal cryptosystem and parameter generation: definition, correctness (encryption and decryption are inverse operations). Theorem: ElGamal keys versus DLP (with proof).
(11) Elliptic curve: definition, singularities, normal forms, tangents. Theorem: the intersection of E with a projective line (with proof).
(12) Group structure on the elliptic curve over the algebraic closure, geometrically: definition and theorem (with proof).
(13) Cayley-Bacharach’s theorem (with proof).
(14) Associativity (sketch of proof).
(15) Elliptic curves over finite fields: theorems (without proof) and examples. Check that for a prime q, each natural number in the Hasse interval occurs as the order of the elliptic curve group over the field of q elements.
(16) Diffie-Hellman key agreement: protocol, attacks. The DHP problem. The ECDHE.
(17) Digital Signature Scheme. RSA signature algorithm. Attacks: definitions and examples.
(18) DSS with hashing. Hash functions from block ciphers: definition and example, with proof (the example where (x,y)àaxby).
(19) DSS and Public-key cryptosystem: sign-then-encrypt versus encrypt-versus- sign.
(20) ElGamal variant of DSS: definition and correctness. Security assumptions. Example of misuse (with proof).
(21) ElGamal variant of DSS: example of misuse (with proof). ECDSA: definition and correctness.
(22) Digital currency: definition and security requirements. Distributed ledgers. Blockchain. Security assumptions underlying the generation of the bitcoin address.
(23) Bitcoin transaction and its verification. Merkle tree. Bitcoin mining.
(24) Bit generator. Linear feedback shift register: definition, periods, security. RSA bit generator.
(25) Distinguisher. Next bit predictor. Yao’s theorem (sketch of proof).
(26) Error-correcting codes and expander graphs.
(27) Describe the probabilistic pigeonhole principle and explain, with examples, why it is relevant in cryptography (i.e hash functions, birthday paradox, etc).
(28) Describe a variety of attacks that rely on structural weaknesses in respective cryptosystems (for instance, known message attacks for multiplicative systems, or weaknesses of El Gamal under weak random choices).
(29) Describe Shanks algorithm, give examples of its use and outline how to use Shanks Algorithm to compute the order of an elliptic curve of prime order in combination with Hasse’s bound.
Reading list
1. Martin, Keith M. Everyday cryptography. Fundamental principles and applications. Second edition. Oxford University Press, Oxford, 2017. xxx+674 pp. ISBN: 978-0-19-878801-0; 978-0-19-878800-3
2. Stinson, Douglas R. Cryptography. Theory and practice. Third edition. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006. xviii+593 pp. ISBN: 978-1-58488-508-5; 1-58488-508-4
3. Daniel J. Bernstein & Tanja Lange, Post-quantum cryptography, Nature, 2017, Vol.549, 188–194. ISSN: 0028-0836 ; E-ISSN: 1476-4687 ; DOI: 10.1038/nature23461
2. Stinson, Douglas R. Cryptography. Theory and practice. Third edition. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006. xviii+593 pp. ISBN: 978-1-58488-508-5; 1-58488-508-4
3. Daniel J. Bernstein & Tanja Lange, Post-quantum cryptography, Nature, 2017, Vol.549, 188–194. ISSN: 0028-0836 ; E-ISSN: 1476-4687 ; DOI: 10.1038/nature23461
Association in the course directory
MALV, MAMV
Last modified: We 09.09.2020 16:09