Challenge Points: 297
Challenge Solves: 9
Challenge Description:

Some people think that combination of cryptographic systems will definitely improve the security. That’s your turn to prove them wrong.

This is a multi-prime RSA challenge where we are given an encryption script, which has two functions:

  1. Generating public and private keys - make_pubpri
  2. Encrypting data using the public key generated from the first function - encrypt

Preliminary Analysis: make_pubpri function

Function generating public and private keys:

def make_pubpri(nbit):
    p, q, r = [ getPrime(nbit) for _ in xrange(3)]
    n = p * q * r
    phi = (p-1)*(q-1)*(r-1)
    l = min([p, q, r])
    d = getPrime(1)
    e = inverse(d, phi)
    a = gensafeprime.generate(2*nbit)
    while True:
        g = getRandomRange(2, a)
        if pow(g, 2, a) != 1 and pow(g, a/2, a) != 1:
            break
    return (n, e, a, g), (n, d, a, g)

Observations:

  1. Instead of two, there are three 512-bit-primes: p, q, r generated in this RSA encryption.
  2. Decryption exponent d, is generated as a 256-bit prime.
  3. The function returns n, e, a, g as the public key.

Preliminary Analysis: encrypt function

def encrypt(m, pub):
    n, e, a, g = pub
    k = getRandomRange(2, a)
    K = pow(g, k, a)
    c1, c2 = pow(k, e, n), (m * K) % a
    return c1, c2

\(K = g^k\mod a\)

Unlike the conventional RSA encryption, here the message is not encrypted using RSA, instead of that, k is encrypted using the public key exponent e, the ciphertext of which is \(c_1\):
\(c_1 = k^e\mod n\)

There is another ciphertext variable returned in the function along with \(c_1\) that is \(c_2\):
\(c_2 = (m*K)\mod a\)

Flow of solution

  1. Decrypt the ciphertext \(c_1\) to get k
  2. Use this k to generate K as discussed in the previous section
  3. Multiply \(c_2\) with modular multiplicative inverse of K over a, to get the message m
    • \(m \equiv c_2*K^{-1}\mod a\)

Decrypting ciphertext \(c_1\)

Here are values of public key given:

n = 1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L

e = 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L

The first thought that would come to one’s mind is to get the corresponding private key using Wiener’s Attack.

Criteria for a public key to be vulnerable to Wiener’s Attack:
\(d<((1 / 3)*n^{1 / 4})\) or \(e > n^{3 / 2}\)

I found that e given in the challenge is a few bits smaller than \(n^{3 / 2}\), which led to a conclusion that d, i.e. the private key exponent, must be a few bits greater than \(d<((1 / 3)*n^{1 / 4})\)

The given values fail to fall under conventional criteria of Wiener’s Attack, but only by a few bits, which is kind of shady. Anyway, I wrote this script implementing Wiener’s Attack in python-sage to see if I find any luck:

from sage.all import continued_fraction, Integer
def wiener(e, n):
    m = 12345
    c = pow(m, e, n)

    list1 = continued_fraction(Integer(e)/Integer(n))
    conv = list1.convergents()
    for i in conv:
        d = int(i.denominator())
        m1 = pow(c, d, n)
        if m1 == m:
            return d
pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L,
814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L,
171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L,
96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
n, e, a, g = pubkey
print wiener(e, n)

As expected, the function did not return anything. I couldn’t find any other vulnerability in the code except the Wiener’s Attack and the close values of e and n suggested that there must be some kind of a Wiener’s Attack vulnerability, although not the conventional one.

A variant of Wiener’s attack on RSA

There is a paper by Andrej Dujella on a variant of Wiener’s Attack. It also works well when the size of d is just a few bits greater than \(N^{1 / 4}\)

You can read the paper here: A variant of Wiener’s Attack on RSA

Here is a conclusion of the paper which is significant in our attack:

Along with decryption exponent d being a denominator of the convergent of the continued fraction of (e/n), d can also be written in the form:

\(d = rq_{m+1} + sq_m\)

\(q_{m+1}\) & \(q_m\) are (m+1)th and mth denominators respectively, of convergents of the continued fraction of (e/n).

Decrypting ciphertext \(c_1\) (cont.)

I assigned \(q_0\) = 0 and \(q_1\) as the first denominator of convergent of continued fraction of (e/n).

Here is the exploit where the variant of Wiener’s Attack is implemented:

from sage.all import continued_fraction, Integer

def wiener(e, n):
    m = 12345
    c = pow(m, e, n)
    q0 = 1

    list1 = continued_fraction(Integer(e)/Integer(n))
    conv = list1.convergents()
    for i in conv:
        k = i.numerator()
        q1 = i.denominator()

        for r in range(20):
            for s in range(20):
                d = r*q1 + s*q0
                m1 = pow(c, d, n)
                if m1 == m:
                    return d
        q0 = q1

pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L,
814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L,
171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L,
96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L,
139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)

n, e, a, g = pubkey
c1, c2 = c

d = wiener(e, n)
print d

Running the above script gave out the private key exponent:

d = 100556095937036905102538523179832446199526507742826168666218687736467897968451

Computing \(K\) and getting the flag

Now that we have d, we can get the flag by simply running the below script:

from Crypto.Util.number import *

k = pow(c1, d, n)
K = pow(g, k, a)
print long_to_bytes(c2 * inverse(K, a) % a)

Flag: ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}

You can read the full solution script here

References

  1. Niklasb’s solution