Skip to main content

Paillier 同态加密

同态加密 - Paillier 加密方案​

同态加密的核心思想是允许在密文上直接进行某些运算，运算后的结果在解密后与在明文上进行相同运算的结果一致。具体来说，同态加密方案可以分为两类：加法同态和乘法同态。Paillier 加密方案是加法同态加密方案。

加法同态性质​

在 Paillier 加密方案中，如果我们有两个明文 m1m_1 和 m2m_2，以及它们对应的密文 c1c_1 和 c2c_2，则可以在密文上进行加法运算，使得结果在解密后等于明文的加法结果。

具体来说，Paillier 加密方案满足以下性质：

E(m1)×E(m2)≡E(m1+m2)mod  N2E(m_1) \times E(m_2) \equiv E(m_1 + m_2) \mod N^2

其中：

  • E(m)E(m) 表示明文 mm 的加密结果。
  • NN 是公钥的一部分。

示例说明​

假设我们有两个明文 m1m_1 和 m2m_2，它们的加密结果分别是 c1c_1 和 c2c_2。根据 Paillier 加密方案的加法同态性质，我们可以通过在密文上进行乘法运算得到加密后的和：

c1=E(m1)c_1 = E(m_1)

c2=E(m2)c_2 = E(m_2)

csum=c1×c2mod  N2c_{\text{sum}} = c_1 \times c_2 \mod N^2

解密 csumc_{\text{sum}} 的结果将等于 m1+m2m_1 + m_2。

示例代码​

以下是一个完整的示例代码，展示了如何在 Paillier 加密方案中利用同态加法性质进行运算：

package main

import (
	"fmt"
	"math/big"

	"yourmodule/paillier" // 替换为实际的包路径
)

func main() {
	// 生成密钥对
	paillier, err := paillier.GenerateKeyPair(2048)
	if err != nil {
		fmt.Println("Error generating key pair:", err)
		return
	}

	message1 := big.NewInt(42)
	message2 := big.NewInt(58)

	fmt.Println("Original message1:", message1)
	fmt.Println("Original message2:", message2)

	// 加密消息
	ciphertext1, err := paillier.PublicKey.Encrypt(message1)
	if err != nil {
		fmt.Println("Error encrypting message1:", err)
		return
	}
	fmt.Println("Encrypted message1:", ciphertext1)

	ciphertext2, err := paillier.PublicKey.Encrypt(message2)
	if err != nil {
		fmt.Println("Error encrypting message2:", err)
		return
	}
	fmt.Println("Encrypted message2:", ciphertext2)

	// 同态加法
	ciphertextSum, err := paillier.PublicKey.AddCiphertexts(ciphertext1, ciphertext2)
	if err != nil {
		fmt.Println("Error adding ciphertexts:", err)
		return
	}
	fmt.Println("Encrypted sum:", ciphertextSum)

	// 解密结果
	decryptedSum, err := paillier.PrivateKey.Decrypt(ciphertextSum, paillier.PublicKey)
	if err != nil {
		fmt.Println("Error decrypting sum:", err)
		return
	}
	fmt.Println("Decrypted sum:", decryptedSum)
}

解释​

  1. 密钥生成：

    • GenerateKeyPair 函数生成一个 Paillier 密钥对，包括公钥和私钥。

  2. 加密：

    • Encrypt 函数使用公钥加密消息 mm，得到密文 cc。

  3. 同态加法：

    • AddCiphertexts 函数对两个密文进行乘法运算，得到加密后的和 csumc_{\text{sum}} 。

  4. 解密：

    • Decrypt 函数使用私钥解密密文 csumc_{\text{sum}} ，得到明文和 m1+m2m_1 + m_2。

通过这种方式，我们可以在不解密数据的情况下，在密文上进行加法运算，解密后的结果与在明文上进行相同运算的结果一致。这就是同态加密的核心优势。

code​



package paillier

import (
	"fmt"
	"math/big"
	"runtime"

	"github.com/okx/threshold-lib/crypto"
)

const (
	PrimeBits = 2048
)

type (
	PublicKey struct {
		N *big.Int // g = n+1, n2 = n*n
	}

	PrivateKey struct {
		PublicKey
		Lambda *big.Int // lcm(p-1, q-1)
		Phi    *big.Int // (p-1) * (q-1)
	}
)

var (
	zero = big.NewInt(0)
	one  = big.NewInt(1)
)

