- Aulas às terças e quintas, sala IC-3, sala 351, 14-16h.
- Local e horário de atendimento
do professor: IC-1, sala 28, em horário a ser definido.
O programa desta
disciplina cobre os algoritmos necessários à implementação da maioria
dos sistemas criptográficos modernos. Tais algoritmos estão presentes
nas funções de encriptação/decriptação, acordos de chaves, resumos
(hash), geração de sequências pseudo-aleatórias de bits, entre outras.
Duas vertentes de algoritmos serão explorados: (i) os não-resistentes a
ataques (por algoritmos) quânticos, baseados predominantemente na
Teoria dos Números e (ii) os resistentes a ataques quânticos, baseados
na Teoria dos Reticulados, Teoria dos Códigos, e técnicas ad-hoc como é
o caso dos algoritmos simétricos e de resumo. Algoritmos básicos,
intermediários e avançados serão estudados, de forma que muito poucas
noções de Criptografia serão necessárias, sendo mais desejável que o
aluno tenha bons conhecimentos de Álgebra Linear e Análise de
Algoritmos e Estatística e Probabilidade. É necessário que o
aluno tenha também alguma prática de programação em Linguagem C, que
será usada na confecção dos trabalhos práticos que serão parte da
avaliação.
- Breve introdução à Criptografia moderna.
- Algoritmos e criptossistemas baseados em Teoria dos Números
- Algoritmos básicos: aritmética básica de precisão arbitrária,
aritmética modular, máximo divisor comum, resolução de congruências.
- Algoritmos intermediários: testes de primalidade, fatoração,
logaritmo discreto, aritmética de corpos finitos, aritmética em curvas
elípticas.
- Algoritmos avançados: emparelhamentos bilineares, teste de primalidade.
- Algoritmos baseados em Teoria dos Reticulados
- Amostragem de vetores
- Algoritmos para redução de base - LLL
- Algoritmos para operações da Álgebra Linear
- Algoritmos baseados em Teoria dos Códigos
- Algoritmos baseados em técnicas adhoc para encriptação simétrica
- Algoritmos baseados em técnicas adhoc para resumo (hash) criptográfico
- (23/8) Breve introdução ao curso.
- (25 e 30/8) Introdução à Criptografia.
- (1, 6, 8, 13/9] Aritmética modular, congruências, geração de primos e o criptossistema RSA.
- [15/9] Fatoração de inteiros e o criptossistema de Rabin.
- [20/9] Não houve aula.
- [22/9] Logaritmos discretos e o criptossistema de ElGamal-I. (versão mais atual de 23/9, 16:30h)
- [27/9] Logaritmos discretos - algoritmos para cálculo do DL (parte 1).
- [29/9]
- [4/10] Corpos finitos e curvas elípticas
- [6/10] Curvas elípticas
- [11/10 - 17/11]
- Emparelhamentos bilineares
- Digital Signatures
- Criptografia pós-quântica,
- Utilizamos projeções de páginas do livro "Intro to Math
Crypto" para várias aulas. Slides sobre parte do capítulo de aplicações
de reticulados à criptografia podem ser encontrados no site de um dos
autores do livro, Joseph Silverman, aqui.
- Temos promovido escolas de criptografia nos últimos anos e
com isso
colecionamos um conjunto de slides e vídeos, de material básico e
avançado em criptografia pós-quântica, a maioria dos quais podem
ser encontrados aqui:
- [22/11]
- [24/11]
- [29/11]
- [1/12]
Incluiremos aqui materiais adicionais como transparências, artigos, trechos
de livros, etc. Os enunciados dos trabalhos também serão colocados aqui.
Algumas referências importantes para o material discutido nesta disciplina são:
- An Introduction to Mathematical Cryptography. Series: Undergraduate Texts in Mathematics. J. Hoffstein, J. Pipher, J.H. Silverman. Springer.
- Introduction to Cryptography with Coding Theory. W. Trappe, L. Washington. Pearson.
- Understanding Cryptography. C. Paar, J. Pelzl, Springer.
- Introduction to Cryptography. J.A. Buchmann, Springer.
- Handbook of Applied Cryptography. A. Menezes, P. v. Oorschot, S. Vanstone. Disponível em http://www.cacr.math.uwaterloo.ca/hac/
- A Computational Introduction to Number Theory and Algebra. V. Shoup. Disponível em http://shoup.net/ntb/
- Cryptography: Theory and Practice. D. Stinson. Ed. Chapman & Hall/CRC, 3a. edição.
- Guide to Elliptic Curve Cryptography. D. Hankerson, A. Menezes, S. Vanstone. Springer.
- Post-Quantum Cryptography.
D.J. Bernstein; J.A. Buchmann; E. Dahmen (Eds.).
Critério de avaliação (revisto em 27/9/2016) (revisto em 25/11/2016) (menu principal)
A avaliação será baseada em uma prova e
dois
trabalhos, sendo o primeiro de implementação e o segundo de escrita e
implementação. Detalhes e datas de entrega dos trabalhos serão
divulgados no decorrer do curso.
O critério de avaliação será o seguinte:
- O peso da nota P1 da primeira prova será 3. O peso da
nota T1 do primeiro trabalho será 3. O peso da nota T2 do segundo
trabalho será 4.
- A média MA das três atividades será MA= (3*P1 + 3*T1 + 4*T2)/10.
- Se MA >= 5.0, então o aluno estará aprovado; caso contrário, estará reprovado. Em ambos os casos, a média final será MA.
Todas as notas de provas e trabalhos estarão no intervalo [0, 10]. Todas as notas serão arredondadas para uma casa decimal.
Os intervalos de notas que serão usados na conversão para conceitos, no caso de alunos de
pós-graduação, são:
- A: [8.5, 10.0]; B: [7, 8.4]; C: [5.0, 6.9]; D: [0, 4.9].
Notas finais podem ser encontradas
aqui.
- Prova 1: 18 de outubro
- Trabalho 1: Data de entrega: 24 de outubro.
- Trabalho 2: Data de entrega: 16 de dezembro.