zh3ro CTF 2021
I only discovered this CTF 3 hours before it ended (haha). So I decided to work on a few crypto challenges, but only managed to solve this 100 point RSA challenge which took up most of my time. But doing this challenge has opened my mind up to a lot more RSA concepts. I’d like to thank Google, without whom I couldn’t have solved this challenge.
alice_bob_dave
Description
Alice and Bob are sending their flags to Dave. But sadly Dave lost the modulus :( Try to retrieve the flag!
Solution
In the folder, we can find a source code for this RSA implementation, and the output as shown below.
ct_a=1991374644522844726604723395302447678829362766488998002689642863876589167224123634868869407586265887639572846618361378190717796457675877867002990630200549839187693737176043693114429036857443618075597595356236777647214186597416429862630588853297534066191784060030827904725960955181749644590885127762513958644117342351741609981560458367036971039921421548984093411630930209440031060634872093143755813835906517674672118355461511837533783279547447855290393938723966500874359457216314821548439555245649159786182924722770460929014017979622168454175758261065999271764594369618940918533185330319317089809708951104047147411596
ct_b=11560415492145861207516424108577715664730529386805857287246533744961821151018194362544284902991666685182413092786353089517543091603274250128250910669110530206320138191614471688310529571895441809729559056935543845898702106837033971935287923495445981173899073238286288875669342754013550227359718814123485311705960547980778357375585882146296937739196745327987012437076826111202650212821723168353665944362122152786549834258495316372518691633486765982945106049194892430437710982481105051765183397588927444843790029563399175420351710322220501327577415113508236805750358567711052779340011355629159610689505604941700815518380
d_a=12007894588345817095001901772235818535532128075248502006167506715501613386280619988757005912270381074208611126718938214462213079931302423653355153363846803336576965899104058007549509604040316897464770127372797630135493394807353800174267249408200186888724103432412296802728616667116382243738519746110159825921676647202689661952040602841752466515868580858475210918168761862255041985423595605698941150797550252491451770611246462256935118062094973933183288422900540413805923476283359196218128607678993284504582128505198491110084905108072190837781925478455984417366202863689318005069821086805269764308054632708127147397685
d_b=15309121030008789112453654624398278092026139678301334759817236349957760197277968332173160272007689043235997494440248487531238644015060915059836861728115118555482791561589562225055947155368216166612774271639118879220806859714069050410034235487298164832205885978355955618431606156727831992132535894020870312453902803351757466444078059503362362343138846985263572980446344678973847354860739168547872456538618897496981232096868408852088578700314051200160980186449222946973789039336701174360592471866811887750298968395798446811465432587371913161943176018766518394820191044593922558127924048562996714970537749736086175516533
e=65537
We can see from the source code that three primes, \( p,q,r \) were chosen, \( n_a = p \times q \) and \( n_b = p \times r \) and both moduli share the same factor, \( p \).
The Math
The private exponent, \( d \), and the public exponent, \( e\), are related as shown below.
\[\begin{equation} de \equiv 1 \mod {lcm(p-1,q-1)} \end{equation}\]Hence,
\[\begin{equation} ed_a = 1 + k(p-1)(q-1) \end{equation}\]for some \( k \in ℤ \).
We can apply this to the other modulus as well, and then we get:
\[\begin{equation} ed_a -1 = k_a(p-1)(q-1) \end{equation}\] \[\begin{equation} ed_b -1 = k_b(p-1)(r-1) \end{equation}\]We are given the values of \( d_a,d_b,e \), so we can find the GCD (greatest common divisor) of \( ed_b -1 \) and \( ed_a -1 \), to find a multiple of \( p-1 \). Let’s call this \( xp \).
Once we have found \( xp \), we can bruteforce for \( x \) by asserting that \( p \) is prime.
This is my solution so far:
ac = 1991374644522844726604723395302447678829362766488998002689642863876589167224123634868869407586265887639572846618361378190717796457675877867002990630200549839187693737176043693114429036857443618075597595356236777647214186597416429862630588853297534066191784060030827904725960955181749644590885127762513958644117342351741609981560458367036971039921421548984093411630930209440031060634872093143755813835906517674672118355461511837533783279547447855290393938723966500874359457216314821548439555245649159786182924722770460929014017979622168454175758261065999271764594369618940918533185330319317089809708951104047147411596
ad = 12007894588345817095001901772235818535532128075248502006167506715501613386280619988757005912270381074208611126718938214462213079931302423653355153363846803336576965899104058007549509604040316897464770127372797630135493394807353800174267249408200186888724103432412296802728616667116382243738519746110159825921676647202689661952040602841752466515868580858475210918168761862255041985423595605698941150797550252491451770611246462256935118062094973933183288422900540413805923476283359196218128607678993284504582128505198491110084905108072190837781925478455984417366202863689318005069821086805269764308054632708127147397685
bc = 11560415492145861207516424108577715664730529386805857287246533744961821151018194362544284902991666685182413092786353089517543091603274250128250910669110530206320138191614471688310529571895441809729559056935543845898702106837033971935287923495445981173899073238286288875669342754013550227359718814123485311705960547980778357375585882146296937739196745327987012437076826111202650212821723168353665944362122152786549834258495316372518691633486765982945106049194892430437710982481105051765183397588927444843790029563399175420351710322220501327577415113508236805750358567711052779340011355629159610689505604941700815518380
bd = 15309121030008789112453654624398278092026139678301334759817236349957760197277968332173160272007689043235997494440248487531238644015060915059836861728115118555482791561589562225055947155368216166612774271639118879220806859714069050410034235487298164832205885978355955618431606156727831992132535894020870312453902803351757466444078059503362362343138846985263572980446344678973847354860739168547872456538618897496981232096868408852088578700314051200160980186449222946973789039336701174360592471866811887750298968395798446811465432587371913161943176018766518394820191044593922558127924048562996714970537749736086175516533
e = 65537
aed = e * ad
bed = e * bd
xp = gmpy2.gcd(aed-1,bed-1)
for i in range(1, 100):
p = gmpy2.add(gmpy2.c_div(xp,i),1)
if gmpy2.is_prime(p):
break
Now, since we know \( p\), we can try to find \( q \), in a similar manner.
\[\begin{equation} \frac{ed_a -1}{p-1} = k_a(q-1) \end{equation}\]kaq = gmpy2.c_div(gmpy2.sub(aed,1), gmpy2.sub(p,1))
for ka in range (1,100000):
q = gmpy2.add(gmpy2.c_div(kaq,ka), 1)
if gmpy2.is_prime(q):
m = gmpy2.powmod(ac,ad,p*q)
msg = long_to_bytes(m)
try:
print(msg.decode())
break
except:
continue
Now, we find \( r \) in the exact same manner we find \( q\).
kbr = gmpy2.c_div(gmpy2.sub(bed,1), gmpy2.sub(p,1))
for kb in range(1, 100000):
r = gmpy2.add(gmpy2.c_div(kbr,kb), 1)
if gmpy2.is_prime(r):
m = gmpy2.powmod(bc,bd,p*r)
msg = long_to_bytes(m)
try:
print(msg.decode())
break
except:
continue
At the end of it all, we get this output:
Hey Dave its Alice here.My flag is zh3r0{GCD_c0m3s_
Hey Dave its Bob here.My flag is 70_R3sCue_3742986}
Here’s the flag: zh3r0{GCD_c0m3s_70_R3sCue_3742986}.
This is my full code, I’m sorry for the weird variable naming, I always had trouble naming my variables.
from Crypto.Util.number import long_to_bytes, bytes_to_long
from decimal import *
import gmpy2
import math
import random
ac = 1991374644522844726604723395302447678829362766488998002689642863876589167224123634868869407586265887639572846618361378190717796457675877867002990630200549839187693737176043693114429036857443618075597595356236777647214186597416429862630588853297534066191784060030827904725960955181749644590885127762513958644117342351741609981560458367036971039921421548984093411630930209440031060634872093143755813835906517674672118355461511837533783279547447855290393938723966500874359457216314821548439555245649159786182924722770460929014017979622168454175758261065999271764594369618940918533185330319317089809708951104047147411596
ad = 12007894588345817095001901772235818535532128075248502006167506715501613386280619988757005912270381074208611126718938214462213079931302423653355153363846803336576965899104058007549509604040316897464770127372797630135493394807353800174267249408200186888724103432412296802728616667116382243738519746110159825921676647202689661952040602841752466515868580858475210918168761862255041985423595605698941150797550252491451770611246462256935118062094973933183288422900540413805923476283359196218128607678993284504582128505198491110084905108072190837781925478455984417366202863689318005069821086805269764308054632708127147397685
bc = 11560415492145861207516424108577715664730529386805857287246533744961821151018194362544284902991666685182413092786353089517543091603274250128250910669110530206320138191614471688310529571895441809729559056935543845898702106837033971935287923495445981173899073238286288875669342754013550227359718814123485311705960547980778357375585882146296937739196745327987012437076826111202650212821723168353665944362122152786549834258495316372518691633486765982945106049194892430437710982481105051765183397588927444843790029563399175420351710322220501327577415113508236805750358567711052779340011355629159610689505604941700815518380
bd = 15309121030008789112453654624398278092026139678301334759817236349957760197277968332173160272007689043235997494440248487531238644015060915059836861728115118555482791561589562225055947155368216166612774271639118879220806859714069050410034235487298164832205885978355955618431606156727831992132535894020870312453902803351757466444078059503362362343138846985263572980446344678973847354860739168547872456538618897496981232096868408852088578700314051200160980186449222946973789039336701174360592471866811887750298968395798446811465432587371913161943176018766518394820191044593922558127924048562996714970537749736086175516533
e = 65537
aed = e * ad
bed = e * bd
xp = gmpy2.gcd(aed-1,bed-1)
for i in range(1, 100):
p = gmpy2.add(gmpy2.c_div(xp,i),1)
if gmpy2.is_prime(p):
break
kaq = gmpy2.c_div(gmpy2.sub(aed,1), gmpy2.sub(p,1))
for ka in range (1,100000):
q = gmpy2.add(gmpy2.c_div(kaq,ka), 1)
if gmpy2.is_prime(q):
m = gmpy2.powmod(ac,ad,p*q)
msg = long_to_bytes(m)
try:
print(msg.decode())
break
except:
continue
kbr = gmpy2.c_div(gmpy2.sub(bed,1), gmpy2.sub(p,1))
for kb in range(1, 100000):
r = gmpy2.add(gmpy2.c_div(kbr,kb), 1)
if gmpy2.is_prime(r):
m = gmpy2.powmod(bc,bd,p*r)
msg = long_to_bytes(m)
try:
print(msg.decode())
break
except:
continue
