TUM Logo

Algebraic methods and algorithms in cryptology

Algebraic methods and algorithms in cryptology  

Seminare 2 SWS / 4 or 5 ECTS
Veranstalter: Alexander Malkis
Zeit und Ort:

Mo, 08:00 – 09:55 Uhr, 01.06.011
Beginn: 2017-04-24

The lecture is given in english
The slides are available in english
The exam will be in english

Preliminary meeting and registration

All possible registration deadlines and procedures are over, and the time table is full. However, a possibility for joining might still exist. If a student wishes to participate but did not register before, he/she is asked to contact the instructor, send him his/her preferences, and wait for an answer. The specified preferences should contain:

  • who he/she would like to work with in the same group (ordered from most preferred to least preferred),
  • who he/she is opposed to work with in the same group (ordered from most opposed to least opposed),
  • the topic(s) of his/her preference (linearly ordered from the most preferred to the least preferred; please mention as many topics from the lists of taken and available lists and as possible),
  • the number of ECTS points (4 or 5) he/she needs.

Contents

This seminar provides an overview of the most important cryptologic methods and algorithms. The seminar focuses on the algebraic techniques. The necessary mathematical knowledge, such as modular arithmetic, prime numbers, factorization, discrete logarithms, quadratic residues, and elliptic curves, is introduced, including detailed proofs from seminar participants on the corresponding topics.

As of 2017-02-27, the topics in the list below have been assigned for presentations.

  1. Mathematical background. The (almost finalized) list of topics is as follows:
    • Introduction, public-key cryptography, best practices
    • Euclidean algorithm
    • Extended Euclidean algorithm (descriptions, possibly proofs, and possibly examples)
    • Chinese remainder theorem example and explanation
    • Euclidean space (overview)
    • Hadamard inequality (overview)
    • Legendre symbol (overview)
    • Jacobi symbol (overview)
    • Finite fields (brief overview)
    • Gram-Schmidt orthonormalization
    • Symmetric vs. assymetric cryptography
    • Conclusion
  2. Monoalphabetic and polyalphabetic ciphers:
    • Monoalphabetic ciphers:
      • Permutation-based cipher
      • Substitution-based cipher
      • Affine cipher
      • Cryptanalysis of monoalphabetic ciphers: Kerkhoff's principle, confusion principle, diffusion principle, known-ciphertext attack, known-plaintext attack, chosen-plaintext attack, chosen-ciphertext attack
    • Polyalphabetic ciphers:
      • Vigenère cipher
      • Hill cipher
      • Block and stream ciphers
      • Electronic-Codebook
      • Cipher-block-chaining
      • Cipher-feedback
      • Output-feedback
      • One-time pad
  3. RSA:
    • Cryptographic systems:
      • Definition
      • Symmetric-key cryptography
      • Public-key cryptography
    • RSA cryptosystem:
      • Key generation
      • Encryption and decryption
      • Correctness proof
      • Example
      • Optimization
    • Security of RSA
    • Application of RSA
  4. Solovay-Strassen and Miller-Rabin primality tests (canceled)
  5. Discrete logarithm
  6. Diffie-Hellman key exchange
  7. ElGamal cryptography system
  8. Massey-Omura cryptosystem
  9. Elliptic curves
    • Over a field of characteristics 2
    • Over a field of characteristics > 3
    • The discrete logarithm problem for elliptic curves
    • Cryptographic methods over elliptic curves (Diffie-Hellman, Massey-Omura, ElGamal)
    • Choosing a suitable curve
    • …
  10. Lattice-based cryptography
    • Lattices and bases
    • Lattice basis reduction, the LLL algorithm
    • The knapsack cryptosystem
    • …

The following topics have not been assigned as of 2017-02-27:

  • PRIMES ∈ PTIME
  • PRIMES ∉ AC⁰
  • Integer factorization

Prerequisites

  • Ability to quickly and independently obtain necessary background knowledge.
  • Linear Algebra.
  • Real Analysis.
  • Complexity classes.
  • Helpful: discrete structures, number theory, and combinatorics.

Objective

Understand the mathematical foundations of cryptography.

Teaching and learning method

The work shall be accomplished in groups (of at least one participant per topic). Each group shall submit one report, one set of slides, and give one till three talks, where each talk is given by one till three participants presenting their material one speaker at a time. The contribution of each participant to the report must be clearly specified. Every member of the group has to understand the whole topic and be able to speak about any part of it. The report and the presentation(s) are strictly compulsory: the absence of any of them means a failure. All the written work shall be done in (variants of) LaTeX, possibly using (variants of) bibtex. Using more modern XeLaTeX, LuaLaTex, and/or Biber+Biblatex is welcome. We fix a common notation for all the reports and presentations. The student code of conduct must be observed.
In addition, each participant shall review one report in a double-blind way. (This is just a simulation of what is happening in conferences. In our seminar, it will be virtually impossible to maintain complete anonymity. E.g., the group introducing the mathematical background is likely to get to know the identities of the others and vice versa.)
In a presentation, each participant of each group shall speak at least 25 minutes long. By all means each presentation on a day shall finish by 9:55 a.m., including all questions and answers. There are no other hard restrictions: the duration shall be chosen by the group depending on the topic and on the distribution of work within a group. Each group shall make sure that its presentation is understandable to the audience. Of course, it goes without saying that the speakers shall show that they are scientifically knowledgeable and fluent.
Attending all talks and active participation in discussions is compulsory.
Every action or its absence is influencing the grade, including complying with the schedule.
The seminar language is English.

