Education » Criptografia » ElementosCriptografia0607 » ElementosCriptografiaTP0607
Sessões laboratoriais de EC
5ª feira, 16:00-18:00, DI 1.04
01/03/2007 - Introdução ao PARI/GP
Tipos do PARI e comandos básicos
Exemplo: Primalidade e Factorização
Do Algoritmo de Euclides à Aritmética Modular
08/03/2007 - Computações
15/03/2007 - Continuação da aula anterior
22/03/2007 - "Birthday attack", colisões e funções de Hash
29/03/2007 - Funções de Hash - continuação da aula anterior
12/04/2007 - RSA
03/05/2007 - Corpos Finitos e ElGamal
Esta sessão é acompanhada de um documento PDF que apresenta uma versão mais detalhada da introdução que se segue.
O PARI/GP é um sistema de algebra computacional particularmente indicado para computações na área de Teoria de Números e, consequentemente, para a resolução de pequenos problemas na área de Criptografia. Além das bibliotecas, contém um interpretador, gp, e uma linguagem de script, gp-script.
A página oficial é http://pari.math.u-bordeaux.fr/.
Para instalar o programa da distribuição de source, faça:
Download da última versão pari-X.X.X.tar.gz
tar zxvf pari-X.X.X.tar.gz; cd pari-X.X.X
./Configure --prefix=$HOME/pari ( default: /usr/local/ )
make all; make install; make test-all
export PATH=$HOME/pari/bin:$PATH
Se usa o Emacs, a distribuição inclui modos de suporte para o PARI/GP. Consulte a documentação e o ficheiro pariemacs.txt para mais informação.
A distribuição inclui também documentação, em particular, um manual de utilizador, um tutorial e uma Reference Card. Esta última será de grande utilidade no futuro. Robert B. Ash escreveu também um tutorial do Pari/GP.
Para correr, chame num terminal o comando gp. Para terminar, escreva quit ou \q. Para ajuda numa função ou palavra ( e.g, foo ), ?foo ou ??foo. O último output pode ser chamado através de %, %n para a linha n. O carácter # acciona ou desacciona o temporizador. Finalmente, \r fich lê um ficheiro fich (mais tarde importaremos pequenos programas GP desta forma).
Há quinze tipos fundamentais no PARI, enumerados a seguir. Concentraremo-nos nos oito primeiros (no entanto, encontrará por certo referências aos outros tipos na literatura na área de Criptografia).
t_INT - Inteiros
t_REAL - Reais
t_FRAC - Racionais
t_INTMOD - Inteiros Modulares
t_COMPLEX - Complexos
t_POL - Polinómios
t_MAT - Matrizes
t_VEC/t_COL - Vectores
t_LIST - Listas
t_STR - Strings
t_QUAD - Corpos Quadráticos
t_PADIC - P-ádicos
t_POLMOD - Polinómios mod P(X)
t_SER - Séries de potências
t_RFRAC - Funções Racionais
Siga o documento PDF que acompanha esta aula. As notas seguintes são apenas um resumo dos passos a seguir.
Defina p como o menor primo maior que 2100, q como o primo seguinte e n = p*q.
Accione o timer e corra trial division (isto é, divida por todos os números) até 20000
Como explica o resultado? E por que razão continuar a tentar dividir por todos os números até à raiz quadrada de n não é uma boa estratégia?
Use o teste do Pequeno Teorema de Fermat para a = 2 e confirme o resultado com o comando isprime (registe o tempo que este último levou)
Factorize n usando o comando factor e compare o tempo que este levou com o tempo do isprime
Como curiosidade, corra a seguinte sequência de instruções,
gp > { u = nextprime(sqrtint(n));
while(i < 100 && n%u, u = nextprime(u); i = i + 1);
gp > u == q
gp > q - p
No que se segue, crie e edite um ficheiro com extensão .gp e importe no GP através do comando \r fich.
A função factorial pode ser definida da seguinte forma,
\\ exemplo simples da definicao de uma funcao em GP
myFact(n) =
{ local(fact);
if( type(n) != "t_INT" || n < 0,
Com base neste exemplo,
escreva uma função que calcule o maior divisor comum ( gcd ) de dois inteiros não negativos através do algoritmo de Euclides e estime a complexidade do algoritmo;
extenda a sua função de forma a calcular u e v, tal que un + vm = gcd(n,m) segundo a versão extendida do algoritmo de Euclides;
compare o resultado da sua função com o da função bezout, para m = 2101+1 e n = 2237+25+1;
verifique que o inverso de m mod n é v mod n, ainda no exemplo acima;
tente calcular o inverso de 5 mod n usando os dois métodos e explique o resultado
Pretende-se nesta sessão sensibilizar os alunos para a complexidade de um algoritmo, através da discussão de certos exemplos de algoritmos simples mas fundamentais. Consulte o PDF auxiliar para a descrição dos algoritmos.
Seja (G, *) um grupo multiplicativo. Pretende-se calcular de uma forma eficiente gn para um elemento g de G e um inteiro n.
Implemente o algoritmo de potenciação descrito no PDF auxiliar
Conte o número de multiplicações no pior caso e em média.
Diga a complexidade em tempo do algoritmo.
Na aula passada foi apresentado o teste de Fermat para teste da não primalidade de um número. O teste de Miller-Rabin não só elimina os casos de pseudo-primos do estilo dos números de Carmichael como requere menos tentativas feitas. É um algoritmo não determinístico que poderia ser tornado deterministico assumindo a hipótese generalizada de Riemann.
Implemente o teste de Miller-Rabin, descrito no PDF auxiliar (consulte a função random)
Explique a presença de c = 20 no algoritmo.
Dê uma estimativa para o tempo médio do algoritmo e discuta a probabilidade de o teste falhar-
Utilize o teste de Miller-Rabin para gerar um número (provavelmente) primo aleatório com n bits
Sabendo que a variável aleatória X que toma o valor do número de tentativas necessárias para ter um primeiro sucesso segue a distribuição discreta geométrica e que o número de primos até N tende para N/(log N) à medida que N tende para infinito, dê uma estimativa para a complexidade média deste método.
Primeiro, um pequeno aquecimento,
Use a função bezout, para calcular o GCD (extendido) de m = 2101+1 e n = 2237+25+1; esta função calcula u e v, tal que un + vm = gcd(n,m).
Calcule seguidamente o inverso de m mod n e verifique que é v mod n
Voltando para o tema da aula anterior, faça a segunda e terceira parte da aula: o teste de Miller-Rabin e uma função que gere um primo aleatório com n bits. Responda também às questões postas.
Calcule quantas pessoas são necessárias numa sala para que a probabilidade de uma delas partilhar o seu aniversário seja superior a 50%.
Calcule quantas pessoas são necessárias para que a probabilidade que duas façam anos no mesmo dia seja superior a 50%.
Seja H(x) uma função de hash que dada uma mensagem de tamanho arbitrário, devolve uma string de tamanho fixo 160 bits. Supondo que qualquer string de 160 bits tem igual probabilidade de ocorrência e usando a aproximação e^(-a/n) = (1 - a/n), calcule o número de tentativas necessárias num ataque à força bruta para encontrar uma colisão com probabilidade superior a 0.5. Como referência um ataque de pré-imagem à força bruta numa função de hash n-bit deverá requerer aproximadamente 2n tentativas.
Construa uma função de hash da seguinte forma:
Escolha p e q primos aleatórios de 512 bits e defina uma funcao f(x) = x2 mod pq
Defina uma função que dada uma mensagem a parta em blocos de k bits.
Defina uma função que cicle sobre os blocos Sk+1 = (Sk + bk)2 mod pq, sendo S0 um valor aleatório (a seed) e bk o bloco k da mensagem.
Defina a função de hash como sendo uma função que retire 160 bits aleatórios dos 1024 bits do último Sk
Dado estar a decorrer a ETAPS, a aula desta semana foi mais curta e concentrou-se em terminar o estudo de funções de Hash da aula anterior.
Implementação das funções primitivas de geração de chaves, cifragem e decifragem do RSA. Verificação de correcção.
PKCS #1: RSA Cryptography Standard (RSA labs)
03/05/2007 - Corpos Finitos e ElGamal?
Implemente as operações de adiçao e multiplicação sobre corpos finitos F2n, na representação Z2[X]/f(X)Z2[X], onde f(X) é um polinómio primitivo de grau n com coeficientes em Z2.