Plongeon Rapide Super Artistique

Crypto - Moyen

Énoncé

Vous vous avancez sur le plongeoir, la foule est tellement en liesse que la planche en tremble. C'est le dernier saut avant d'avoir votre note finale et donc votre classement pour ce sport. Vous sautez, le monde se ralentit et, comme à l'entrainement, vous effectuez l'enchaînement de figures que vous avez travaillées. Une fois la tête sortie de l'eau, personne du jury ne montre de note ! Un flash vous frappe, c'est vrai que la note est transmise par chiffrement RSA ! Mais après vos multiples figures aériennes, vous ne vous souvenez que de votre clef publique, et de la trajectoire que vous avez empruntée...

Analyse

Voici le code de l'énoncé

python

from sage.all import *
from Crypto.Util.number import bytes_to_long, isPrime, getRandomNBitInteger
from secret import flag

m = bytes_to_long(flag)

D = 7
R = 32
nbit = 512

def genPoly(deg):
    F = PolynomialRing(ZZ, "x")
    x = F.gen()

    P = 0
    coeffs = []
    for i in range(deg + 1):
        c = getRandomNBitInteger(R)
        coeffs.append(c)
        P += c * x ** i
    P //= GCD(coeffs)
    return P

def genParent(deg):
    P, Q = genPoly(D), genPoly(D)
    while P.gcd(Q) != 1 or len(list(P.change_ring(QQ).factor())) > 1 or len(list(Q.change_ring(QQ).factor())) > 1 :
        P, Q = genPoly(D), genPoly(D)
    return P, Q

def genPrimes(P, Q, l):
    t = (l - R) // D

    r = getRandomNBitInteger(t)
    while not (isPrime(P(r)) and isPrime(Q(r))) :
        r = getRandomNBitInteger(t)

    return P(r), Q(r)

P, Q = genParent(D)
N = P*Q

print("N =", N, "\n")

p, q = genPrimes(P, Q, nbit)

n = p*q
print("n =", p*q)

c = pow(m, 65537, n)

print("c =", c)


# N = 15193992477728078349*x^14 + 20849951573235599290*x^13 + 31626787439292941810*x^12 + 41606030540518542243*x^11 + 51135239778172914618*x^10 + 54839205054373601768*x^9 + 61504808736544546256*x^8 + 69077638236743212818*x^7 + 53980744540731499013*x^6 + 48344582546079800218*x^5 + 37874750456914975063*x^4 + 28415628763501783372*x^3 + 19286832846769454663*x^2 + 13073046561885731511*x + 7807279729190335309 
# n = 108467639697839662757675119579277149084242308356218922071090918908615374948181781274150380885272044494446721088127180898926333391217444363867805503733024234462862873998737363236748030712385045260063783565046555205958369142785754700441856622886319553247371639123221105096296162808152357323029673800985543
# c = 88755015861533943167974559872713361696099145214213848793491838241022886852405120609704167406295045592769591587483471982775519184576012814288576845480957257644075924651736974849836538134802852128574442137122106558275855261092222278387967861419587133198657052818619203674183040801840364877770834201106835

from sage.all import *
from Crypto.Util.number import bytes_to_long, isPrime, getRandomNBitInteger
from secret import flag

m = bytes_to_long(flag)

D = 7
R = 32
nbit = 512

def genPoly(deg):
    F = PolynomialRing(ZZ, "x")
    x = F.gen()

    P = 0
    coeffs = []
    for i in range(deg + 1):
        c = getRandomNBitInteger(R)
        coeffs.append(c)
        P += c * x ** i
    P //= GCD(coeffs)
    return P

def genParent(deg):
    P, Q = genPoly(D), genPoly(D)
    while P.gcd(Q) != 1 or len(list(P.change_ring(QQ).factor())) > 1 or len(list(Q.change_ring(QQ).factor())) > 1 :
        P, Q = genPoly(D), genPoly(D)
    return P, Q

def genPrimes(P, Q, l):
    t = (l - R) // D

    r = getRandomNBitInteger(t)
    while not (isPrime(P(r)) and isPrime(Q(r))) :
        r = getRandomNBitInteger(t)

    return P(r), Q(r)

P, Q = genParent(D)
N = P*Q

print("N =", N, "\n")

p, q = genPrimes(P, Q, nbit)

n = p*q
print("n =", p*q)

c = pow(m, 65537, n)

print("c =", c)


