「plain RSAに対する攻撃手法を実装してみる」では、plain RSAに対する種々の攻撃手法を実装した。 plain RSAに対する攻撃手法には、他にもCoppersmithの定理に関連した手法が知られている。ここでは、Pythonベースの数式処理システムSageMathを用いてこれを実装してみる。

環境

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

$ ./sage --version
SageMath Version 6.10, Release Date: 2015-12-18

Coppersmithの定理

Coppersmithの定理は、整数Nを法とする方程式の求解に関する次のような定理である。

ある整数 N と次数 d のモニック多項式 f ∈ Z[x] に対し、f(x) = 0 (mod N) を満たすすべての |x| < N^1/d-ε (ε ≧ 0) は効率的に求めることができる。 w = min(1/ε, log₂N) としたとき、計算時間はおおむね O(w) 次元の格子に対するLLL格子次元縮小アルゴリズムの計算時間となる。

ここで、モニック多項式は最高次の係数が1となる多項式を指す。普通の方程式の場合はニュートン法により解を求めることができるが、一般のNを法とする方程式はこのような方法で解を求めることができない。この定理はそのような方程式についても、「Nのd乗根より小さな解」は現実的な時間で求められることを示している。

数式処理システムであるPari/GPやSageMathではCoppersmithのアルゴリズムで解を求める関数が存在し、これを用いることでLLLアルゴリズムを直接扱うことなく計算することが可能である。

以下では、SageMathを用いる。

SageMathを使ってみる

SageMathはPythonベースの数式処理システムである。 Numpy、ScipyをはじめとしてR、Maxima、Pari/GPなどさまざまなライブラリが統合されており、巨大ではあるが統一的に各種演算を行うことができる。また、Pythonがベースとなっているため、通常のPythonのように各種ライブラリを利用することも可能である。

SageMathをインストールするには、まず下のページから環境に合ったtarballをダウンロードし展開する。

SageMath - Download for Linux

$ wget http://ftp.tsukuba.wide.ad.jp/software/sage/linux/64bit/sage-6.10-Ubuntu_14.04-x86_64.tar.bz2
$ tar xvf sage-6.10-Ubuntu_14.04-x86_64.tar.bz2
$ cd SageMath

展開したディレクトリにあるsageを実行すると、初回のみ展開されたパスに合わせてファイルが書き換えられ、SageMathのインタラクティブシェルが起動する。

$ ./sage

Rewriting paths for your new installation directory
===================================================

This might take a few minutes but only has to be done once.

patching /home/user/tmp/SageMath/src/build/cythonized/sage/structure/list_clone.c
(snip)
patching /home/user/tmp/SageMath/src/build/cython_debug/cython_debug_info_sage.gsl.ode
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.10, Release Date: 2015-12-18                    │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage:

Coppersmithのアルゴリズムで3次多項式 x^3 + 10*x^2 + 5000*x - 222 = 0 (mod 10001) において |x| < 10001^(1/3) = 21 となる解を求めてみる。なお、SageMathにおいて演算子^はビット否定ではなく累乗を表す。

sage: N = 10001
sage: K = Zmod(N)
sage: K
Ring of integers modulo 10001
sage: PR.<x> = PolynomialRing(K)
sage: PR
Univariate Polynomial Ring in x over Ring of integers modulo 10001
sage: f = x^3 + 10*x^2 + 5000*x - 222
sage: f.small_roots()
[4]
sage: f(4)
0

上のコードは、10001を法とする多項式環PRを作り、変数xをその環における不定値として定義する。そして、xからなる多項式fを定義し、その根をCoppersmithのアルゴリズムで計算する。結果から、根として4が得られ、実際に代入したときの多項式の値が0となっていることがわかる。

SageMathではDockerイメージも提供されている。

sagemath/sage - Docker Hub

Dockerを使ってSageMathが使えるbashシェルを立ち上げるには次のようにする。

$ sudo docker run --rm -i -t sagemath/sage -sh
Launching Sage...

Starting subshell with Sage environment variables set.  Don't forget
to exit when you are done.  Beware:
 * Do not do anything with other copies of Sage on your system.
 * Do not use this for installing Sage packages using "sage -i" or for
   running "make" at Sage's root directory.  These should be done
   outside the Sage shell.

Bypassing shell configuration files...

