Loading [MathJax]/jax/output/HTML-CSS/jax.js

Tags: rsa crypto coppersmith 

Rating: 4.5

Dowload the given package and unpack it, we got a python code with its output (public keys and encrypted texts)

#!/usr/bin/python

from Crypto.PublicKey import RSA
import gmpy
from secret import r, s, p, q, FLAG

assert ((p-1) % r)**2 + ((q-1) % s)**4 + ((r**3 - 1) % p)**8 + ((s**3 - 1) % q)**16 == 0
assert gmpy.is_prime(r) + gmpy.is_prime(s) + gmpy.is_prime(p) + gmpy.is_prime(q) == 4

def keysaz(a, b):
    e, n = 65537, a * b
    d = gmpy.invert(e, (a-1)*(b-1))
    key = RSA.construct((long(n), long(e), long(d)))
    return key

key_0, key_1 = keysaz(gmpy.next_prime(r+s), gmpy.next_prime((r+s)<<2)), keysaz(p, q)
pkey_0, pkey_1 = key_0.publickey().exportKey(), key_1.publickey().exportKey()

print pkey_0
enc_0 = key_0.encrypt(FLAG[:18], 1L)[0]
print 'enc_0 =\n', enc_0.encode('base64')

print pkey_1
enc_1 = key_1.encrypt(FLAG[18:], 1L)[0]
print 'enc_1 =\n', enc_1.encode('base64')

From the code, the message is breaking into 2 parts, each encripted with RSA using a different key.

Part 1

For the first key:

key_0 = keysaz(gmpy.next_prime(r+s), gmpy.next_prime((r+s)<<2))

Here N=pq (p<q), and p, q have an near linear relation q4p. We have q=2N+ϵ, ϵ is very small compared to N, according to Primes number Theorem.

We can now find ϵ using Reformulation of Coppersmith's attack by Howgrave-Graham.

qbar = isqrt(4*n1)    # approximation q' of q
F.<x> = PolynomialRing(Zmod(n1), implementation='NTL');
pol = x + qbar

beta = 0.5                             # we should have q >= N^beta
dd = pol.degree()
epsilon = beta / 7                     # <= beta/7
mm = ceil(beta**2 / (dd * epsilon))    # optimized
tt = floor(dd * mm * ((1/beta) - 1))   # optimized
XX = ceil(n1**((beta**2/dd) - epsilon)) # we should have |diff| < X
roots = coppersmith_howgrave_univariate(pol, n1, beta, mm, tt, XX)

It gives root 976 and q=976+[4N]=90829988108297459126723951986073924022504128225586222454376617387900632408868147010157825639889602300446053601539575136123106704382046836252729190919472251

Now that we've factored N, it is trival to decrypt the cipher and get first half of message:

p1 = (n1//q1)
d1 = (inverse(e1, (p1-1)*(q1-1)//2))
m1 = RSA.construct((n1, e, long(d1))).decrypt(c1)
print 'msg1:', m1

msg1: ASIS{0240093faf9ce and we also get the range limit on r+s:

r_s_min = max(p1.previous_prime(), (q1.previous_prime()>>2)+1)
r_s_max = min(p1-1, q1>>2)
print 'r+s: [%d, %d]' % (r_s_min, r_s_max)

r+s: [22707497027074364781680987996518481005626032056396555613594154346975158102217036752539456409972400575111513400384893784030776676095511709063182297729867955, 22707497027074364781680987996518481005626032056396555613594154346975158102217036752539456409972400575111513400384893784030776676095511709063182297729868062]

Part 2

For the second key:

assert ((p-1) % r)**2 + ((q-1) % s)**4 + ((r**3 - 1) % p)**8 + ((s**3 - 1) % q)**16 == 0
assert gmpy.is_prime(r) + gmpy.is_prime(s) + gmpy.is_prime(p) + gmpy.is_prime(q) == 4
key_1 = keysaz(p,q)

There are many constraint posed on p,q,r and s:

  1. p, q, r, s are all primes;
  2. r|(p1)
  3. s|(q1)
  4. p|(r31)
  5. q|(s31)

From 2 and 4, r<p, and p|(r2+r+1)

Suppose r2+r+1=kp, since p1 (mod r), we have k1 (mod r)

If kr+1, then r2+r+1kpr2+r+1(r+1)p=(r+1)(rp)+1(r+1)+1<0 Thus k=1, and p=r2+r+1. Similar q=s2+s+1.

Now we have N=pq=(r2+r+1)(s2+s+1)=(rs)2+(r+s1)rs+(r+s)2+(r+s)+1 Enumerate r+s from the limited range got from Part 1, we can try solving rs and finally r,s.

p = q = None
for r_s in range(r_s_min, r_s_max):
    # solve x**2+(r+s-1)*x+((r+s)**2+(r+s)+1-N) = 0
    d2 = (r_s-1)**2-4*(r_s**2+r_s+1-N)
    d = isqrt(d2)
    if d**2 != d2:
        continue
    rs = (d-(r_s-1))/2
    # solve x**2 - r_s*x + rs = 0
    dd2 = r_s**2-4*rs
    dd = isqrt(dd2)
    if dd**2 != dd2:
        continue
    r, s = (r_s+dd)/2, abs(r_s-dd)/2
    p, q = (r**2+r+1, s**2+s+1)
    break

And finally the flag:

d = (inverse(e, (p-1)*(q-1)//2))
m2 = RSA.construct((N, e, long(d))).decrypt(c2)
print 'msg2:', m2
print m1+m2

msg2: 4d7be86d87d49a95cf7}

ASIS{0240093faf9ce4d7be86d87d49a95cf7}

dorianrMay 1, 2018, 6:09 p.m.

How did you arrive at p|(r2+r+1)?


technic_tecMay 3, 2018, 1:21 a.m.

```
assert ((p-1) % r)**2 + ((q-1) % s)**4 + ((r**3 - 1) % p)**8 + ((s**3 - 1) % q)**16 == 0
```
all 4 terms (((p1), ((q1), ((r31), ((s31)) are non-negative, so they must be 0.