Corso di Algebra per Codici e Crittografia

Anno accademico 2021/2022

Presentazione

Il fine di questo corso è quello di presentare alcune tecniche di base, a carattere algebrico, fondamentali per la crittografia e la teoria dei codici, nonché esempi concreti del loro effettivo utilizzo. In particolare, si vogliono fornire nozioni sufficienti per poter comprendere in dettaglio crittosistemi moderni quali AES, RSA e i protocolli basati su curve ellittiche, enucleandone pregi e limitazioni.

Osserviamo che le medesime tecniche, oltre che per problematiche di network security, si rivelano particolarmente significative anche per l'implementazione di alcune tipologie di codifica di sorgente (codici correttori a blocchi). Questo secondo filone, tradizionalmente legato alla trasmissione numerica dell'informazione, riveste un crescente interesse nello studio di sistemi software per l'immagazzinamento dati in memorie intrinsecamente inaffidabili, quali quelle a stato solido.

  1. Programma del Corso

Avvisi

Non ci sono avvisi al momento

Esempi

  1. Esempio di macchina a rotori stile Enigma
  2. Esempio di macchina a rotori stile Enigma - julia
  3. Elevamento a potenza, Zp, primalità (jl)
  4. Esempio di textbook ElGamal e generalizzazioni
  5. Algoritmi Euclidei
  6. Metodo di Gauss per SVP (jl)
  7. LLL e GCD (jl)
  8. Primalità e fattorizzazione
  9. RSA
  10. Birthday Paradox
  11. Birthday Paradox (jl)
  12. Permutazioni casuali
  13. RC4 (jl)
  14. Campi Finiti
  15. AES
  16. Meet in the middle
  17. Curve Ellittiche
  18. Protocollo MQV
  19. Protocollo ECDSA
  20. Funzioni Hash
  21. Esempio di MixNet
  22. Dining Cryptographers
  23. Superposed Sending
  24. DCT

Bibliografia

  1. N.P. Smart, Cryptography Made Simple, Springer-Verlag (2016)
  2. A.R. Meijer, Algebra for Cryptologists, Springer-Verlag (2016)
  3. J. von zur Gathen, CryptoSchool, Springer-Verlag (2015)
  4. W. Stallings, Cryptography and network security, Sixth Edition, Prentice Hall (2014)
  5. N.P. Smart, Cryptography: an introduction, (2013) pdf file:3.0.1.3
  6. M.W. Baldoni, C. Ciliberto, G.M. Piacentini Cattaneo, Aritmetica, crittografia e codici, Springer-Verlag UNITEXT 24, (2006)
  7. A. Languasco, A. Zaccagnini Manuale di crittografia. Teoria, algoritmi e protocolli. Hoepli (2015)
  8. L. Giuzzi, Codici correttori - un'introduzione Springer-Verlag UNITEXT 25, (2006)
  9. A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of applied cryptography, CRC Press (2001)
  10. C. Swenson, Modern Cryptanalysis, Wiley Publishing, Inc. (2008)
  11. G.V. Bard, Algebraic Cryptanalysis, Springer-Verlag (2009)
  12. A. Joux, Algorithmic cryptanalysis, CRC Press (2009)
  13. R. Wobst, Cryptology Unlocked Wiley (2007)
Tutte le lezioni saranno erogate in presenza. Esse saranno anche trasmesse in modalità sincrona mediante la piattaforma Microsoft teams. Il codice del team è csdllv0. Le lezioni saranno erogate sul canale Lezione; saranno inoltre rese disponibili in forma registrata al team del corso.

Lezioni

Video

Appunti

Avviso: I video sono registrazioni non modificate di lezioni erogate in modalità sincrona, messi a disposizione degli studenti per poter sopperire ad eventuali difficoltà tecniche nella fruizione del corso. Non si offre alcuna garanzia di completezza o correttezza delle informazioni fornite; in particolare la loro fruizione non può considerarsi in alcun modo sostitutiva dello studio individuale sui libri degli argomenti del corso. Salvo esplicita diversa indicazione, quanto presente sui testi consigliati fa fede per il programma del corso. Eventuali opinioni espresse durante le lezioni sono da attribuirsi esclusivamente alla persona che le ha formulate e non rappresentano la posizione dell'Università.

Referenze e approfondimenti

Referenze generali

  1. C. E. Shannon, Communication Theory of Secrecy Systems, in "A mathematical Theory of Cryptography" (1949).

