forked from Roasbeef/go-go-gadget-paillier
-
Notifications
You must be signed in to change notification settings - Fork 0
/
paillier.go
177 lines (150 loc) · 4.89 KB
/
paillier.go
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
package paillier
import (
"crypto/rand"
"errors"
"io"
"math/big"
)
var one = big.NewInt(1)
// ErrMessageTooLong is returned when attempting to encrypt a message which is
// too large for the size of the public key.
var ErrMessageTooLong = errors.New("paillier: message too long for Paillier public key size")
// GenerateKey generates an Paillier keypair of the given bit size using the
// random source random (for example, crypto/rand.Reader).
func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
p, err := rand.Prime(random, bits/2)
if err != nil {
return nil, err
}
q, err := rand.Prime(random, bits/2)
if 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),
Pinvq: new(big.Int).ModInverse(p, q),
HP: h(p, pp, n),
HQ: h(q, qq, n),
N: n,
}, nil
}
// PrivateKey represents a Paillier key.
type PrivateKey struct {
PublicKey
P *big.Int
PP *big.Int
Pminusone *big.Int
Q *big.Int
QQ *big.Int
Qminusone *big.Int
Pinvq *big.Int
HP *big.Int
HQ *big.Int
N *big.Int
}
// PublicKey represents the public part of a Paillier key.
type PublicKey struct {
N *big.Int // modulus
G *big.Int // n+1, since p and q are same length
NSquared *big.Int
}
func h(p *big.Int, pp *big.Int, n *big.Int) *big.Int {
gp := new(big.Int).Mod(new(big.Int).Sub(one, n), pp)
lp := l(gp, p)
hp := new(big.Int).ModInverse(lp, p)
return hp
}
func l(u *big.Int, n *big.Int) *big.Int {
return new(big.Int).Div(new(big.Int).Sub(u, one), n)
}
// Encrypt encrypts a plain text represented as a byte array. The passed plain
// text MUST NOT be larger than the modulus of the passed public key.
func Encrypt(pubKey *PublicKey, plainText []byte) ([]byte, error) {
r, err := rand.Int(rand.Reader, pubKey.N)
if err != nil {
return nil, err
}
m := new(big.Int).SetBytes(plainText)
if pubKey.N.Cmp(m) < 1 { // N < m
return nil, ErrMessageTooLong
}
// c = g^m * r^n mod n^2 = ((m*n+1) mod n^2) * r^n mod n^2
n := pubKey.N
c := new(big.Int).Mod(
new(big.Int).Mul(
new(big.Int).Mod(new(big.Int).Add(one, new(big.Int).Mul(m, n)), pubKey.NSquared),
new(big.Int).Exp(r, n, pubKey.NSquared),
),
pubKey.NSquared,
)
return c.Bytes(), nil
}
// Decrypt decrypts the passed cipher text.
func Decrypt(privKey *PrivateKey, cipherText []byte) ([]byte, error) {
c := new(big.Int).SetBytes(cipherText)
if privKey.NSquared.Cmp(c) < 1 { // c < n^2
return nil, ErrMessageTooLong
}
cp := new(big.Int).Exp(c, privKey.Pminusone, privKey.PP)
lp := l(cp, privKey.P)
mp := new(big.Int).Mod(new(big.Int).Mul(lp, privKey.HP), privKey.P)
cq := new(big.Int).Exp(c, privKey.Qminusone, privKey.QQ)
lq := l(cq, privKey.Q)
mqq := new(big.Int).Mul(lq, privKey.HQ)
mq := new(big.Int).Mod(mqq, privKey.Q)
m := crt(mp, mq, privKey)
return m.Bytes(), nil
}
func crt(mp *big.Int, mq *big.Int, privKey *PrivateKey) *big.Int {
u := new(big.Int).Mod(new(big.Int).Mul(new(big.Int).Sub(mq, mp), privKey.Pinvq), privKey.Q)
m := new(big.Int).Add(mp, new(big.Int).Mul(u, privKey.P))
return new(big.Int).Mod(m, privKey.N)
}
// AddCipher homomorphically adds together two cipher texts.
// To do this we multiply the two cipher texts, upon decryption, the resulting
// plain text will be the sum of the corresponding plain texts.
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()
}
// Add homomorphically adds a passed constant to the encrypted integer
// (our cipher text). We do this by multiplying the constant with our
// ciphertext. Upon decryption, the resulting plain text will be the sum of
// the plaintext integer and the constant.
func Add(pubKey *PublicKey, cipher, constant []byte) []byte {
c := new(big.Int).SetBytes(cipher)
x := new(big.Int).SetBytes(constant)
// c * g ^ x mod n^2
return new(big.Int).Mod(
new(big.Int).Mul(c, new(big.Int).Exp(pubKey.G, x, pubKey.NSquared)),
pubKey.NSquared,
).Bytes()
}
// Mul homomorphically multiplies an encrypted integer (cipher text) by a
// constant. We do this by raising our cipher text to the power of the passed
// constant. Upon decryption, the resulting plain text will be the product of
// the plaintext integer and the constant.
func Mul(pubKey *PublicKey, cipher []byte, constant []byte) []byte {
c := new(big.Int).SetBytes(cipher)
x := new(big.Int).SetBytes(constant)
// c ^ x mod n^2
return new(big.Int).Exp(c, x, pubKey.NSquared).Bytes()
}