NTRU暗号

さて、次にNTRU暗号をみていきましょう。

NTRU暗号はJ. Hoffstein, J. Pipher, and J.H. Silvermanの3人によって1990年代後半に提案された公開鍵暗号です。多項式環に基づいており、これまでさまざまな攻撃に耐えてきています。最近、耐量子計算機暗号が盛り上がっていることもあり、注目を集めています。

暗号方式の定義

では、パラメータ設定を振り返ったあとに、アルゴリズムの定義をみて、実装していきます。

パラメータ設定

正整数 $n$ , $q$ について, $\begin{align} R_{n} &:= \mathbb{Z}[x]/(x^n-1) \\ R_{q,n} &:= \mathbb{Z}_q[x]/(x^n-1) \end{align}$ と定義します。また, $R_{n}$ の部分集合として, $\{0,1\}$ 係数多項式のうち係数 $1$ が丁度 $d$ 個ある多項式の集合を $S(n,d)$ と書きます。

In [11]:

# parameters ====================
# NTRU256.2
n,p,q,df,dg,dr=[256,2,127,35,35,22]
# ====================
R.<x>  = ZZ[]
Rq.<x> = Integers(q)[]
Rqn = Rq.quotient(x^n-1)
Rp.<x> = Integers(p)[]
Rpn = Rp.quotient(x^n-1)
# ====================
print "n,p,q", n,p,q
print "df,dg, dr", df, dg, dr

Out[11]:

n,p,q 256 2 127
df,dg, dr 35 35 22

NTRU256.2というのは後で攻撃対象になるパラメータです。当時のNTRU論文では NTRU263.2 n,p,q,df,dg,dr=[263,2,127,35,35,22] 等のパラメータ集合が提案されています。約20年前の設定なので数字が小さいですね。

アルゴリズム詳細

以上のパラメータを用いた場合, NTRU論文によると, $p=2$ のときの鍵の作り方は以下です.

$f \in S(n,d_f)$ と $g \in S(n,d_g)$ をランダムに選ぶ
$f$ が $R_{p,n}$ と $R_{q,n}$ で逆元を持たない場合、1に戻る
$h = g/f \bmod{q}$ とする
$f$ を秘密鍵とする
$h$ を公開鍵とする

暗号化はこんな感じです

$m \in R_{p,n}$ を平文とする
$r \in S(n,d_r)$ をランダムに選ぶ
$c := p * h * r + m \bmod{q}$ とする
$c$ を暗号文とする

復号はこう。

$d := f * c \bmod{q}$ を計算し, $d$ を $R_n$ の多項式だと思う
$m' := d/f \bmod{p}$ を計算する

$d \equiv f * c \equiv p * g * r + m * f \pmod{q}$ なので, $d = pgr + mf$ が整数上でも成立するなら, $m' \equiv d/f \equiv (pgr + mf)/f \equiv mf/f \equiv m \pmod{p}$ として復号できます。 $g, r, m, f$ はすべて $0,1$ 係数の多項式なので、掛けても足しても小さいということで、 $d = prg + mf$ が整数上でも成立します.

実装

実装していきましょう。

$R_{q,n}$ から重み $d$ の多項式を得られます。 sample(range(n),d)で集合 $\{0,\dots,n-1\}$ から $d$ 個重複無しで選んだリストが生成出来るので、これを使って, $S(n,d)$ からのランダム元生成を実現できます。 (random_tpoly(d))

In [12]:

# ランダム多項式の生成
def random_tpoly(d):
    f = R(0)
    for i in sample(range(n),d):
        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(df)
        g = random_tpoly(dg)
    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())

# テスト ====================
# 擬似乱数のシードを0に固定
set_random_seed(0)

f,g = skgen()
h = pkgen(f,g)

# ランダムな平文を作って、暗号化して復号する
m = random_tpoly(int(n/2))
c = enc(h,m)
d = dec(f,c)

# 表示用にh.lift()とRの要素にする
print "pk", h.lift()
print "m", m
print "d", d
print "flag,", m == d

Out[12]:

