Introdução à Criptografia

Primeiro quadrimestre de 2011
Horário: 2^a (14:00-16:00) e 4^a (14:00-16:00)
Sala de aula: 302A (bloco B) 006-0 (térreo do bloco A)
Professor: Jerônimo C. Pellegrini
Sala do professor: S 805 (bloco B)
Email do professor: jeronimo.pellegrini ufabc edu br

Tragam o trabalho na minha sala SEGUNDA

Novidades:

20/07 -- Notas de aula atualizadas (v.33) [ Grandes mudanças ]
29/05 -- Conceitos após T
09/04 -- Notas de aula atualizadas (v.31) [ Mudanças estéticas e pequenas correções ]
05/04 -- Conceitos após P1
05/04 -- Notas de aula atualizadas (v.30) [ Correções no cap. sobre protocolos;
                                            Cap. sobre compartilhamento de segredos expandido ]
03/04 -- Notas de aula atualizadas (v.29) [ Capítulo sobre protocolos;
                                            Rascunho sobre compartilhamento de segredos ]
01/04 -- Mudança de sala! Vamos para a 006-0 do bloco A
25/03 -- Notas de aula atualizadas (v.28) [ Melhorias no Cap. sobre cripto de chave publica e
                                            redação inicial do Cap. sobre assinatura digital ]
24/03 -- Data da prova alterada (30/março)
23/03 -- Notas de aula atualizadas (v.27) [ Melhorias no Cap. sobre cripto assimétrica e
                                            no Apêndice sobre Teoria dos Números ]
23/03 -- Notas de aula atualizadas (v.26) [ Melhorias no Cap. sobre cripto assimétrica ]
22/03 -- Notas de aula atualizadas (v.25) [ Mais sobre Diffie-Hellman e cripto assimétrica ]
19/03 -- Notas de aula atualizadas (v.24) [ Demonstração do Teorema 8.1 ]
18/03 -- Notas de aula atualizadas (v.23) [ Diversas correções, e um exemplo a mais ]
18/03 -- Notas de aula atualizadas (v.22) [ Melhorias do final do Cap. sobre MAC
                                            em diante ]
16/03 -- Notas de aula atualizadas (v.21) [ Várias pequenas mudanças no texto;
                                            Apresentação de CBC-MAC mais completa ]
16/03 -- Indicações de livros interessantes (não obrigatórios, não tem na UFABC -- pra quem quiser
                                             entender mais sobre Cripto)
14/03 -- Notas de aula atualizadas (v.20) [ Mudanças SOMENTE no Cap. sobre Criptanálise
                                            (que está muito mais claro) ]
13/03 -- Notas de aula atualizadas (v.19) [ Cap. sobre hashing corrigido;
                                            Rascunho de Cap. sobre MAC;
                                            Rascunho de Cap. sobre cripto assimétrica ]
12/03 -- Notas de aula atualizadas (v.18) [ Mais sobre hashing; Apendice B melhorado;
                                            Cap. sobre Criptanálise muito aumentado ]
09/03 -- Exercícios selecionados disponíveis nesta página
04/03 -- Notas de aula atualizadas (v.17) [ Apêndice c/prob do aniversário; mais sobre hashing;
                                            menos-que-rascunho de Capítulo sobre Criptanálise ]
03/03 -- Lista de trabalhos com referências e links disponível
01/03 -- Notas de aula atualizadas (v.16) [ Diversas melhorias ]
27/02 -- Notas de aula atualizadas (v.15) [ Capítulo 5 sofreu muitas alterações ]
25/02 -- Notas de aula atualizadas (v.14) [ Muitas melhorias nos Capítulos 1-4 ]
23/02 -- Data da prova (28/03) no site
23/02 -- Notas de aula atualizadas (v.13) [ Mudanças na apresentação de cifras de bloco ]
22/02 -- Notas de aula atualizadas (v.12) [ Algumas mudanças em cifras de bloco ]
22/02 -- Notas de aula atualizadas (v.11) [ Mudanças principalmente na parde sobre cifras de bloco ]
21/02 -- Notas de aula atualizadas (v.10) [ Muitas mudanças ]
18/02 -- Notas de aula atualizadas (v.9) [ Pequenas melhorias; mais sobre cifras de fluxo ]
15/02 -- Notas de aula atualizadas (v.8) [ Melhorias importantes no Ap. A ]
15/02 -- Notas de aula atualizadas (v.7) [ Melhorias no Cap. 4 e no Ap. A ]
15/02 -- Notas de aula atualizadas (v.6) [ Demonstrações no Cap. 3; melhorias no Ap. A ]
14/02 -- Notas de aula atualizadas (v.5) [ Melhorias pontuais porém importantes ]
14/02 -- Notas de aula atualizadas (v.4) [ Muitas melhorias; mais texto ]
11/02 -- Notas de aula atualizadas (v.3) [ apêndice sobre Complexidade melhorado ]
09/02 -- Notas de aula atualizadas (v.2) [ apêndices incluídos - teoria dos números e complexidade ]
08/02 -- Notas de aula disponíveis (v.1)

