Sessões laboratoriais de EC

5ª feira, 16:00-18:00, DI 1.04

01/03/2007 - Introdução ao PARI/GP

Esta sessão é acompanhada de um documento PDF que apresenta uma versão mais detalhada da introdução que se segue.

Instalação

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:

1. Download da última versão pari-X.X.X.tar.gz
2. tar zxvf pari-X.X.X.tar.gz; cd pari-X.X.X
3. ./Configure --prefix=$HOME/pari ( default: /usr/local/ )
4. make all; make install; make test-all
5. 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.

Tipos do PARI e comandos básicos

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).

1. t_INT - Inteiros
2. t_REAL - Reais
3. t_FRAC - Racionais
4. t_INTMOD - Inteiros Modulares
5. t_COMPLEX - Complexos
6. t_POL - Polinómios
7. t_MAT - Matrizes
8. t_VEC/t_COL - Vectores
9. t_LIST - Listas
10. t_STR - Strings
11. t_QUAD - Corpos Quadráticos
12. t_PADIC - P-ádicos
13. t_POLMOD - Polinómios mod P(X)
14. t_SER - Séries de potências
15. 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.

Exemplo: Primalidade e Factorização

• 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));
          i = 1;
          while(i < 100 && n%u, u = nextprime(u); i = i + 1);
          u
          }
          gp > u == q
          gp > q - p
          gp > #
      

Do Algoritmo de Euclides à Aritmética Modular

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,
      return(-1));
  fact = 1;
  while( n > 0,
         fact = fact*n;
         n = n - 1;
  );
  fact
}

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

08/03/2007 - Computações

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.

1. Implemente o algoritmo de potenciação descrito no PDF auxiliar
2. Conte o número de multiplicações no pior caso e em média.
3. 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.

1. Implemente o teste de Miller-Rabin, descrito no PDF auxiliar (consulte a função random)
2. Explique a presença de c = 20 no algoritmo.
3. 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

1. Qual o pior caso?
2. 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.

15/03/2007 - Continuação da aula anterior

Primeiro, um pequeno aquecimento,

1. 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).
2. Calcule seguidamente o inverso de m mod n e verifique que é v mod n
3. Tente calcular o inverso de 5 mod n usando os dois métodos e explique o resultado

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.

22/03/2007 - "Birthday attack", colisões e funções de Hash

1. 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%.
2. Calcule quantas pessoas são necessárias para que a probabilidade que duas façam anos no mesmo dia seja superior a 50%.
3. 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 2ⁿ tentativas.
4. Construa uma função de hash da seguinte forma:
   1. Escolha p e q primos aleatórios de 512 bits e defina uma funcao f(x) = x2 mod pq
   2. Defina uma função que dada uma mensagem a parta em blocos de k bits.
   3. 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.
   4. Defina a função de hash como sendo uma função que retire 160 bits aleatórios dos 1024 bits do último Sk

29/03/2007 - Funções de Hash - continuação da aula anterior

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.

12/04/2007 - RSA

Implementação das funções primitivas de geração de chaves, cifragem e decifragem do RSA. Verificação de correcção.

Referências:

• 1363-2000 IEEE Standard Specifications for Public-Key Cryptography
• 1363a-2004 IEEE Standard Specifications for Public-Key Cryptography- Amendment 1: Additional Techniques
• PKCS #1: RSA Cryptography Standard (RSA labs)

Trabalho Prático 1

• Cifra RSA

03/05/2007 - Corpos Finitos e ElGamal?

• Implemente as operações de adiçao e multiplicação sobre corpos finitos F_2ⁿ, na representação Z₂[X]/f(X)Z₂[X], onde f(X) é um polinómio primitivo de grau n com coeficientes em Z₂.
• Implemente as primitivas de cifragem ElGamal? sobre F_2ⁿ. Use as seguintes funções de conversão:

pol2int(p) = { local(x); x = 2; eval(lift(lift(p))) }


// c e' o polinomio caracteristico
int2pol(u, c) =
{
  local(bin_exp, i, n, p);

  bin_exp = binary(u);
  n = length(bin_exp);
  p = 0;
  for(i = 1, i <= n, p += bin_exp[i]*x^(n-i));
  return( Mod(p, c))
}

Trabalho Prático 2

• Funções sobre GF(2ⁿ) e GF(2)ⁿ

-- PaulaCristinaValenca? - 15 Apr 2007