SharedNTRU-Composite.ipynbOpen in CoCalc
Author: Keita Xagawa
Views : 18
Description: Implementation of Gentry's Attack against NTRU-Composite

Gentry攻撃

最後に dblp: Craig Gentryの2001年の論文である Key Recovery and Message Attacks on NTRU-Composite (pdf) の攻撃方法を実装してみます。

前置き

SilvermanはNTRU Tech. Rep. #11 の中で, nを2の冪にするとFFTが使えるので、暗号化・復号が高速化出来るだろう、と述べました。

それに対してGentryが新しい攻撃を提案し、(当時の技術で)実装し、 NTRU256.2というパラメータセットでも秘密鍵回復攻撃が成功することを示しました。 以下ではこの秘密鍵回復攻撃を追試してみます。

アイデア

nn256256ということは, 非自明な約数ddを持ちます。 例えばd=64d = 64としましょう。 すると, xn1x^n-1xd1x^d-1で割り切れます。 θ ⁣:RnRd\theta \colon R_{n} \to R_{d}

θ(i=0n1fixi):=i=0n1fiximodxd1=i=0d1j=0n/d1fjd+ixi \theta(\sum_{i=0}^{n-1} f_i x^i) := \sum_{i=0}^{n-1} f_i x^i \bmod{x^d - 1} = \sum_{i=0}^{d-1} \sum_{j=0}^{n/d-1} f_{jd+i} x^i

と定義すると, これは環準同型です。

環準同型性のチエック

n=10n = 10, d=5d = 5で試してみます。

In [8]:
Rq.<x> = Integers(127)[] Rqn.<xx> = Rq.quotient(x^10-1) Rqd.<xx> = Rq.quotient(x^5-1) f = Rqn(1 + x^2 + x^3) g = Rqn(2 + x^1 + x^6) print "Addition" print f + g print Rqd(f + g) print Rqd(f) + Rqd(g) print "Multiplication" print f * g print Rqd(f * g) print Rqd(f) * Rqd(g)
Addition xx^6 + xx^3 + xx^2 + xx + 3 xx^3 + xx^2 + 2*xx + 3 xx^3 + xx^2 + 2*xx + 3 Multiplication xx^9 + xx^8 + xx^6 + xx^4 + 3*xx^3 + 2*xx^2 + xx + 2 2*xx^4 + 4*xx^3 + 2*xx^2 + 2*xx + 2 2*xx^4 + 4*xx^3 + 2*xx^2 + 2*xx + 2

環準同型性が確認できました。

鍵の関係式

Coppersmith-Shamir攻撃法では 鍵の関係式 hf+qk=gh f + q k = g から格子の基底を作成していました。 この関係式に準同型写像θ\thetaを適用すると, θ(h)θ(f)+qθ(k)=θ(g)\theta(h) \cdot \theta(f) + q \theta(k) = \theta(g) となります。 自然なアイデアとして,

Ld=(IdHdOdqId)Z2d×2d L_d = \begin{pmatrix} I_d & H_d \\ O_d & q I_d \end{pmatrix} \in \mathbb{Z}^{2d \times 2d}

を考えます。 (θ(f),θ(k))Ld=...=(θ(f),θ(g))(\theta(f),\theta(k)) L_d = ... = (\theta(f),\theta(g)) となり, (θ(f),θ(g))(\theta(f),\theta(g))も小さくなった格子に含まれます。

さて、この環準同型は f=f0+f1xd+f2x2d+f3x3df = f_0 + f_1 x^d + f_2 x^{2d} + f_3 x^{3d}というfRnf \in R_{n}θ(f)=f0+f1+f2+f3Rd\theta(f) = f_0 + f_1 + f_2 + f_3 \in R_dに写しています。 よって, θ(f)(n/d)f\lVert \theta(f) \rVert_{\infty} \leq (n/d) \lVert f \rVert_{\infty} が分かります。 秘密鍵ff0,10,1係数なので, θ(f)\lVert \theta(f)\rVert_{\infty}は高々44ですし, θ(f)1=df\lVert \theta(f) \rVert_{1} = d_fです。

