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:
- 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.
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).
-
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.
Exemplo: Primalidade e Factorização
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
.
- 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
- Qual o pior caso?
- 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,
- 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
- 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
- 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
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:
Trabalho Prático 1
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.
- Implemente as primitivas de cifragem ElGamal? sobre F2n. 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
--
PaulaCristinaValenca? - 15 Apr 2007