plain RSAに対する攻撃手法を実装してみる

Crypto

RSAは「単純な素因数分解アルゴリズムを実装してみる」「Msieveを使って大きな数を素因数分解してみる」「YAFUを使って大きな数を素因数分解してみる」で示したような方法により、公開鍵nを素因数分解することができれば秘密鍵dを得ることができる。 一方、平文をそのまま暗号化した場合のRSA（plain RSA）では、nの素因数分解以外にも、特定の条件のもとで暗号文cから平文mを復号できる場合がある。 ここでは、そのようなplain RSAに対する攻撃手法を実装してみる。

環境

Ubuntu 14.04.3 LTS 64bit版

$ uname -a
Linux vm-ubuntu64 3.19.0-25-generic #26~14.04.1-Ubuntu SMP Fri Jul 24 21:16:20 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 14.04.3 LTS
Release:        14.04
Codename:       trusty

GMPYのインストール

Pythonは標準で多倍長整数を扱うことができるため、GNU Multi-Precision Library（GMP）のような多倍長整数ライブラリを用いなくても大きな整数を扱うことができる。 しかし、整数の範囲でのn乗根や拡張ユークリッド互除法、mod nにおける逆元演算を行うにあたっては、GMPが提供する実装を用いると簡単である。

GMPYまたはその後継のGMPY2を用いると、PythonからGMPを使うことができる。 GMPY2はGMPに加えMPFR（多倍長浮動小数点数）やMPC（多倍長複素数）も使うことができるが、GMPの他にこれらのライブラリのインストールも必要となるため、ここではGMPYを用いることとする。

インストールするにはpipを用いて次のようにすればよい。

$ sudo apt-get install python-dev libgmp3-dev
$ sudo pip install gmpy

GMPYのドキュメントは下記から参照することができる。

e乗根

eが小さいとき、nのe乗根以下の平文mについては、単純に暗号文cのe乗根を取れば求めることができる。

# root_e.py

import sys
import gmpy

def root_e(c, e, n):
    bound = gmpy.root(n, e)[0]
    m = gmpy.root(c, e)[0]
    return m, bound


if __name__ == '__main__':
    n = 0x00d91f0102279d099a9aa3a819faefef8e39e71075c5ed59275ae33fd16f10c6b120fbc14f2b0e85b09b7372853c22b359fb4b850e0b66da55585e1221bc23d4a84bc0cce1c1f1c080c74520c3f7cb2d041bc2c372ae96a3b9344dc00b00a75873fd339121804b39b74969ceab850a5ce8c65860fa1e7cfafb052e994a832198ece195ee8bb427a04609b69f052b1d2818741604e2d1fc95008961365f0536f1d3d12b11f3b56f55aa478b18cc5e74918869d9ef8935ce29c66ac5abdde9cc44b8a33c4a3c057624bee9bdfeb8e296798c377110e2209b68fc500d872fd847fe0a7b41c6826b4db3645133a497424b5c111fc661e320b024bccf4b8120847fc92d
    e = 17

    m = long(sys.argv[1])
    c = pow(m, e, n)

    print m
    m, bound = root_e(c, e, n)
    print "%d (possible solution under %d)" % (m, bound)
$ time python root_e.py 123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890 (possible solution under 1824116372372090135441744160659843710)

real    0m0.012s
user    0m0.008s
sys     0m0.000s

Common Modulus Attack

同一の平文mを異なるeで暗号化した暗号文cの組がある場合、拡張ユークリッド互除法を用いて平文mを復号することができる。

# common_modulus_attack.py

import sys
import gmpy

def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    m = (v * w) % n
    return m


if __name__ == '__main__':
    n = 0x00d91f0102279d099a9aa3a819faefef8e39e71075c5ed59275ae33fd16f10c6b120fbc14f2b0e85b09b7372853c22b359fb4b850e0b66da55585e1221bc23d4a84bc0cce1c1f1c080c74520c3f7cb2d041bc2c372ae96a3b9344dc00b00a75873fd339121804b39b74969ceab850a5ce8c65860fa1e7cfafb052e994a832198ece195ee8bb427a04609b69f052b1d2818741604e2d1fc95008961365f0536f1d3d12b11f3b56f55aa478b18cc5e74918869d9ef8935ce29c66ac5abdde9cc44b8a33c4a3c057624bee9bdfeb8e296798c377110e2209b68fc500d872fd847fe0a7b41c6826b4db3645133a497424b5c111fc661e320b024bccf4b8120847fc92d
    e1 = 65537
    e2 = 257

    m = long(sys.argv[1])
    c1 = pow(m, e1, n)
    c2 = pow(m, e2, n)

    print m
    print common_modulus_attack(c1, c2, e1, e2, n)
$ time python common_modulus_attack.py 1234567890123456789012345678901234567890
1234567890123456789012345678901234567890
1234567890123456789012345678901234567890

real    0m0.014s
user    0m0.012s
sys     0m0.000s

