Help us understand the problem. What is going on with this article?

Paillier暗号(Paillier cryptosystem)

More than 1 year has passed since last update.

はじめに

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

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away