• 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

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



## Solution in sage

n1 = 0xD564B978F9D233504958EED8B744373281ED1418B29F1ECFA8093D8CF
n3 = 0xC5B69E1979E541F85DACDE2AA14D2722A846F41B3DB83E667E3B3D11D

factors1 = factor(n1)
p1 = list(factors1)
q1 = list(factors1)

factors2 = factor(n2)
p2 = list(factors2)
q2 = list(factors2)

factors3 = factor(n3)
p3 = list(factors3)
q3 = list(factors3)

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
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, phi1))
d2 = Integer(mod(bezout2, phi2))
d3 = Integer(mod(bezout3, 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')