基于Paillier算法的匿名电子投票流程实现（Go实现）

(Updated: )
Crypto

​

实验名称：基于Paillier 算法的匿名电子投票流程实现

实验原理：

Paillier加密算法是佩利尔在1999年发明的概率公钥加密算法。该算法基于复合剩余类的困难问题，是一种满足加法同态性质的加密算法。该算法已经被广泛应用于加密信号处理以及第三方数据处理领域。Paillier算法如下图所示。

在电子投票系统中，由于统计票数是使用加法累加票数进行统计的，因此具有加法同态性质的Paillier算法可被应用于实现匿名的电子投票系统，以保护投票人的投票信息。电子投票系统架构如下图所示。

实验环境：Windows 11 + Go 1.20.4

实验步骤：

1.配置实验环境

1.1配置Go语言环境：

1.1.1下载和安装Go语言SDK，下载地址：https://golang.org/dl/

下载go1.20.4.windows-amd64.msi文件后，点击安装。

1.1.2配置系统环境变量

  • 新增 GOROOT，即 GO 语言安装目录

  • 在系统变量自带的 Path 下添加路径%GOROOT%\bin

  • 创建工程文件夹，为了方便识别，需要在文件夹中创建bin、pkg、src三个文件夹

  • 新增 GOPATH，即刚才创建的GO 的工程目录

  • 在系统变量自带的Path下添加路径%GOPATH%

  • 打开命令行工具，输入命令go env和go version，显示类似下图说明配置成功

2.创建Go语言代码文件，编写Paillier加密程序，验证Paillier算法具有加法同态性：

package main  



import (
    “crypto/rand”
    “errors”
    “fmt”
    “io”
    “math/big”
)  


var one = big.NewInt(1)  


// ErrMessageTooLong 当所需加密信息长度大于公钥长度时，报错。
var ErrMessageTooLong = errors.New(“信息过长！请调整公钥长度！”)  


// GenerateKey 生成指定位数的公私钥。
func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
    // 生成素数p
    var p *big.Int
    var errChan = make(chan error, 1)
    go func() {
       var err error
       p, err = rand.Prime(random, bits/2)
       errChan <- err
    }()  


// 生成素数q  
q, err := rand.Prime(random, bits/2)  
if err != nil {  
   return nil, err  
}  

// 等待素数p生成完成  
if err := &lt;-errChan; err != nil {  
   return nil, err  
}  
n := new(big.Int).Mul(p, q)  
pp := new(big.Int).Mul(p, p)  
qq := new(big.Int).Mul(q, q)  

return &amp;PrivateKey{  
   PublicKey: PublicKey{  
      N:        n,  
      NSquared: new(big.Int).Mul(n, n),  
      G:        new(big.Int).Add(n, one), // g = n + 1  
   },  
   p:         p,  
   pp:        pp,  
   pminusone: new(big.Int).Sub(p, one),  
   q:         q,  
   qq:        qq,  
   qminusone: new(big.Int).Sub(q, one),  
}, nil  



}  


// PrivateKey 私钥
type PrivateKey struct {
    PublicKey
    p         *big.Int
    pp        *big.Int
    pminusone *big.Int
    q         *big.Int
    qq        *big.Int
    qminusone *big.Int
    Lambda    *big.Int
}  


// PublicKey 公钥
type PublicKey struct {
    N        *big.Int
    G        *big.Int
    NSquared *big.Int
}  


// L L(x)=(x-1)/n
func L(x, n *big.Int) *big.Int {
    return new(big.Int).Div(new(big.Int).Sub(x, one), n)
}  