まとめると, 2d2d次元に小さくなった基底LdL_dが張る格子の中に、まだまだ短いベクトル(θ(f),θ(g))(\theta(f),\theta(g))が含まれています。 これなら格子基底縮小アルゴリズムで見つけられそうです。

こうして小さい格子から秘密鍵の情報を求め、 それを大きい格子から秘密鍵を求める際のヒントとして用いるというのがGentry攻撃のアイデアです。

実装

d1=128d1 = 128d2=64d2 = 64と非自明な約数ddを二つ使うので, それぞれに環を定義していきます。

In [9]:
# ==================== # parameters # ==================== debug = false n,p,q,df,dg,dr=[256,2,127,35,35,22] d2 = int(n/4) d1 = int(n/2) R.<x> = ZZ[] Rq.<x> = Integers(q)[] Rqn = Rq.quotient(x^n-1) Rqd2 = Rq.quotient(x^d2-1) Rqd1 = Rq.quotient(x^d1-1) Rp.<w> = Integers(p)[] Rpn = Rp.quotient(w^n-1) # ==================== # NTRU # ==================== def random_tpoly(p): f = R(0) for i in sample(range(n),df): f += R(x**i) return f def skgen(): f,g = [0,0] while not Rpn(f).is_unit() or not Rqn(f).is_unit(): f = random_tpoly(p) g = random_tpoly(p) return f,g def pkgen(f,g): h = Rqn(g)/Rqn(f) return h def enc(h,m): r = random_tpoly(dr) c = p * h * Rqn(r) + Rqn(m) return c def dec(f,c): d = (c * Rqn(f)).lift() m = Rpn(d)/Rpn(f) return R(m.lift()) # ==================== # Attack # ==================== def vectorize(b,n): return vector(ZZ,[b.monomial_coefficient(R(x^i)) for i in range(n)]) def circulant_matrix(b,n): return matrix(ZZ,n,n,lambda i,j: b.monomial_coefficient(R(x^((j-i) % n)))) def vec_to_poly(z): tmp = R(0) for i in range(len(z)): tmp += R(z[i]*w**i) return tmp def check_g(h,f): return vectorize((h*Rqn(f)).lift().change_ring(ZZ),n).norm(1) == dg # ==================== # Gentry's attack # ==================== # d2次元に圧縮されたfを探す def CS2(h): Id = identity_matrix(d2) Ze = zero_matrix(d2) HH = circulant_matrix(Rqd2(h).lift().change_ring(ZZ),d2) return block_matrix(ZZ,2,2,[Id,HH,Ze,q*Id]) def find_fv2(h,debug=false): L2 = CS2(h) L2 = L2.BKZ() fv2_candidates = [] for i in range(d1): fv2 = L2[i][0:d2] if fv2.norm(1) == df: if min(fv2.list()) >= 0: fv2_candidates.append(fv2) if max(fv2.list()) <= 0: fv2_candidates.append(-fv2) if len(fv2_candidates) == 0: raise ValueError('Oops, I cannot find any fv2_candidates') else: return fv2_candidates # d2次元に圧縮されたヒントからd1次元に復元する def CS2to1(h,fd): HH = circulant_matrix(Rqd1(h).lift().change_ring(ZZ),d1) t = vector(ZZ,list(zero_vector(d2))+list(fd)) * HH Hnew = block_matrix(ZZ,[[identity_matrix(d2),-identity_matrix(d2)]]) * HH CS1 = block_matrix([\ [identity_matrix(d2),Hnew],\ [zero_vector(d2).row(),t.row()],\ [zero_matrix(d1,d2),q*identity_matrix(d1)]\ ]) return CS1[0:(d1+1),0:d1] def find_fv1(h,fv2,debug=false): L1 = CS2to1(h,fv2) L1 = L1.BKZ() fv1_candidates = [] # range(1,d1+1) because L1[0] = 0 for i in range(1,L1.nrows()): fv1 = zero_vector(d1) fv1_left = L1[i][0:d2] if max(fv1_left.list()) <= 0: fv1_left = -fv1_left if min(fv1_left.list()) >= 0: fv1 = vector(ZZ,list(fv1_left)+list(fv2-fv1_left)) if fv1.norm(1) == df: fv1_candidates.append(fv1) if len(fv1_candidates) == 0: raise ValueError('Oops, I cannot find any fv1_candidates') else: return fv1_candidates # d1次元に圧縮されたヒントからn次元に復元する def CS1to0(h,fd): HH = circulant_matrix(Rqn(h).lift().change_ring(ZZ),n) t = vector(ZZ,list(zero_vector(d1))+list(fd))*HH; Hnew = block_matrix(ZZ,[[identity_matrix(d1),-identity_matrix(d1)]]) * HH CS0 = block_matrix([\ [identity_matrix(d1),Hnew],\ [zero_vector(d1).row(),t.row()],\ [zero_matrix(n,d1),q*identity_matrix(n)]\ ]) return CS0[0:(n+1),0:n] def get_supports_of_0(z): s0 = [] for i in range(len(z)): if z[i] == 0: s0.append(i) return s0 def find_fv0(h,fv1,debug=false): supports_of_0 = get_supports_of_0(fv1) # Gentryの勧めに従って, fv1の係数が0の場合、その列ベクトルは使わないので、消す L0 = CS1to0(h,fv1).delete_rows(supports_of_0) # デフォルトはblock_size=10だが遅くなるので, 5に変更。精度が必要らしいのでlong doubleを使うよう設定 L0 = L0.BKZ(block_size=5,fp='ld') fv0_candidates = [] for i in range(1,L0.nrows()): fv0 = zero_vector(n) fv0_left = L0[i][0:d1] if max(fv0_left.list()) <= 0: fv0_left = -fv0_left if min(fv0_left.list()) >= 0: fv0 = vector(ZZ,list(fv0_left)+list(fv1-fv0_left)) if fv0.norm(1) == df: fv0_candidates.append(fv0) if len(fv0_candidates) == 0: raise ValueError('Oops, I cannot find any fv0_candidates') else: return fv0_candidates # 攻撃本体 def test(seed,debug=false): set_random_seed(seed) f,g = skgen() h = pkgen(f,g) # Find fv2 if debug: print "start find_fv2" try: fv2_candidates = find_fv2(h) except ValueError as err: print("Value Error: {0}".format(err)) if debug: print "end find_fv2" fv2 = fv2_candidates[0] # Find fv1 if debug: print "start find_fv1" try: fv1_candidates = find_fv1(h,fv2) except ValueError as err: print("Value Error: {0}".format(err)) if debug: print "end find_fv1" fv1 = fv1_candidates[0] # Find fv0 if debug: print "start find_fv0" try: fv0_candidates = find_fv0(h,fv1) except ValueError as err: print("Value Error: {0}".format(err)) if debug: print "end find_fv0" # f0s is a list of polynomials f0's in R = ZZ[x] f0s = [vec_to_poly(fv0_candidates[i]) for i in range(len(fv0_candidates))] f0s = [f0 for f0 in f0s if check_g(h,f0)] return f,g,h,f0s print "n,p,q", n,p,q print "df,dg,dr", df, dg, dr print "d1,d2", d1,d2 # %time ... で時間を計測 %time f,g,h,f0s = test(0,true) for i in range(len(f0s)): print "i:", i print "fi:", f0s[i] print "gi:", (h*Rqn(f0s[i])).lift().change_ring(ZZ) print "!!!! End !!!!"
n,p,q 256 2 127 df,dg,dr 35 35 22 d1,d2 128 64 start find_fv2 end find_fv2 start find_fv1 end find_fv1 start find_fv0 end find_fv0 CPU times: user 44.5 s, sys: 243 ms, total: 44.8 s Wall time: 46.4 s i: 0 fi: x^251 + x^234 + x^229 + x^226 + x^220 + x^219 + x^218 + x^208 + x^198 + x^190 + x^186 + x^184 + x^162 + x^159 + x^157 + x^152 + x^143 + x^140 + x^138 + x^128 + x^125 + x^107 + x^105 + x^93 + x^79 + x^68 + x^67 + x^54 + x^45 + x^37 + x^32 + x^28 + x^20 + x^7 + 1 gi: x^254 + x^253 + x^247 + x^243 + x^241 + x^236 + x^231 + x^229 + x^214 + x^213 + x^210 + x^206 + x^203 + x^202 + x^198 + x^176 + x^170 + x^162 + x^151 + x^140 + x^135 + x^120 + x^110 + x^106 + x^105 + x^104 + x^100 + x^99 + x^63 + x^55 + x^51 + x^34 + x^25 + x^23 + x^6 i: 1 fi: x^253 + x^235 + x^233 + x^221 + x^207 + x^196 + x^195 + x^182 + x^173 + x^165 + x^160 + x^156 + x^148 + x^135 + x^128 + x^123 + x^106 + x^101 + x^98 + x^92 + x^91 + x^90 + x^80 + x^70 + x^62 + x^58 + x^56 + x^34 + x^31 + x^29 + x^24 + x^15 + x^12 + x^10 + 1 gi: x^248 + x^238 + x^234 + x^233 + x^232 + x^228 + x^227 + x^191 + x^183 + x^179 + x^162 + x^153 + x^151 + x^134 + x^126 + x^125 + x^119 + x^115 + x^113 + x^108 + x^103 + x^101 + x^86 + x^85 + x^82 + x^78 + x^75 + x^74 + x^70 + x^48 + x^42 + x^34 + x^23 + x^12 + x^7 !!!! End !!!!

