plain RSAに対するLSB decryption oracle attackをやってみる

Crypto

「RSAに対する適応的選択暗号文攻撃とパディング方式」では、パディングなしのRSA（plain RSA）が選択暗号文攻撃に対して安全でない、つまり任意の暗号文を復号した結果を得られるとき、与えられた暗号文を直接復号することなく平文が得られることについて確認した。 一方、復号した結果の最下位ビットのみが得られるときについても、暗号文に対応する平文が求められることが知られている（LSB decryption oracle attack）。 ここでは、plain RSAに対してLSB decryption oracle attackを行い、平文が得られることを確認してみる。

LSB decryption oracle attack

LSB decryption oracle attackは、任意の暗号文を復号した結果の最下位ビットを得ることができるとき、与えられた暗号文に対応する平文を求める攻撃である。

RSAの公開鍵n, e、与えられた暗号文c、これに対応する平文mについて、次のような性質が成り立つ。

  • (2^e)*c = (2*m)^e (mod n) を復号した結果の 2*m (mod n) について、最下位ビットが1であれば2*m > n、0であれば2*m <= n
    • nは奇数、かつ2*m < 2*nであるから、2*m (mod n) が奇数であれば2*m > n、偶数であれば2*m <= nとなる

これを言い換えると「最下位ビットが1であればn/2 < m < n、0であれば0 <= m <= n/2」となり、mの範囲を半分に絞ることができる。 同様に、(2^e)*(2^e)*cを復号した結果の最下位ビットからこの範囲をさらに半分に絞ることができ、これを繰り返して二分探索を行うことでmを求めることができる。

実際にコードを書くと、次のようになる。

# lsb_decryption_oracle.py
from fractions import Fraction

def lsb_decryption_oracle(c, decrypt_lsb):
    bounds = [0, Fraction(n)]

    i = 0
    while True:
        print i
        i += 1

        c2 = (c * pow(2, e, n)) % n
        lsb = decrypt_lsb(c2)
        if lsb == 1:
            bounds[0] = sum(bounds)/2
        else:
            bounds[1] = sum(bounds)/2
        diff = bounds[1] - bounds[0]
        diff = diff.numerator / diff.denominator
        if diff == 0:
            m = bounds[1].numerator / bounds[1].denominator
            return m
        c = c2

n = 0x00c1e6ad543efcdd3cc8e6cafa580cd3b875a96a8bfdf87e207cddd333f120bce34fc1e1c7893f69065370d47d63c5e52bd342ad34f9b6d326a76c77cf21b6a299953825042f1a57a4886df800a868f5e301725b6ff957382f100375bef368250908192b3be2015d6284eb07cc492321452a74f664d2fe317c2651e306d69e5a7d0fb88bad26878b7bc82b836e5a23f336c3a30ad161c5769e4429ef6ac6803f217b015de4c1251fac8f92f1bafa5fa36573a0dddb8b5b1a5c39ff162c8aaca32a7a3fa872d3565b781cca4dc3e0e095d884c97032e4e3f3f3a31788d110b1d9ab60e39c6ad6742d9460be8432fe33a6b506473acaef8badb88ab74a3fa79bfa61
e = 65537

def decrypt_lsb(c):
    d = 0x00c087fe7f7273be71c6c273b5948c580606bf0c0ea9457e675fd51b0bae57e576881169d0a9550f41bac48419656270a5cd859d5ac6c1647433361ed8cb0efff1241bb595abf7aa22b35d0e2e090aff6c42597cb5788dc439e6daa8a5cc2712ef1edd6ef26cfd11eeeb303c73fa0329dbf5c66189c77fa33f350586399a0d6ea698e9b59b7a6434672e247d96c0d5a6f70d8bd403c9b59e4c25cf9208f3a56920837d817ca3dde1f456c7b5a568f1f4802777a58e93308a94826c9a1e19bfce23c715937b7a47d4200150f2af0e5163e130ecdd0ad89062c7356cb5b3a3dc0b9f2de73b1f40bcc93b40b31ba1e46055336d782826e4955242bb0b23a4a5e90001
    m = pow(c, d, n)
    return m % 2

m = 1234567890123456789012345678901234567890
c = pow(m, e, n)

print lsb_decryption_oracle(c, decrypt_lsb)

decrypt_lsb関数は、暗号文を復号し、その結果の最下位ビットを返す関数である。 また、上のコードでは、切り捨て誤差をなくすためfractionsモジュールで有理数演算を行っている。

このコードを実行すると、次のようになる。

$ python lsb_decryption_oracle.py
0
1
2
3
4
(snip)
2044
2045
2046
2047
1234567890123456789012345678901234567890

上の結果から、Nのビット数の回数だけ二分探索を繰り返した後、与えられた暗号文に対応する平文が得られていることが確認できる。

関連リンク