// Encrypt 加密。
func Encrypt(pubKey *PublicKey, plainText []byte) ([]byte, *big.Int, error) {
    r, err := rand.Int(rand.Reader, pubKey.N)
    if err != nil {
       return nil, nil, err
    }  


m := new(big.Int).SetBytes(plainText)  
if pubKey.N.Cmp(m) &lt; 1 { // N &lt; m  
   return nil, nil, ErrMessageTooLong  
}  

// c = g^m * r^n mod n^2 = [(m*n+1) mod n^2] * r^n mod n^2  
c := new(big.Int).Mod(  
   new(big.Int).Mul(  
      new(big.Int).Mod(new(big.Int).Add(one, new(big.Int).Mul(m, pubKey.N)), pubKey.NSquared),  
      new(big.Int).Exp(r, pubKey.N, pubKey.NSquared),  
   ),  
   pubKey.NSquared,  
)  

return c.Bytes(), r, nil  



}  


// Decrypt 解密。
func Decrypt(privKey *PrivateKey, cipherText []byte) ([]byte, error) {
    c := new(big.Int).SetBytes(cipherText)
    if privKey.NSquared.Cmp(c) < 1 {
       return nil, ErrMessageTooLong
    }
    mu := new(big.Int).ModInverse(privKey.Lambda, privKey.N)
    m := new(big.Int).Mod(new(big.Int).Mul(L(new(big.Int).Exp(c, privKey.Lambda, privKey.NSquared), privKey.N), mu), privKey.N)
    return m.Bytes(), nil
}  


// AddCipher 将两个密文相乘，以达到明文相加的目的。
func AddCipher(pubKey *PublicKey, cipher1, cipher2 []byte) []byte {
    x := new(big.Int).SetBytes(cipher1)
    y := new(big.Int).SetBytes(cipher2)
    // x * y mod n^2
    return new(big.Int).Mod(new(big.Int).Mul(x, y), pubKey.NSquared).Bytes()
}  


func main() {
    // 生成一个4096位私钥
    privKey, err := GenerateKey(rand.Reader, 4096)
    if err != nil {
       fmt.Println(err)
       return
    }
    privKey.Lambda = new(big.Int).Mul(privKey.pminusone, privKey.qminusone)
    // 加密明文1
    fmt.Print(“请输入第一个明文：”)
    var Plaintext1 big.Int
    fmt.Scan(&Plaintext1)
    Cipher1, _, err := Encrypt(&privKey.PublicKey, Plaintext1.Bytes())
    if err != nil {
       fmt.Println(err)
       return
    }  


// 加密明文2  
fmt.Print("请输入第二个明文：")  
var plaintext2 big.Int  
fmt.Scan(&amp;plaintext2)  
Cipher2, _, err := Encrypt(&amp;privKey.PublicKey, plaintext2.Bytes())  
if err != nil {  
   fmt.Println(err)  
   return  
}  

fmt.Println("对第一个明文加密后得到密文：", new(big.Int).SetBytes(Cipher1))  
fmt.Println("对第二个明文加密后得到密文：", new(big.Int).SetBytes(Cipher2))  

// 将明文1与明文2相加。  
EncryptedPlusCipher1Cipher2 := AddCipher(&amp;privKey.PublicKey, Cipher1, Cipher2)  
fmt.Println("两密文相乘得到：", new(big.Int).SetBytes(EncryptedPlusCipher1Cipher2))  
DecyptedPlusCipher1Cipher2, err := Decrypt(privKey, EncryptedPlusCipher1Cipher2)  
if err != nil {  
   fmt.Println(err)  
   return  
}  
fmt.Println("密文相乘后解密得到的明文为：", new(big.Int).SetBytes(DecyptedPlusCipher1Cipher2))  



}

3.运行Paillier加密程序，结果如下图所示，说明Paillier算法具有加法同态性。

在这里插入图片描述

4.创建Go语言代码文件，编写基于Paillier的电子投票系统：

package main  


import (
    "crypto/rand"
    "errors"
    "fmt"
    "io"
    "math/big"
)  


var one = big.NewInt(1)  


// ErrMessageTooLong 当所需加密信息长度大于公钥长度时，报错。
var ErrMessageTooLong = errors.New("信息过长！请调整公钥长度！")  


// GenerateKey 生成指定位数的公私钥。
func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
    // 生成素数p
    var p *big.Int
    var errChan = make(chan error, 1)
    go func() {
       var err error
       p, err = rand.Prime(random, bits/2)
       errChan <- err
    }()  


