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

作者：你好赵伟 | 2024-06-14 08:45:43

踩

paillier电子投票

实验名称：基于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 := <-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 &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) < 1 { // N < 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(&plaintext2)  
    Cipher2, _, err := Encrypt(&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(&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))  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

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 := <-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 &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) < 1 { // N < 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(&CandidatesNum)  
    if CandidatesNum <= 0 {  
       fmt.Println("候选者人数至少为1")  
       return  
    }  
    EncryptedVotes := make([][]byte, CandidatesNum)  
    for i := 0; i < CandidatesNum; i++ {  
       EncryptedVotes[i], _, err = Encrypt(&privKey.PublicKey, big.NewInt(int64(0)).Bytes())  
    }  
    fmt.Print("请设置投票者人数：")  
    var VotersNum int  
    fmt.Scan(&VotersNum)  
    if VotersNum <= 0 {  
       fmt.Println("投票者人数至少为1")  
       return  
    }  
  
    // 投票提示  
    for i := 0; i < VotersNum; i++ {  
       fmt.Println("-----请第", i+1, "名投票者为候选者投票-----")  
       Vote := make([]int, CandidatesNum)  
       var flag bool  
       for j := 0; j < CandidatesNum; j++ {  
          fmt.Print("请为第", j+1, "名候选者投票：")  
          fmt.Scan(&Vote[j])  
          if Vote[j] == 1 {  
             if flag {  
                fmt.Println("非法投票！每位投票者只有1张选票！")  
                return  
             }  
             flag = true  
          }  
       }  
       // 将加密的投票结果发给计票人  
       EncryptedVote := make([][]byte, CandidatesNum)  
       for i := 0; i < CandidatesNum; i++ {  
          EncryptedVote[i], _, err = Encrypt(&privKey.PublicKey, big.NewInt(int64(Vote[i])).Bytes())  
          if err != nil {  
             fmt.Println(err)  
             return  
          }  
       }  
       fmt.Println("对该投票结果进行加密并发送给计票人")  
       fmt.Println("计票人对此投票结果进行计票")  
       SendtoTeller(&EncryptedVotes, EncryptedVote, CandidatesNum, &privKey.PublicKey)  
    }  
  
    fmt.Println("-----计票人计票完成并将加密后的投票结果发给公布人-----")  
    fmt.Println("加密后的投票结果为：")  
    for i := 0; i < CandidatesNum; i++ {  
       fmt.Println("第", i+1, "位候选人获得的选票票数的加密结果为", new(big.Int).SetBytes(EncryptedVotes[i]))  
    }  
    fmt.Println("-----公布人解密计票结果并公布最终的投票结果-----")  
    SendtoSpokesman(&EncryptedVotes, CandidatesNum, privKey)  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219

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

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/717282