Tags: rsa crypto
Rating:
## Bad keys
#### 197 Points
-----
>I captured this encrypted message a while ago.
>Today, I got into their network and managed to take a snapshot of their key server. I don't think more than 10k messages have been sent between when I captured the message and when I took the snapshot.
>You can access the snapshot here:
>nc 138.68.67.161 60005
-----
I solved this challenge with Hyperreality and the help of a stack exchange post. We are given access to a server which gives public, private key pairs. We have a ciphertext c. To solve this challenge, we generate new key pairs and use an algorithm to factor `N` using `(e,d,n)` and try to find a weakness in the implementation.
To factor `N`, I used the algorithm described by fgrieu [here](https://crypto.stackexchange.com/questions/62482/algorithm-to-factorize-n-given-n-e-d) which I repeat
1. Compute `f <- ed - 1` and express `f = 2**s * t`
2. Set `i = s` and `a = 2`
3. Compute `b = a**t mod n`
- If `b == 1`: set `a` to the next prime and jump to `3`.
4. If `i != 1`:
- `Compute c = b**2 mod N`
- If `c != 1` set `b = c` and `i -= 1`
- Jump to `4`.
5. If `b == N - 1`: set `a` to next prime and jump to `3`.
6. Compute `p = gcd(N, b - 1)` and `q = N // q`
Putting this into python, we can write an algorithm to factor generated keys. Note I discard any key pairs that have `d < 0`. Potentially there's a way to use these, but as I don't have `\phi(N)` I couldn't see a quick way and it was easier to just grab a different key pair.
```py
from sympy import nextprime
import math
def find_prime_factors(n,e,d):
k = e * d - 1
s = 0
t = k
while t % 2 == 0:
t = t // 2
s += 1
i = s
a = 2
while True:
b = pow(a,t,n)
if b == 1:
a = nextprime(a)
continue
while i != 1:
c = pow(b,2,n)
if c == 1:
break
else:
b = c
i -= 1
if b == n - 1:
a = nextprime(a)
continue
p = math.gcd(b-1, n)
q = n // p
return p, q
keys = [
((65537, 16730003700605898732103808147265049097309227731116112091966825592580794522488597118108918276114596284933863997925167175825551948545026542789031655603762767594028984696331306133063729472164129741174402731943970446813396896291870363659061827254054595300539660296594191052826127087049878251823692914198236061007), (4549013014706152484948805425702476080901634773768849924147410349265144245094325352773256689814335502044973929887338130723275946764001602033973848404093142468913140303660855127247147909135645926989846389684877266437028310259235212527602515443688484814503867603041563521965407000243692658755982940385673478273, 16730003700605898732103808147265049097309227731116112091966825592580794522488597118108918276114596284933863997925167175825551948545026542789031655603762767594028984696331306133063729472164129741174402731943970446813396896291870363659061827254054595300539660296594191052826127087049878251823692914198236061007)),
((65537, 144517755992564048861504174877857487852987341166328935206455623191881428189718009215250567859676443497706126512409112506483468354898393992286046087915659080819539156733582684190969034177936751150611020408774463197135796355334158803766859705325385107989926116428050293832482242072477621375482173139770930869421), (31054878277053870334567699083035033666991481539365707836985436339949435482182564410613451137034398183899100960896249926435550678884204076984976228025637830486164122358535037197188466113194006283698671271205473089863266402202388548638617988140763543550548546126891968521417488321501698697994048418712496082773, 144517755992564048861504174877857487852987341166328935206455623191881428189718009215250567859676443497706126512409112506483468354898393992286046087915659080819539156733582684190969034177936751150611020408774463197135796355334158803766859705325385107989926116428050293832482242072477621375482173139770930869421)),
((65537, 123741962902154205189909884965124653318102255507428661008324023486380505709197314715589325195416080106121685443970029442140815672039378844508982777903697232853456171326974565483936014318756930718266360727767369367994474730211277431252795244877611270845326337495473012176653152632601881293713941472626554833217), (15541146171592097027910161636143568083087411158302108866129286316376977012869113591162484332262229814509171809654352691430200555358898443156589975814049037029826267580422408827286358483357720841255938886100043208316256177732763374420025617386627628801933221633401610870745630145991479549460332955788507442461, 123741962902154205189909884965124653318102255507428661008324023486380505709197314715589325195416080106121685443970029442140815672039378844508982777903697232853456171326974565483936014318756930718266360727767369367994474730211277431252795244877611270845326337495473012176653152632601881293713941472626554833217))]
e = 65537
for k in keys:
n = k[0][1]
d = k[1][0]
if d > 0:
p, q = find_prime_factors(n,e,d)
if p == 1 or q == 1:
print('[-] Algorithm broken')
else:
print("[+] Prime pair found")
print("p = ", p)
print("q = ", q)
print("")
```
Running this script we get the following prime pairs
```
[+] Prime pair found
p = 1380623332297453118984873537786777519839182349276676087241139668719694587529609212189422107766171700904217158758941493834627126539787388156700567832193247
q = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129864081
[+] Prime pair found
p = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129865231
q = 11926153121375457949010884635428120250029675016450611713057458832154147128348531323843554423542842489299014770027236460611202063816127702713202828814511491
[+] Prime pair found
p = 10211655910202382811964911729055262513625584135244524229115154619070582543942720064521969215139126418488027025507905871989461676818719689776178201641556303
q = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129865839
```
and we see that for each prime pair, one prime seems to be very close in value. Guessing that the algorithm is generating p as `p = nextprime(p)` we can find the prime factors of `N` by starting with one of our found `p` and going backwards towards `0` until we find a factor.
```py
from Crypto.Util.number import inverse
p0 = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129864081
n = 2318553827267041599931064141028026591078453523755133761420994537426231546233197332557815088229590256567177621743082082713100922775483908922217521567861530205737139513575691852244362271068595653732088709994411183164926098663772268120044065766077197167667585331637038825079142327613226776540743407081106744519
e = 65537
c = 2255296633936604604490193777189642999170921517383872458719910324954614900683697288325565056935796303372973284169167013060432104141786712034296127844869460366430567132977266285093487512605926172985342614713659881511775812329365735530831957367531121557358020217773884517112603921006673150910870383826703797655
while True:
if n % p0 == 0:
p = p0
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(bytes.fromhex(format(m,'x')).decode('utf-8'))
break
p0 -= 2
```
#### Flag
`HackTM{SanTa_ple@s3_TakE_mE_0ff_yOur_l1st_4f2d20ec18}`