Wiener's Attack

Wiener's Attackは、秘密鍵dが小さい（d < 1/3 * n1/4）とき、公開鍵n、eから秘密鍵を求めることができる手法である。 具体的には、適当なkに対してk/dがe/nで近似できることをもとに、e/nを連分数展開したのちこれを途中で打ち切ることによって得られる近似分数の中からdを見つけ出す。 秘密鍵dが小さいとき、ペアとなる公開鍵eは非常に大きくなるため、Wiener's Attackはeが大きい場合に対する手法といえる。

nがkビット、つまりnが約2kであるとしたとき、上の条件式に対応するdのビット数はk/4 - log2(3) = k/4 - 1.58となる。 適当なn=p*qに対しそのようなdをひとつ選び、対応するeを求めるコードを書くと次のようになる。

# weak_e.py

import sys
import random
from fractions import gcd
import gmpy

def weak_e():
    n = 0x00d91f0102279d099a9aa3a819faefef8e39e71075c5ed59275ae33fd16f10c6b120fbc14f2b0e85b09b7372853c22b359fb4b850e0b66da55585e1221bc23d4a84bc0cce1c1f1c080c74520c3f7cb2d041bc2c372ae96a3b9344dc00b00a75873fd339121804b39b74969ceab850a5ce8c65860fa1e7cfafb052e994a832198ece195ee8bb427a04609b69f052b1d2818741604e2d1fc95008961365f0536f1d3d12b11f3b56f55aa478b18cc5e74918869d9ef8935ce29c66ac5abdde9cc44b8a33c4a3c057624bee9bdfeb8e296798c377110e2209b68fc500d872fd847fe0a7b41c6826b4db3645133a497424b5c111fc661e320b024bccf4b8120847fc92d
    p = 0x00f4df425732311763642a435d135c62e99117e146c4b7c2a2ef3664cee80852e52a3eed7dc1f9ff36b923620562330a8751b61ca33e12c684e47d4296fb002ff708bd0dd999f2340997481b2628526d3caa75eb6ce9f9d6db8f1218dee7f41ee2e7f325ba55545f99cfd453fdac06feca005a7efdd45d9f0a4eafb6770a48929f
    q = 0x00e2fce6b312912d6c65b07d435b63b541b11b2e9525e83cb7342d046082aaba8adefc0be953328a573dc31b7594c23d6535e16c37bc326de39cc390e1ce550f34ac3b9b6ed75bbf9dc1fc183559779e91558c86f2c74eb2ff6b81382b9acf8223bae022a801dc29737cdcfa75cc370f56021728fe467d17cfe2484437b81c3cb3
    phi = (p-1)*(q-1)
    while True:
        d = random.getrandbits(2048/4-2)
        if gcd(d, phi) == 1:
            break
    e = gmpy.invert(d, phi)
    return e

if __name__ == '__main__':
    print hex(weak_e())
$ python weak_e.py
0x470a2650f57fed98dbde75761701a2b2711c668dcaf1f58c1e87bd1ff21b19ca107bbf8ae7cfdd31e991a6900aa2e4f24ab20fa291fb014a7a7dc73df4726a057a222aa331726cf9b9ebb22e8b8812025340ed1bdf882eef353f009cbf20c1be0e6231c8021d63e82f66c94118cefb1fd3c155bede6037f822992b8e37cd6a1b011aec6dfeb63079030e1af7fabf53bb625a7c58aceaa5805b59495989965cd62440acaa326bb90ba5d315845ad295eced02a8aca56f479c7ed97cb8dbb48b89366cb0467fa77ddfccfd09d428bc4aa6f5170e68a7c219b4c8bd032dc13946e2e1ab5d18e41eddd2dad1d8cef5e7f45dcd9ada2c696dc16f7510b155d7b72c35

このeを用いて暗号化した場合について、Wiener's Attackにより秘密鍵dを求め、これを用いて平文を復号するコードを書くと次のようになる。 このコードでは、「二次方程式の解p、qがともに整数であること」と「判別式Dが平方数であること」が必要十分の関係にあることを利用して、後者を満たすk、dの組を特定している。

# wieners_attack.py

import sys
import gmpy

def continued_fraction(n, d):
    """
    415/93 = 4 + 1/(2 + 1/(6 + 1/7))

    >>> continued_fraction(415, 93)
    [4, 2, 6, 7]
    """
    cf = []
    while d:
        q = n // d
        cf.append(q)
        n, d = d, n-d*q
    return cf

def convergents_of_contfrac(cf):
    """
    4 + 1/(2 + 1/(6 + 1/7)) is approximately 4/1, 9/2, 58/13 and 415/93

    >>> list(convergents_of_contfrac([4, 2, 6, 7]))
    [(4, 1), (9, 2), (58, 13), (415, 93)]
    """
    n0, n1 = cf[0], cf[0]*cf[1]+1
    d0, d1 = 1, cf[1]
    yield (n0, d0)
    yield (n1, d1)

    for i in xrange(2, len(cf)):
        n2, d2 = cf[i]*n1+n0, cf[i]*d1+d0
        yield (n2, d2)
        n0, n1 = n1, n2
        d0, d1 = d1, d2