# N = 15193992477728078349*x^14 + 20849951573235599290*x^13 + 31626787439292941810*x^12 + 41606030540518542243*x^11 + 51135239778172914618*x^10 + 54839205054373601768*x^9 + 61504808736544546256*x^8 + 69077638236743212818*x^7 + 53980744540731499013*x^6 + 48344582546079800218*x^5 + 37874750456914975063*x^4 + 28415628763501783372*x^3 + 19286832846769454663*x^2 + 13073046561885731511*x + 7807279729190335309 
# n = 108467639697839662757675119579277149084242308356218922071090918908615374948181781274150380885272044494446721088127180898926333391217444363867805503733024234462862873998737363236748030712385045260063783565046555205958369142785754700441856622886319553247371639123221105096296162808152357323029673800985543
# c = 88755015861533943167974559872713361696099145214213848793491838241022886852405120609704167406295045592769591587483471982775519184576012814288576845480957257644075924651736974849836538134802852128574442137122106558275855261092222278387967861419587133198657052818619203674183040801840364877770834201106835

On a donc $N$ , le combiné de $P, Q$ et $n$ le combiné de $p, q$ des points de $P, Q$ .

On cherche donc, dans le but de récupérer $p, q$ , de trouver les facteurs utilisés pour $N = n$ . En d'autres termes on cherche $p, q$ tel que $N = p * q$ .

Ce qui revient à déterminer les racines de l'équation suivante :

N - n = 0

Solution

En utilisant SageMath, on peut :

Récupérer $P, Q$ en factorisant $N$
Récupérer $r$ racine de $N - n$
Déchiffrer $c$

python

from sage.all import *
from Crypto.Util.number import long_to_bytes, isPrime

# Retrieve P and Q
F = PolynomialRing(ZZ, "x")
x = F.gen()
N = 15193992477728078349*x^14 + 20849951573235599290*x^13 + 31626787439292941810*x^12 + 41606030540518542243*x^11 + 51135239778172914618*x^10 + 54839205054373601768*x^9 + 61504808736544546256*x^8 + 69077638236743212818*x^7 + 53980744540731499013*x^6 + 48344582546079800218*x^5 + 37874750456914975063*x^4 + 28415628763501783372*x^3 + 19286832846769454663*x^2 + 13073046561885731511*x + 7807279729190335309

(P, _),(Q, _) = N.factor()

# Retrieve used "r"
n = 108467639697839662757675119579277149084242308356218922071090918908615374948181781274150380885272044494446721088127180898926333391217444363867805503733024234462862873998737363236748030712385045260063783565046555205958369142785754700441856622886319553247371639123221105096296162808152357323029673800985543

r = (N - n).roots(ring=ZZ)[0][0]

assert isPrime(int(P(r))) and isPrime(int(Q(r))) # Assert solution is valid

# Decrypt c
c = 88755015861533943167974559872713361696099145214213848793491838241022886852405120609704167406295045592769591587483471982775519184576012814288576845480957257644075924651736974849836538134802852128574442137122106558275855261092222278387967861419587133198657052818619203674183040801840364877770834201106835
e = 65537

p,q = P(r), Q(r)
phi = (p-1)*(q-1)
d = pow(e, -1, phi)

m = pow(c, d, n)
long_to_bytes(int(m)).decode()

print(f"Le flag est {long_to_bytes(int(m)).decode()}")

from sage.all import *
from Crypto.Util.number import long_to_bytes, isPrime

# Retrieve P and Q
F = PolynomialRing(ZZ, "x")
x = F.gen()
N = 15193992477728078349*x^14 + 20849951573235599290*x^13 + 31626787439292941810*x^12 + 41606030540518542243*x^11 + 51135239778172914618*x^10 + 54839205054373601768*x^9 + 61504808736544546256*x^8 + 69077638236743212818*x^7 + 53980744540731499013*x^6 + 48344582546079800218*x^5 + 37874750456914975063*x^4 + 28415628763501783372*x^3 + 19286832846769454663*x^2 + 13073046561885731511*x + 7807279729190335309

(P, _),(Q, _) = N.factor()

# Retrieve used "r"
n = 108467639697839662757675119579277149084242308356218922071090918908615374948181781274150380885272044494446721088127180898926333391217444363867805503733024234462862873998737363236748030712385045260063783565046555205958369142785754700441856622886319553247371639123221105096296162808152357323029673800985543

r = (N - n).roots(ring=ZZ)[0][0]

assert isPrime(int(P(r))) and isPrime(int(Q(r))) # Assert solution is valid

# Decrypt c
c = 88755015861533943167974559872713361696099145214213848793491838241022886852405120609704167406295045592769591587483471982775519184576012814288576845480957257644075924651736974849836538134802852128574442137122106558275855261092222278387967861419587133198657052818619203674183040801840364877770834201106835
e = 65537

p,q = P(r), Q(r)
phi = (p-1)*(q-1)
d = pow(e, -1, phi)

m = pow(c, d, n)
long_to_bytes(int(m)).decode()

print(f"Le flag est {long_to_bytes(int(m)).decode()}")

Plongeon Rapide Super Artistique ​

Énoncé ​

Analyse ​

Solution ​

Plongeon Rapide Super Artistique

Énoncé

Analyse

Solution