Universität Wien

250107 VO Topics in Algebra: Cryptography (2018W)

4.00 ECTS (2.00 SWS), SPL 25 - Mathematik

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Details

Sprache: Englisch

Prüfungstermine

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

Dienstag 09.10. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 09.10. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 16.10. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 16.10. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 23.10. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 23.10. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 30.10. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 30.10. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 06.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 06.11. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 13.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 13.11. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 20.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 20.11. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 27.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 27.11. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 04.12. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 04.12. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 11.12. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 11.12. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 08.01. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 08.01. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 15.01. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 15.01. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 22.01. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 22.01. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 29.01. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
Dienstag 29.01. 11:30 - 12:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.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 cyphers. Vigenère cipher. If the given key of a Vigenère Cipher has repeated letters, does it make it any easier to break?
(4) 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 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: 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 pidgeonhole 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

Letzte Änderung: Mo 07.09.2020 15:40