Introdução ao SAGEMATH¶
Funções importantes de Teoria dos Números¶
Vamos rever alguns conceitos das semanas passadas.
Máximo Divisor Comum (GCD)¶
Já sabemos que o mdc entre dois números pode ser computado facilmente em Sage:
gcd(14, 7)
Exponenciação modular¶
Também já vimos que, quando estamos tratando do grupo de inteiros $\bmod n$, devemos usar sempre a exponenciação modular, pois fazer a exponenciação normal e tirar o módulo pode ser muito caro.
power_mod(13, 123784, 273892)
13**123784 % 273892
import timeit
MAX_INT = 10000
NSAMPLES = 1000
def compare_modular_exponentiation_efficiency(nsamples=NSAMPLES, max_int=MAX_INT):
data = {
'n': [],
'p': [],
'time_power_mod': [],
'time_regular_exponentiation': []
}
for _ in range(nsamples):
n = randint(1, max_int)
p = random_prime(max_int)
exponent = randint(1, max_int)
def compute_with_power_mod():
v = power_mod(n, exponent, p)
time_power_mod = timeit.timeit(compute_with_power_mod, number=10)
def compute_with_regular_exponentiation():
v = n**exponent % p
time_regular_exponentiation = timeit.timeit(compute_with_regular_exponentiation, number=10)
data['n'].append(n)
data['p'].append(p)
data['time_power_mod'].append(time_power_mod)
data['time_regular_exponentiation'].append(time_regular_exponentiation)
return data
data = compare_modular_exponentiation_efficiency()
%matplotlib notebook
import matplotlib.pyplot as plt
import pandas as pd
df = pd.DataFrame.from_dict(data)
ax = plt.gca()
df.plot.scatter(x='n', y='time_power_mod', label='Usando power_mod', c='red', ax=ax, s=0.4)
df.plot.scatter(x='n', y='time_regular_exponentiation', c='blue', label='Sem usar power_mod', ax=ax, s=0.4)
plt.ylabel('Tempo de execução')
plt.legend()
Inverso Módulo¶
Já vimos que é possível calcular a inversa $\bmod n$ usando o algoritmo de Euclides estendido. Mas como essa é uma função muito importante, já vem implementada diretamente em Sage.
inverse_mod(4, 13)
4*10 % 13
Trabalhando com Anel de Inteiros em Sage¶
Nesta seção veremos como o Sage dá uma interface um pouco mais amigável e natural para trabalhar com as funções acima.
Definindo um anel de inteiros $\bmod n$¶
Para trabalhar diretamente no anel de inteiros $\bmod n$ fazemos assim:
A = Integers(13) # n = 13
Alguns métodos do grupo:
A.addition_table('digits')
A.multiplication_table('digits')
a = A.random_element()
b = A.random_element()
a, b
a*b
A(12)*4
A.cardinality()
Podemos até gerar o anel polinomial com coeficientes em R:
R.<t> = A[]
R.random_element(degree=(-1, 100))
R
R.cardinality()
Podemos pegar elementos irredutíveis de R:
m = R.irreducible_element(3)
m
Q.<u> = R.quotient(m)
p1 = Q.random_element()
p2 = Q.random_element()
print('p1=', p1)
print('p2=', p2)
Q.cardinality()
p = p1*p2
print(p)
Podemos fazer a operação de lift para transformar $p_1$ num elemento no anel pai (sem módulo)
p1.lift()*p2.lift()
Compare o que acontece quando elevamos o $p_1$ lifted ao quadrado
p1**2
p1.lift()**2
q1 = p1.lift()
q2 = p2.lift()
(q1*q2)
q = (q1*q2).mod(m)
print(q)
Note que o valor de $q$ é o mesmo de $p$ quando lifted
q == p.lift()
Acho que já viemos longe demais de cripto!
Exponenciação modular vem de tabela¶
Voltando paro o nosso anel $R$
A
Podemos transformar pegar qualquer inteiro e escalá-lo para um elemento de $R$
A(10)
A(-2)
Elementos em $R$ têm o privilégio de já vir com exponenciação modular
A(3)**902323489594240240419283287419823479128347439
Inverso módulo vem de tabela¶
Além disso, o inverso dos elementos em $R$ também é feito levando o módulo em consideração
1/A(5)
inverse_mod(5, 13)
A(5)^-1
A(5)^-1 * A(5)
B = Integers(50)
B(3)^(-1)
IMPORTANTE: Uma operação com elementos em $R$ é automaticamente avaliada em $R$
R(5) * 1000
Funções de Hash¶
Agora saímos um pouco de Sage e vamos falar sobre Cripto.
O que vocês sabem sobre funções de Hash?
Propriedades de funções de Hash Criptográficas¶
- Uma função determinística $h$: mesma entrada implica em mesma saída.
- Computação de $h$ é eficiente
- Dado um valor $y$ é computacionalmente inviável encontrar $x$ tal que $h(x) = y$
- Computacionalmente inviável encontrar duas mensagens com mesmo hash
- Uma pequena alteração na entrada deve produzir alteração catastrófica na saída
É importante internalizar essas propriedades.
São das primitivas mais importantes em criptografia hoje.
Implementação de funções de Hash é uma área bem ativa e importante de criptografia simétrica.
Aplicações básicas de funções de Hash¶
Uma das principais aplicações de funções de hash é na autenticação de mensagens quando as duas partes compartilham uma chave secreta. Note que é bem diferente de assinatura digital (assimétrica).
Seja $k$ uma chave secreta que eu compartilho com o Luís. Para autenticar uma mensagem $m$ basta que eu mande para o Luís o par $(m, s)$, onde $s = h(m\|k)$. Para Luís garantir que eu mesmo escrevi $m$, basta que ele compute o valor de $h(m\|k)$ e verificar se este valor é igual a $s$.
Note que, pela propriedade 3 de funções de hash, um atacante que vê $s$ não consegue descobrir $k$, e nem gerar outra assinatura válida para uma mensagem diferente
Hash em Python¶
Python vem com um módulo com várias funções de hash implementadas.
import hashlib
hashlib.algorithms_available
Vamos usar o hash SHA512. Note que a entrada para as funções de hash são sequências de bytes:
help(hashlib.sha512)
Não é toda string que pode ser lida como uma sequência de bytes:
b'este e um teste'
Precisamos então codificar as strings antes de aplicar o hash.
m = 'este é um teste'.encode('utf-8')
print(m)
Agora podemos aplicar a função de hash.
hash_m = hashlib.sha512(m)
print(hash_m)
Para efetivamente calcular o hash como sequẽncia de bytes, podemos usar o método digest, cuja saída é totalmente ilegível.
hash_m.digest()
Em geral é mais útil chamar o método hexdigest, cuja saída é em hexadecimal.
hash_m.hexdigest()
OBS: Mostrei a saída do digest só para quem não está acostumado com hexadecimal passar a achar hexadecimais até que razoáveis.
Implementação do esquema simples de autenticação¶
def auth(message, key):
m = message.encode('utf-8')
k = key.encode('utf-8')
c = m + k # Operação de concatenação de sequências de bytes
return hashlib.sha512(c).hexdigest()
Veja que mesmo pequenas mudanças na mensagem tem resultado catastrófico. Então esta função garante
- Autenticidade (sei quem gerou a mensagem)
- Integridade (a mensagem não foi modificada)
message = 'Essa é uma mensagem boa'
key = 'H4CK3R'
print(auth(message, key))
key_false = 'H4CK3r'
print(auth(message, key_false))
message_false = 'Essa é uma mensagem Boa'
print(auth(message_false, key))
Apesar de bem simples, há limitações bem severas como:
- A única coisa que se pode garantir é que um dois dois criou a mensagem! Uma pessoa de fora não saberia dizer de quem veio a mensagem.
- Apenas quem sabe $k$ consegue determinar a autenticidade (não funciona para assinar documentos públicos)
Estes problemas são resolvidos assinaturas digitais.
Distância de Hamming¶
Vimos que as saída da função auth são bem diferentes mesmo quando mudamos pouco a mensagem.
Mas quão diferentes elas são?
Uma medida muito usada para determinar a diferença entre duas strings é o número de bits em que essas strings diferem, conhecida como distância de Hamming.
h1 = auth('Mensagem 1', key)
h2 = auth('Mensagem 2', key)
h1, h2
Exemplo. A distância de Hamming entre $(1, 0, 0, 0, 1, 1)$ e $(1, 1, 0, 0, 0, 1)$ é 2.
Precisamos descobrir quanto valem esses valores em binário. Python vem com a função bin, que devolve a representação binária de um inteiro.
bin(152)
Devemos então transformar os hash em inteiros. A função int toma como entrada uma string e uma base, e resolve exatamente o nosso problema.
int(h1, 16)
Agora podemos aplicar a função bin.
bin(int(h1, 16))
def get_binary_representation_512_bits(h):
bin_h = bin(int(h, 16))[2:] # [2:] Tira o 0b da frente
bin_h_512bits = '0' * (512 - len(bin_h)) + bin_h
return bin_h_512bits
get_binary_representation_512_bits(h1)
def hamming_distance_with_strings(h1, h2):
bin_h1 = get_binary_representation_512_bits(h1)
bin_h2 = get_binary_representation_512_bits(h2)
distance = 0
for x1, x2 in zip(bin_h1, bin_h2):
if x1 != x2:
distance += 1
return distance
A distância de Hamming entre $h_1$ e $h_2$ deve ser de aproximadamente $512/2 = 256$ bits, pois estes valores devem ter distribuição uniformemente aleatória para quem não conhece as mensagens.
hamming_distance_with_strings(h1, h2)
Assinatura Digital¶
Uma assinatura digital tem o objetivo de fornecer as 3 garantias
- Autenticidade: o documento foi assinado por certa entidade
- Integridade: o documento assinado não foi alterado
- Irretratabilidade: aquele que assinou o documento não pode negar tê-la assinado no futuro
Por que assinamos Hashs e não as próprias mensagens?¶
- Mensagens podem ter qualquer tamanho, e os esquemas de assinatura trabalham com espaços enormes (porém finitos e prefixados de mensagens)
Poderíamos tentar "tirar o módulo da mensagem" mas isso tem um problema tremendo: é muito previsível. Um atacante poderia facilmente gerar uma mensagem totalmente que tem o mesmo módulo. Usando uma função de hash, em que cada bit de entrada afeta toda a saída, isso é evitado.
- Eficiência, pois podemos trabalhar com números nos esquemas criptográficos.
Calculando o Hash de um arquivo¶
Baseado em https://nitratine.net/blog/post/how-to-hash-files-in-python/
Queremos computar o hash de um arquivo. Poderíamos simplesmente ler todo o arquivo para uma string de bytes e depois aplicar o SHA512 como já fizemos. Porém isso tem o problema de ler o arquivo inteiro para e memória de uma vez. A ideia então é ler bloco por bloco e usar o método update que atualiza o estado de um hash conforme novos dados vão entrando.
def sha512_file(filepath):
BLOCK_SIZE = 65536 # = 64Kb
file_hash = hashlib.sha512()
with open(filepath, 'rb') as f:
fb = f.read(BLOCK_SIZE)
while len(fb) > 0:
file_hash.update(fb)
fb = f.read(BLOCK_SIZE)
return file_hash.hexdigest()
Exemplo do estado do objeto Hash. Quero calcular o Hash da mensagem 'Esta é uma mensagem Grande!'
h(Esta) + h(é) + h(uma) + h(mesagem) + h(Grande) v1 = 3 v1 = 2 v2 = 12 v2 = 3 v3 = 3 v3 = 4
cat exs/file.txt
cat exs/file_alter.txt
sha512_file('exs/file.txt')
sha512_file('exs/file_alter.txt')
hamming_distance_with_strings(sha512_file('exs/file.txt'), sha512_file('exs/file_alter.txt'))
int(sha512_file('exs/file.txt'), 16)