Crittografia classica e macchine cifranti

  1. W.F. Friedman, Military Cryptanalysis - Part I: monoalphabetic subsitution systems
  2. W.F. Friedman, Military Cryptanalysis - Part II: simpler varieties of polyalphabetic substitution systems
  3. W.F. Friedman, Military Cryptanalysis - Part III: simpler varieties of aperiodic substitution systems
  4. W.F. Friedman, Military Cryptanalysis - Part IV: transposition and fractionating systems
  5. A. Turing, A treatise on the Enigma
  6. Brevetto US 6175625 (Sigaba)

Diffie-Hellman e STS

  1. W. Diffie, M.E. Hellman, New directions in Cryptography, IEEE Transactions on Information Theory 22: 644-654 (1976), doi:10.1109/TIT.1976.1055638
  2. W. Diffie, P.C. Oorschot and M.J. Wiener, Authentication and Authenticated Key Exchanges, Des. Codes and Cryptography 2: 107-125 (1992), doi:10.1007/BF00124891

ElGamal

  1. T. Elgamal, A public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory IT-31: 469-472 (1985) oppure CRYPTO'84: 10-18, Springer-Verlag.
  2. D. Boneh, A. Joux, P.Q. Nguyen, Why Textbook ElGamal and RSA Encryption are Insecure

Pairing e ID-based cryptography

  1. A. Menezes, An introduction to pairing-based cryptography, Recent trends in cryptography, Contemp. Math. 477: 47-65 (2009).
  2. A. Shamir, Identity-based Cryptosystems and Signature Schemes, Advances in Cryptology, Lecture Notes in Computer Science 7: 47-53 (1984)
  3. D. Boneh, M. Franklin, Identity-based Ecryption from the Weil Pairing, SIAM J. of Computing 32: 586-615 (2003).

RSA

  1. R.L Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21: 120-126 (1978)
  2. R.L. Rivest, R.D. Silverman, Are 'strong' primes needed for RSA? (1999)
  3. D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices of the AMS, 46(2): 203-213 (1999)
  4. M. Bellare, P. Rogaway, Optimal Asymmetric Encryption - How to encrypt with RSA, Extended abstract in Advances in Cryptology - Eurocrypt 94 Proceedings, Lecture Notes in Computer Science 950 (1995)

Primalità e fattorizzazione

  1. A. Granville, It is easy to determine whether a given integer is prime, Bull. of the A.M.S. 42(1):3-38 (2004)
  2. M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, Ann. of Math. 160(2):781-793 (2004).
  3. A.K. Lenstra, Integer factoring, Des. Codes. Crypto. 19:101-128 (2000)

Birthday paradox

  1. P.J. Cameron, Notes on probability

Prodotto di polinomi

  1. J.M. Pollard, The Fast Fourier Transform in a Finite Field, Mathematics of Computation 114(25): 365-374 (1971)
  2. R.T. Moenck, Practical Fast Polynomial Multiplication, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation (1976)
  3. A.A. Karatsuba, The Complexity of Computations, Proceedings of the Steklov Institute of Mathematics 211: 169-183 (1995)

Codici a blocchi

  1. H. Feistel, Block Cipher Cryptographic System, US Patent 3798359 (1975)
  2. Data Encryption Standard (DES), FIPS-46-3 (1999)
  3. D. Coppersmith, The Data Encryption Standard (DES) and its strenth against attacks, IBM Journal of Research and development, 38(3) 243-250 (1994).
  4. M. Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology - Eurocrypt'93, 765/1994, 386-397 (1994), doi:10.1007/3-540-48285-7_33 .
  5. E. Biham, A. Shamir, Differential Cryptanalysis of DES-like Cryptosystems, J. Criptol., 4 3-72 (1991).
  6. R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, L. Wingers, The Simon and Speck Families of Lightweight Block Ciphers (2013).
  7. The Advanced Encryption Standard (AES), FIPS-197 (2001)
  8. J. Daemen, V. Rjimen, AES Proposal: Rijndael (1999)
  9. M. Dworkin, Recommendation for Block Cipher Modes of Operation, NIST Special Publication 800-38A (2001)
  10. D.A. McGrew, J. Viega, The Galois/Counter Mode of Operation (GCM)
  11. V. Rjimen, Efficient implementation of the Rijndael S-Box
  12. F.X. Standaert, G. Piret, J.J. Quisquater, Cryptanalysis of Block Ciphers: a survey, UCL Crypto Group Technical Report CG-2003/2
  13. C.Cid, Some algebraic aspects of the Advanced Encryption Standard, Proceedings of the Fourth Conference on the Advanced Encryption Standard (AES4), LNCS 3373: 58-66 (2004)
  14. C.Cid, S. Murphy, M. Robshaw Computational and Algebraic Aspects of the Advanced Encryption Standard, Proceedings of the Seventh International Workshop on Computer Algebra in Scientific Computing CASC' 2004: 93-103 (2004)
  15. C. Burwick, D. Coppersmith, E. D'Avignon, R. Gennaro, S. Halevi, C. Jutla, S.M. Matyas Jr., L. O'Connor, M. Peyravian, D. Safford, N. Zunic, Mars - a candidate cipher for AES (1999)