// NewKeyPair generate paillier key pair
func NewKeyPair(concurrency ...int) (*PrivateKey, *PublicKey, error) {
	var currency int
	if 0 < len(concurrency) {
		currency = concurrency[0]
	} else {
		currency = runtime.NumCPU()
	}

	var values = make(chan *big.Int, currency)
	var p, q *big.Int
	for p == q {
		var quit = make(chan int)
		for i := 0; i < currency; i++ {
			go crypto.GenerateSafePrime(PrimeBits/2, values, quit)
		}
		p, q = <-values, <-values
		close(quit)
	}

	// n = p*q
	n := new(big.Int).Mul(p, q)

	// phi = (p-1) * (q-1)
	pMinus1 := new(big.Int).Sub(p, one)
	qMinus1 := new(big.Int).Sub(q, one)
	phi := new(big.Int).Mul(pMinus1, qMinus1)

	// lambda = lcm(p−1, q−1)
	gcd := new(big.Int).GCD(nil, nil, pMinus1, qMinus1)
	lambda := new(big.Int).Div(phi, gcd)

	publicKey := &PublicKey{N: n}
	privateKey := &PrivateKey{PublicKey: *publicKey, Lambda: lambda, Phi: phi}
	return privateKey, publicKey, nil
}

// Encrypt E(m) =  (g^m) * (r^n) mod n^2
func (pk *PublicKey) Encrypt(m *big.Int) (*big.Int, *big.Int, error) {
	r, err := crypto.RandomPrimeNum(pk.N)
	if err != nil {
		return nil, nil, fmt.Errorf("getRandom error")
	}
	c, err := pk.EncryptWithR(m, r)
	if err != nil {
		return nil, nil, fmt.Errorf("EncryptRandom error")
	}
	return c, r, err
}

// EncryptWithR E(m) =  (g^m) * (r^n) mod n^2
func (pk *PublicKey) EncryptWithR(m, r *big.Int) (c *big.Int, err error) {
	if m.Cmp(zero) == -1 || m.Cmp(pk.N) != -1 { // 0 <=  m < N
		return nil, fmt.Errorf("m range error")
	}
	N2 := pk.N2()
	// g^m mod N2
	Gm := new(big.Int).Exp(pk.G(), m, N2)
	// r^n mod N2
	xN := new(big.Int).Exp(r, pk.N, N2)
	//  (g^m) * (r^n) mod N2
	c = new(big.Int).Mod(new(big.Int).Mul(Gm, xN), N2)
	return
}

// HomoMulPlain  E(ab) = E(a) ^ b mod n^2
func (pk *PublicKey) HomoMulPlain(c1, m *big.Int) (*big.Int, error) {
	if m.Cmp(zero) == -1 || m.Cmp(pk.N) != -1 { // 0 <=  m < N
		return nil, fmt.Errorf("m range error")
	}
	N2 := pk.N2()
	if c1.Cmp(zero) == -1 || c1.Cmp(N2) != -1 { //  // 0 <= c1 < N2
		return nil, fmt.Errorf("c range error")
	}
	// c^m mod N2
	return new(big.Int).Exp(c1, m, N2), nil
}

// HomoAdd E(ab)=E(a)*E(b) mod n^2
func (pk *PublicKey) HomoAdd(c1, c2 *big.Int) (*big.Int, error) {
	N2 := pk.N2()
	if c1.Cmp(zero) == -1 || c1.Cmp(N2) != -1 { //  // 0 <= c1 < N2
		return nil, fmt.Errorf("c1 range error")
	}
	if c2.Cmp(zero) == -1 || c2.Cmp(N2) != -1 { //  // 0 <= c2 < N2
		return nil, fmt.Errorf("c2 range error")
	}
	// c1 * c2 mod N2
	return new(big.Int).Mod(new(big.Int).Mul(c1, c2), N2), nil
}

// HomoAddPlain   E(a+b) = E(a) * g^b mod n^2
//						 = E(a) * (1 + b*n) mod n^2
func (pk *PublicKey) HomoAddPlain(eA, b *big.Int) (*big.Int, error) {
	N2 := pk.N2()
	if eA.Cmp(zero) == -1 || eA.Cmp(N2) != -1 { //  // 0 <= eA < N2
		return nil, fmt.Errorf("eA range error")
	}
	if b.Cmp(zero) == -1 || b.Cmp(pk.N) != -1 { //  // 0 <= b < N
		return nil, fmt.Errorf("c2 range error")
	}
	gb := new(big.Int).Add(new(big.Int).Mul(b, pk.N), one)
	return new(big.Int).Mod(new(big.Int).Mul(eA, gb), N2), nil
}

// n*n
func (pk *PublicKey) N2() *big.Int {
	return new(big.Int).Mul(pk.N, pk.N)
}

// g = n + 1
func (pk *PublicKey) G() *big.Int {
	return new(big.Int).Add(pk.N, one)
}

// Decrypt m = L(c^lambda mod n^2) * mu mod n
func (priv *PrivateKey) Decrypt(c *big.Int) (m *big.Int, err error) {
	N2 := priv.N2()
	if c.Cmp(zero) == -1 || c.Cmp(N2) != -1 { // 0 <= c < N2
		return nil, fmt.Errorf("c range error")
	}
	cg := new(big.Int).GCD(nil, nil, c, N2)
	if cg.Cmp(one) == 1 {
		return nil, fmt.Errorf("the message is mal-formed")
	}
	//  lc = L[(c^Lambda mod N2) / N]
	lc := l(new(big.Int).Exp(c, priv.Lambda, N2), priv.N)
	// lg = L[(g^Lambda mod N2) / N]
	lg := l(new(big.Int).Exp(priv.G(), priv.Lambda, N2), priv.N)
	// m = (lc/lg) mod N
	inv := new(big.Int).ModInverse(lg, priv.N)
	m = new(big.Int).Mod(new(big.Int).Mul(lc, inv), priv.N)
	return
}

