Universität Wien FIND

Kehren Sie für das Sommersemester 2022 nach Wien zurück. Wir planen Lehre überwiegend vor Ort, um den persönlichen Austausch zu fördern. Digitale und gemischte Lehrveranstaltungen haben wir für Sie in u:find gekennzeichnet.

Es kann COVID-19-bedingt kurzfristig zu Änderungen kommen (z.B. einzelne Termine digital). Informieren Sie sich laufend in u:find und checken Sie regelmäßig Ihre E-Mails.

Lesen Sie bitte die Informationen auf https://studieren.univie.ac.at/info.

250085 VU Topics in Algebra: Cryptography (2019W)

7.00 ECTS (4.00 SWS), SPL 25 - Mathematik
Prüfungsimmanente Lehrveranstaltung

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!

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

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

Zuordnung im Vorlesungsverzeichnis

MALV, MAMV

Letzte Änderung: Mi 09.09.2020 16:09