Note: SAGE_ROOT=/opt/sage-6.7
(sage-sh) sage@861c4aa9c0b9:~$ which sage
/opt/sage-6.7/src/bin/sage
(sage-sh) sage@861c4aa9c0b9:~$

SageMathのスクリプトファイルには、拡張子.sageを用いる。

素数pの上位bitまたは下位bitがわかっている場合

Coppersmithの定理は法Nにおける解が求められるというものであるが、Sageのsmall_rootメソッドではより詳細にb >= N^βとなるNの約数bを法とした解を求めることができる。ここで、法Nにおける解はβ = 1とした場合にあたる。 RSAにおいて公開鍵nが同じbit数の素数p、qの積であることを考えると、β = 0.3程度とすることでb = p or qを法とした解について計算することができる。

素数pの上位bitがnのbit数の1/4、すなわちpのbit数の1/2程度わかっているとき、残りのbitを0とした値をpbarとする。このとき、f(x) = x + pbar = 0 (mod b)の解を求めることで、これを満たすf(x)の値、つまりpを求めることができる。

SageMathのスクリプトコードを書くと次のようになる。

# partial_p.sage

p = 0x00f23799c031b942026e420769b74d22fa2114428189139c43c366c6ab8367c6b3d6f821449aafb2058b0e6ed964fa0ad45fb306f96376e80823a72b58101919e50acad3b5e6d079e7ff9218ed6df6edbef536742714ce88b2e717f45af53ef0d04c89faf01c80b28e764973aba27726c85c0236e8756a865c03577722bac5e391
q = 0x00c9d24330fa4945cfe1e5d6912d6bde0231035a1cc8d8ae67d949347b895f8d579bce2adaf37c568957b17a6564dbf80d36d81e4622ab30e02132b0155aefbd3912a27c625a9b7b05bc72217039f5aa88c20cbf9871c3228e9d80d9106f94b11c1f50c40c96862b5cd6b6f781883dd2eff80a059d3ca027af6a03edeb34a7390f
n = p*q
e = 3

beta = 0.5
epsilon = beta^2/7

pbits = p.nbits()
kbits = floor(n.nbits()*(beta^2-epsilon))
pbar = p & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar

print p
x0 = f.small_roots(X=2^kbits, beta=0.3)[0]  # find root < 2^kbits with factor >= n^0.3
print x0 + pbar

ここで、kbitsは未知の部分のbit数を表す。実際にはCoppersmithの定理におけるεの部分が存在するため、既知である必要があるbit数はpのbit数の1/2よりいくらか大きくなる。ここでは、small_rootsメソッドがデフォルトでε = β^2/8としていることを考慮し、適当なkbitsを選択している。

実際に実行すると、次のようにpの値が復元できていることがわかる。

$ ./sage partial_p.sage
upper 586 bits (of 1024 bits) is given
170090695019458457073866384150605420308877489550438408808672442208415156751900392963448822268978897866276342297238400021749188358294951475191836681118971072815541539631571918856159498704307385675052568489711538426642180178334905471587161766425888755957683305474050262712211176884573264113883154193083087053713
170090695019458457073866384150605420308877489550438408808672442208415156751900392963448822268978897866276342297238400021749188358294951475191836681118971072815541539631571918856159498704307385675052568489711538426642180178334905471587161766425888755957683305474050262712211176884573264113883154193083087053713

上位bitではなく下位bitがわかっている場合も、次項の中で説明するような多項式を用いることでpの値を復元することができる。

秘密鍵dの下位bitがわかっている場合

秘密鍵dについては、下位bitがnのbit数の1/4程度わかっている場合、dの値を復元することができる。これは、Partial Key Exposure Attackと呼ばれることもある。

# partial_d.sage

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p


if __name__ == '__main__':
    n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
    e = 3
    d = 0x7f4dbb449cc8aa9a0cb73c2fc7b1372da924d7b46c8a710c93e9281c010faaabfd8bec59ef47f5702648925cccc284099d138b33ad65a8a54db425a3c1f5b0b4f5cac22273b13cc617aed340d98ec1af4ed5206be011097c459726e72b7459192f35e1a8768567ea46883d30e7aaabc1fa2d8baa62cfcde93915a4a809bc3e9547bb07e1ecca16e51078312e89f0561e31b55db8b0ea5bc87a6ca7464a3d7c28a68c60e2ba88fe6a7d2b300d723e549910a987da89fc0a1c0de197a3d62c501b1f0e819891b1c32a0d6c233f2a285df87bb9e5c6c72d983ff3e706696bba639f573f9c3646968f02f3a615a438e20bb7c38d53621079f2899547a95350f3abeb

    beta = 0.5
    epsilon = beta^2/7

    nbits = n.nbits()
    kbits = floor(nbits*(beta^2+epsilon))
    d0 = d & (2^kbits-1)
    print "lower %d bits (of %d bits) is given" % (kbits, nbits)

    p = find_p(d0, kbits, e, n)
    print "found p: %d" % p
    q = n//p
    print d
    print inverse_mod(e, (p-1)*(q-1))