pk 62*x^255 + 59*x^254 + 29*x^253 + 104*x^252 + 117*x^251 + 107*x^250 + 17*x^249 + 120*x^248 + 89*x^247 + 19*x^246 + 72*x^245 + 122*x^244 + 68*x^243 + 45*x^242 + 7*x^241 + 119*x^240 + 115*x^239 + 61*x^238 + 80*x^237 + 85*x^236 + 118*x^235 + 24*x^232 + 49*x^231 + 65*x^230 + 96*x^229 + 7*x^228 + 103*x^227 + 108*x^226 + 68*x^225 + 42*x^224 + 31*x^223 + 13*x^222 + 24*x^221 + 77*x^220 + 62*x^219 + 91*x^218 + 6*x^217 + 77*x^216 + 47*x^215 + 4*x^214 + 30*x^213 + 76*x^212 + 45*x^211 + 79*x^210 + 79*x^209 + 122*x^208 + 71*x^207 + 123*x^206 + 56*x^205 + 112*x^204 + 63*x^203 + 86*x^202 + 113*x^201 + 75*x^200 + 58*x^199 + 122*x^198 + 124*x^197 + 115*x^196 + 18*x^195 + 109*x^194 + 53*x^193 + 90*x^192 + 27*x^191 + 38*x^190 + 101*x^189 + 107*x^188 + 110*x^187 + 100*x^186 + 105*x^185 + 91*x^184 + 69*x^183 + 106*x^182 + 123*x^181 + 112*x^180 + 99*x^179 + 82*x^178 + 47*x^177 + 93*x^176 + 94*x^175 + 17*x^174 + 67*x^173 + 108*x^172 + 15*x^171 + 106*x^170 + 69*x^169 + 67*x^168 + 125*x^167 + 48*x^166 + 73*x^165 + 64*x^164 + 84*x^163 + 63*x^162 + 104*x^161 + 40*x^160 + 104*x^159 + 98*x^158 + 51*x^157 + 101*x^156 + 40*x^155 + 73*x^154 + 2*x^153 + 11*x^152 + 113*x^151 + 117*x^150 + 51*x^149 + 95*x^148 + 98*x^147 + 97*x^146 + 28*x^145 + 109*x^144 + 49*x^143 + 41*x^142 + 121*x^141 + 98*x^140 + 50*x^139 + 118*x^138 + 82*x^137 + 93*x^136 + 56*x^135 + 63*x^134 + 116*x^133 + 64*x^132 + 103*x^131 + 100*x^130 + 11*x^129 + 25*x^128 + 16*x^127 + 36*x^126 + 45*x^125 + 38*x^124 + 54*x^123 + 108*x^122 + 58*x^120 + 43*x^119 + 104*x^118 + 62*x^117 + 123*x^116 + 9*x^115 + 95*x^114 + 71*x^113 + 37*x^112 + 94*x^111 + 18*x^110 + 53*x^109 + 84*x^108 + 104*x^107 + 24*x^106 + 54*x^105 + 92*x^104 + 13*x^103 + 46*x^102 + 100*x^101 + 114*x^100 + 17*x^99 + 20*x^98 + 118*x^97 + 98*x^96 + 111*x^95 + 31*x^94 + 18*x^93 + x^92 + 106*x^91 + 5*x^90 + 5*x^89 + 69*x^88 + 125*x^87 + 28*x^86 + 12*x^85 + 91*x^84 + 82*x^83 + 69*x^82 + 42*x^81 + 14*x^80 + 75*x^79 + 53*x^78 + 96*x^77 + 18*x^76 + 32*x^75 + 109*x^74 + 109*x^73 + 74*x^72 + 34*x^71 + 13*x^70 + 70*x^69 + 4*x^68 + 111*x^67 + 83*x^66 + 22*x^65 + 13*x^64 + 108*x^63 + 54*x^62 + 11*x^61 + x^60 + 10*x^59 + 25*x^58 + 83*x^57 + 31*x^56 + 37*x^55 + 18*x^54 + 102*x^53 + 112*x^52 + 5*x^51 + 60*x^50 + 3*x^49 + 70*x^48 + 121*x^46 + 109*x^45 + 108*x^44 + 10*x^43 + 28*x^42 + 62*x^41 + 18*x^40 + 49*x^39 + 34*x^38 + 76*x^37 + 116*x^36 + 73*x^35 + 123*x^34 + 85*x^33 + 119*x^32 + 47*x^31 + 62*x^30 + 106*x^29 + 26*x^28 + 123*x^27 + 75*x^26 + 16*x^25 + 82*x^24 + 10*x^23 + 72*x^22 + 105*x^21 + 56*x^19 + 121*x^18 + 43*x^17 + 57*x^16 + 103*x^15 + 114*x^14 + 104*x^13 + 10*x^12 + 78*x^11 + 107*x^10 + 17*x^9 + 118*x^8 + 52*x^7 + 22*x^6 + 83*x^5 + 105*x^4 + 3*x^3 + 83*x^2 + 74*x + 51
m x^248 + x^247 + x^246 + x^244 + x^243 + x^242 + x^241 + x^240 + x^239 + x^235 + x^233 + x^229 + x^228 + x^227 + x^226 + x^225 + x^220 + x^219 + x^218 + x^217 + x^216 + x^215 + x^213 + x^209 + x^208 + x^207 + x^206 + x^204 + x^203 + x^202 + x^201 + x^199 + x^192 + x^191 + x^190 + x^189 + x^188 + x^181 + x^179 + x^176 + x^175 + x^171 + x^168 + x^167 + x^164 + x^162 + x^161 + x^160 + x^159 + x^158 + x^155 + x^153 + x^152 + x^149 + x^148 + x^147 + x^145 + x^140 + x^135 + x^134 + x^132 + x^129 + x^122 + x^118 + x^117 + x^116 + x^115 + x^112 + x^111 + x^110 + x^106 + x^103 + x^102 + x^98 + x^97 + x^96 + x^94 + x^93 + x^91 + x^90 + x^88 + x^87 + x^86 + x^84 + x^83 + x^82 + x^81 + x^79 + x^78 + x^77 + x^70 + x^69 + x^68 + x^67 + x^64 + x^62 + x^56 + x^55 + x^51 + x^47 + x^44 + x^43 + x^40 + x^36 + x^35 + x^34 + x^31 + x^30 + x^28 + x^26 + x^25 + x^23 + x^22 + x^21 + x^20 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^5 + x^4 + x^3
d x^248 + x^247 + x^246 + x^244 + x^243 + x^242 + x^241 + x^240 + x^239 + x^235 + x^233 + x^229 + x^228 + x^227 + x^226 + x^225 + x^220 + x^219 + x^218 + x^217 + x^216 + x^215 + x^213 + x^209 + x^208 + x^207 + x^206 + x^204 + x^203 + x^202 + x^201 + x^199 + x^192 + x^191 + x^190 + x^189 + x^188 + x^181 + x^179 + x^176 + x^175 + x^171 + x^168 + x^167 + x^164 + x^162 + x^161 + x^160 + x^159 + x^158 + x^155 + x^153 + x^152 + x^149 + x^148 + x^147 + x^145 + x^140 + x^135 + x^134 + x^132 + x^129 + x^122 + x^118 + x^117 + x^116 + x^115 + x^112 + x^111 + x^110 + x^106 + x^103 + x^102 + x^98 + x^97 + x^96 + x^94 + x^93 + x^91 + x^90 + x^88 + x^87 + x^86 + x^84 + x^83 + x^82 + x^81 + x^79 + x^78 + x^77 + x^70 + x^69 + x^68 + x^67 + x^64 + x^62 + x^56 + x^55 + x^51 + x^47 + x^44 + x^43 + x^40 + x^36 + x^35 + x^34 + x^31 + x^30 + x^28 + x^26 + x^25 + x^23 + x^22 + x^21 + x^20 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^5 + x^4 + x^3
flag, True

