forked from taurusgroup/multi-party-sig
-
Notifications
You must be signed in to change notification settings - Fork 0
/
public.go
158 lines (139 loc) · 4.4 KB
/
public.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
package paillier
import (
"crypto/rand"
"errors"
"fmt"
"io"
"github.com/cronokirby/saferith"
"github.com/MixinNetwork/multi-party-sig/common/params"
"github.com/MixinNetwork/multi-party-sig/pkg/math/arith"
"github.com/MixinNetwork/multi-party-sig/pkg/math/sample"
)
var (
ErrPaillierLength = errors.New("wrong number bit length of Paillier modulus N")
ErrPaillierEven = errors.New("modulus N is even")
ErrPaillierNil = errors.New("modulus N is nil")
)
// PublicKey is a Paillier public key. It is represented by a modulus N.
type PublicKey struct {
// n = p⋅q
n *arith.Modulus
// nSquared = n²
nSquared *arith.Modulus
// These values are cached out of convenience, and performance
nNat *saferith.Nat
// nPlusOne = n + 1
nPlusOne *saferith.Nat
}
// N is the public modulus making up this key.
func (pk *PublicKey) N() *saferith.Modulus {
return pk.n.Modulus
}
// NewPublicKey returns an initialized paillier.PublicKey and caches N, N² and (N-1)/2.
func NewPublicKey(n *saferith.Modulus) *PublicKey {
oneNat := new(saferith.Nat).SetUint64(1)
nNat := n.Nat()
nSquared := saferith.ModulusFromNat(new(saferith.Nat).Mul(nNat, nNat, -1))
nPlusOne := new(saferith.Nat).Add(nNat, oneNat, -1)
// Tightening is fine, since n is public
nPlusOne.Resize(nPlusOne.TrueLen())
return &PublicKey{
n: arith.ModulusFromN(n),
nSquared: arith.ModulusFromN(nSquared),
nNat: nNat,
nPlusOne: nPlusOne,
}
}
// ValidateN performs basic checks to make sure the modulus is valid:
// - log₂(n) = params.BitsPaillier.
// - n is odd.
func ValidateN(n *saferith.Modulus) error {
if n == nil {
return ErrPaillierNil
}
// log₂(N) = BitsPaillier
nBig := n.Big()
if bits := nBig.BitLen(); bits != params.BitsPaillier {
return fmt.Errorf("have: %d, need %d: %w", bits, params.BitsPaillier, ErrPaillierLength)
}
if nBig.Bit(0) != 1 {
return ErrPaillierEven
}
return nil
}
// Enc returns the encryption of m under the public key pk.
// The nonce used to encrypt is returned.
//
// The message m must be in the range [-(N-1)/2, …, (N-1)/2] and panics otherwise.
//
// ct = (1+N)ᵐρᴺ (mod N²).
func (pk PublicKey) Enc(m *saferith.Int) (*Ciphertext, *saferith.Nat) {
nonce := sample.UnitModN(rand.Reader, pk.n.Modulus)
return pk.EncWithNonce(m, nonce), nonce
}
// EncWithNonce returns the encryption of m under the public key pk.
// The nonce is not returned.
//
// The message m must be in the range [-(N-1)/2, …, (N-1)/2] and panics otherwise
//
// ct = (1+N)ᵐρᴺ (mod N²).
func (pk PublicKey) EncWithNonce(m *saferith.Int, nonce *saferith.Nat) *Ciphertext {
mAbs := m.Abs()
nHalf := new(saferith.Nat).SetNat(pk.nNat)
nHalf.Rsh(nHalf, 1, -1)
if gt, _, _ := mAbs.Cmp(nHalf); gt == 1 {
panic("paillier.Encrypt: tried to encrypt message outside of range [-(N-1)/2, …, (N-1)/2]")
}
// (N+1)ᵐ mod N²
c := pk.nSquared.ExpI(pk.nPlusOne, m)
// ρᴺ mod N²
rhoN := pk.nSquared.Exp(nonce, pk.nNat)
// (N+1)ᵐ rho ^ N
c.ModMul(c, rhoN, pk.nSquared.Modulus)
return &Ciphertext{c: c}
}
// Equal returns true if pk ≡ other.
func (pk PublicKey) Equal(other *PublicKey) bool {
_, eq, _ := pk.n.Cmp(other.n.Modulus)
return eq == 1
}
// ValidateCiphertexts checks if all ciphertexts are in the correct range and coprime to N²
// ct ∈ [1, …, N²-1] AND GCD(ct,N²) = 1.
func (pk PublicKey) ValidateCiphertexts(cts ...*Ciphertext) bool {
for _, ct := range cts {
if ct == nil {
return false
}
_, _, lt := ct.c.CmpMod(pk.nSquared.Modulus)
if lt != 1 {
return false
}
if ct.c.IsUnit(pk.nSquared.Modulus) != 1 {
return false
}
}
return true
}
// WriteTo implements io.WriterTo and should be used within the hash.Hash function.
func (pk *PublicKey) WriteTo(w io.Writer) (int64, error) {
if pk == nil {
return 0, io.ErrUnexpectedEOF
}
buf := pk.n.Bytes()
n, err := w.Write(buf)
return int64(n), err
}
// Domain implements hash.WriterToWithDomain, and separates this type within hash.Hash.
func (PublicKey) Domain() string {
return "Paillier PublicKey"
}
// Modulus returns an arith.Modulus for N which may allow for accelerated exponentiation when this
// public key was generated from a secret key.
func (pk *PublicKey) Modulus() *arith.Modulus {
return pk.n
}
// ModulusSquared returns an arith.Modulus for N² which may allow for accelerated exponentiation when this
// public key was generated from a secret key.
func (pk *PublicKey) ModulusSquared() *arith.Modulus {
return pk.nSquared
}