Curve Ellittiche

  1. S.C. Vo, A survey of Elliptic Curve Cryptosystems, part I: Introductory, NASA Ames Research Center Technical Report NAS-03-012 (2003)
  2. Certicom Research, Standards for Efficient Cryptography 1 (SEC1), 2009
  3. Nippon Telephone and Telegraph Corporation, Standards for Efficient Cryptography SEC X.1: Supplemental Document for Odd Characteristic Extension Fields, Working Draft 2009
  4. H. Krawczyk, HMQV: A High-Performance Secure Diffie-Hellman Protocol, Advances in cryptology - CRYPTO 2005, 3621: 546-566 (2005)
  5. A. Menezes, Another look at HMQV, Journal of Mathematical Cryptology 1: 148-175 (2007)
  6. H. W. Lenstra, Factoring integers with elliptic curves, Annals of Mathematics 1126: 649-673 (1987)
  7. S. Goldwasser, J. Kilian, Primality testing using elliptic curves, Journal of the ACM 46(4): 450-472 (1999)
  8. FIPS 186-4: Digital Signature Standard (DSS) (2013)
  9. ANS X9.62: Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA) (1998, draft)

Numeri Casuali

  1. E. Barker, J. Kelsey Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST Special Publication 800-90A (2012)
  2. D. J. Bernstein, T. Lange, R. Niederhagen, Dual EC: A Standardized Back Door (2015)

Nozioni di sicurezza per crittosistemi a chiave pubblica

  1. M. Bellare, A. Desai, D. Pointcheval, P. Rogaway Relations Among Notions of Security for Public Key Encryption Schemes, Extended abstract in Advances in Cryptology - CRYPTO'98, Lecture Notes in Computer Science 1462 (1998)
  2. A. Shamir, R.L. Rivest, L.M. Adleman, Mental Poker in The Mathematical Gardner, ed. D.A. Klarner: 37-43 (1981)
  3. M. Blum, Coin flipping by telephone: a protocol for solving impossible problems, ACM SIGACT News, 15 (1983)

Hash functions

  1. B. Preneel, Analysis and design of cryptographic hash functions, Ph.D. thesis (1993)
  2. FIPS 180-4: Secure Hash Standard (SHS) (2012)
  3. FIPS 198: The Keyed-Hash Message Authentication Code (HMAC) (2002)
  4. P. Gauravaram et al., Grøstl - a SHA-3 candidate (2008)
  5. P. Gauravaram et al., Grøstl Addendum (2009)
  6. E. Biham, O. Dunkelman, A framework for Iterative Hash Functions --- HAIFA Proceedings of the Second NIST Cryptographic Hash Workshop (2006-2007)
  7. G. Bertoni, J. Daemen, M. Peeters, G. Van Assche The Keccak reference, 2011
  8. G. Bertoni, J. Daemen, M. Peeters, G. Van Assche Cryptographic sponge functions, 2011
  9. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, FIPS-202 (2015)

Condivisione di segreti

  1. A. Shamir, How to Share a Secret, Communications of the ACM 22:612-613 (1979)
  2. O. Goldreich, D. Ron, M. Sudan, Chinese Remaindering with Errors, IEEE Transactions on Information Theory 46: 1330-1338 (2000)

