Introdução à Criptografia

Terceiro quadrimestre de 2011
Horário: 2^a (21:00-23:00) e 4^a (19:00-21:00)
Sala de aula: 2^a: S503. 5^a: L505. Ambas no bloco B.
Professor: Jerônimo C. Pellegrini
Sala do professor: S 805 (bloco B)
Email do professor: jeronimo.pellegrini ufabc edu br

Entrega do trabalho adiada: 15/12

Podem fazer melhorias e mandar novamente!

Novidades:

15/12 -- Conceitos finais (após entrega do trabalho) disponíveis
13/12 -- Notas de aula v.71 disponíveis (diversas melhorias)
11/12 -- Notas de aula v.70 disponíveis (apêndice:complexidade)
08/12 -- Carlos Trufen e Fabrízio: devo-lhes os dois brindes!
06/12 -- Notas de aula v.69 disponíveis (geradores pseudoaleatóreos, distribuições indistinguíveis)
06/12 -- Notas de aula v.68 disponíveis (encriptação negável)
30/11 -- Notas de aula v.67 disponíveis (cifras históricas; encriptação negável)
28/11 -- Conceitos após P1 disponíveis
28/11 -- Notas de aula v.66 disponíveis (criptografia visual; cifras históricas)
24/11 -- Notas de aula v.65 disponíveis (criptografia visual)
22/11 -- Notas de aula v.64 disponíveis (complexidade)
22/11 -- Notas de aula v.63 disponíveis (conhecimento zero; complexidade)
19/11 -- Notas de aula v.62 disponíveis (conhecimento zero; complexidade; outras pequenas melhorias)
16/11 -- Notas de aula v.60 disponíveis (protocolos)
14/11 -- Notas de aula v.59 disponíveis (hashing; assinaturas)
09/11 -- Notas de aula v.58 disponíveis (pequenas melhorias)
07/11 -- Notas de aula v.57 disponíveis (expansão do cap. sobre assinaturas; correção de erros)
05/11 -- Capítulos [1-6] e agora também Apêndice B disponíveis para revisão
05/11 -- Notas de aula v.56 disponíveis (melhorias no ap. sobre álgebra e teoria de números)
04/11 -- Capítulos [1,2,6] e agora também 3, 4, 5 disponíveis para revisão
04/11 -- Notas de aula v.55 disponíveis (descrição algébrica do AES; diversas correções)
31/10 -- Notas de aula v.54 disponíveis (pequenas melhorias)
29/10 -- Notas de aula v.53 disponíveis (pequenas melhorias)
27/10 -- Notas de aula v.52 disponíveis (diversas melhorias)
19/10 -- Capítulos [1,2] e agora também 6 disponíveis para revisão
19/10 -- Notas de aula v.51 disponíveis (ap. sobre Álgebra bem melhor; pequenas melhorias em criptanálise)
18/10 -- Notas de aula v.50 disponíveis (melhorias: apêndice sobre álgebra)
15/10 -- Notas de aula v.49 disponíveis (melhorias: cifras de fluxo; apêndice sobre álgebra)
14/10 -- Notas de aula v.48 disponíveis (melhorias: cifras de bloco; cifras de fluxo)
13/10 -- Trabalho (implem. Rabin) já escolhido; mais duas opções (Pailler, Cramer-Shoup) disponíveis
12/10 -- Notas de aula v.47 disponíveis (melhorias no cap. sobre cifras de bloco; mais um apendice)
11/10 -- Regras para sorteio de caneca/pendrive disponíveis
10/10 -- Tópicos para trabalho disponíveis (ainda podem surgir outros)
09/10 -- Notas de aula v.46 disponíveis (pequenas mudanças, capítulo sobre Pós-Quantica inserido)
07/10 -- Notas de aula v.45 disponíveis (descrição simplificada do AES agora legível)
05/10 -- Data da prova no site
05/10 -- Notas de aula v.44 disponíveis
04/10 -- Notas de aula v.43 disponíveis
22/09 -- Capítulos 1 e 2 disponíveis para revisão (valendo chocolate)
22/09 -- Notas de aula v.41 disponíveis