// 生成素数q  
q, err := rand.Prime(random, bits/2)  
if err != nil {  
   return nil, err  
}  

// 等待素数p生成完成  
if err := &lt;-errChan; err != nil {  
   return nil, err  
}  
n := new(big.Int).Mul(p, q)  
pp := new(big.Int).Mul(p, p)  
qq := new(big.Int).Mul(q, q)  

return &amp;PrivateKey{  
   PublicKey: PublicKey{  
      N:        n,  
      NSquared: new(big.Int).Mul(n, n),  
      G:        new(big.Int).Add(n, one), // g = n + 1  
   },  
   p:         p,  
   pp:        pp,  
   pminusone: new(big.Int).Sub(p, one),  
   q:         q,  
   qq:        qq,  
   qminusone: new(big.Int).Sub(q, one),  
}, nil  



}  


// PrivateKey 私钥
type PrivateKey struct {
    PublicKey
    p         *big.Int
    pp        *big.Int
    pminusone *big.Int
    q         *big.Int
    qq        *big.Int
    qminusone *big.Int
    Lambda    *big.Int
}  


// PublicKey 公钥
type PublicKey struct {
    N        *big.Int
    G        *big.Int
    NSquared *big.Int
}  


// L L(x)=(x-1)/n
func L(x, n *big.Int) *big.Int {
    return new(big.Int).Div(new(big.Int).Sub(x, one), n)
}  


// Encrypt 加密。
func Encrypt(pubKey *PublicKey, plainText []byte) ([]byte, *big.Int, error) {
    r, err := rand.Int(rand.Reader, pubKey.N)
    if err != nil {
       return nil, nil, err
    }  


m := new(big.Int).SetBytes(plainText)  
if pubKey.N.Cmp(m) &lt; 1 { // N &lt; m  
   return nil, nil, ErrMessageTooLong  
}  

// c = g^m * r^n mod n^2 = [(m*n+1) mod n^2] * r^n mod n^2  
c := new(big.Int).Mod(  
   new(big.Int).Mul(  
      new(big.Int).Mod(new(big.Int).Add(one, new(big.Int).Mul(m, pubKey.N)), pubKey.NSquared),  
      new(big.Int).Exp(r, pubKey.N, pubKey.NSquared),  
   ),  
   pubKey.NSquared,  
)  

return c.Bytes(), r, nil  



}  


// Decrypt 解密。
func Decrypt(privKey *PrivateKey, cipherText []byte) ([]byte, error) {
    c := new(big.Int).SetBytes(cipherText)
    if privKey.NSquared.Cmp(c) < 1 {
       return nil, ErrMessageTooLong
    }
    mu := new(big.Int).ModInverse(privKey.Lambda, privKey.N)
    m := new(big.Int).Mod(new(big.Int).Mul(L(new(big.Int).Exp(c, privKey.Lambda, privKey.NSquared), privKey.N), mu), privKey.N)
    return m.Bytes(), nil
}  


// AddCipher 将两个密文相乘，以达到明文相加的目的。
func AddCipher(pubKey *PublicKey, cipher1, cipher2 []byte) []byte {
    x := new(big.Int).SetBytes(cipher1)
    y := new(big.Int).SetBytes(cipher2)
    // x * y mod n^2
    return new(big.Int).Mod(new(big.Int).Mul(x, y), pubKey.NSquared).Bytes()
}  


func SendtoTeller(evts *[][]byte, evt [][]byte, canum int, pubKey *PublicKey) {
    for i := 0; i < canum; i++ {
       (*evts)[i] = AddCipher(pubKey, (*evts)[i], evt[i])
    }
}  


