picoCTF 2017: Weird RSA

問題

問題文

We recovered some data. It was labeled as RSA, but what in the world are dq and dp Can you decrypt the ciphertext for us

問題概要

解答例

指針

  • 中国人剰余定理

解説

与えられたファイルの中身を表示してみる.

$ cat RSA.txt
c: 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p: 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q: 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp: 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq: 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659

c, p, q を RSA ではおなじみの記号だが, dp, dq とは何なのだろうか?

英語版の Wikipedeia を見ると書いてあった.

d_p = d mod (p-1)

d_q = d mod (q-1)

であり, この値を利用すると中国人剰余定理 (Chinese Remainder Theorem: CRT) を用いて復号を高速化できるらしい.

中国の剰余定理とは

与えられた k 個の整数 m1, m2, ..., mk がどの二つも互いに素ならば,任意に与えられる整数 a1, a2, ..., ak に対し

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
  …
x ≡ ak (mod mk)

を満たす整数 x が m1*m2*…*mk を法として一意に存在する。

という定理でありアルゴリズムではない.

具体的には以下のようにして計算を行う.

求めたいものは平文 m で m = cd mod (p*q) である.

ここで,

d_p = d mod (p-1)

d_q = d mod (q-1)

とすると, Fermat の小定理より

m ≡ c^{d_p} mod p

m ≡ c^{d_q} mod q

となり, 中国人剰余定理により m を計算できることが分かる.

# coding: utf-8

def extgcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b/a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        g = b
    return x, y, g


def modinv(a, m):
    x, y, g = extgcd(a, m)
    if g != 1:
        print "[+]Inverse does not exist."
    else:
        return ((m + x) % m) % m


# a ≡ x1  (mod m1)
# a ≡ x2  (mod m2) を満たす整数 a を返す.
def crt(x1, m1, x2, m2):
    x = x1 + m1 * (x2 - x1) * modinv(m1, m2)

    return x % (m1 * m2)


c = 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p = 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q = 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp = 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq = 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659

m1 = pow(c, dp, p)
m2 = pow(c, dq, q)

print format(crt(m1, p, m2, q), 'x').decode('hex')
  • 実行結果
$ python solve.py
Theres_more_than_one_way_to_RSA

この計算方法は効率的で OpenSSL などではこのようにして計算をしているらしい。

参考文献