Paillier暗号(Paillier cryptosystem)

はじめに

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ライブラリを探せばある可能性が高いと思います。