I found somebody's notes on their private RSA! Help me crack this.
p: 31633324922152208667782365945327593684774069143774669661619572762724400715661831
q: 36515984267977612350498121647561131263792046107668364547689126140974588406556229
e: 65537
c: 38503996594561449090540233562221047034749981034302051032887385945442450753262325
2932642491630030372490846191037269295383730831605896115604912885466639330684242
RSA 1 is actually super easy. You are given P, Q, E, and C which is all that you need to know. In fact at this stage all you need to do is take a Python Program from the internet and then run it.
The p, q, e, and c that I was given is:
p: 31633324922152208667782365945327593684774069143774669661619572762724400715661831
q: 36515984267977612350498121647561131263792046107668364547689126140974588406556229
e: 65537
c: 38503996594561449090540233562221047034749981034302051032887385945442450753262325
2932642491630030372490846191037269295383730831605896115604912885466639330684242
In this case I used the following code:
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
def main():
p = 31633324922152208667782365945327593684774069143774669661619572762724400715661831
q = 36515984267977612350498121647561131263792046107668364547689126140974588406556229
e = 65537
ct = 3850399659456144909054023356222104703474998103430205103288738594544245075326232
52932642491630030372490846191037269295383730831605896115604912885466639330684242
# compute n
n = p * q
# Compute phi(n)
phi = (p - 1) * (q - 1)
# Compute modular inverse of e
gcd, a, b = egcd(e, phi)
d = a
print( "d: " + str(d) );
# Decrypt ciphertext
pt = pow(ct, d, n)
print( "Message: " + str(pt) )
if __name__ == "__main__":
main()Now you just have to do is run it in order to get the message! However, the message is in number form - so we are not quite there yet. The next step is super easy if you have access to a terminal (command line). On at least a mac, if you type in "python" it enters python editing mode. If not, you would have to download it.
>>> m = 930065689241951596323063985482301033224298538756726271155598276091087010038627243314545460589275053735502205
>>> hexed = hex(m)
>>> hexed
'0x656173796374667b7768336e5f7930755f683476655f7026715f5253415f697a5f657a5f63653339383937617dL'
>>> "656173796374667b7768336e5f7930755f683476655f7026715f5253415f697a5f657a5f63653339383937617d".decode("hex")
'easyctf{wh3n_y0u_h4ve_p&q_RSA_iz_ez_ce39897a}'
This is kind of a hit or miss however. Sometimes you get weird negative d. So, the best method is of course: BY HAND (for the most part). Before I get into this I need to explain some of the terminology and math behind RSA. We know the generic p, q, e, and c because that was given. But what is the purpose of P and Q? Well it is used to calculate two very important variables that are used in RSA. The first one is "N" which is called the N module. The second one is "phi" which is the totient. N is calculated with:
N = P * Q
Phi is calculated with:
Phi = (P-1) * (Q-1)
Easy. Now what you need to do is take into account the RSA formula:
d*e mod phi = 1
To solve this you would need to write out the recursions by hand. They follow the pattern of using the previous (or starting upon initiation) number and finding the remainder as well as how many times the current number goes into the prior number. For example, if I had the prior number 5 and current number 3, I would write 5%3 = 2 which is the same as 5 = 1(3) + 2.
A quick note: do no expand the brackets even it is 1(3) because that is necessary in calculations.
This process repeats until the remainder is 1. So in my case I would do:
Level 1 =>
(115512199520113418062325793634107913377234527205309802248463299677048852517
0695732758328411500269800192553388316177742336988882715906206082682990096014
128377240%65537) = 53466 =>
1155121995201134180623257936341079133772345272053098022484632996770488525170
6957327583284115002698001925533883161777423369888827159062060826829900960141
28377240 = 17625493922534357395414162020554482716211380930666616147895585650
4034137230983373172151366632630392021690554696763315735689592553199903273369
69804782247102(65537)+ 53466 =>
53466 = 11551219952011341806232579363410791337723452720530980224846329967704
8852517069573275832841150026980019255338831617774233698888271590620608268299
0096014128377240 - 176254939225343573954141620205544827162113809306666161478
9558565040341372309833731721513666326303920216905546967633157356895925531999
0327336969804782247102(65537)
Level 2 => (65537%53466) = 12071 => 65537 = 1(53466) + 12071 => 12071 = 65537 - 1(53466)
Level 3 => (53466%12071) = 5182 => 53466 = 4(12071) + 5182 => 5182 = 53466 - 4(12071)
Level 4 => (12071%5182) = 1707 => 12071 = 2(5182) + 1707 => 1707 = 12071-2(5182)
Level 5 => (5182%1707) = 61 => 5182 = 3(1707) +61 => 61 = 5182 - 3(1707)
Level 6 => (1707%61) = 60 => 1707 = 27(61) + 60 => 60 = 1707 - 27(61)
Level 7 => (61%60) = 1 => 1 = 61 - 1(60)
Whew, that took a while. What now? Well, you have to go back. To comprehend all my values better, I separated each operation into levels. I just went from Level 1 to Level 7 - now I must go from Level 7 to Level 1. To do this you plug in the equations you calculated until you get to the Level 1. For example, if we have:
Level 1 => (20%3) = 2 => 20 = 6(3)+2 => 2 = 6(3)-20
Level 2 => (3%2) = 1 => 3 = 1(2)+1 => 1 = 1(2)-3 //This format is important to convert to once you
are in Reverse Mode
The Backtrace would be:
Level 2 => 1 = 1(2)-1(3)
Level 1 => 1 = 1(6(3)-20)-1(3) = 5(3)-1(20) // I just plugged in what I got for Level 1.
REMEBER TO KEEP IN BRACKETS
In my case:
Level 7 => (61%60) = 1 => 1 = 61 - 1(60)
Level 6 => 1 = 61 - 1(1707 - 27(61)) => 28(61) - 1(1707)
Level 5 => 28(5182 - 3(1707)) -1(1707) => 28(5182) - 85(1707)
Level 4 => 28(5182) - 85(12071-2(5182)) => 198(5182)-85(12071)
Level 3 => 198(53466 - 4(12071))-85(12071) =>198(53466)-877(12071)
Level 2 => 198(53466) - 877(65537 - 1(53466)) => 1075(53466)-877(65537)
Level 1 =>
1075(1155121995201134180623257936341079133772345272053098022484632996770
488525170695732758328411500269800192553388316177742336988882715906206082
682990096014128377240 - 176254939225343573954141620205544827162113809306
666161478955856504034137230983373172151366632630392021690554696763315735
68959255319990327336969804782247102(65537))-877(65537)=>
1075(1155121995201134180623257936341079133772345272053098022484632996770
488525170695732758328411500269800192553388316177742336988882715906206082
682990096014128377240)-1894740596672443420007022417209606891992723450046
661235898775457418366975233071261600627191300776714233173462990205644158
6631199468989601887242540140915635527(65537)
This last part to find d is easy. All you have to do is take "phi" and subtract the number in front of e (in this case it is 65537) from it. For example, if you ended up with 20(500)-250(e) where phi is the 500, you would do d = 500 - 250 = 250. In my case it would be:
d = 115512199520113418062325793634107913377234527205309802248463299677048852
517069573275832841150026980019255338831617774233698888271590620608268299
0096014128377240 - 18947405966724434200070224172096068919927234500466612
358987754574183669752330712616006271913007767142331734629902056441586631
199468989601887242540140915635527 =
113617458923440974642318771216898306485241803755263141012564524219630485
541836502014232213958726203305022165368627568589540225151643721648079574
7555873212741713
Now it is time for the final steps using ur python terminal (online calculators can't handle such large numbers). To find "m" we must use the formula: m = c^d % n where c is given & n has already been calculated.
>>> c = 38503996594561449090540233562221047034749981034302051032887385945442
45075326232529326424916300303724908461910372692953837308316058961156
04912885466639330684242
>>> d = 11361745892344097464231877121689830648524180375526314101256452421963
04855418365020142322139587262033050221653686275685895402251516437216
480795747555873212741713
>>> n = 11551219952011341806232579363410791337723452720530980224846329967704
88525170695800907637601630090818473040981204902690903104134158940415
391381893795003250595299
>>> m = pow(c,d,n)
Just follow the hex und decode steps that I mentioned in the beginning and you get your flag: easyctf{wh3n_y0u_h4ve_p&q_RSA_iz_ez_ce39897a}