title: RSA Strong Prime Generator

category: Cryptography

difficulty: Difficile

point: 100

author: Maestran

description:

*J’ai trouvé une nouvelle méthode ultra méga sécurisé pour générer des nombres premiers pour mon RSA! *

Aie, encore un qui pense avoir inventé l’eau chaude. Arriverez-vous à lui prouver que son algorithme est mauvais ?

Solution

Le chiffrement se fait en 3 étapes :

• Trouver P
• Trouver Q en fonction de P
• Définir les autres constantes et chiffrer

Autrement dit, tout repose sur P. C’est la fonction getcustomprime qui permet d’en trouver un.

def getcustomprime(x): 
    temp = pow(2,x) + 1
    while(True):
        temp += 2 
        if(isPrime(temp)):
            if(random.randint(0,x/4) == 1):
                return temp

Cette fonction ne prend qu’un argument, paramétré à 2048 lors de son seul appel à la ligne 26.

Les étapes de la fonction :

• commence sa recherche de nombre à 2 puissance 2048
• checher le prochain nombre premier
• accepte aléatoirement ce nombre sinon revient à l’étape précédente

On a donc simplement à prendre tous les nombres premiers un à un à partir de 2 puissance 2048, utiliser getQfromP et regarder si avec nos P et Q on retrouve le même N que celui utilisé pour chiffrer.

En Python cela donne :

from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, isPrime
from sympy import nextprime


def getQfromP(p, x):
	q = p + pow(x, 4)
	if q % 2 == 0:
		q += 1
	while True:
		q += 2
		if isPrime(q):
			return q

# Vient du fichier fourni
N = 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595675060721402585322600565985385121957064267685048717582539091861314633558372199675658759951897053295703754115986193655578673689318545596445419093215810501609619257152817755437079130517411345903818136591084857047106308910607155890465462009811722668913587545383444017790937144963851125848728378498694718673604637863388020812060694976166343887105011071984554935131011120853485053205093581036504384606038239089036759379324375297517756312815397394215367768137609893631252487584012192433190749360353541619297336606658574357506677182441079868383886834268095117087361217779167394938251961040980267912057862492087370347458406903676238458893333

# Valeur utilisée dans le script originel 
x = 2048

# Valeur de départ de P
p = 2**x
while True:
	p = nextprime(p)
	q = getQfromP(p, x)
	if p*q == N:
		print(f"P :\n{p}")
		print(f"Q :\n{q}")
		exit()

# P :
# 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596265937
# Q :
# 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853628651782312709

A partir de là il ne reste plus qu’à calculer les autres constantes et déchiffrer, toujours en python :

def decrypt(p, q, e, C):
	d = pow(e, -1, (p-1) * (q-1))
	N = p*q
	M = pow(C, d, N)
	return M.to_bytes((M.bit_length() + 7) // 8, 'big').decode()


# Vient du fichier fourni
M = 208839685207073959285938333742687813317657647637520074119367093175961495887115246373839847188154342821124463336498976224073211105831584259013245157704959523974330317662393399569376571504288233084376186536518947485133704231589087559642539363659998336828687182989292496692994217881468763453280868277067609390825593599069923952904965999430081537996133513569845920740438630174862334228696104136870491680053238446883866449602945714761806989424781570383145502908455705502124403245500742375015740832631297053536725527567046266731022190006040111115541849760411900694098117387561973028806088687698077013537961037688834020586639137935687048156957749642817844387141618742705499597477545058734155746184724851931565810448851761592862521756799234123322220077490765708314261884636345673479609306937671296417425529268731310556536083479271242770479334453335224683720388469267692550787092148872142223573154865121020523863011516718923812697457767309598586882797813682732190405650644155905985683201257974470055089637618879139075283927294730464524046995917991348238325127974276508483663663427699611000555907315783717537818440260069692964883020705464244452674818863466658227046355713522935338125884935064807159961428080870773765938090378459468100466299997
e = 65537

# Calculés du scripts précédents
p = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596265937
q = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853628651782312709
print(decrypt(p, q, e, M))

# Bravo jeune cryptologue en herbe, le flag est CYBN{d0nt_r0ll_y0ur_0wn_crypt0_dammit!!}

FLAG : CYBN{d0nt_r0ll_y0ur_0wn_crypt0_dammit!!}