On 4 vs 5 ECTS points

Some students apparently require 4 ECTS points for IN0014 while others require 5 ECTS points. The seminar is going to be conducted as usual. Some students already get 5 instead of 4 credits.

Schedule

  • February 21: participants are informed.
  • ≤ February 23: each participant is kindly asked to send his/her preferences to the instructor.
  • ≤ February 25: the instructor organizes and announces the constellation of the groups.
  • ≤ March 2: if a person cannot participate, he/she is kindly asked to cancel by that deadline.
  • ≤ March 6: the participants send the list of the required background topics to the instructor. The instructor resends it to the group giving a talk on mathematical background.
  • 6 weeks before the first presentation of a group or earlier: the group writes the 1st informal notice on how the group progresses; a short text e-mail suffices.
  • 5 weeks before the first presentation of a group or earlier: the group writes the 2nd informal notice on progress; again, a short text e-mail suffices.
  • 4 weeks before the first presentation of a group or earlier: the group submits the report and the slides as [sources and [PDF or Postscript]] blindly, i.e., without the names of the author(s) in the two documents. (Simply leave the author field empty; don't use dummy names, nicknames, or pseudonyms.) The sources are the LaTeX, bibliography, and graphic files which get compiled to the final PDF/Postscript file(s).
  • At an arbitrary time point each participant obtains one report for a double-blind review, which he or she has to accomplish within 12 days.
  • 2 weeks before the first presentation of a group or earlier: the group obtains feedback on its report. Since the feedback is done by the other participants, the timely presence of the feedback or its quality are not guaranteed.
  • 1 week before the first presentation of a group or earlier: the group submits the final version of the report and the slides as [sources and [PDF or Postscript]] with the authors' names in the two documents. The contribution of each participant to the report shall be clearly stated. Please provide some information on how you compiled your sources into Postscript or PDF. An example would be "xelatex report && biber report && xelatex report". The compilation should terminate in an error-free way. If you wish your report to be distributed among the other participants, please say so explicitly, including the desired distribution form (PDF/Postscript or on paper).
  • After a participant submitted the final report, he/she obtains feedback on it.
  • After a participant did his/her presentation, he/she obtains feedback on it.
  • After the end of the term, the grade goes formally to TUMonline.

Timetable of talks

Topic Date
Mathematical background 24.04.2017
Monoalphabetic and polyalphabetic ciphers 08.05.2017
RSA 15.05.2017
(canceled) 22.05.2017
(canceled) 29.05.2017
Discrete logarithm 12.06.2017
Diffie-Hellman key exchange 19.06.2017
ElGamal cryptography system 26.06.2017
Massey-Omura cryptosystem 03.07.2017
Elliptic curves; seminar evaluation 10.07.2017
(continuation of elliptic curves) 17.07.2017
Lattice-based cryptography 24.07.2017

A choice of literature

  • https://en.wikipedia.org/wiki/Primality_test
  • Christian Karpfinger and Hubert Kiechle, Kryptologie - Algebraische Methoden und Algorithmen, (1. Auflage 2010), ISBN: 978-3-8348-0884-4.
  • Christof Paar and Jan Pelzl, Understanding Cryptography - A Textbook for Students and Practitioners, ISBN: 978-3-642-04100-6
  • P. Ribenboim, Die Welt der Primzahlen, Springer, 2008.
  • M. Dietzfelbinger, Primality testing in polynomial time, Lecture Notes in Computer Science, 2004.
  • R. Waldecker, L. Rempe-Gillen, Primzahltests für Einsteiger, Vieweg+Teubner Verlag, 2009.
  • S. Y. Yan, Primality testing and integer factorization, 2nd edition, Springer, 2009.
  • J. Buchmann, Einführung in die Kryptographie, Springer, 2010.
  • Eric Allender, Michael Saks, and Igor Shparlinski, A lower bound for primality, Journal of Computer and System Sciences, Volume 62, Issue 2, March 2001, pages 356-366.
  • Affine cipher
  • Kerkhoff's principle
  • Vigenère cipher
  • Hill cipher
  • Stream cipher
  • One-time pad
  • Three-pass protocol
  • M. Ajtai: The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions, Electronic Colloquium on Computational Complexity TR97-047.
  • A. K. Lenstra, H. W. Lenstra, L. Lovász: Factoring Polynomials with Rational Coefficients, Mathematische Annalen 261, 515-534.
  • J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press, Cambridge (1999).
  • W. Diffie, M. E. Hellman: New directions in cryptography, IEEE Transactions on Information Theory, IT-22(6), 644-654.
  • R. C. Merkle, M. E. Hellman: Hiding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, IT-24(5), 525-530.
  • A. Shamir: A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem, IEEE Transactions on Information Theory, IT-30(5), 699-704.
  • R. L. Rivest, A. Shamir, L. M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM 21(2), 120-126 (1978).
  • Elliptic Curve Cryptography
  • Lattice-based cryptography
  • …

General help on scientific writing and [PDF|Xe|Lua]LaTeX