Multi-prime RSAを復号してみる（Hack The Vote 2016 The Best RSA）

Crypto CTF

この記事は「CTF Advent Calendar 2016」9日目の記事です。

RSA暗号は二つの素数p, qから計算されるn=p*qを公開鍵として暗号化を行うものであるが、これを一般化したものとしてMulti-prime RSAがある。 ここでは、Multi-prime RSAの概要を説明し、これを題材にした問題を紹介する。

Multi-prime RSA

RSA暗号は、二つの素数p, qとある条件を満たす整数eを用いて、次のような式をもとに計算される。

n = p * q
phi(n) = (p-1) * (q-1)
d = e^(-1) mod phi(n)
c = m^e mod n
m = c^d mod n

mは平文、cは暗号文を表し、公開鍵はnおよびe、秘密鍵はdである。 また、phi(n)はオイラーのトーシェント関数と呼ばれる関数であり、nと互いに素となるn以下の自然数の個数を表す。 上の場合、p, qが素数であることから、その値は(p-1)*(q-1)となる。

ここで、nを任意の自然数に一般化し、互いに異なる素数p1, p2, …, pmと正の整数k1, k2, …, kmを用いて次のように表される場合を考える。

n = p1^k1 * p2*k2 * … * pm^km

このような場合でも、オイラーのトーシェント関数の定義に基づきphi(n)を計算することにより、上と同様の関係が成り立つ。 これは（特にk1, k2, …, kmがすべて1の場合を指して）Multi-prime RSAと呼ばれる。 このとき、phi(n)の具体的な値は次のようになる。

phi(n) = phi(p1^k1) * phi(p2*k2) * … * phi(pm^km)
       = (p1^(k1-1) * (p1-1)) * (p2^(k2-1) * (p2-1)) * … * (pm^(km-1) * (pm-1))

RSA同様、Multi-prime RSAの安全性も素因数分解の困難さに基づいている。 したがって、nが現実的な時間で素因数分解できる場合、Multi-prime RSAは破られる。

Hack The Vote 2016 The Best RSA (Crypto 250)

この問題では、e、n、cの三つの数字が与えられる。 nは524283ビットの非常に大きな値であるが、下位の桁を見ると5で割り切れることがわかる。

$ wget "https://raw.githubusercontent.com/ctfs/write-ups-2016/master/hack-the-vote-ctf-2016/crypto/the-best-rsa-250/the-best-rsa.txt"

$ mv the-best-rsa.txt the_best_rsa.py

$ python
Python 2.7.12 (default, Nov 19 2016, 06:48:10)
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from the_best_rsa import *
>>> len(bin(n))-2
524283
>>> n % 1000
875L

実際にnを素因数分解してみると、次のように素因数分解することができる。

# factor.py
from the_best_rsa import *
from collections import Counter

c = Counter()
i = 3
while True:
    while i*i <= n:
        if n % i == 0:
            c[i] += 1
            n = n // i
            break
        i += 2
    else:
        c[n] += 1
        break

divisors = c.items()
print divisors
$ python factor.py
[(3, 1545), (5, 1650), (7, 1581), (137, 1547), (11, 1588), (13, 1595), (17, 1596), (19, 1553), (149, 1572), (23, 1579), (29, 1549), (31, 1613), (163, 1589), (37, 1594), (167, 1578), (41, 1524), (43, 1538), (173, 1617), (47, 1571), (229, 1610), (179, 1556), (53, 1635), (59, 1556), (151, 1549), (61, 1605), (181, 1582), (193, 1549), (67, 1606), (197, 1520), (71, 1589), (73, 1571), (241, 1564), (79, 1548), (83, 1630), (139, 1638), (89, 1535), (199, 1574), (223, 1610), (97, 1456), (227, 1600), (131, 1540), (101, 1514), (103, 1583), (233, 1564), (107, 1591), (109, 1529), (239, 1556), (157, 1600), (113, 1601), (211, 1544), (251, 1493), (191, 1564), (127, 1565)]

ここで、それぞれのタプルは上の式における (pi, ki) (i=1,…,m) を表している。

この結果と上に示した定義から直接phi(n)およびdを求めることもできるが、dはphi(n)と同じ程度に大きな値となるため復号時のd乗の計算に非常に時間がかかる。 そこで、RSA同様に中国の剰余定理を用いて復号を高速化することを考える。 中国の剰余定理は剰余の計算を法の因数ごとに分解できるという定理であり、Multi-prime RSAの場合もphi(n)がphi(pi^ki)の積で表されることからRSAと同様の計算により適用することができる。 具体的には、ni=pi^kiそれぞれについてphi(ni)、di、miを順に求め、得られたniとmiの組に中国の剰余定理を適用することで解を得る。

# solve.py
from the_best_rsa import *
import gmpy

divisors = [(3, 1545), (5, 1650), (7, 1581), (137, 1547), (11, 1588), (13, 1595), (17, 1596), (19, 1553), (149, 1572), (23, 1579), (29, 1549), (31, 1613), (163, 1589), (37, 1594), (167, 1578), (41, 1524), (43, 1538), (173, 1617), (47, 1571), (229, 1610), (179, 1556), (53, 1635), (59, 1556), (151, 1549), (61, 1605), (181, 1582), (193, 1549), (67, 1606), (197, 1520), (71, 1589), (73, 1571), (241, 1564), (79, 1548), (83, 1630), (139, 1638), (89, 1535), (199, 1574), (223, 1610), (97, 1456), (227, 1600), (131, 1540), (101, 1514), (103, 1583), (233, 1564), (107, 1591), (109, 1529), (239, 1556), (157, 1600), (113, 1601), (211, 1544), (251, 1493), (191, 1564), (127, 1565)]

# https://en.wikipedia.org/wiki/Euler%27s_totient_function
n_ary = []
a_ary = []
for p, k in divisors:
    pk = p ** k
    phi = pk * (p-1)/p
    d = gmpy.invert(e, phi)
    mk = pow(c, d, pk)
    n_ary.append(pk)
    a_ary.append(mk)

# http://rosettacode.org/wiki/Chinese_remainder_theorem#Python
def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)

    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * gmpy.invert(p, n_i) * p
    return sum % prod

m = chinese_remainder(n_ary, a_ary)
m = "%x" % m
print m.decode('hex')

平文をファイルに書き出し、fileコマンドで調べるとGIF画像であることがわかる。

$ python solve.py >result.bin

$ file result.bin
result.bin: GIF image data, version 89a, 512 x 316

$ mv result.bin result.gif

f:id:inaz2:20161202110000g:plain

関連リンク