Ementa

Criptografia clássica. Tópicos em Teoria dos Números aplicada à Criptografia. Criptografia de bloco simética: DES, Twofish, IDEA, AES. Criptografia de bloco assimétrica ou de chave pública: RSA e ElGamal. Modos de operação da Criptografia de bloco. Autenticação de mensagens e assinaturas digitais.

Avaliação

O conceito final da disciplina poderá ser:

• F - Reprovado. O aluno deve cursar novamente a disciplina.
• C - Desempenho mínimo satisfatório, demonstrando capacidade de uso adequado dos conceitos da disciplina, habilidade para enfrentar problemas relativamente simples e prosseguir em estudos avançados.
• B - Bom desempenho, demonstrando boa capacidade de uso dos conceitos da disciplina.
• A - Desempenho excepcional, demonstrando excelente compreensão da disciplina e do uso da matéria.

A avaliação ser composta de:

• Uma prova;
• Um trabalho sobre algum tópico de Criptografia. No momento adequado apresentarei uma lista de tópicos.
  O trabalho será apresentado três vezes: nas duas primeiras ainda incompleto, para que seja possível direcionar melhor os esforços.

A avaliação final de cada aluno não será o resultado de alguma "conta" feita a partir dos valores das avaliações. O resultado de cada avaliação reflete o desempenho do aluno em todo o curso até aquele instante, e não é apenas uma "nota isolada". Isso significa que cada avaliação leva em conta também o resultado das avaliações anteriores. De maneira simples, cada avaliação mostra qual seria o conceito final do aluno se o curso terminasse naquele instante.

Exercícios

Selecionei alguns exercícios; mais tarde incluo mais.

Trabalho

A lista de livros e artigos a seguir é apenas um subsídio e forte recomendação -- servem de ponto de partida. Vocês podem usar outras referências, claro! Pretendo incluir mais referências nos próximos dias.

1. O algoritmo LLL e uma aplicação em Criptografia
   • Hoffstein; Pipher; Silverman An Introduction to Mathematical Cryptography (Seções 6.12.2, 6.12.3)
   • Trappe; Washington Introduction to Cryptography with coding theory (cap. 17)
   • Nguyen; Valée The LLL algorithm: survey and applications. Springer
2. Criptografia multivariada
   • Daniel J. Bernstein; Erik Dahmen; Johannes Buchmann. "Post-Quantum Cryptography"
3. Esteganografia
   
   • Stefan Katzenbeisser, Information Hiding Techniques for Steganography and Digital Watermarking (só a parte de fundamentos e o survey)
   • Petitcolas; Anderson; Kuhn. Information Hiding: A survey. Proceedings of the IEEE 87 (7): 1062–78. doi:10.1109/5.771065
4. Encriptação com negação plausível
   • Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky. "Deniable Encryption". Lecture Notes in Computer Science 1294: 90–104.
   • Markus Duermuth and David Mandell Freeman Deniable Encryption with Negligible Detection Probability: An Interactive Construction
5. Reticulados em Criptografia (pode escolher um sistema só, se quiser -- GGH, NTRU, Ajtai-Dwork etc)
   • Hoffstein; Pipher; Silverman An Introduction to Mathematical Cryptography (cap. 6)
   • Daniel J. Bernstein; Erik Dahmen; Johannes Buchmann. "Post-Quantum Cryptography"
6. Códigos em Criptografia
   • Elementary Number Theory, Cryptography, and Codes (cap. 8)
   • Daniel J. Bernstein; Erik Dahmen; Johannes Buchmann. "Post-Quantum Cryptography"
7. Computação segura com vários atores
   • Smart, N. Cryptography: an introduction. Mcgraw-Hill, 2004 (cap 26)
   • Yao Protocols for Secure Computations
   • References to Secure Multiparty Computation Literature
8. Dinheiro digital (digital cash)
   • Notas de aula de Goldwasser e Bellare (Seção 12.5)
   • Trappe; Washington Introduction to Cryptography with coding theory (cap. 17)
   • D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24:84­88, February 1981.
9. Ataques teóricos a criptossistemas. Um exemplo:
   • Alex Biryukov; Orr Dunkelman; Nathan Keller; Dmitry Khovratovich; Adi Shamir Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds
