##                       ##

########           ########

############   ############

 ###########   ########### 

   #########   #########   

"@_    #####   #####    _@"

#######             #######

############   ############

############   ############

############   ############

######    "#   #"    ######

 #####               ##### 

  #####             #####  

    ####           ####    

       '####   ####'

/

/Team

/Meetings

/Writeups

/Scores

/Sponsors

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: BZ�������%�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: �nj�a��Nyj��VaSA_K3YS_4R
m3: o�ba5�����3_SO_BAD!}

=> flag: IW{WEAK_RSA_K3YS_4R3_SO_BAD!} :)

Solution in sage

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')
/writeups/ $

$