'''
Lua Jaz Ramos Apostolico (14590197)
27.05.25
EP2 MAC0336 (Criptografia e Seguranca de Dados)
Implementacao do esquema de assinatura Menezes-Vanstone
sobre curvas elipticas, junto de todas as funcoes auxiliares
de aritmetica modular e curvas elipticas necessarias.
Ao ser executado, o programa imprime as respostas para as perguntas
enunciadas no terminal.
'''
import random
# region CONSTANTES GLOBAIS
# definicao do ponto no infinito
EC_POINT_AT_INFINITY = 'inf'
# coeficientes da curva do MV
MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS = (
0, # A
7, # B
0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f # MODULO
)
# ponto P, parametro publico do esquema
MV_POINT_P = (
0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
)
# ordem de P (i.e., MV_POINT_P_ORDER * MV_POINT_P = EC_POINT_AT_INFINITY)
MV_POINT_P_ORDER = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
# endregion
# region FUNCOES AUXILIARES (ARITMETICA MODULAR E BINÁRIO)
def extended_euclid(a, b) :
'''
Implementa algoritmo de Euclides estendido.
Entrada:
a: inteiro
b: inteiro
Saida:
(s, t, gcd), inteiros tais que
s * a + t * b = gcd
'''
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 v_antigo, u_antigo, b
else:
return v_antigo, u_antigo, a
def inverse_mod(a, m) :
'''Calcula a inversa de a modulo m usando o algoritmo de Euclides Estendido .
Entrada :
a: inteiro
m: inteiro
Saida:
a^(-1) mod m, caso exista, ou seja mdc(a, m) == 1
Caso nao exista, levanta ValueError.
'''
s, t, gcd = extended_euclid(a, m)
if (gcd != 1) :
raise ValueError ('mdc(a, m) deve ser 1 para haver inversa de a mod m')
# Garante que o resultado esta correto antes de devolve-lo, ou joga um AssertionError
assert (a * s % m == 1)
# Inseri um '% m' para que o resultado esteja entre 0 e m-1.
return s % m
def hamming(a: int, b:int):
'''
Retorna a distancia de Hamming entre os ints a e b,
ou seja, o numero de bits diferentes entre a e b.
Entrada:
a: inteiro
b: inteiro
Saida:
d, inteiro que conta o numero de bits diferentes nas
representacoes binarias de a e b.
'''
# a_bin = f'{a:0b}'
# b_bin = f'{b:0b}'
# a_n = len(a_bin)
# b_n = len(b_bin)
# # padding
# if a_n > b_n:
# b_bin = (a_n - b_n)*'0' + b_bin
# elif a_n < b_n:
# a_bin = (b_n - a_n)*'0' + a_bin
# dist = 0
# for i in range(a_n):
# if a_bin[i] == b_bin[i]:
# dist += 1
# ideia mais legal: fazer o XOR e contar os 0's
dist = 0
for i in f'{a^b:0b}':
if i == '0':
dist += 1
return dist
# EDIT: eu errei aqui! dist de hamming tem que contar os 1's (i.e. os bits DIFERENTES, seu jumento). na docstring ta certo, mas eu chapei no código.
# endregion
# region FUNCOES AUXILIARES (CURVAS ELIPTICAS)
def EC_is_in_curve(ec_coefficients: tuple, point: tuple):
'''
Verifica se o ponto point esta contida na curva eliptica
definida pelos coeficientes em ec_coefficients.
Entrada:
ec_coefficients: tuple
point: tuple
Saida:
booleano
'''
if point == EC_POINT_AT_INFINITY:
return True
A, B, M = ec_coefficients
x, y = point
if pow(y, 2) % M == (pow(x, 3) + A*x + B) % M:
return True
else:
return False
def EC_invert_point(ec_coefficients: tuple, point: tuple):
'''
Obtem o ponto inverso a point, ou seja, aquele que somado
com point resulta no ponto no infinito, na curva eliptica
definida pelos coeficientes ec_coefficients.
Entrada:
ec_coefficients: tuple
point: tuple
Saida:
point_inv, tuple com as coordenadas do ponto inverso
a point
'''
x, y = point
A, B, M = ec_coefficients
point_inv = (x, -y % M)
# Garante que o ponto esta na curva
assert(EC_is_in_curve(ec_coefficients, point_inv))
return (point_inv)
def EC_add_points(ec_coefficients:tuple, point1: tuple, point2: tuple):
'''
Obtem a soma dos pontos point1 e point2 dentro da curva eliptica
definida pelos coeficientes em ec_coefficients.
Entrada:
ec_coefficients: tuple
point1: tuple
point2: tuple
Saida:
point3, tuple com as coordenadas da soma de poin1 e point2
'''
if not EC_is_in_curve(ec_coefficients, point1) or not EC_is_in_curve(ec_coefficients, point2):
raise ValueError('Os dois pontos devem fazer parte da curva eliptica definida por ec_coefficients')
if point1 == EC_POINT_AT_INFINITY:
return point2
if point2 == EC_POINT_AT_INFINITY:
return point1
x1, y1 = point1
x2, y2 = point2
A, B, M = ec_coefficients
# caso 1: point1 = -point2
if point1 == EC_invert_point(ec_coefficients, point2):
return EC_POINT_AT_INFINITY
# caso 2: point1 = point2
elif point1 == point2:
lmb = (3*pow(x1,2) + A)*inverse_mod(2*y1 % M, M)
# caso 3: nenhum dos anteriores
else:
lmb = (y2 - y1)*inverse_mod((x2 - x1) % M, M)
x3 = (pow(lmb, 2) - x1 - x2) % M
y3 = (lmb*(x1 - x3) - y1) % M
return (x3, y3)
def EC_scalar_multiplication(ec_coefficients: tuple, scalar: int, point: tuple):
'''
Obtem a multiplicacao de point com o escalar scalar, como definida na curva
eliptida determinada pelos coeficientes ec_coefficients.
Entrada:
ec_coefficients: tuple
scalar: inteiro
point: tuple
Saida:
result_point, tuple com as coordenadas do resultado da multiplicacao
'''
bits = f'{scalar:0b}'
result_point = EC_POINT_AT_INFINITY
for bit in bits:
result_point = EC_add_points(ec_coefficients, result_point, result_point)
if bit == '1':
result_point = EC_add_points(ec_coefficients, result_point, point)
# garantir que o resultado estA na curva
assert(EC_is_in_curve(ec_coefficients, point))
return result_point
# endregion
# region IMPLEMENTACAO ASSINATURA MV EM EC
def MV_keygen():
'''
Gera chaves publica e privada para o esquema de assinatura
Menezes-Vanstone sobre curvas elipticas de acordo com os
parametros definidos nas constantes globais.
Saida:
s, chave privada no formato de um inteiro
Q, tuple com as coordenadas da chave publica
'''
A, B, q = MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS
n = MV_POINT_P_ORDER
s = random.randrange(1,n)
Q = EC_scalar_multiplication(MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS, s, MV_POINT_P)
return s, Q
def MV_sign(secret_key: int, hash_x: int):
'''
Obtem a assinatura de hash_x no esquema Menezes-Vanstone
sobre curvas elipticas de acordo com os parametros definidos
nas constantes globais.
Entrada:
secret_key: int
hash_x: int
Saida:
x_sign, a assinatura de hash_x num tuple (r,z)
'''
n = MV_POINT_P_ORDER
ec = MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS
P = MV_POINT_P
k = random.randrange(1, n+1)
r = EC_scalar_multiplication(ec, k, P)[0]
z = inverse_mod(k, n)*(hash_x + secret_key*r) % n
if z % n == 0:
(r, z) = MV_sign(secret_key, hash_x)
return (r, z)
def MV_verify(public_key: tuple, signature: tuple, hash_x: int):
'''
Verifica se a assinatura signature e' valida para a mensagem
hash_x com a chave publica public_key no esquema de assinatura
Menezes-Vanstone sobre curvas elipticas de acordo com os
parametros definidos nas variaveis globais. Retorna um booleano
de acordo.
Entrada:
public_key: tuple (o ponto Q)
signature: tuple
hash_x: inteiro
Saida:
booleano
'''
r, z = signature
n = MV_POINT_P_ORDER
# verificar intervalos
if r < 1 or r > n-1:
return False
if z < 1 or z > n-1:
return False
ec = MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS
P, Q = MV_POINT_P, public_key
u1 = inverse_mod(z, n)*hash_x % n
u2 = inverse_mod(z, n)*r % n
u1_times_P = EC_scalar_multiplication(ec, u1, P)
u2_times_Q = EC_scalar_multiplication(ec, u2, Q)
x0, y0 = EC_add_points(ec, u1_times_P, u2_times_Q)
return (x0 == r % n)
# endregion
# region BATERIA DE TESTES SUGERIDA
def EC_run_tests () :
'''
Esta e ' uma funcao para fazer alguns testes das suas implementacoes .
Os testes sao bem simples e voces devem fazer outros .
'''
assert ( EC_is_in_curve ( MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS , EC_POINT_AT_INFINITY ) )
P = MV_POINT_P
assert ( EC_is_in_curve ( MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS , P ) )
cummP = EC_POINT_AT_INFINITY
points = []
for i in range (1 , 300) :
cummP = EC_add_points ( MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS , P , cummP )
scalar_multP = EC_scalar_multiplication ( MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS , i , P )
# print (i , cummP , ' should be equal to ', scalar_multP )
assert ( cummP == EC_scalar_multiplication ( MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS , i , P ) )
assert ( EC_is_in_curve ( MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS , cummP ) )
points . append ( cummP )
assert ( not all ([ p == EC_POINT_AT_INFINITY for p in points ]) )
print ( ' Completed EC_run_tests () ')
def MV_run_tests () :
'''
Verifica que os parametros estao saos :
* Testa se o ponto MV_POINT_P nao e ' o ponto no infinito
* Testa se o ponto MV_POINT_P esta ' na curva MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS
* Testa se MV_POINT_P_ORDER * MV_POINT_P == EC_POINT_AT_INFINITY
'''
assert ( MV_POINT_P != EC_POINT_AT_INFINITY )
assert ( EC_is_in_curve ( MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS , MV_POINT_P ) )
assert ( EC_scalar_multiplication ( MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS ,
MV_POINT_P_ORDER ,
MV_POINT_P ) == EC_POINT_AT_INFINITY )
# Verifica se a assinatura e verificacao estao funcionando direito
s , Q = MV_keygen ()
n = MV_POINT_P_ORDER
x = random . randrange ( n )
signature = MV_sign (s , x )
assert ( MV_verify (Q , signature , x ) == True )
assert ( MV_verify (Q , signature , x + 1) == False )
assert ( MV_verify (Q , signature , x - 1) == False )
assert ( MV_verify (Q , signature , x * n ) == False )
print ( ' Completed MV_run_tests () ')
# endregion
# region TESTES PRELIMINARES
def tests():
ec_coefficients = (4, 8, 13)
A, B, M = ec_coefficients
for i in range(13):
for j in range(13):
if EC_is_in_curve(ec_coefficients, (i,j)):
print(f'({i}, {j}) esta na curva y^2 = x^3 + {A}x + {B} mod {M}')
point1 = (4, 6)
point2 = (6, 12)
print(f'{point1} + {point2} = {EC_add_points(ec_coefficients, point1, point2)}')
point1_inv = EC_invert_point(ec_coefficients, point1)
print(f'-point1 = {point1_inv}')
print(f'point1 + (-point1) = {EC_add_points(ec_coefficients, point1, point1_inv)}')
print(f'4*{point1} = {EC_scalar_multiplication(ec_coefficients, 4, point1)}')
EC_run_tests()
MV_run_tests()
print(hamming(0b001010110101, 0b011101101010))
print(hamming(0b100, 0b101000))
# endregion
def main():
# atalho para os parametros do protocolo
ec = MV_ELLIPTIC_CURVE_A_B_COEFFICIENTS
# Q1: O ponto Z pertence a curva? SIM
Z = (
0x714f956d8365148f9372ff1e69cf550b279381d6a837e87e5dcd38cfa1c56727,
0xc403a250a26946f672517c118ed4f61b6c407d3407b0175437d1fba7a945d3e1
)
if EC_is_in_curve(ec, Z):
print('Q1: SIM')
else:
print('Q1: NAO')
# Q2: O ponto Y pertence a curva? SIM
Y = (
0x76e64113f677cf0e10a2570d599968d31544e179b760432952c02a4417bdde39,
0xc90ddf8dee4e95cf577066d70681f0d35e2a33d2b56d2032b4b1752d1901ac01
)
if EC_is_in_curve(ec, Y):
print('Q2: SIM')
else:
print('Q2: NAO')
# Q3: O ponto X pertence 'a curva? NAO
X = (
0x6cbc4847a842d45d0d031f0b933cfcb8488884685da384bc6c7ea175bd5dd1f0,
0xc3d779d0048e8d4192864ae7226e9e6007a18bd8643e3d4f6f75b8a32ba6bc4c
)
if EC_is_in_curve(ec, X):
print('Q3: SIM')
else:
print('Q3: NAO')
# Q4: Calcule o ponto Z+Y
Z_add_Y = EC_add_points(ec, Z, Y)
print(f'Q4: Z+Y = ({hex(Z_add_Y[0])}, {hex(Z_add_Y[1])})')
# Q5: Calcule o ponto 2^100 * Z
Z_2a100 = EC_scalar_multiplication(ec, 2**100, Z)
print(f'Q5: Z * 2^100 = ({hex(Z_2a100[0])}, {hex(Z_2a100[1])})')
# Q6: Gere um par de chaves privada e publica (s, Q)
s, Q = MV_keygen()
print(f'Q6: s = {hex(s)}, Q = ({hex(Q[0])}, {hex(Q[1])})')
# Q7: Calcule a assinatura (r, z) de x usando a chave secreta s.
x = 0xd221c4371788e41c91a4be95c9cac7a7ea7a593f405b4213a5d903a457dbfa8
r, z = MV_sign(s, x)
x_sign = (r, z)
print(f'Q7: (r,z) = ({hex(r)}, {hex(z)})')
# Q8: Verifique se assinatura (r, z) e' valida para x usando a chave publica Q.
print(f'Q8: {MV_verify(Q, x_sign, x) = }')
# Q9: Construa x′ = x XOR 1. Assim, x′ sera igual a x com seu ultimo bit alterado.
x_prime = x ^ 1
print(f"Q9: x' = {hex(x_prime)}")
# Q10: Verifique se a assinatura (r, z) de x vale como assinatura de x′ e mostre o resultado na saida padrao.
print(f'Q10: {MV_verify(Q, x_sign, x_prime) = }')
# Q11: Calcule a assinatura (r′, z′) de x′ e mostre o resultado na saida padrao.
r_prime, z_prime = MV_sign(s, x_prime)
x_prime_sign = (r_prime, z_prime)
print(f'Q11: (r_prime,z_prime) = ({hex(r_prime)}, {hex(z_prime)})')
# Q12: Verifique se a assinatura (r′, z′) de x′ vale como assinatura de x e mostre-a na saida padrao.
print(f'Q12: {MV_verify(Q, x_prime_sign, x) = }')
# Q13: Qual a distancia de Hamming entre (r, z) e (r′, z′)
print(f'Q13: {hamming(r,r_prime) + hamming(z, z_prime) = }')
# tests()
if __name__ == '__main__':
main()