上のコードでは、次のような順序でdの値を復元する。

下位bitについてe、d、n、pが満たす方程式をもとに、dの下位bitからpの下位bitの候補を求める
1で得た候補の中から、Coppersmithのアルゴリズムでpの値を復元できるものを探す
復元したpの値からもう一つの素数qを求め、dの値を計算する

2ではpの下位bitをp0としたとき、f(x) = 2^k * x + p0 = 0 (mod b)の解を求めることでpの値の復元を試みる。

実際に実行すると、次のようにdの値が復元できていることがわかる。

$ ./sage partial_d.sage
lower 585 bits (of 2048 bits) is given
found p: 170090695019458457073866384150605420308877489550438408808672442208415156751900392963448822268978897866276342297238400021749188358294951475191836681118971072815541539631571918856159498704307385675052568489711538426642180178334905471587161766425888755957683305474050262712211176884573264113883154193083087053713
16070595569687450115608171924808914271748521737817954209679168387304326174177221251605418301426474191738471931653299099628537592216302521090442291612674220250090663623917575986623108130832502528129647157168707290028664207692539596343502685133605615233575678192994672683899600425651367919262800652478769003262433371189164169086698876897239481110301805575327494730630314230062670467145493663248435642576570039574908319467275999843302907632330828524818095830788274188996932673288182646930739560803236240369311255012922664104459262162533812101040838759847298788136516755214927401958516270479481280238728735341318868544491
16070595569687450115608171924808914271748521737817954209679168387304326174177221251605418301426474191738471931653299099628537592216302521090442291612674220250090663623917575986623108130832502528129647157168707290028664207692539596343502685133605615233575678192994672683899600425651367919262800652478769003262433371189164169086698876897239481110301805575327494730630314230062670467145493663248435642576570039574908319467275999843302907632330828524818095830788274188996932673288182646930739560803236240369311255012922664104459262162533812101040838759847298788136516755214927401958516270479481280238728735341318868544491

平文mの上位bitまたは下位bitがわかっている場合

平文mの一部bitがわかっている場合も、対応する暗号文をもとにmの値を復元することができる。

平文mの上位bitがnのbit数の (1-1/e) 程度わかっているとき、残りのbitを0とした値をmbarとする。対応する暗号文をcとしたとき、f(x) = (mbar + x)^e - c (mod n)の解を求めることで、これを満たすf(x)の値、つまりmを求めることができる。なお、この場合b = nであるからβ = 1となる。

# partial_m.sage

n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
e = 3

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

beta = 1
epsilon = beta^2/7

nbits = n.nbits()
kbits = floor(nbits*(beta^2/e-epsilon))
mbar = m & (2^nbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)

PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c

print m
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n
print mbar + x0

実際に実行してみると、次のようにmの値が復元できていることがわかる。

$ ./sage partial_m.sage
upper 1658 bits (of 2048 bits) is given
4001428855453454091281999218607416935031586048356835681186038264139619035066133182654403737586971808695197035667406868980453804276989723838734168979853630097942716393055362204471823180358268640844695584614952743227808621092828292222308282594714031169256523734278306946407757371005505274890446020731547723992256925110412818796385500005962673933406805713726227061857928867232759144185552380329416435508135864688626771505185119814004512990839538994521493042663210135124304398559131445004143883561400489636718893351706766443146055878866389281166286280831280785114136541136859519247836256246040188223122296424178901997772
4001428855453454091281999218607416935031586048356835681186038264139619035066133182654403737586971808695197035667406868980453804276989723838734168979853630097942716393055362204471823180358268640844695584614952743227808621092828292222308282594714031169256523734278306946407757371005505274890446020731547723992256925110412818796385500005962673933406805713726227061857928867232759144185552380329416435508135864688626771505185119814004512990839538994521493042663210135124304398559131445004143883561400489636718893351706766443146055878866389281166286280831280785114136541136859519247836256246040188223122296424178901997772

