from modular_arithmetic import extended_gcd # On a E: Y² = X³ + 497X + 1768 mod 9739 # On connait P(8045, 6936) # Avec O le seul point à l'infini représentant l'élément neutre du groupe abélien équivalent à la courbe elliptique : # On cherche Q tel que P + Q = O # On sait que P + O = P # Donc (8045 + O_1, 6936 + O_2) = P # Donc O = (0, 0) # On veut Q = (x, y) # https://www.bibmath.net/dico/index.php?action=affiche&quoi=./c/courbelliptique.html # Avec # P = x_1, y_1 # Q = x_2, y_2 # P+Q = x_3, y_3 point = tuple[int, int] def ec_add(P: point, Q: point, N: int, polynom: [int]) -> point: """ Args: P: a point for the addition Q: a second point for the addition N: the modulus polynom: a list of coefficients. Returns: P + Q """ a = polynom[0] if P == (0, 0): return Q if Q == (0, 0): return P x1, y1 = P[0], P[1] x2, y2 = Q[0], Q[1] if x1 == x2 and y1 == -y2: return (0, 0) if P != Q: inv = extended_gcd((x2 - x1) % N, N)[1] Lambda = (y2 - y1) * inv % N elif P == Q: inv = extended_gcd((2 * y1) % N, N)[1] Lambda = (3 * pow(x1, 2) + a) * inv % N R = [] R.append((pow(Lambda, 2, N) - x1 - x2) % N) R.append(((Lambda * (x1 - R[0])) - y1) % N) return R def ec_inv(P: point, N: int) -> point: return (P[0], -P[1] % N) if __name__ == "__main__": # Premier challenge sérieux : trouver l'inverse d'un point sur une courbe elliptique, tq P + -P = O # On veut simplement inverser y (mod N) pour avoir le point sur l'autre coté de la courbe. print(ec_inv((8045, 6936), 9739)) # Second challenge, addition de points N = 9739 polynom = [497, 1768] res = ec_add((5274, 2841), (8669, 740), N, polynom) assert res == [1024, 4440] res = ec_add((5274, 2841), (5274, 2841), N, polynom) print(res) assert res == [7284, 2107] P = [493, 5564] PP = ec_add(P, P, N, polynom) Q = [1539, 4742] PPQ = ec_add(PP, Q, N, polynom) R = [4403, 5202] PPQR = ec_add(PPQ, R, N, polynom) print(f"crypto{{{PPQR[0]},{PPQR[1]}}}")