m == dとなり, 無事に復号できました。

Coppersmith-Shamir攻撃

NTRUはCRYPTO 1996のランプセッションで公開され、論文自体はANTS1998で出版されています。 CoppersmithとShamirによる攻撃論文が、EUROCRYPT __1997__に採択されています (Lattice Attacks on NTRU | SpringerLink)。

格子

Lattice Attacksというからには Lattice (格子) を使っています。基底ベクトル $b_1,\dots,b_n$ を適当な整数係数で足したベクトル全体の集合を格子と呼びます。すなわち, $\Lambda = \{ \sum_i w_i b_i \mid w_i \in \mathbb{Z}\}$ が格子です。あ、この稿ではベクトルはすべて列ベクトルです。

鍵の関係式

NTRU暗号の鍵をみると, $h = g/f \bmod{q}$ という関係があります。

CoppersmithとShamirは $H$ を $h$ に対応する巡回行列として, $L = \begin{pmatrix} I_n & H \\ O_n & q I_n \end{pmatrix} \in \mathbb{Z}^{2n \times 2n}$ という行列の列ベクトルを基底とする格子を考えたときに, $(f,g)$ というベクトルがこの格子に含まれることに気づきました。

具体的な計算は以下です。

鍵の関係式から, $hf \equiv g \pmod{q}$ が成立
なので, ある $k \in R_n$ が存在して, $hf = g + qk$
よって, $hf - qk = g$
これと基底 $L$ を考えると, $(f,-k) L = (f, fh) + (0, -k q) = (f,g)$ より, $(f,g)$ は $L$ が張る格子に含まれる.

