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 を計算できることが分かる.
- Python による実装例
# 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 などではこのようにして計算をしているらしい。