from sage.all import *
import random
def gera_doc():
'''
None -> str
Retorna uma string hexadecimal de 10'000 dígitos
começando com meu NUSP, 14590197.
'''
txt = '14590197'
for _ in range(10**4 - 8):
n = random.randint(0, 15)
match n:
case 10:
txt = txt + 'a'
case 11:
txt = txt + 'b'
case 12:
txt = txt + 'c'
case 13:
txt = txt + 'd'
case 14:
txt = txt + 'e'
case 15:
txt = txt + 'f'
case _:
txt = txt + str(n)
return txt
def euclides_ext(a, b):
'''
int, int -> int, int, int
Recebe dois inteiros a, b e retorna o tuple
(mdc(a,b), u, v), onde u e v são tais que
u*a + v*b = mdc(a,b). Se a e b são primos
entre si, v = b^(-1) mod a.
'''
u_antigo = 1
v_antigo = 0
u = 0
v = 1
while a != 0 and b != 0:
if a > b:
q = a // b
a = a % b
else:
q = b // a
b = b % a
buffer = u
u = u_antigo - q * u
u_antigo = buffer
buffer = v
v = v_antigo - q * v
v_antigo = buffer
if a == 0:
return b, u_antigo, v_antigo
else:
return a, u_antigo, v_antigo
def ECMenVan_enc(x1, x2, k, Q, P, p, a, b):
'''
int, int, int, (int, int), (int, int), int, int -> ell_point, int, int
Criptografa a mensagem (x1,x2) com x1, x2 < 263 usando o criptossistema Menezes-Vanstone em curvas
elípticas sobre a curva elíptica y² = x³ + ax + b mod p com a chave pública (Q, P) e o NONCE k.
'''
# Seja a curva elíptica E: y² = x³ + ax + b
E = EllipticCurve(IntegerModRing(p), [0, 0, 0, a, b])
# Tornar P e Q objetos de ponto da curva do SAGE, caso não sejam
P = E(P)
Q = E(Q)
c1, c2, _ = k*Q
y0 = k*P
y1 = c1 * x1 % p
y2 = c2 * x2 % p
return y0, int(y1), int(y2)
def ECMenVan_dec(y0, y1, y2, s, p, a, b):
'''
(int, int), int, int, int, int, int, int -> int, int
Decriptografa a mensagem ilegível (y0, y1, y2) usando o criptossistema Menezes-Vanstone em curvas
elípticas sobre alguma curva elíptica mod p, com a chave privada s sob a curva y² = x³ + ax + b
'''
# Seja a curva elíptica E: y² = x³ + ax + b
E = EllipticCurve(IntegerModRing(p), [0, 0, 0, a, b])
# Tornar y0 objeto de ponto da curva do SAGE, caso não seja
y0 = E(y0)
c = s*y0
c1 = int(c[0])
c2 = int(c[1])
c1_inv = euclides_ext(c1, p)[2] % p
c2_inv = euclides_ext(c2, p)[2] % p
x1 = y1*c1_inv % p
x2 = y2*c2_inv % p
return int(x1), int(x2)
def ECMenVan_CBC_enc(txt, vi, k, Q, P, a, b):
'''
str, str, int, (int, int), (int, int)
Criptografa a string txt em base 16 usando o criptossistema Menezes-Vanstone em curvas
elípticas sobre a curva elíptica y² = x³ + ax + b mod 263 com a chave pública (Q, P) e o NONCE k
no modo Cipher Block Chaining com valor inicial vi em base 16.
'''
# Inicializamos a saída
out = ''
# Tomamos o primeiro par de blocos (x1, x2)
x1 = int(txt[0 : 2], 16)
x2 = int(txt[2 : 4], 16)
# XOR do primeiro bloco com o valor inicial. Por algum motivo preciso converter
# para um objeto do SAGE, caso contrário ele interpreta ^ como exponenciação.
x1 = Integer(x1) ^ int(vi[0 : 2], 16)
x2 = Integer(x2) ^ int(vi[2:], 16)
# Criptografamos o primeiro bloco
y0, y1, y2 = ECMenVan_enc(x1, x2, k, Q, P, 263, a, b)
# Tomamos cada um dos pares de blocos (x1, x2) restantes
for i in range(1, len(txt)//4):
# Escrevemos o par (y1, y2) na saída. Estes terão três digitos,
# pois x1 e x2 estão em [0, 256), mas y1 e y2 estão em [0, 263).
out = out + f'{y1:03x}' + f'{y2:03x}'
# Próximo par de blocos
x1 = int(txt[4*i: 4*i + 2], 16)
x2 = int(txt[4*i + 2: 4*i + 4], 16)
# Como y1 e y2 têm três digitos, tomamos apenas os últimos dois
# para fazer o XOR com x1 e x2, pois queremos que x1 e x2 tenham
# sempre apenas 2 dígitos.
y1 = int(f'{y1:02x}'[-2:], 16)
y2 = int(f'{y2:02x}'[-2:], 16)
# XOR com o bloco anterior
x1 = Integer(x1) ^ Integer(y1)
x2 = Integer(x2) ^ Integer(y2)
# Criptografia
y0, y1, y2 = ECMenVan_enc(x1, x2, k, Q, P, 263, a, b)
out = out + f'{y1:03x}' + f'{y2:03x}'
# Caso o comprimento da mensagem não seja múltiplo do comprimento dos blocos,
# adicionamos um padding de zeros ao final para formar um último bloco.
remainder = len(txt) % 4
if remainder != 0:
block = txt[ len(txt) - remainder : ]
block = block + (4 - len(block))*'0'
x1 = int(block[:2], 16)
x2 = int(block[2:], 16)
y0 = int(f'{y1:02x}'[-2:], 16)
y2 = int(f'{y1:02x}'[-2:], 16)
x1 = Integer(x1) ^ Integer(y1)
x2 = Integer(x2) ^ Integer(y2)
y0, y1, y2 = ECMenVan_enc(x1, x2, k, Q, P, 263, a, b)
out = out + f'{y1:03x}' + f'{y2:03x}'
return y0, out
def ECMenVan_CBC_dec(y0, txt, vi, s, p, a, b):
'''
Decriptografa a string txt em base 16 usando o criptossistema Menezes-Vanstone em curvas
elípticas sobre uma curva elíptica mod p com a chave privada s e o ponto y0 no modo Cipher Block Chaining
com valor inicial vi em base 16. Se n é o número de digitos de vi em base 16, 2^n deve ser maior que p.
'''
# Inicializamos a saída
out = ''
# Tomamos o primeiro par de blocos (y1, y2)
y1 = int(txt[0 : 3], 16)
y2 = int(txt[3 : 6], 16)
# Guardamos estes valores para o XOR futuro
y1_buffer = y1
y2_buffer = y2
# Decriptografamos os primeiros blocos.
x1, x2 = ECMenVan_dec(y0, y1, y2, s, p, a, b)
# x1 = x1 % 256
# x2 = x2 % 256
# XOR dos primeiros blocos com o valor inicial. Por algum motivo preciso converter
# para um objeto do SAGE, caso contrário ele interpreta ^ como exponenciação.
x1 = Integer(x1) ^ int(vi[:3], 16)
x2 = Integer(x2) ^ int(vi[3:], 16)
# Tomamos cada um dos pares de blocos (y1, y2) restantes
for i in range(1, len(txt) // 6):
# Escrevemos o par (x1, x2) na saída. x1 e x2 terão um dígito a menos
# que y1 e y2.
out = out + hex(x1)[2:].zfill(2)[-2:] + hex(x2)[2:].zfill(2)[-2:]
# Próximo par de blocos
y1 = int(txt[6*i: 6*i + 3], 16)
y2 = int(txt[6*i + 3: 6*i + 6], 16)
# Decriptografia
x1, x2 = ECMenVan_dec(y0, y1, y2, s, p, a, b)
# XOR com o bloco anterior
x1 = Integer(x1) ^ Integer(y1_buffer)
x2 = Integer(x2) ^ Integer(y2_buffer)
# Guardamos os blocos atuais para o XOR futuro
y1_buffer = y1
y2_buffer = y2
out = out + hex(x1)[2:].zfill(2)[-2:] + hex(x2)[2:].zfill(2)[-2:]
# A mensagem ilegível é sempre múltiplo do comprimento dos blocos,
# então não há necessidade de um condicional.
return out
def main():
print(f"PARTE 1: Demonstração do criptosistema Menezes-Vanstone sobre curvas elípticas.\n")
print("1. Seja E a curva y² = x³ + 2x + 1\n")
E = EllipticCurve(IntegerModRing(263), [0,0,0,2,3])
print("2. Seja P = (200,39).\n")
P = E((200,39))
if P in E:
print(f"O ponto {P[0], P[1]} está na curva E. De fato, 39² mod 263 = 206 = 200³ + 2*200 + 3 mod 263.\n")
else:
print(f"O ponto {P[0], P[1]} não está na curva E.\n")
'''
Aqui iremos percorrer todos os pontos (i,j) possíveis em (Z/263Z)^2 e contar aqueles que estão na curva.
Isso pode ser feito simplesmente checando se a equação que define E é válida. Como o SAGE tem uma
funcionalidade para checagem de inclusão em curvas elípticas, utilizaremos isso.
Existem algoritmos muito mais eficientes para o cálculo de |E|, como o algoritmo de Schoof, mas estes estão
fora do escopo deste exercício.
'''
print("A próxima parte do código demora um pouco.....\n")
count = 0
for i in range(263):
for j in range(263):
if (i,j) in E:
count += 1
print(f"3. O número de pontos em E é {count}.\n")
print("4. Os primeiros dez múltiplos do ponto P são:")
sum = P
for i in range(1, 11):
print(f"{i}P = ({sum[0]}, {sum[1]})")
sum += P
print("\n5. Seja R = (175, 83).\n")
R = E((175,83))
if R in E:
print(f"O ponto {R[0], R[1]} está na curva E. De fato, 83² mod 263 = 51 = 175³ + 2*175 + 3 mod 263.\n")
else:
print(f"O ponto {R[0], R[1]} não está na curva E.\n")
sum_P_R = P+R
print(f"6. A soma de P e R é {sum_P_R[0], sum_P_R[1]}.\n")
s = 14590197 % 263
print(f"7. Meu NUSP é 14590197. Dessa maneira, seja s = 14590197 mod 263 = {s}.\n")
Q = s*P
print(f"8. Seja Q = sP = {Q[0], Q[1]}.\n")
print(f"A chave pública (Q = {Q[0], Q[1]}, P = {P[0], P[1]}) é enviada para Beto.\n\n")
R = E((175,83))
x1, x2, _ = R
print(f"Beto criptografa a informação R = (x1, x2) = {R[0], R[1]} da seguinte maneira:\n")
k = s + 14590197 % 263
print(f"9. Tomamos o NONCE k = s + 14590197 mod 263 = {k}.\n")
c1, c2, _ = k*Q
print(f"Calculamos (c1, c2) = kQ = {c1, c2}.\n")
# Casting para int, pois c1 e c2 continuam como elementos do espaço de anel modular do sage.
c1, c2 = int(c1), int(c2)
y0 = k*P
print(f"Seja y0 o ponto k*P = {y0[0], y0[1]} da curva E.\n")
y1 = c1 * x1 % 263
y2 = c2 * x2 % 263
print(f"Seja y1 = c1*x1 mod 263 = {y1} e y2 = c2*x2 mod 263 = {y2}.\n")
print(f"10. A mensagem criptografada que Beto deve enviar a Alice é Y = (y0, y1, y2) = ( {y0[0], y0[1]} , {y1}, {y2} ).\n\n")
print("Alice decriptografa a mensagem Y da seguinte maneira:\n")
s_y0_mult = s*y0
print(f"Calculamos s*y0 = (c1, c2) = {s_y0_mult[0], s_y0_mult[1]}.\n")
# Encontramos a inversa de c1 e c2 mod 263 usando o algoritmo extendido de Euclides.
c1_inv = euclides_ext(c1, 263)[2] % 263
c2_inv = euclides_ext(c2, 263)[2] % 263
print(f"Calculamos c1^(-1) mod 263 = {c1_inv} e c2^(-1) mod 263 = {c2_inv}.\n")
print(f"11. Obtemos a mensagem legível de Beto x1 = y1 * c1^(-1) = {y1*c1_inv} e x2 = y2 * c2^(-1) = {y2*c2_inv}.\n\n")
print("PARTE 2: Aplicação do criptosistema.\n\n")
# Geramos o texto e escrevemos no documento 'documento1'
documento1 = gera_doc()
with open('documento1', 'w') as f:
f.write(documento1)
print("12. Geramos um texto pseudo-aleatório \"documento1\" em base 16 começando com o meu número USP. Os primeiros 100 dígitos desse texto são:")
print(documento1[:100])
y0, doc1_cript = ECMenVan_CBC_enc(documento1, 4*'0', 18, Q, P, 2, 3)
print("\n13. Encriptamos o texto gerado, em modo CBC com VI = 0000, obtendo o texto ilegível \"doc1_cript\". Os primeiros 100 dígitos desse texto são:")
print(doc1_cript[:100])
# Escrevemos o texto encriptado no arquivo doc1_cript
with open('doc1_cript', 'w') as f:
f.write(doc1_cript)
doc1_cript_inverso = ECMenVan_CBC_dec(y0, doc1_cript, '0000', s, 263, 2, 3)
print("\n14. Agora decriptamos, obtendo o texto legível \"doc1_cript_inverso\". Os primeiros 100 dígitos desse texto são:")
print(doc1_cript_inverso[:100])
# Escrevemos o texto decriptado no arquivo doc1_cript_inverso
with open('doc1_cript_inverso', 'w') as f:
f.write(doc1_cript_inverso)
print("\nDe fato, podemos verificar que o texto obtido é igual ao texto gerado originalmente, indicando que ambas funções estão corretas.\n")
documento1_bin = f'{int(documento1, 16):b}'[:80]
doc1_cript_bin = f'{int(doc1_cript, 16):b}'[:80]
count = 0
for i in range(80):
if documento1_bin[i] != doc1_cript_bin[i]:
count += 1
print(f"15. Calculamos a distância de Hamming (em binário) entre os 10 primeiros blocos (i.e. os primeiros 80 bits) do texto encriptado para o texto decriptado, contando o número de bits em que um é diferente do outro. O resultado obtido é {count}.\n")
print("É importante notar que as distância de Hamming obtidas nesse EP tendem a ser um pouco a baixo do ideal (que seria 40) pois a imagem da criptografia usada é [1, 263)x[1, 263), que é [001, 107)x[001, 107) em hex. Dessa forma, o primeiro dígito de qualquer metade de bloco tem uma alta chance de ser zero.\n")
print("O resultado desejável aqui é grande (o mais próximo de 40 quanto possível), pois gostariamos que o texto ilegível não aparentasse ter relação com o texto legível. Dessa maneira, evitamos padrões estatísticos entre texto legível e ilegível, dificultando a criptanálise. \n\n")
documento2 = '2' + documento1[1:]
print("16. Obtemos o texto \"documento2\" adicionando 1 ao primeiro dígito do documento1. Os primeiros 100 dígitos desse texto são:")
print(documento2[:100])
y0, doc2_cript = ECMenVan_CBC_enc(documento2, 4*'0', 18, Q, P, 2, 3)
with open('doc2_cript', 'w') as f:
f.write(doc2_cript)
print("\n17. Encriptamos esse texto, obtendo o texto ilegível \"doc2_cript\". Os primeiros 100 dígitos desse texto são:")
print(doc2_cript[:100])
doc2_cript_bin = f'{int(doc2_cript, 16):b}'[:80]
count = 0
for i in range(80):
if doc1_cript_bin[i] != doc2_cript_bin[i]:
count += 1
print(f"\n18. Calculamos a distância de Hamming (em binário) entre os 10 primeiros blocos (i.e. os primeiros 80 bits) de doc1_cript e doc2_cript. O resultado obtido é {count}.\n")
print("Também é desejável que essa distância seja grande (o mais próximo de 40 quanto possível), pois ela é um indicativo da presença do efeito avalanche, ou seja, de que a informação de cada bit do texto legível é difundida por todo o texto ilegível. Isso é desejável pois torna a relação entre texto legível e ilegível ainda mais nebulosa.\n")
s_B = random.randint(2, 263)
Q_B = s_B * P
print(f"\n19. Geramos uma outra chave secreta s_B = {s_B} e calculamos Q_B = s_B * P = {Q_B[0], Q_B[1]}.\n")
y0, doc1_cript_beto = ECMenVan_CBC_enc(documento1, 4*'0', 18, Q_B, P, 2, 3)
with open('doc1_cript_beto', 'w') as f:
f.write(doc1_cript_beto)
print(f"20. Encriptamos o texto documento1 com a nova chave pública (Q_B, P), obtendo o texto ilegível \"doc1_cript_beto\". Os primeiros 100 dígitos desse texto são:")
print(doc1_cript_beto[:100])
doc1_cript_beto_bin = f'{int(doc1_cript_beto, 16):b}'[:80]
count = 0
for i in range(80):
if doc1_cript_bin[i] != doc1_cript_beto_bin[i]:
count += 1
print(f"\n21. Calculamos a distância de Hamming (em binário) entre os 10 primeiros blocos (i.e. os primeiros 80 bits) de doc1_cript e doc1_cript_beto. O resultado obtido é {count}.\n")
print("Também é desejável que este valor seja grande (o mais próximo de 40 quanto possível), o que indica que a informação de cada bit da chave está difundida em todo o texto ilegível. Isso é um indício da confusão da informação no criptosistema.")
if __name__ == '__main__':
main()