D
O

N
O
T

F
E
E
D

T
H
E

B
U
G
S

# Oh Bob!

[Internetwache CTF, 2016]

category: crypto

by kw

• Category: #crypto #RSA
• Used Tools #sage
• Points: 60
• Solves: 167
• Description:

Alice wants to send Bob a confidential message. They both remember the crypto lecture about RSA. So Bob uses openssl to create key pairs. Finally, Alice encrypts the message with Bob's public keys and sends it to Bob.

Clever Eve was able to intercept it. Can you help Eve to decrypt the message? My friend set up a small signing scheme, however she won't let me sign stuff. Can you get it signed?

## Credits

Thanks to

• creed & kree

for extracting the public modulus and exponent out of the provided file

## Write-up

This crypto challenge is about breaking an RSA encryption.

As we got 3 ciphertexts for Bob, our first thought was that we could maybe apply the Chinese Remainder Theorem. But after the extraction of the public modulus and exponent it was clear that this would not work, because the public exponent is 65537. First, taking the 65537-th root is computationally expensive. Second, we would need more encrypted messages; so that the ciphertext would not get reduced by mod n_1*n_2*...*n_m. Third, we would need ciphertexts of the same plaintext, which - what we later found out - is not the case.

Next we tried to factorize the given modulus with sage:

```sage: factor(0xD564B978F9D233504958EED8B744373281ED1418B29F1ECFA8093D8CF) 17963604736595708916714953362445519 * 20016431322579245244930631426505729 sage: factor(0x0A23370E7D0FB00232164AC6D642840FC54E9202433F927A60EB5ADBD9) 16514150337068782027309734859141427 * 16549930833331357120312254608496323 sage: factor(0x0C5B69E1979E541F85DACDE2AA14D2722A846F41B3DB83E667E3B3D11D) 17357677172158834256725194757225793 * 19193025210159847056853811703017693```

VoilÃ ! After about 3 minutes we got the factors of the modulus :) From now on it was a straight forward task:

1. Calculate the private keys
2. Decrypt the ciphertexts
3. Decode the result

But there was one little obstacle left. After running our solution approch we got this:

```m1: ï¿½ï¿½ï¿½ï¿½Iï¿½~ï¿½zï¿½ï¿½ï¿½Ú¯8ï¿½IW{WEAK_R m2: BZï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½%ï¿½t=Lï¿½ï¿½8ï¿½ï¿½ ï¿½ï¿½ï¿½ï¿½ m3: S9ï¿½ã‘¢t 8ï¿½Hï¿½ï¿½pnï¿½ï¿½ï¿½ï¿½ï¿½ï¿½a4ï¿½ ```

The first message looks good. What about the other 2? We exchanged the second and third ciphertext and got this:

```m1: ï¿½ï¿½ï¿½ï¿½Iï¿½~ï¿½zï¿½ï¿½ï¿½Ú¯8ï¿½IW{WEAK_R m2: ï¿½ÇŒï¿½aï¿½ï¿½Nyjï¿½ï¿½VaSA_K3YS_4R m3: oï¿½ba5ï¿½ï¿½ï¿½ï¿½ï¿½3_SO_BAD!} ```

```n1 = 0xD564B978F9D233504958EED8B744373281ED1418B29F1ECFA8093D8CF n2 = 0xA23370E7D0FB00232164AC6D642840FC54E9202433F927A60EB5ADBD9 n3 = 0xC5B69E1979E541F85DACDE2AA14D2722A846F41B3DB83E667E3B3D11D factors1 = factor(n1) p1 = list(factors1)[0][0] q1 = list(factors1)[1][0] factors2 = factor(n2) p2 = list(factors2)[0][0] q2 = list(factors2)[1][0] factors3 = factor(n3) p3 = list(factors3)[0][0] q3 = list(factors3)[1][0] if p1*q1 == n1 and p3*q3 == n3 and p2*q2 == n2: print 'ps and qs seem to be correct :)' else: print 'damn it...factors are not correct!' exit(1) e = 65537 c1 = 0x0caf5db76313c9b32a473fcdd9150cab6a9abafa8520e9d0f3d98b8d76 c3 = 0x00afd63d8b0ae44085b2ea6e5bdf1b085298500a60ad0e8b4dc9b72b16 c2 = 0xa22d279350208a93235ff0d56789f18a292d8527b56758a9c47728176 phi1 = (p1 - 1) * (q1 -1) phi2 = (p2 - 1) * (q2 -1) phi3 = (p3 - 1) * (q3 -1) bezout1 = xgcd(e, phi1) bezout2 = xgcd(e, phi2) bezout3 = xgcd(e, phi3) d1 = Integer(mod(bezout1[1], phi1)) d2 = Integer(mod(bezout2[1], phi2)) d3 = Integer(mod(bezout3[1], phi3)) print 'd1: ' + str(d1) print 'd2: ' + str(d2) print 'd3: ' + str(d3) if mod(d1*e,phi1) != 1 or mod(d1*e,phi1) != 1 or mod(d1*e,phi1) != 1: print 'one of the inverse is wrong!!' exit(1) m1 = power_mod(c1,d1,n1) m2 = power_mod(c2,d2,n2) m3 = power_mod(c3,d3,n3) print 'm1: ' + ('0' + str(hex(m1))).decode('hex') print 'm2: ' + ('0' + str(hex(m2))).decode('hex') print 'm3: ' + ('0' + str(hex(m3))).decode('hex')```