上位bitではなく下位bitがわかっている場合も、素数pの場合と同じような多項式を用いることでmの値を復元することができる。

Coppersmith’s Short Pad Attack & Franklin-Reiter Related Message Attack

ここまでの例は求めたい値の一部がすでにわかっていることが前提となっている。その他のパターンとしては、二つの暗号文について平文の上位bitがnのbit数の (1-1/e²) 程度共通する場合、これらからそれぞれの平文を求めることができる。具体的には、次のような手順となる。

g1 = x^e - c1とg2 = (x+y)^e - c2の終結式（resultant）を求め、その根としてyの値を得る
yの値を代入した上でg1(x)とg2(x)の最大公約式を求め、その根としてm1を得る
m2 = m1 + yよりm2を得る

1はCoppersmith’s Short Pad Attack、2はFranklin-Reiter Related Message Attackとして知られている。

SageMathのスクリプトコードを書くと次のようになる。

# coppersmiths_short_pad_attack.sage

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]


if __name__ == '__main__':
    n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
    e = 3

    nbits = n.nbits()
    kbits = nbits//(2*e*e)
    print "upper %d bits (of %d bits) is same" % (nbits-kbits, nbits)

    # ^^ = bit-wise XOR
    # http://doc.sagemath.org/html/en/faq/faq-usage.html#how-do-i-use-the-bitwise-xor-operator-in-sage
    m1 = randrange(2^nbits)
    m2 = m1 ^^ randrange(2^kbits)
    c1 = pow(m1, e, n)
    c2 = pow(m2, e, n)

    diff = short_pad_attack(c1, c2, e, n)
    print "difference of two messages is %d" % diff

    print m1
    m1 = related_message_attack(c1, c2, diff, e, n)
    print m1
    print m2
    print m1 + diff

実際に実行すると、m1、m2それぞれを復元できていることがわかる。

$ ./sage coppersmiths_short_pad_attack.sage
upper 1935 bits (of 2048 bits) is same
difference of two messages is 4388092340502603107865813838945308
13683862597564640002570405911824006430744598828732478219723629281123186571541818575461067997183312125280248651626988519428631697061256568088356422361330075160755675224267970582706266558279346802647127041158083057459412193628357317347212486102742543064641093796453903283450512610012357433196095880957046954606066987535968173037021809120901813347549522912921113358087208581740226612727466045525064361975843656144562820066320916267916544858839889927426347960927691208972781507668278551022918601266361617085369830137399951651172329003621246993109061317951282330374232258850797785354730172654912684496886442788533889814106
13683862597564640002570405911824006430744598828732478219723629281123186571541818575461067997183312125280248651626988519428631697061256568088356422361330075160755675224267970582706266558279346802647127041158083057459412193628357317347212486102742543064641093796453903283450512610012357433196095880957046954606066987535968173037021809120901813347549522912921113358087208581740226612727466045525064361975843656144562820066320916267916544858839889927426347960927691208972781507668278551022918601266361617085369830137399951651172329003621246993109061317951282330374232258850797785354730172654912684496886442788533889814106
13683862597564640002570405911824006430744598828732478219723629281123186571541818575461067997183312125280248651626988519428631697061256568088356422361330075160755675224267970582706266558279346802647127041158083057459412193628357317347212486102742543064641093796453903283450512610012357433196095880957046954606066987535968173037021809120901813347549522912921113358087208581740226612727466045525064361975843656144562820066320916267916544858839889927426347960927691208972781507668278551022918601266361617085369830137399951651172329003621246993109061317951282330374232258850797785354730177043005024999489550654347728759414
13683862597564640002570405911824006430744598828732478219723629281123186571541818575461067997183312125280248651626988519428631697061256568088356422361330075160755675224267970582706266558279346802647127041158083057459412193628357317347212486102742543064641093796453903283450512610012357433196095880957046954606066987535968173037021809120901813347549522912921113358087208581740226612727466045525064361975843656144562820066320916267916544858839889927426347960927691208972781507668278551022918601266361617085369830137399951651172329003621246993109061317951282330374232258850797785354730177043005024999489550654347728759414

ももいろテクノロジー

SageMathを使ってCoppersmith's Attackをやってみる

環境