10. Ataques práticos (WEP, Word etc) a criptossistemas, com explicação teórica
    • Há diversos desritos no livro de Stamp e Low, "Applied Cryptanalysis"
    • MD5 (um pouco trabalhoso)
      • Xie; Feng How To Find Weak Input Differences For MD5 Collision Attacks
      • M.J. Stevens (June 2007). On Collisions for MD5. MSc Thesis, Eindhoven University of Technology, 2007
    • WEP -- há diferentes ataques, diferentes textos a ler (inclusive em diferentes níveis de dificuldade):
      • Uma página sobre o RC4
      • Andrea Bittau; Mark Handley; Joshua Lackey The Final Nail in WEP's Coffin
      • Mantin; Shamir A Practical Attack on Broadcast RC4
      • Scott R. Fluhrer; Itsik Mantin; Adi Shamir Weaknesses in the Key Scheduling Algorithm of RC4
      • Borisov; Goldberg; Wagner Intercepting Mobile Communications: The Insecurity of 802.11
11. Descrição detalhada do AES
    
    • Joan Daemen, Vincent Rijmen. The Design of Rijndael. Springer.

Conceitos

Se seu RA não está na lista (ou parece estar errado), pode ser que estivesse ilegível (ou semi-legível) na prova. Me mande uma mensagem com seu nome e RA.

RA          após P1  após T
---------------------------
11181209          C       C
11077707          B       B
11034109          B       B
11013610          A       A
11020407          B       A
11080209          B       C
11075208          B       B
11062908          B       B
11053909          F       C
11069007          F       C
11082109          A       B
11014308          A       A
11020009          B       B
11148108          B       C
11085008          B       B
11041208          C       B
11064107          F       C
11030509          F       C

Programa aproximado

Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.

Visão geral dos problemas abordados pela Criptografia
Sigilo perfeito e o teorema de Shannon
Funções de mão única
Geração de números pseudo-aleatóreos
Cifras de fluxo
Cifras de bloco
Resumos criptográficos (hashing)
MAC (autenticação de mensagens)

Cifras assimétricas 
Curvas Elípticas
Assinaturas digitais
Distribuição de chaves
Autenticação de entidades (identificação)

Criptografia Pós-quântica
Reticulados e códigos
Grupos não comutativos

Comprometimento
Transferência opaca (ou "inconsciente")
Provas de Conhecimento Zero
Assinatura simultânea de contrato
Compartilhamento de segredos
Eleições eletrônicas

Criptografia Quântica

Data da prova: 28 30 de Março. Data da entrega do trabalho: 20 de Abril.

Bibliografia

Principal

Não há um único livro que contenha o material que abordaremos, mas os dois livros abaixo com as notas de aula deverão ser suficientes.

• Notas de aula: versão 33 (agradeço correções!)
• Mao, W. Modern Cryptography: theory and practice Prentice Hall, 2004.
• Stinson, D. Cryptography: theory and practice Chapman&Hall, 2006.
• Smart, N. Cryptography: an introduction. Mcgraw-Hill, 2004 (mas também disponível livremente -- siga o link no título do livro

Secundária

• Dasgupta, Papadimitriou, Vazirani. Algorithms
• Hopcroft, John E; Ullman, Jeffrey D; Motwani, Rajeev. Introdução à teoria de autômatos, linguagens e computação. Campus, 2003.
• Talbot, J; Welsh, D. Complexity and Cryptography: an introduction Cambridge University Press, 2006 (não tem na biblioteca)
• Cormen, Leiserson, Rivest, Stein. Algoritmos - Teoria e Prática Campus, 2002
• Notas de aula de Jonathan Katz
• Notas de aula de Mihir Bellare e Philip Rogaway
• Notas de aula de Goldwasser e Bellare
• Menezes, OOrschot, Vanstone. Handbook of Applied Cryptography CRC Press, 1996.
• Coutinho, S. C. Números Inteiros e Criptografia RSA, IMPA, 2005
• Joan Daemen, Vincent Rijmen. The Design of Rijndael. Springer.
• Dahab, López. Técnicas Criptográficas Modernas

Embora não exista em nossa biblioteca, quem tiver interesse em continuar estudando Criptografia poderá consultar estes livros:

• Ireland A Classical Introduction to Modern Number Theory -- Teoria dos Números, com mais profundidade
• Catalano. Contemporary Cryptology -- sobre Cripto Moderna
• Delfs. Introduction to Cryptography: Principles and Applications -- também sobre Cripto Moderna
• Hoffstein, Pipher, Silverman. A Introduction to Mathematical Cryptography
• Baldoni et all Elementary Number Theory, Cryptography and Codes
• Katz/Lindell Introduction to Modern Cryptography -- excelente introdução à Cripto Moderna (um pouco pesado)
• Goldreich Foundations of Cryptography -- 2 volumes; sobre os fundamentos (muito abstrato, denso, pesado -- mas excelente)