func SendtoSpokesman(evts *[][]byte, canum int, privKey *PrivateKey) {
    var err error
    var Winner = 0
    for i := 0; i < canum; i++ {
       (*evts)[i], err = Decrypt(privKey, (*evts)[i])
       if err != nil {
          fmt.Println(err)
          return
       }
       fmt.Println("第", i+1, "位候选人获得了", new(big.Int).SetBytes((*evts)[i]), "张选票；")
       if new(big.Int).SetBytes((*evts)[Winner]).Cmp(new(big.Int).SetBytes((*evts)[i])) < 1 {
          Winner = i
       }
    }
    fmt.Println("最终第", Winner+1, "位候选人获得的选票最多，为", new(big.Int).SetBytes((*evts)[Winner]), "张")
    return
}  


func main() {
    // 生成一个4096位私钥
    privKey, err := GenerateKey(rand.Reader, 4096)
    if err != nil {
       fmt.Println(err)
       return
    }
    privKey.Lambda = new(big.Int).Mul(privKey.pminusone, privKey.qminusone)
    // 程序开始运行提示
    fmt.Println("此程序模拟了基于Paillier算法的匿名电子投票的流程")
    fmt.Println("首先每位投票者为候选人投票并将结果加密发送给计票人。每人只有1张选票，\n选票上被投票的候选者得到1张选票，其他候选者得到0张选票；")
    fmt.Println("然后计票人将所有选票上对应候选人的加密的投票结果相乘，并将加密的统计\n结果发送给公布人；")
    fmt.Println("最后公布人对统计的票数进行解密并公布。")
    fmt.Println("********************************************************************")  


fmt.Print("请设置候选者人数：")  
var CandidatesNum int  
fmt.Scan(&amp;CandidatesNum)  
if CandidatesNum &lt;= 0 {  
   fmt.Println("候选者人数至少为1")  
   return  
}  
EncryptedVotes := make([][]byte, CandidatesNum)  
for i := 0; i &lt; CandidatesNum; i++ {  
   EncryptedVotes[i], _, err = Encrypt(&amp;privKey.PublicKey, big.NewInt(int64(0)).Bytes())  
}  
fmt.Print("请设置投票者人数：")  
var VotersNum int  
fmt.Scan(&amp;VotersNum)  
if VotersNum &lt;= 0 {  
   fmt.Println("投票者人数至少为1")  
   return  
}  

// 投票提示  
for i := 0; i &lt; VotersNum; i++ {  
   fmt.Println("-----请第", i+1, "名投票者为候选者投票-----")  
   Vote := make([]int, CandidatesNum)  
   var flag bool  
   for j := 0; j &lt; CandidatesNum; j++ {  
      fmt.Print("请为第", j+1, "名候选者投票：")  
      fmt.Scan(&amp;Vote[j])  
      if Vote[j] == 1 {  
         if flag {  
            fmt.Println("非法投票！每位投票者只有1张选票！")  
            return  
         }  
         flag = true  
      }  
   }  
   // 将加密的投票结果发给计票人  
   EncryptedVote := make([][]byte, CandidatesNum)  
   for i := 0; i &lt; CandidatesNum; i++ {  
      EncryptedVote[i], _, err = Encrypt(&amp;privKey.PublicKey, big.NewInt(int64(Vote[i])).Bytes())  
      if err != nil {  
         fmt.Println(err)  
         return  
      }  
   }  
   fmt.Println("对该投票结果进行加密并发送给计票人")  
   fmt.Println("计票人对此投票结果进行计票")  
   SendtoTeller(&amp;EncryptedVotes, EncryptedVote, CandidatesNum, &amp;privKey.PublicKey)  
}  

fmt.Println("-----计票人计票完成并将加密后的投票结果发给公布人-----")  
fmt.Println("加密后的投票结果为：")  
for i := 0; i &lt; CandidatesNum; i++ {  
   fmt.Println("第", i+1, "位候选人获得的选票票数的加密结果为", new(big.Int).SetBytes(EncryptedVotes[i]))  
}  
fmt.Println("-----公布人解密计票结果并公布最终的投票结果-----")  
SendtoSpokesman(&amp;EncryptedVotes, CandidatesNum, privKey)  



}

5.运行电子投票系统，结果如下图所示：