無事にfi, giが復元できました。 f0s[0]f0s[1]で復号できるかどうか確かめてみます。

In [11]:
# ランダムな平文を作って、暗号化して復号する m = random_tpoly(int(n/2)) c = enc(h,m) print "m:", m for i in range(len(f0s)): d = dec(f0s[i],c) print "i:", i print "d:", d print "flag,", d == m
m: x^253 + x^251 + x^248 + x^245 + x^235 + x^232 + x^224 + x^219 + x^213 + x^203 + x^191 + x^156 + x^151 + x^148 + x^147 + x^135 + x^129 + x^118 + x^117 + x^95 + x^94 + x^87 + x^79 + x^72 + x^51 + x^50 + x^49 + x^45 + x^36 + x^29 + x^23 + x^21 + x^19 + x^16 + x^7 i: 0 d: x^253 + x^251 + x^248 + x^245 + x^235 + x^232 + x^224 + x^219 + x^213 + x^203 + x^191 + x^156 + x^151 + x^148 + x^147 + x^135 + x^129 + x^118 + x^117 + x^95 + x^94 + x^87 + x^79 + x^72 + x^51 + x^50 + x^49 + x^45 + x^36 + x^29 + x^23 + x^21 + x^19 + x^16 + x^7 flag, True i: 1 d: x^253 + x^251 + x^248 + x^245 + x^235 + x^232 + x^224 + x^219 + x^213 + x^203 + x^191 + x^156 + x^151 + x^148 + x^147 + x^135 + x^129 + x^118 + x^117 + x^95 + x^94 + x^87 + x^79 + x^72 + x^51 + x^50 + x^49 + x^45 + x^36 + x^29 + x^23 + x^21 + x^19 + x^16 + x^7 flag, True

本来の秘密鍵とはずれていますが、ちゃんと復号出来ることがわかります。

h=g/fh = g/fなので, 任意のiih=(gxi)/(fxi)h = (g x^i)/(f x^i)が成立します。 よって fxif x^iも秘密鍵になっています。今回はこれを二つ引いてきたことがわかります。

In [13]:
for i in range(len(f0s)): print Rqn(f0s[i])/Rqn(f)
xbar^9 xbar^137