LLLやBKZといった格子基底縮小アルゴリズムと呼ばれるアルゴリズムを使うと、格子の基底を与えられたときに（そこそこ）短いベクトルを探せることが多いです。

$L$ を格子基底縮小アルゴリズムに掛けて短いベクトルを探してやると, それが $(f,g)$ なり $(f*x^i,g*x^{n-i})$ であることが期待できます。

これを実装してみましょう。

In [18]:

def vectorize(f,n):
    return vector(ZZ,[f.monomial_coefficient(R(x^i)) for i in range(n)])

def vec_to_poly(z):
    tmp = R(0)
    for i in range(len(z)):
        tmp += R(z[i]*x**i)
    return tmp

def circulant_matrix(f,n):
    return matrix(ZZ,n,n,lambda i,j: f.monomial_coefficient(R(x^((j-i) % n))))

# g = h * f mod qのL1ﾉﾙﾑがdgに一致するかどうかチェック
def check_g(h,f):
    return vectorize((h*Rqn(f)).lift().change_ring(ZZ),n).norm(1) == dg

# 公開鍵から格子の基底を作る関数 (Coppersmith and Shamirが提案)
def CS(h,n):
    Id = identity_matrix(n)
    Ze = zero_matrix(n)
    HH = circulant_matrix(h.lift().change_ring(ZZ),n)
    return block_matrix(ZZ,2,2,[Id,HH,Ze,q*Id])

def find_fv(h):
    # 基底を得て、それを格子基底簡約アルゴリズム (今回はBKZ) で簡約する
    L = CS(h,n)
    L = L.BKZ()

    # Lの横ベクトルを(f,g)と思って, fに対応するベクトルのL1ノルムがdfに等しいなら採用
    fv_candidates = []
    for i in range(2*n):
        fv = L[i][0:n]
        if fv.norm(1) == df:
            if min(fv.list()) >= 0:
                fv_candidates.append(fv)
            if max(fv.list()) <= 0:
                fv_candidates.append(-fv)
    if len(fv_candidates) == 0:
        raise ValueError('Oops, I cannot find any fv_candidates')
    else:
        return fv_candidates
    
def test_CS(seed,debug=true):
    set_random_seed(seed)
    f,g = skgen()
    h = pkgen(f,g)
    print h
    
    # Find fv
    if debug:
        print "start find_fv"
    try:
        fv_candidates = find_fv(h)
    except ValueError as err:
        print("Value Error: {0}".format(err))
    if debug:
        print "end find_fv"

    # f0s is a list of polynomials f0's in R = ZZ[x]
    f0s = [vec_to_poly(fv_candidates[i]) for i in range(len(fv_candidates))]
    # check_gでフィルター
    f0s = [f0 for f0 in f0s if check_g(h,f0)]
    return f,g,h,f0s

# 今回のパラメータ設定ではCS攻撃はうまくいかない
# print "!!! Start !!!"
# %time f,g,h,f0s = testCS(0,true)
# for i in range(len(f0s)):
#    print "i:", i
#    print "fi:", f0s[i]
#    print "gi:", R((h*Rqn(f0s[i])).lift())
# print "!!! End !!!"

NTRU暗号

暗号方式の定義

パラメータ設定

アルゴリズム詳細

実装

Coppersmith-Shamir攻撃

格子

鍵の関係式

Product

Resources

Company