1// Package blindsecp256k1 implements the Blind signature scheme explained at
  2// "New Blind Signature Schemes Based on the (Elliptic Curve) Discrete
  3// Logarithm Problem", by Hamid Mala & Nafiseh Nezhadansari
  4// https://sci-hub.st/10.1109/ICCKE.2013.6682844
  5//
  6// LICENSE can be found at https://github.com/arnaucube/go-blindsecp256k1/blob/master/LICENSE
  7//
  8package blindsecp256k1
  9
 10// WARNING: WIP code
 11
 12import (
 13	"bytes"
 14	"crypto/ecdsa"
 15	"crypto/rand"
 16	"fmt"
 17	"math/big"
 18
 19	"github.com/ethereum/go-ethereum/crypto"
 20	"github.com/ethereum/go-ethereum/crypto/secp256k1"
 21)
 22
 23var (
 24	s256 *secp256k1.BitCurve = secp256k1.S256()
 25	zero *big.Int            = big.NewInt(0)
 26
 27	// B (from y^2 = x^3 + B)
 28	B *big.Int = s256.B
 29
 30	// P represents the secp256k1 finite field
 31	P *big.Int = s256.P
 32
 33	// G represents the base point of secp256k1
 34	G *Point = &Point{
 35		X: s256.Gx,
 36		Y: s256.Gy,
 37	}
 38
 39	// N represents the order of G of secp256k1
 40	N *big.Int = s256.N
 41)
 42
 43// Point represents a point on the secp256k1 curve
 44type Point struct {
 45	X *big.Int
 46	Y *big.Int
 47}
 48
 49// Add performs the Point addition
 50func (p *Point) Add(q *Point) *Point {
 51	x, y := s256.Add(p.X, p.Y, q.X, q.Y)
 52	return &Point{
 53		X: x,
 54		Y: y,
 55	}
 56}
 57
 58// Mul performs the Point scalar multiplication
 59func (p *Point) Mul(scalar *big.Int) *Point {
 60	x, y := s256.ScalarMult(p.X, p.Y, scalar.Bytes())
 61	return &Point{
 62		X: x,
 63		Y: y,
 64	}
 65}
 66
 67func (p *Point) isValid() error {
 68	if !s256.IsOnCurve(p.X, p.Y) {
 69		return fmt.Errorf("Point is not on secp256k1")
 70	}
 71
 72	if bytes.Equal(p.X.Bytes(), zero.Bytes()) &&
 73		bytes.Equal(p.Y.Bytes(), zero.Bytes()) {
 74		return fmt.Errorf("Point (%s, %s) can not be (0, 0)",
 75			p.X.String(), p.Y.String())
 76	}
 77	return nil
 78}
 79
 80// Compress packs a Point to a byte array of 33 bytes, encoded in little-endian.
 81func (p *Point) Compress() [33]byte {
 82	xBytes := p.X.Bytes()
 83	odd := byte(0)
 84	if isOdd(p.Y) {
 85		odd = byte(1)
 86	}
 87	var b [33]byte
 88	copy(b[32-len(xBytes):32], xBytes)
 89	b[32] = odd
 90	return b
 91}
 92
 93func isOdd(b *big.Int) bool {
 94	return b.Bit(0) != 0
 95}
 96
 97// DecompressPoint unpacks a Point from the given byte array of 33 bytes
 98// https://bitcointalk.org/index.php?topic=162805.msg1712294#msg1712294
 99func DecompressPoint(b [33]byte) (*Point, error) {
100	x := new(big.Int).SetBytes(b[:32])
101	var odd bool
102	if b[32] == byte(1) {
103		odd = true
104	}
105
106	// secp256k1: y2 = x3+ ax2 + b (where A==0, B==7)
107
108	// compute x^3 + B mod p
109	x3 := new(big.Int).Mul(x, x)
110	x3 = new(big.Int).Mul(x3, x)
111	// x3 := new(big.Int).Exp(x, big.NewInt(3), nil)
112	x3 = new(big.Int).Add(x3, B)
113	x3 = new(big.Int).Mod(x3, P)
114
115	// sqrt mod p of x^3 + B
116	y := new(big.Int).ModSqrt(x3, P)
117	if y == nil {
118		return nil, fmt.Errorf("not sqrt mod of x^3")
119	}
120	if odd != isOdd(y) {
121		y = new(big.Int).Sub(P, y)
122		// TODO if needed Mod
123	}
124
125	// check that y is a square root of x^3 + B
126	y2 := new(big.Int).Mul(y, y)
127	y2 = new(big.Int).Mod(y2, P)
128	if !bytes.Equal(y2.Bytes(), x3.Bytes()) {
129		return nil, fmt.Errorf("invalid square root")
130	}
131
132	if odd != isOdd(y) {
133		return nil, fmt.Errorf("odd does not match oddness")
134	}
135
136	p := &Point{X: x, Y: y}
137	return p, nil
138}
139
140// WIP
141func newRand() (*big.Int, error) {
142	pk, err := ecdsa.GenerateKey(s256, rand.Reader)
143	if err != nil {
144		return nil, err
145	}
146	return pk.D, nil
147}
148
149// PrivateKey represents the signer's private key
150type PrivateKey big.Int
151
152// PublicKey represents the signer's public key
153type PublicKey Point
154
155// NewPrivateKey returns a new random private key
156func NewPrivateKey() (*PrivateKey, error) {
157	k, err := newRand()
158	if err != nil {
159		return nil, err
160	}
161	if err := checkBigIntSize(k); err != nil {
162		return nil, fmt.Errorf("k error: %s", err)
163	}
164	sk := PrivateKey(*k)
165	return &sk, nil
166}
167
168// BigInt returns a *big.Int representation of the PrivateKey
169func (sk *PrivateKey) BigInt() *big.Int {
170	return (*big.Int)(sk)
171}
172
173// Public returns the PublicKey from the PrivateKey
174func (sk *PrivateKey) Public() *PublicKey {
175	q := G.Mul(sk.BigInt())
176	pk := PublicKey(*q)
177	return &pk
178}
179
180// Point returns a *Point representation of the PublicKey
181func (pk *PublicKey) Point() *Point {
182	return (*Point)(pk)
183}
184
185// NewRequestParameters returns a new random k (secret) & R (public) parameters
186func NewRequestParameters() (*big.Int, *Point, error) {
187	k, err := newRand()
188	if err != nil {
189		return nil, nil, err
190	}
191	// k, R = kG
192	return k, G.Mul(k), nil
193}
194
195func checkBigIntSize(b *big.Int) error {
196	// check b.Bytes()==32, as go returns big-endian representation of the
197	// bigint, so if length is not 32 we have a smaller value than expected
198	if len(b.Bytes()) != 32 { //nolint:gomnd
199		return fmt.Errorf("invalid length, need 32 bytes")
200	}
201	return nil
202}
203
204// BlindSign performs the blind signature on the given mBlinded using the
205// PrivateKey and the secret k values.
206func (sk *PrivateKey) BlindSign(mBlinded *big.Int, k *big.Int) (*big.Int, error) {
207	// TODO add pending checks
208	if mBlinded.Cmp(N) != -1 {
209		return nil, fmt.Errorf("mBlinded not inside the finite field")
210	}
211	if bytes.Equal(mBlinded.Bytes(), big.NewInt(0).Bytes()) {
212		return nil, fmt.Errorf("mBlinded can not be 0")
213	}
214	if err := checkBigIntSize(mBlinded); err != nil {
215		return nil, fmt.Errorf("mBlinded error: %s", err)
216	}
217	if err := checkBigIntSize(k); err != nil {
218		return nil, fmt.Errorf("k error: %s", err)
219	}
220
221	// s' = dm' + k
222	sBlind := new(big.Int).Add(
223		new(big.Int).Mul(sk.BigInt(), mBlinded),
224		k)
225	sBlind = new(big.Int).Mod(sBlind, N)
226	return sBlind, nil
227}
228
229// UserSecretData contains the secret values from the User (a, b) and the
230// public F
231type UserSecretData struct {
232	A *big.Int
233	B *big.Int
234
235	F *Point // public (in the paper is named R)
236}
237
238// Blind performs the blinding operation on m using signerR parameter
239func Blind(m *big.Int, signerR *Point) (*big.Int, *UserSecretData, error) {
240	if err := signerR.isValid(); err != nil {
241		return nil, nil, fmt.Errorf("signerR %s", err)
242	}
243
244	var err error
245	u := &UserSecretData{}
246	u.A, err = newRand()
247	if err != nil {
248		return nil, nil, err
249	}
250	u.B, err = newRand()
251	if err != nil {
252		return nil, nil, err
253	}
254
255	// (R) F = aR' + bG
256	aR := signerR.Mul(u.A)
257	bG := G.Mul(u.B)
258	u.F = aR.Add(bG)
259
260	if err := u.F.isValid(); err != nil {
261		return nil, nil, fmt.Errorf("u.F %s", err)
262	}
263
264	rx := new(big.Int).Mod(u.F.X, N)
265
266	// m' = a^-1 rx h(m)
267	ainv := new(big.Int).ModInverse(u.A, N)
268	ainvrx := new(big.Int).Mul(ainv, rx)
269	hBytes := crypto.Keccak256(m.Bytes())
270	h := new(big.Int).SetBytes(hBytes)
271	mBlinded := new(big.Int).Mul(ainvrx, h)
272	mBlinded = new(big.Int).Mod(mBlinded, N)
273
274	return mBlinded, u, nil
275}
276
277// Signature contains the signature values S & F
278type Signature struct {
279	S *big.Int
280	F *Point
281}
282
283// Compress packs a Signature to a byte array of 65 bytes, encoded in
284// little-endian.
285func (s *Signature) Compress() [65]byte {
286	var b [65]byte
287	sBytes := s.S.Bytes()
288	fBytes := s.F.Compress()
289	copy(b[:32], swapEndianness(sBytes))
290	copy(b[32:], fBytes[:])
291	return b
292}
293
294// DecompressSignature unpacks a Signature from the given byte array of 65 bytes
295func DecompressSignature(b [65]byte) (*Signature, error) {
296	s := new(big.Int).SetBytes(swapEndianness(b[:32]))
297	var fBytes [33]byte
298	copy(fBytes[:], b[32:])
299	f, err := DecompressPoint(fBytes)
300	if err != nil {
301		return nil, err
302	}
303	sig := &Signature{S: s, F: f}
304	return sig, nil
305}
306
307// Unblind performs the unblinding operation of the blinded signature for the
308// given the UserSecretData
309func Unblind(sBlind *big.Int, u *UserSecretData) *Signature {
310	// s = a s' + b
311	as := new(big.Int).Mul(u.A, sBlind)
312	s := new(big.Int).Add(as, u.B)
313	s = new(big.Int).Mod(s, N)
314
315	return &Signature{
316		S: s,
317		F: u.F,
318	}
319}
320
321// Verify checks the signature of the message m for the given PublicKey
322func Verify(m *big.Int, s *Signature, q *PublicKey) bool {
323	// TODO add pending checks
324	if err := s.F.isValid(); err != nil {
325		return false
326	}
327	if err := q.Point().isValid(); err != nil {
328		return false
329	}
330
331	sG := G.Mul(s.S) // sG
332
333	hBytes := crypto.Keccak256(m.Bytes())
334	h := new(big.Int).SetBytes(hBytes)
335
336	rx := new(big.Int).Mod(s.F.X, N)
337	rxh := new(big.Int).Mul(rx, h)
338	// do mod, as go-ethereum/crypto/secp256k1 can not handle scalars > 256 bits
339	rxhMod := new(big.Int).Mod(rxh, N)
340	// rxhG := G.Mul(rxh) // originally the paper uses G
341	rxhG := q.Point().Mul(rxhMod)
342
343	right := s.F.Add(rxhG)
344
345	// check sG == R + rx h(m) Q (where R in this code is F)
346	if bytes.Equal(sG.X.Bytes(), right.X.Bytes()) &&
347		bytes.Equal(sG.Y.Bytes(), right.Y.Bytes()) {
348		return true
349	}
350	return false
351}