Notas de aula

Quem encontrar erros (gramaticais, de conteúdo ou de redação em geral) nos capítulos 1 e 2 ganha um chocolate (pelo conjunto de erros, não por erro).

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 P

Um trabalho T

Data da prova: 09/11

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.

Ganhe uma caneca ou pendrive!

Quem encontrar mais erros nas notas de aula ganhará:

1^o lugar: uma caneca com sigilo perfeito OU um pendrive de 8Gb, a escolha do ganhador
2^o lugar: o que o primeiro não quis.

Regras:

Somente valem erros encontrados em Capítulos que deixei prontos para revisão. Se você encontrar um erro na versão n do texto e eu receber seu email mais de 24h após ter postado uma versão n+1 que corrige o erro, seu erro não conta (use sempre a última versão)
Só participa quem encontrar um erro por semana, em média.
Um erro só conta da primeira vez que é reportado. Se vier por email, vale o email que chegar primeiro.

Erros já encontrados:

Trabalho

Conceitos

Lembrem-se de que o conceito final leva este em consideração, mas o conceito da prova não "puxa para cima ou para baixo" o outro.

		após P1   	final
11007006	B       	B
11103908	B		B
11008808	F		C
11037708	B		B
11119111	C		B
11092608	F		B
11043006	F		C

Programa aproximado

Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer. O segundo item (complexidade de algoritmos) será abordado inicialmente porque seria muito difícil prosseguir sem tais conceitos. Já outras ferramentas e tópicos como Teoria dos Números e Álgebra serão introduzidos à medida em que forem necessários.

PARTE ZERO:
Visão geral dos problemas abordados pela Criptografia
Noções de complexidade de algoritmos

PARTE UM:
Sigilo perfeito e o teorema de Shannon
Funções de mão única
Geradores pseudoaleatóreos e cifras de fluxo
Funções pseudoaleatóreas e cifras de bloco
Noções de Criptanálise
Resumos criptográficos (hashing)
MAC (autenticação de mensagens)
Cifras assimétricas
Assinaturas digitais
Autenticação de entidades (identificação)

PARTE DOIS:
Protocolos com dois participantes
Provas de conhecimento zero
Compartilhamento de segredos
Computação segura com múltiplos prticipantes

PARTE TRES:
Curvas elípticas
Criptografia pós-quântica
Reticulados
Códigos corretores de erros
Encriptação negável

Bibliografia

Principal

Usaremos as notas de aula no primeiro link da lista a seguir. Outros livros poderão ser úteis.

Notas de aula (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
Talbot, J; Welsh, D. Complexity and Cryptography: an introduction Cambridge University Press, 2006.
Katz/Lindell Introduction to Modern Cryptography -- excelente introdução à Cripto Moderna (um pouco pesado)

Secundária

Baldoni et all Elementary Number Theory, Cryptography and Codes
R. Pass and A. Shelat: A Course in Cryptography
Hoffstein, Pipher, Silverman. A Introduction to Mathematical Cryptography
Victor Shoup. A Computational Introduction to Number Theory and Algebra (livre!)
Dasgupta, Papadimitriou, Vazirani. Algorithms
Hopcroft, John E; Ullman, Jeffrey D; Motwani, Rajeev. Introdução à teoria de autômatos, linguagens e computação. Campus, 2003.
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
Rothe, J. Complexity Theory and Cryptology Springer, 2005.

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

Vaudenay, S. A Classical Introduction to Cryptography -- uma abordagem um pouco diferente dos outros; dá mais atenção a criptografia simétrica, por exemplo
Ireland e Rosen. 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
Goldreich Foundations of Cryptography -- 2 volumes; sobre os fundamentos (muito abstrato, denso, pesado -- mas excelente)