250085 VU Topics in Algebra: Cryptography (2019W)
Prüfungsimmanente Lehrveranstaltung
Labels
Exam May 2020
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.Exam October 2020
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.Moodle was exclusive used for the video exam on May!
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.Exam October 2020
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.Moodle was exclusive used for the video exam on May!
Details
max. 25 Teilnehmer*innen
Sprache: Englisch
Lehrende
Termine (iCal) - nächster Termin ist mit N markiert
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.
Dienstag
08.10.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
09.10.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
15.10.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
16.10.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
22.10.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
23.10.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
29.10.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
30.10.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
05.11.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
06.11.
09:45 - 11:15
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
12.11.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
13.11.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
19.11.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
20.11.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
26.11.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
27.11.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
03.12.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
04.12.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
10.12.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
11.12.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
17.12.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
07.01.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
08.01.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
14.01.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
15.01.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
21.01.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
22.01.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag
28.01.
09:45 - 13:00
Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
Mittwoch
29.01.
09:45 - 11:15
Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Donnerstag
30.01.
13:15 - 18:15
Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
Freitag
31.01.
08:00 - 13:15
Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
Mittwoch
11.03.
08:00 - 13:00
Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
Information
Ziele, Inhalte und Methode der Lehrveranstaltung
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.
Art der Leistungskontrolle und erlaubte Hilfsmittel
Oral exam or written manuscript.
Mindestanforderungen und Beurteilungsmaßstab
The knowledge of the following fundamental concepts is required: groups, vector spaces, linear transformations, basics in number theory and probability.
Prüfungsstoff
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: (non)- 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: (non)- 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.
Literatur
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
Zuordnung im Vorlesungsverzeichnis
MALV, MAMV
Letzte Änderung: Mi 09.09.2020 16:09