Algorithme d'Euclide

def euclide(a, b):
    if b == 0:
        return a
    else:
        return euclide(b, a % b)

euclide(21, 15)

3

def euclideEtendu(a, b):
    if b == 0:
        return (1, 0, a)
    else:
        (x, y, d) = euclideEtendu(b, a % b)
        return (y, x - (a//b) * y, d)

euclideEtendu(21, 15)

(-2, 3, 3)

Exponentiation modulaire

#entrée : trois entiers x, y, N sur n bits
#sortie : x^y mod N (sur n bits)
def expomod(x, y, N):
    if y == 0: return 1
    z = expomod(x, y//2, N)
    if y % 2 == 0:
        return z ** 2 % N
    else:
        return x * z ** 2 % N

expomod(2, 4, 10)

6

Inverse modulaire

def inv(a, N):
    (x, y, d) = euclideEtendu(a, N)
    if d == 1: 
        return x % N
    return "non inversible"

inv(3, 10)

7

Test de primalité naïf

import math

def estPremier(N):
    if N == 1: return False
    for d in range(2, 1+math.floor(math.sqrt(N))):
        if N % d == 0:
            return False
    return True

estPremier(7786117)

True

Test de primalité de Fermat

import random

def testFermat(N):
        a = random.randint(1, N-1)
        return expomod(a, N-1, N) == 1
    
def testFermat2(N):
    for i in range(1000):
        if not testFermat(N): return False
    return True

def testFermat3(N):
    return expomod(2, N-1, N) == 1 and expomod(3, N-1, N) == 1 and expomod(5, N-1, N) == 1

testFermat2(14)

False

Génération de nombres premiers

def genererNombrePremier(nbChiffres):
    while True:
        N = random.randint(3, 10 ** nbChiffres)
        if testFermat2(N):
            return N  

genererNombrePremier(200)

60489837867193217613131866658373023853130794099046952772433601682401225889113281191591392165345249993544238769393834945855671142972532097276720140055514656608585901261137631913724914362017371856153037

Factorisation de nombres composés : algorithme naïf

import math

def facteur(N):
    if N == 1: return 1
    for d in range(2, 1+math.floor(math.sqrt(N))):
        if N % d == 0:
            return d
    return True

facteur(15 * 17)

3

facteur(82967981 * 659796497)

82967981

facteur(551192454931 * 391000822831)

Factorisation de nombres composés : algorithme rho de Pollard

def rho(N):
    def f(x):
        return (x ** 2 + 1) % N
    (tortue, lapin) = (f(2), f(f(2)))
    while euclide(abs(tortue - lapin), N) == 1:
        (tortue, lapin) = (f(tortue), f(f(lapin)))
    return euclide(abs(tortue - lapin), N)

rho(15 * 17)

3

rho(82967981 * 659796497)

82967981

rho(551192454931 * 391000822831)

391000822831

def rhoObtenirSuite(N):
    suite = [];
    def f(x):
        return (x ** 2 + 1) % N
    (tortue, lapin) = (f(2), f(f(2)))
    suite.append(tortue)
    suite.append(lapin)
    while euclide(abs(tortue - lapin), N) == 1:
        suite.append(f(lapin))
        suite.append(f(f(lapin)))
        (tortue, lapin) = (f(tortue), f(f(lapin)))
    return suite

rhoObtenirSuite(19 * 17)

[5, 26, 31, 316, 50, 240]

RSA

# génère une clef publique et une clef privée
def genererClefsRSA():
    p = genererNombrePremier(64)
    q = genererNombrePremier(64)
    if p == q:
        raise "error"
    e = 3
    d = inv(e, (p-1) * (q-1))
    
    if isinstance(d, int):
        return ({"N": p*q, "e": e}, {"N": p*q, "d": d})
    else:
        return genererClefsRSA()

publicKey, privateKey = genererClefsRSA()
print(publicKey)
print(privateKey)

{'N': 953658074081688797791260750167418954299498982120548339172297751352451620554898587092402219286146642764175942602458538351073061, 'e': 3}
{'N': 953658074081688797791260750167418954299498982120548339172297751352451620554898587092402219286146642764175942602458538351073061, 'd': 635772049387792531860840500111612636199665988080365559448198496579724804905161560881327549771994960002301369871121732003653867}

#chiffre un message clair avec une clef publique
def chiffrer(message, publicKey):
    return expomod(message, publicKey["e"], publicKey["N"])

chiffrer(123456789, publicKey)

1881676371789154860897069

#déchiffre un message chiffré avec la clef privée (seul le possesseur de la clef privée peut le faire)
def dechiffrer(messageChiffré, privateKey):
    return expomod(messageChiffré, privateKey["d"], privateKey["N"])

dechiffrer(1881676371789154860897069, privateKey)

123456789