// l(x) = (x-1)/N
func l(u, N *big.Int) *big.Int {
	t := new(big.Int).Sub(u, one)
	return new(big.Int).Div(t, N)
}

这个实现是一个完整的 Paillier 同态加密方案，包括密钥生成、加密、解密以及同态加法和同态乘法操作。以下是对代码的逐步解释：

代码结构​

  • 密钥结构：

    • PublicKey：包含公钥的部分，主要是 NN。
    • PrivateKey：包含私钥的部分，继承了 PublicKey，并增加了 λ\lambda 和 ϕ\phi。

  • 常量和变量：

    • PrimeBits：设置素数的位数。
    • zero 和 one：常用的 big.Int 值。

主要函数​

  1. 密钥生成 (NewKeyPair)：

    • 生成两个大素数 pp 和 qq。
    • 计算 n=p×qn = p \times q。
    • 计算 ϕ=(p−1)×(q−1)\phi = (p-1) \times (q-1)。
    • 计算 λ=lcm(p−1,q−1)\lambda = \text{lcm}(p-1, q-1)。
    • 返回公钥和私钥。

  2. 加密 (Encrypt 和 EncryptWithR)：

    • Encrypt：生成随机数 rr，然后调用 EncryptWithR。
    • EncryptWithR：计算 c=(gm)×(rn)mod  n2c = (g^m) \times (r^n) \mod n^2。

  3. 同态加法 (HomoAdd 和 HomoAddPlain)：

    • HomoAdd：对两个密文进行同态加法 E(m1)×E(m2)mod  n2E(m_1) \times E(m_2) \mod n^2。
    • HomoAddPlain：对密文和明文进行同态加法 E(m)×gbmod  n2E(m) \times g^b \mod n^2。

  4. 同态乘法 (HomoMulPlain)：

    • 对密文和明文进行同态乘法 E(m)bmod  n2E(m)^b \mod n^2。

  5. 解密 (Decrypt)：

    • 计算 m=L(cλmod  n2)×μmod  nm = L(c^\lambda \mod n^2) \times \mu \mod n。

  6. 辅助函数：

    • N2：计算 n2n^2。
    • G：计算 g=n+1g = n + 1。
    • l：计算 L(x)=x−1nL(x) = \frac{x-1}{n}。

使用示例​

以下是如何使用上述 Paillier 加密实现的示例代码：

package main

import (
	"fmt"
	"math/big"

	"yourmodule/paillier" // 替换为实际的包路径
)

func main() {
	// 生成密钥对
	privateKey, publicKey, err := paillier.NewKeyPair()
	if err != nil {
		fmt.Println("Error generating key pair:", err)
		return
	}

	message1 := big.NewInt(42)
	message2 := big.NewInt(58)

	fmt.Println("Original message1:", message1)
	fmt.Println("Original message2:", message2)

	// 加密消息
	ciphertext1, _, err := publicKey.Encrypt(message1)
	if err != nil {
		fmt.Println("Error encrypting message1:", err)
		return
	}
	fmt.Println("Encrypted message1:", ciphertext1)

	ciphertext2, _, err := publicKey.Encrypt(message2)
	if err != nil {
		fmt.Println("Error encrypting message2:", err)
		return
	}
	fmt.Println("Encrypted message2:", ciphertext2)

	// 同态加法
	ciphertextSum, err := publicKey.HomoAdd(ciphertext1, ciphertext2)
	if err != nil {
		fmt.Println("Error adding ciphertexts:", err)
		return
	}
	fmt.Println("Encrypted sum:", ciphertextSum)

	// 解密结果
	decryptedSum, err := privateKey.Decrypt(ciphertextSum)
	if err != nil {
		fmt.Println("Error decrypting sum:", err)
		return
	}
	fmt.Println("Decrypted sum:", decryptedSum)
}

解释​

  1. 密钥生成：

    • NewKeyPair 函数生成一个 Paillier 密钥对，包括公钥和私钥。

  2. 加密：

    • Encrypt 函数使用公钥加密消息 mm，得到密文 cc。

  3. 同态加法：

    • HomoAdd 函数对两个密文进行同态加法操作，得到加密后的和 csumc_{\text{sum}}。

  4. 解密：

    • Decrypt 函数使用私钥解密密文 csumc_{\text{sum}}，得到明文和 m1+m2m_1 + m_2。

通过这种方式，我们可以在不解密数据的情况下，在密文上进行加法运算，解密后的结果与在明文上进行相同运算的结果一致。这就是同态加密的核心优势。