-
Notifications
You must be signed in to change notification settings - Fork 2
/
paillier.go
148 lines (129 loc) · 3.98 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
package crypto
//----------------------------------------------------------------------
// This file is part of Gospel.
// Copyright (C) 2011-2023 Bernd Fix >Y<
//
// Gospel is free software: you can redistribute it and/or modify it
// under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License,
// or (at your option) any later version.
//
// Gospel is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//
// SPDX-License-Identifier: AGPL3.0-or-later
//----------------------------------------------------------------------
import (
"github.com/bfix/gospel/math"
)
// PaillierPublicKey data structure
type PaillierPublicKey struct {
N, G *math.Int
}
// PaillierPrivateKey data structure
type PaillierPrivateKey struct {
*PaillierPublicKey
L, U *math.Int
P, Q *math.Int
}
// NewPaillierPrivateKey generates a new Paillier private key (key pair).
//
// The key used in the Paillier crypto system consists of four integer
// values. The public key has two parameters; the private key has three
// parameters (one parameter is shared between the keys). As in RSA it
// starts with two random primes 'p' and 'q'; the public key parameter
// are computed as:
//
// n := p * q
// g := random number from interval [0,n^2[
//
// The private key parameters are computed as:
//
// n := p * q
// l := lcm (p-1,q-1)
// u := (((g^l mod n^2)-1)/n) ^-1 mod n
//
// N.B. The division by n is integer based and rounds toward zero!
func NewPaillierPrivateKey(bits int) (key *PaillierPrivateKey, err error) {
// generate primes 'p' and 'q' and their factor 'n'
// repeat until the requested factor bitsize is reached
var p, q, n *math.Int
for {
bitsP := (bits - 5) / 2
bitsQ := bits - bitsP
p = math.NewIntRndPrimeBits(bitsP)
q = math.NewIntRndPrimeBits(bitsQ)
n = p.Mul(q)
if n.BitLen() == bits {
break
}
}
// initialize variables
n2 := n.Mul(n)
// compute public key parameter 'g' (generator)
g := math.NewIntRnd(n2)
// compute private key parameters
p1 := p.Sub(math.ONE)
q1 := q.Sub(math.ONE)
l := q1.Mul(p1).Div(p1.GCD(q1))
a := g.ModPow(l, n2).Sub(math.ONE).Div(n)
u := a.ModInverse(n)
// return key pair
pubkey := &PaillierPublicKey{
N: n,
G: g,
}
prvkey := &PaillierPrivateKey{
PaillierPublicKey: pubkey,
L: l,
U: u,
P: p,
Q: q,
}
return prvkey, nil
}
// GetPublicKey returns the corresponding public key from a private key.
func (p *PaillierPrivateKey) GetPublicKey() *PaillierPublicKey {
return p.PaillierPublicKey
}
// Decrypt message with private key.
//
// The decryption function in the Paillier crypto scheme is:
//
// m = D(c) = ((((c^l mod n^2)-1)/n) * u) mod n
//
// N.B. As in the key generation process the division by n is integer
//
// based and rounds toward zero!
func (p *PaillierPrivateKey) Decrypt(c *math.Int) (m *math.Int, err error) {
// initialize variables
pub := p.GetPublicKey()
n2 := pub.N.Mul(pub.N)
// perform decryption function
m = c.ModPow(p.L, n2).Sub(math.ONE).Div(pub.N).Mul(p.U).Mod(pub.N)
return m, nil
}
// Encrypt message with public key.
//
// The encryption function in the Paillier crypto scheme is:
//
// c = E(m) = (g^m * r^n) mod n^2
//
// where 'r' is a random number from the interval [0,n[. This encryption
// allows different encryption results for the same message, based on
// the actual value of 'r'.
func (p *PaillierPublicKey) Encrypt(m *math.Int) (c *math.Int, err error) {
// initialize variables
n2 := p.N.Mul(p.N)
// compute decryption function
c1 := p.G.ModPow(m, n2)
r := math.NewIntRnd(p.N)
c2 := r.ModPow(p.N, n2)
c = c1.Mul(c2).Mod(n2)
return c, nil
}