はじめに
Wikipediaにあるとおり、Pascal Paillierが1999年に提案した公開鍵暗号方式です。
因みに、カタカナで表すと__ペイエ__暗号と言うらしいです。（エルどこいった？）
特徴としては、__加法準同型性__という性質を持っています。
これについては別途説明しますが、簡単に言うと、暗号分の積を複合化すると暗号前のデータの和と等しくなります。
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Paillier cryptosystem - Wikipedia
Paillier暗号 - Wikipedia
₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです
Paillier暗号(Paillier cryptosystem)
アルゴリズム(Algorithm)
鍵生成(Key generation)
2つの大きい素数$\ p,q$を求め、$\ n=p\times q$とします。
$\ \lambda$を、$\lambda=\text{lcm}(p-1,q-1)$とします。
これは、カーマイケル定理で求めた値なので、$a,n$が互いに素である場合、$a^\lambda \equiv 1 \pmod n$となります。
関数$\ \text{L}(u)\ $を以下とします。
\begin{align*}
\text{L}(u) = \frac{u-1}{n}
\end{align*}
$\ n^2$と互いに素である、$g$を選択します。
$\gcd(\text{L}(g^\lambda \bmod n^2),n)=1$が成り立たなければ、再度$g$を選択します。
$g$が選択されたら$\ \mu$を求めます。
$\ \mu = \{\text{L}(g^\lambda \bmod n^2)\}^{-1} \bmod n\ $とします。
- 公開鍵（暗号化）：$\ (g,n)$
- 秘密鍵（復号化）：$\ (p,q)$
暗号化(Encryption)
$m$はメッセージで、$\ 0\le m < n$とします。
$n$と互いに素である、$r$を選択します。
暗号文$\ c = g^m\cdot r^n \bmod n^2$を生成します。
この公開鍵$\ (g,n)$に対する暗号化を、$c= \mathcal{E}_g(m,r)$とします。
復号化(Decryption)
$\ c$ は暗号文で、$0\le c < n^2$とします。
以下の計算でメッセージが復元されます。
\begin{align*}
m = \frac{\text{L}(c^\lambda \bmod n^2)}{\text{L}(g^\lambda \bmod n^2)} \bmod n
\end{align*}
あらかじめ、$\mu$を求めているので、$\ m=\text{L}(c^\lambda \bmod n^2)\cdot \mu \bmod n\ $で求められます。
この秘密鍵$(p,q,\lambda,\mu)\ $に対する暗号化を、$\ m=\mathcal{D}_g(c)$とします。
準同型(Homomorphic properties)
このPaillier暗号の特徴的な準同型の性質をみてみます。
平文の準同型加法(Homomorphic addition of plaintexts)
暗号文の積を複合すると、メッセージの和になります。
\begin{align*}
& \mathcal{E}_g(m_1,r_{1}) = c_1 \\
& \mathcal{E}_g(m_2,r_{2}) = c_2 \\
& \mathcal{D}_g(c_1\cdot c_2 \bmod n^2) = m_1 + m_2 \\
\end{align*}
平文の準同型乗法(Homomorphic multiplication of plaintexts)
暗号文をメッセージで冪乗すると、メッセージの積になります。
\begin{align*}
& \mathcal{E}_g(m_1,r_{1}) = c_1 \\
& \mathcal{D}_g(c_1^{m_2} \bmod n^2) = m_1 \times m_2 \\
& \\
& \mathcal{E}_g(m_2,r_{2}) = c_2 \\
& \mathcal{D}_g(c_2^{m_1} \bmod n^2) = m_2 \times m_1 \\
\end{align*}
解説
詳しい説明は、はじめににあるリンク先を参照ください。ここでは、簡単に解説します。
各所に互いに素という文言が出てきますが、これは最大公約数が1である事を言います。
お互いを素因数分解した時に、同じ素数の項を持ちません。
したがって、$\ n$で互いに素であれば、$n^2$でも互いに素となります。
鍵生成(Key generation)
$\mu = \{\text{L}(g^\lambda \bmod n^2)\}^{-1}$を考えてみます。
$\ g$は、$n^2$と互いに素なので、$n$とも互いに素となります。
カーマイケルの定理により、$\ g^\lambda \equiv 1 \bmod n\ $となるので、
$\ g^\lambda = kn + 1$と表す事が出来ます。
\begin{align*}
\text{L}(g^\lambda \bmod n^2) &= \text{L}(1+kn) \\
&= \frac{1+kn-1}{n} \\
&= \frac{kn}{n} \\
&= k \\
\end{align*}
$\ g$生成時に、$\text{L}(g^\lambda \bmod n^2)$と$n$が互いに素である事を確認しているので、$\ n,k$も互いに素となります。
モジュラ逆数は互いに素であれば存在するので、$\mu = k^{-1} \bmod n$も求める事が出来ます。
暗号化(Encryption)、復号化(Decryption)
暗号文$c$から、$\text{L}(c^\lambda \bmod n^2)$を求めます。
途中、二項定理で分解すると$n^2$が消えていきます。
\begin{align*}
c^\lambda \bmod n^2 &= (g^m\cdot r^n)^\lambda \bmod n^2 \\
&= g^{\lambda m}\cdot r^{\lambda n} \bmod n^2 \\
&= (g^\lambda)^m \cdot (r^{\lambda})^n \bmod n^2 \\
&= (1 + kn)^m \cdot (1 + k'n)^n \bmod n^2 \\
&= (1 +\ _mC_1kn +\ _mC_2k^2n^2 + \cdots + k^mn^m) \\
& \quad \cdot (1 +\ _nC_1k'n +\ _nC_2k'^2n^2 + \cdots + k'^nn^n) \bmod n^2 \\
&= (1 +mkn +\ _mC_2k^2n^2 + \cdots + k^mn^m \bmod n^2) \\
& \quad \cdot (1 + nk'n +\ _nC_2k'^2n^2 + \cdots + k_r^nn^n \bmod n^2) \bmod n^2 \\
&= (1 +mkn)\cdot (1) \bmod n^2 \\
&= 1 +mkn \\
& \\
\text{L}(c^\lambda \bmod n^2) &= \text{L}(1 +mkn) \\
&= \frac{1+mkn-1}{n} \\
&= \frac{mkn}{n} \\
&= mk \\
\end{align*}
復号化の式に当てはめると、メッセージが復元されたことがわかります。
\begin{align*}
\frac{\text{L}(c^\lambda \bmod n^2)}{\text{L}(g^\lambda \bmod n^2)} \bmod n = \frac{mk}{k} = m
\end{align*}
平文の準同型加法(Homomorphic addition of plaintexts)
冪演算は冪の和となるので、$\ g$の$m_1+m_2$累乗となります。
したがって、メッセージの和が計算出来ます。
\begin{align*}
\mathcal{E}_g(m_1,r_{1}) = c_1 &= g^{m_1}\cdot r_1^n \bmod n^2\\
\mathcal{E}_g(m_2,r_{2}) = c_2 &= g^{m_2}\cdot r_2^n \bmod n^2\\
\mathcal{E}_g(m_1,r_{1})\cdot \mathcal{E}_g(m_2,r_{2}) = c_1\cdot c_2 &= g^{m_1+m_2}\cdot r_1^n\cdot r_2^n \bmod n^2\\
\mathcal{D}_g(c_1\cdot c_2 \bmod n^2) &= \frac{\text{L}(\{c_1\cdot c_2\}^\lambda \bmod n^2)}{\text{L}(g^\lambda \bmod n^2)} \bmod n \\
&= \frac{(m_1+m_2)k}{k} \\
&= m_1 + m_2 \\
\end{align*}
平文の準同型乗法(Homomorphic multiplication of plaintexts)
冪の冪演算は積となるので、$\ g$の$m_1\times m_2$累乗となります。
したがって、メッセージの積が計算出来ます。
\begin{align*}
\mathcal{E}_g(m_1,r_{1}) = c_1 &= g^{m_1}\cdot r_1^n \bmod n^2\\
c_1^{m_2} &= g^{m_1\cdot m_2}\cdot r_1^{n\cdot m_2} \bmod n^2\\
\mathcal{D}_g(c_1^{m_2} \bmod n^2) &= \frac{\text{L}(c_1^{\lambda m_2} \bmod n^2)}{\text{L}(g^\lambda \bmod n^2)} \bmod n \\
&= \frac{(m_1\times m_2)k}{k} \\
&= m_1 \times m_2 \\
\end{align*}
プログラミング
go言語で実装してみました、案外簡単です。
ソースコードはここ(Github)です。
鍵生成(Key generation)
乱数生成は、以前の投稿「大きな素数（かもしれない）」を利用しています。
また、最小公倍数も以前の投稿「最小公倍数(least common multiple)」を利用しています。
// L returns (x - 1) / n .
func L(x, n *big.Int) *big.Int {
if new(big.Int).Mod(new(big.Int).Sub(x, ONE), n).Cmp(ZERO) != 0 {
return nil
}
return new(big.Int).Div(new(big.Int).Sub(x, ONE), n)
}
// KeyGeneration returns a public and a private keys of pailliar cipher.
func KeyGeneration(bits int) (*PublicKey, *PrivateKey, error) {
// p and q are large primes
p := probablyPrime(bits / 2)
q := probablyPrime(bits / 2)
if p.Cmp(q) == 0 {
return KeyGeneration(bits)
}
// n = p * q
n := new(big.Int).Mul(p, q)
// n^2 = n * n
n2 := new(big.Int).Mul(n, n)
// λ = lcm(p-1,q-1)
lam := lcm(new(big.Int).Sub(p, ONE), new(big.Int).Sub(q, ONE))
// randomly select a base g
g := new(big.Int)
// μ = 1 / L(g^λ mod n^2)
mu := new(big.Int)
for {
g = Rnd(n2)
if gcd(g, n2).Cmp(ONE) != 0 {
continue
}
mu = L(new(big.Int).Exp(g, lam, n2), n)
// gcd(L(g^λ mod n^2 ), n) = 1
if gcd(mu, n).Cmp(ONE) != 0 {
continue
}
mu = new(big.Int).ModInverse(mu, n)
break
}
// public key
pub := &PublicKey{n: n, g: g, n2: n2}
// private key
pri := &PrivateKey{lam: lam, mu: mu, n: n, n2: n2}
return pub, pri, nil
}
暗号化(Encryption)
乱数$r$は、$n$と互いに素である必要があります。
// PublicKey is a pailliar public key.
type PublicKey struct {
n *big.Int // n
g *big.Int // g
n2 *big.Int // n^2
}
// Encryption returns an encrypted data.
func (pub *PublicKey) Encryption(m *big.Int) (*big.Int, error) {
// plaintext m < n
if m.Cmp(ZERO) < 0 || m.Cmp(pub.n) >= 0 {
return nil, fmt.Errorf("m is out of range")
}
// select a random r < n
r := new(big.Int)
for {
r = Rnd(pub.n)
if gcd(r, pub.n).Cmp(ONE) == 0 {
break
}
}
// ciphertext c = g^m * r^n mod n^2
c := new(big.Int).Mod(new(big.Int).Mul(
new(big.Int).Exp(pub.g, m, pub.n2),
new(big.Int).Exp(r, pub.n, pub.n2)), pub.n2)
return c, nil
}
復号化(Decryption)
あらかじめ計算した$\mu$を使います。
// PrivateKey is a pailliar private key.
type PrivateKey struct {
lam *big.Int // λ = lcm(p-1,q-1)
mu *big.Int // μ = 1 / L(g^λ mod n^2)
n *big.Int // n = p * q
n2 *big.Int // n^2
}
// Decryption returns the decrypted data.
func (pri *PrivateKey) Decryption(c *big.Int) (*big.Int, error) {
// ciphertext c < n 2
if c.Cmp(ZERO) <= 0 || c.Cmp(pri.n2) >= 0 {
return nil, fmt.Errorf("c is out of range")
}
// plaintext m = L(c^λ mod n^2) / L(g^λ mod n^2) mod n
// = L(c^λ mod n^2) * μ mod n
m := new(big.Int).Mod(new(big.Int).Mul(
L(new(big.Int).Exp(c, pri.lam, pri.n2), pri.n), pri.mu), pri.n)
return m, nil
}
平文の準同型加法(Homomorphic addition of plaintexts)
// Mul returns c1 * c2 mod n2
func (pub *PublicKey) Mul(c1, c2 *big.Int) *big.Int {
// c1 * c2 -> m1 + m2
return new(big.Int).Mod(new(big.Int).Mul(c1, c2), pub.n2)
}
平文の準同型乗法(Homomorphic multiplication of plaintexts)
// Exp returns c ^ m mod n2
func (pub *PublicKey) Exp(c, m *big.Int) *big.Int {
// c ^ m2 -> m1 * m2
return new(big.Int).Exp(c, m, pub.n2)
}
#さいごに
案外簡単なので、是非各言語で実装してみてください。
大きな素数生成は、RSAで求める必要があるのでRSAライブラリを探せばある可能性が高いと思います。