Pascal Paillierが提案した加法準同型をもつPaillier暗号について.
元論文を読んだのでまとめてみる.
が, 基本的な内容に関してはelliptic-shiho先生の記事を読むことで理解できる.
elliptic-shiho.hatenablog.com
カーマイケルの定理
Paillier暗号ではカーマイケルの定理が登場する.
これはオイラーの定理とよく似ていて, nを法として以下の式で表される. (ただしaとnは互いに素)
aλ(n) ≡ 1 (mod n)
λ(n)はカーマイケルのλ関数であり, こちらもオイラーのφ関数と似ている.
φ関数を使うと
aφ(n) ≡ 1 (mod n)
aをx乗して1と合同になる値(x)を得ることができるが, このxが最小とは限らない(aによって作られる部分群の位数がφ(n)ではないことを意味している).
λ関数はφ関数をより厳密にしたもので, 最小のxを得ることができる.
RSAではよくオイラーが登場する(個人の見解)が, カーマイケルを使って解説している場合もあるので覚えておくと良い.
少し脱線
RSAにおいてp, qは大きな素数であり, λ, φの入力をn(=p*q)として
φ(n) = (p-1)*(q-1)
λ(n) = LCM(p-1, q-1)
このように得られる.
LCMとGCDの関係をx, yを使って表し.
LCM(x, y) * GCD(x, y) = x * y
x, y をそれぞれp-1, q-1とすれば
LCM(p-1, q-1) = (p-1)*(q-1) / GCD(p-1, q-1)
= φ(n) / GCD(p-1, q-1)
p, qが大きな素数であるということはGCD(p-1, q-1)は最小でも2になる.
λ(n) <= φ(n) / 2
λ(n)がφ(n)よりも小さいことが示せた.
話を戻す
Paillier暗号では法をn2としてカーマイケルの定理を使用しているので,
ax ≡ 1 (mod n2) を満たすxはλ(n)ではなく以下のようになる.
anλ(n) ≡ 1 (mod n2)
これを示すには
λ(n2) = nλ(n)
であることが言えればよい.
λ(n2) = λ(p2 * q2)
= LCM(λ(p2), λ(q2))
= LCM(p2-1(p-1), q2-1(q-1))
= LCM(p(p-1), q(q-1))
ここでp, qは互いに素な大きな素数であり, LCMの計算に関与しないため外に出せる.
LCM(p(p-1), q(q-1))
= pq * LCM(p-1, q-1)
= n * λ(n)
これで示せた.
ちなみにオイラーの定理でも同様に法をn2として
anφ(n) ≡ 1 (mod n2)
これを示すには
φ(n2) = nφ(n)
であればよく, こちらも愚直に計算すると
φ(n2) = φ(p2 * q2)
= (p2 - p1) * (q2 - q1)
= p(p-1) * q(q-1)
= pq * (p-1)(q-1)
= n * φ(n)
となるので正しい.
次の節からPaiiler暗号の鍵生成から暗号化/復号の話をする.
Key Generation
2つの大きな素数p, qを選び, n = p*q とする.
Z_nの元を1つ選びこれをkとし, g = (k*n + 1) mod n2 とする.
公開鍵 : (n, g)
秘密鍵 : (p, q)
Encrypt
Z_n2の元を1つ選び r とする. このrは暗号化のたびに変わる.
平文mの暗号化は以下のように定義される.
Enc(m) := gm * rn mod n2
※平文空間はZ_nだが, 暗号文空間はZ_n2である.
Decrypt
復号は以下のように定義される.
Dec(c) := L(cλ mod n2) * L(gλ mod n2)-1 mod n
ここで
L(u) = (u-1)/n
λ = LCM(p-1, q-1)
λはλ(n)の略記である.
再掲 : ※平文空間はZ_n, 暗号文空間はZ_n2
-> 暗号化では mod n2 が, 復号では mod n になっている.
では Dec(c) = m になることを確認していこう.
cλ = (gm * rn)λ mod n2
= gmλ * rnλ mod n2
= gmλ mod n2
= (1 + kn)mλ mod n2
rnλ mod n2 はカーマイケルの定理により1である.
(1 + kn)mλ mod n2 は二項定理を使って展開し, mod n2 であることに注意すると n2 を因数に持つ項が綺麗に消えるので
(1 + kn)mλ mod n2 = 1 + mλkn
が得られる.
これをL関数に適用し, L(gλ mod n2)も同じように計算する.
L(cλ mod n2) = L(1 + mkλn mod n2)
= ((1 + mkλn) - 1) / n
= mkλL(gλ mod n2) = L((1 + kn)λ mod n2)
= L(1 + kλn mod n2)
= ((1 + kλn) - 1) / n
= kλ
最後に
L(cλ mod n2) * L(gλ mod n2)-1 mod n
= mkλ * (kλ)-1 mod n
= m
これで平文が復号できた.
検証コード
以上を踏まえて検証.
最後に加法準同型であることを確認している.
まとめ
(暗号化, 復号の部分はやっぱり先生の記事読むのが手っ取り早いんだよなぁ)
個人的にPaiilier暗号で好きなのは平文が1であっても暗号文が1にならない点.
plain RSAでは平文をe乗するので平文が1ならどうあがいても暗号文が1になってしまうが, Paiilerでは(1+kn)を平文乗するので平文が1でも暗号文が1になるとは限らない.
参考文献
公開鍵暗号 - Paillier暗号 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes https://link.springer.com/chapter/10.1007/3-540-48910-X_16
カーマイケルのλ関数
Carmichael function - Wikipedia
