Common primes

Easy | cryptography

Description

RSA is a very commonly used cryptosystem. Can you break it? Refer to this for more information.

Challenge Files

encrypt.py

from Crypto.Util.number import *
 
modulus_list = [92917019109246520946111919259944727745544542783982355430716972006653222462839194379791358138811158902436580150837272503813213355567643909357402799120779532615133095691214112430279300157639789109680476278143116007958419546850451489904099400377262985350595742313358525673308487492326205442219054566734280849463, 130568212240286377492144613994596695460424714704485915362255855721255382599513965251301247594774250836123472395907469409589689688325774329295661798442186187372959761946857650743912997464565794093976101055331289489952844031378077429339913607083706389410418100948879873793883371819349687078725496909678189694283, 85811324434028990250875422438123814864093618278891295811031083960296969537454874943141970297507657075578669322788763313935112356048335316873984184009613837190173099517058749779303494309026026236321089968145254403129264309610852345955453506183006563596075448244968379981815939543003661119788848975062475811483, 115064079704344776522310714154365077908838161807754414730220894729951712834496200170064037105718681038883888312094754104496216926238977476483481079628965404218112773573213774902089911524937553684498516876841154214074392188918966248250666407599549523072851000357434568048726545499842775450683899565801029780317]
 
e = 65537
flag = b"flag{######################}"
 
message = bytes_to_long(flag)
ciphertext = [pow(message, e, modulus_list[i]) for i in range(4)]
 
obj1 = open("ciphertext.txt",'w')
obj1.write(str(ciphertext))
obj1.close()

ciphers.txt

[50102990983659676456532118998336626298566275706424430458994552738927976035514899272815060220859043267460423871568841683264287197451826914538260516119258455974857015490581796991478795451696572538648516023976342026892818390989204861808890471532620011530172881403660843299850636314853520771410680378269046388979, 63062735312733399115272377665781523909620049393396278217875481172044321868823005121008771362585418539989732098737142696182916661326272933690991574274013474792692346153902605315448224479394509272214823035494404196515602039840715583040873233101718857937643308720258887723155213790751953221485022508776722908176, 21012532989119487685994320012096944672031326405628764341764637084158339159731759975782976921086002536918980515470686487579031434668098781035664554523379069844816135878829479481271369623009517178239457977731843127707429734387519685487766673353534805367092366038203446216878137260145732263202544039734332802880, 80588314679904213046563421774623688623804361141532273922867958399118054926360145609661314227750976446898249302019629717775392252365827200144668586399355175407405184184442457875582355800463146472795911482454838025589962320548696237182967990644968196021551525134861812534741570327275935245035215320582734195904]

We are given with a list of modulus and a list of ciphertexts. Where the modulus is used to encrypt the same flag.

Dead End☠️

If the message and exponent is the same, then we can use the Chinese Remainder Theorem to find the common $m^e$

solve.py

modulus_list = [92917019109246520946111919259944727745544542783982355430716972006653222462839194379791358138811158902436580150837272503813213355567643909357402799120779532615133095691214112430279300157639789109680476278143116007958419546850451489904099400377262985350595742313358525673308487492326205442219054566734280849463, 130568212240286377492144613994596695460424714704485915362255855721255382599513965251301247594774250836123472395907469409589689688325774329295661798442186187372959761946857650743912997464565794093976101055331289489952844031378077429339913607083706389410418100948879873793883371819349687078725496909678189694283,
                85811324434028990250875422438123814864093618278891295811031083960296969537454874943141970297507657075578669322788763313935112356048335316873984184009613837190173099517058749779303494309026026236321089968145254403129264309610852345955453506183006563596075448244968379981815939543003661119788848975062475811483, 115064079704344776522310714154365077908838161807754414730220894729951712834496200170064037105718681038883888312094754104496216926238977476483481079628965404218112773573213774902089911524937553684498516876841154214074392188918966248250666407599549523072851000357434568048726545499842775450683899565801029780317]
 
c = [50102990983659676456532118998336626298566275706424430458994552738927976035514899272815060220859043267460423871568841683264287197451826914538260516119258455974857015490581796991478795451696572538648516023976342026892818390989204861808890471532620011530172881403660843299850636314853520771410680378269046388979, 63062735312733399115272377665781523909620049393396278217875481172044321868823005121008771362585418539989732098737142696182916661326272933690991574274013474792692346153902605315448224479394509272214823035494404196515602039840715583040873233101718857937643308720258887723155213790751953221485022508776722908176, 21012532989119487685994320012096944672031326405628764341764637084158339159731759975782976921086002536918980515470686487579031434668098781035664554523379069844816135878829479481271369623009517178239457977731843127707429734387519685487766673353534805367092366038203446216878137260145732263202544039734332802880, 80588314679904213046563421774623688623804361141532273922867958399118054926360145609661314227750976446898249302019629717775392252365827200144668586399355175407405184184442457875582355800463146472795911482454838025589962320548696237182967990644968196021551525134861812534741570327275935245035215320582734195904]
 
x = crt(c, modulus_list)
print(x)

Now we got the $m^e$ , I tried to take the e-th root of the $m^e$ , but it didn't work. After wasting some time, I realized that the challenge name is common primes. So lets check the GCD of the modulus and see if we can find any common primes.

solve.py

for i in range(4):
    for j in range(4):
        if not GCD(modulus_list[i], modulus_list[j]) == 1 and not i==j:
            print(i,j)

1 3
3 1

We got two pairs of modulus with common primes. Let's find the primes and solve the challenge

solve.py

p = GCD(modulus_list[1], modulus_list[3])
q = modulus_list[3] // p
 
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
m = pow(c[3], d, modulus_list[3])
long_to_bytes(m)

Flag 🚩

flag{common_primes_means_common_mistakes}

Is it RSA???Common Threads