Anonimità

  1. D.L. Chaum, Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, Communications of the ACM 24: 84-88 (1981)
  2. D.L. Chaum, The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, J. Cryptology 1: 65-75 (1988)
  3. M. Waider, Unconditional Sender and Recipient Untraceability in spite of Active Attacks, Proceedings of EUROCRYPT'89: 302-319 (1989)
  4. M. Waider, B. Pfitzmann, Unconditional sender and recipient untraceability in spite of active attacks - Some remarks, Fakultät für Informatik, Universität Karlshrue, Interner Bericht 5/89 (1989)
  5. M. Waider, B. Pfitzmann, The Dining Cryptographers in the Disco: Unconditional Sender and Recipient Untraceability with Computationally Secure Serviceability (1989).
  6. P.Golle, A.Juels, Dining Cryptographers Revisited, Advances in Cryptology (EUROCRYPT'04): 456-473 (2004)
  7. C.Park, K. Itoh, K.Kurosawa, Efficient Anonymous Channel and All/Nothing Election Scheme, EUROCRYPT'93 Workshop on the theory and application of cryptographic techniques on Advances in cryptology (1993)
  8. B. Pfitzmann, Breaking an Efficient Anonymous Channel, EUROCRYPT'94: 339-348 (1994)
  9. W.Ogata, K.Kurosawa, K.Sako, K.Takatani, Fault Tolerant Anonymous Channel, ICICS'96 Proceedings of the First International Conference on Information and Communication Security (1997)
  10. D.Chaum, T.P. Pedersen, Wallet Databases with Observers, Proc. of Crypto'92: 89-105 (1993)
  11. D. Boneh, P. Golle, Almost Entirely Correct Mixing With Applications to Voting, CCS'02 Proceedings of the 9th ACM Conference on Computer and communications security (2002)
  12. P.Golle, M.Jakobsson, A.Juels, P.Syverson, Universal Re-encryption for Mixnets, Proceedings of the 2004 RSA Conference: 163-178 (2002)

Homomorphic Encryption

  1. R.L. Rivest, L. Aldeman, M.L. Dertouzos, On Data Banks and Privacy Homomorphisms, in Foundations of Secure Computation, 169-180 (1978)
  2. C. Gentry, Computing Arbitrary Functions of Encrypted Data, Communications of the ACM, 53 (3) 97-105 (2010)
  3. C. Gentry, A fully homomorphic encryption scheme, Stanford University, PHD Thesis (2009)
  4. S.Halevi, V.Shoup, Algorithms in HElib, Advances in Cryptology - CRYPTO 2014, Springer-Verlag, 554-571 (2014)

Oblivious Transfer

  1. A. Rabin, How to exchange secrets with oblivious transfer, Technical Report TR-81, Aiken Computation Lab, Harvard University (1981)
  2. S. Even, O. Goldreich, A. Lempel, A randomized protocol for Signing Contracts, Communications of the ACM 28(6), 637-647 (1985)

Secure multiparty computation

  1. A.C. Yao, Protocols for Secure Computations (1982)
  2. A.C. Yao, How to Generate and Exchange Secrets, Foundations of Computer Science - FOCS 1986, IEEE 16-167 (1986)
  3. Y. Lindell, B. Pinkas, Secure Multiparty Computation for Privacy-Preserving Data Mining, Journal of Privacy and Confidentiality 1, 59-98 (2009)
  4. M. Bellare, V.T. Hoang, P. Rogaway, Foundations of Garbled Circuits, In ACM Computer and Communications Security (CCS'12) ACM (2012).
  5. I.Damgård, M.Geisler, M.Krøigaars, J.B.Nielsen Asynchronous Multiparty Computation: Theory and Implementation, In Public Key Cryptography - PKC 2009, Springer-Verlag, 160-179 (2009)

Blind Signatures

  1. D. Chaum, Blind signatures for untraceable payments, Advances in Cryptology - Proceedings of CRYPTO'82, Springer-Verlag, 199-203 (1983)
  2. J.L.Camenisch, J-M.Piveteau, M.A.Stadler, Blind signatures based on the discrete logarithm problem, Advances in Cryptology - EUROCRYPT'94, Springer-Verlag, 428-432 (1994)

Deniable Encryption

  1. R.Canetti, C.Dwork, M.Naor, R.Ostrovsky, Deniable Encryption, Advances in Cryptology - Crypto'97, Springer-Verlag, 90-104 (1997)
  2. A.Sahai, B.Waters, How to use indistinguishability obfuscation: deniable encryption and more, STOC'14 - Proceedings of the 46 Annual ACM Symposium on Theory of Computing, 475-484 (2014)

Problema dei Generali Bizantini

  1. L. Lamport, R. Shostak, M. Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems: 382-401 (1982)

E-Voting

  1. L. Fouard, M.Duclos, P.Lafourcade, Survey on Electronic Voting Schemes
  2. A.Fujioka, T.Okamoto, K.Ohta, A practical secret voting scheme for large scale elections, Advances in Cryptology - AUSCRYPT'92, Springer-Verlag, 244-251 (1992)

Codici correttori

  1. C.E. Shannon, A Mathematical Theory of communication, Bell System Tech. Journal Vol. XXVII: 379-423, 623-656 (1948).
  2. I.S. Reed, G. Solomon, Polynomial codes over certain finite fields, J. Soc. Ind. Appl. Math. Vol. 8: 300-304 (1960).
  3. E. R. Berlekamp Non-binary BCH Decoding, University of North Carolina Institute of Statistics Mimeo Series No. 502 (1966)
  4. L.R. Welch, E.R. Berlekamp, Error Correction for Algebraic Block Codes, US Patent no. 4633470 (1986).