def wieners_attack(e, n):
    cf = continued_fraction(e, n)
    convergents = convergents_of_contfrac(cf)

    for k, d in convergents:
        if k == 0:
            continue
        phi, rem = divmod(e*d-1, k)
        if rem != 0:
            continue
        s = n - phi + 1
        # check if x^2 - s*x + n = 0 has integer roots
        D = s*s - 4*n
        if D > 0 and gmpy.is_square(D):
            return d


if __name__ == '__main__':
    n = 0x00d91f0102279d099a9aa3a819faefef8e39e71075c5ed59275ae33fd16f10c6b120fbc14f2b0e85b09b7372853c22b359fb4b850e0b66da55585e1221bc23d4a84bc0cce1c1f1c080c74520c3f7cb2d041bc2c372ae96a3b9344dc00b00a75873fd339121804b39b74969ceab850a5ce8c65860fa1e7cfafb052e994a832198ece195ee8bb427a04609b69f052b1d2818741604e2d1fc95008961365f0536f1d3d12b11f3b56f55aa478b18cc5e74918869d9ef8935ce29c66ac5abdde9cc44b8a33c4a3c057624bee9bdfeb8e296798c377110e2209b68fc500d872fd847fe0a7b41c6826b4db3645133a497424b5c111fc661e320b024bccf4b8120847fc92d
    e = 0x470a2650f57fed98dbde75761701a2b2711c668dcaf1f58c1e87bd1ff21b19ca107bbf8ae7cfdd31e991a6900aa2e4f24ab20fa291fb014a7a7dc73df4726a057a222aa331726cf9b9ebb22e8b8812025340ed1bdf882eef353f009cbf20c1be0e6231c8021d63e82f66c94118cefb1fd3c155bede6037f822992b8e37cd6a1b011aec6dfeb63079030e1af7fabf53bb625a7c58aceaa5805b59495989965cd62440acaa326bb90ba5d315845ad295eced02a8aca56f479c7ed97cb8dbb48b89366cb0467fa77ddfccfd09d428bc4aa6f5170e68a7c219b4c8bd032dc13946e2e1ab5d18e41eddd2dad1d8cef5e7f45dcd9ada2c696dc16f7510b155d7b72c35

    m = long(sys.argv[1])
    c = pow(m, e, n)

    print m
    d = wieners_attack(e, n)
    print "found d: %d" % d
    m = pow(c, d, n)
    print m
$ time python wieners_attack.py 1234567890123456789012345678901234567890
1234567890123456789012345678901234567890
found d: 1275083233037721186926973395245184092260517180012174852353846980727795785319103669819820390556486356639260897479178672619948490889728830117728813637277349
1234567890123456789012345678901234567890

real    0m0.087s
user    0m0.080s
sys     0m0.004s

Håstad's Broadcast Attack

同一の平文mを異なる公開鍵nで暗号化した暗号文cをe個得られるとき、中国の剰余定理を用いてmを求めることができる。 同報通信あるいは同一平文の問題とも呼ばれる。

# hastads_broadcast_attack.py

import sys
import random
import gmpy

def random_prime(bits):
    while True:
        n = random.getrandbits(bits)
        if gmpy.is_prime(n):
            return n

def chinese_remainder(pairs):
    N = 1
    for a, n in pairs:
        N *= n

    result = 0
    for a, n in pairs:
        m = N/n
        d, r, s = gmpy.gcdext(n, m)
        if d != 1:
            raise "Input not pairwise co-prime"
        result += a*s*m

    return result % N, N

def hastads_broadcast_attack(e, pairs):
    x, n = chinese_remainder(pairs)
    return gmpy.root(x, e)[0]


if __name__ == '__main__':
    m = long(sys.argv[1])

    e = 17

    print "collecting e=%d pairs of (c, n)" % e
    pairs = []
    for i in xrange(e):
        p = random_prime(1024)
        q = random_prime(1024)
        n = p*q
        c = pow(m, e, n)
        pairs.append((c, n))

    print m
    print hastads_broadcast_attack(e, pairs)
$ time python hastads_broadcast_attack.py 1234567890123456789012345678901234567890
collecting e=17 pairs of (c, n)
1234567890123456789012345678901234567890
1234567890123456789012345678901234567890

real    0m1.847s
user    0m1.844s
sys     0m0.000s

その他の攻撃手法

他の攻撃手法としては、LLL格子基底縮小アルゴリズムによるCoppersmithの定理を応用した手法が挙げられる。 具体的には、上位bitが等しい二つの平文に対するFranklin-Reiter Related Message AttackおよびCoppersmith’s Short Pad Attack、d < n0.292となるような小さなdに対するBoneh-Durfee Attackがある。

関連リンク