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
 81// little-endian.
 82func (p *Point) Compress() [33]byte {
 83	xBytes := p.X.Bytes()
 84	odd := byte(0)
 85	if isOdd(p.Y) {
 86		odd = byte(1)
 87	}
 88	var b [33]byte
 89	copy(b[32-len(xBytes):32], xBytes)
 90	b[32] = odd
 91	return b
 92}
 93
 94func isOdd(b *big.Int) bool {
 95	return b.Bit(0) != 0
 96}
 97
 98// DecompressPoint unpacks a Point from the given byte array of 33 bytes
 99// https://bitcointalk.org/index.php?topic=162805.msg1712294#msg1712294
100func DecompressPoint(b [33]byte) (*Point, error) {
101	x := new(big.Int).SetBytes(b[:32])
102	var odd bool
103	if b[32] == byte(1) {
104		odd = true
105	}
106
107	// secp256k1: y2 = x3+ ax2 + b (where A==0, B==7)
108
109	// compute x^3 + B mod p
110	x3 := new(big.Int).Mul(x, x)
111	x3 = new(big.Int).Mul(x3, x)
112	// x3 := new(big.Int).Exp(x, big.NewInt(3), nil)
113	x3 = new(big.Int).Add(x3, B)
114	x3 = new(big.Int).Mod(x3, P)
115
116	// sqrt mod p of x^3 + B
117	y := new(big.Int).ModSqrt(x3, P)
118	if y == nil {
119		return nil, fmt.Errorf("not sqrt mod of x^3")
120	}
121	if odd != isOdd(y) {
122		y = new(big.Int).Sub(P, y)
123		// TODO if needed Mod
124	}
125
126	// check that y is a square root of x^3 + B
127	y2 := new(big.Int).Mul(y, y)
128	y2 = new(big.Int).Mod(y2, P)
129	if !bytes.Equal(y2.Bytes(), x3.Bytes()) {
130		return nil, fmt.Errorf("invalid square root")
131	}
132
133	if odd != isOdd(y) {
134		return nil, fmt.Errorf("odd does not match oddness")
135	}
136
137	p := &Point{X: x, Y: y}
138	return p, p.isValid()
139}
140
141// WIP
142func newRand() (*big.Int, error) {
143	pk, err := ecdsa.GenerateKey(s256, rand.Reader)
144	if err != nil {
145		return nil, err
146	}
147	return pk.D, nil
148}
149
150// PrivateKey represents the signer's private key
151type PrivateKey big.Int
152
153// PublicKey represents the signer's public key
154type PublicKey Point
155
156// NewPrivateKey returns a new random private key
157func NewPrivateKey() (*PrivateKey, error) {
158	k, err := newRand()
159	if err != nil {
160		return nil, err
161	}
162	if err := checkBigIntSize(k); err != nil {
163		return nil, fmt.Errorf("k error: %s", err)
164	}
165	sk := PrivateKey(*k)
166	return &sk, nil
167}
168
169// BigInt returns a *big.Int representation of the PrivateKey
170func (sk *PrivateKey) BigInt() *big.Int {
171	return (*big.Int)(sk)
172}
173
174// Public returns the PublicKey from the PrivateKey
175func (sk *PrivateKey) Public() *PublicKey {
176	q := G.Mul(sk.BigInt())
177	pk := PublicKey(*q)
178	return &pk
179}
180
181// Point returns a *Point representation of the PublicKey
182func (pk *PublicKey) Point() *Point {
183	return (*Point)(pk)
184}
185
186// NewRequestParameters returns a new random k (secret) & R (public) parameters
187func NewRequestParameters() (*big.Int, *Point, error) {
188	k, err := newRand()
189	if err != nil {
190		return nil, nil, err
191	}
192	// k, R = kG
193	return k, G.Mul(k), nil
194}
195
196func checkBigIntSize(b *big.Int) error {
197	// check b.Bytes()==32, as go returns big-endian representation of the
198	// bigint, so if length is not 32 we have a smaller value than expected
199	// if len(b.Bytes()) != 32 { //nolint:gomnd
200	//         return fmt.Errorf("invalid length, need 32 bytes")
201	// }
202	return nil
203}
204
205// BlindSign performs the blind signature on the given mBlinded using the
206// PrivateKey and the secret k values.
207func (sk *PrivateKey) BlindSign(mBlinded *big.Int, k *big.Int) (*big.Int, error) {
208	// TODO add pending checks
209	if mBlinded.Cmp(N) != -1 {
210		return nil, fmt.Errorf("mBlinded not inside the finite field")
211	}
212	if bytes.Equal(mBlinded.Bytes(), big.NewInt(0).Bytes()) {
213		return nil, fmt.Errorf("mBlinded can not be 0")
214	}
215	if err := checkBigIntSize(mBlinded); err != nil {
216		return nil, fmt.Errorf("mBlinded error: %s", err)
217	}
218	if err := checkBigIntSize(k); err != nil {
219		return nil, fmt.Errorf("k error: %s", err)
220	}
221
222	// s' = dm' + k
223	sBlind := new(big.Int).Add(
224		new(big.Int).Mul(sk.BigInt(), mBlinded),
225		k)
226	sBlind = new(big.Int).Mod(sBlind, N)
227	return sBlind, nil
228}
229
230// UserSecretData contains the secret values from the User (a, b) and the
231// public F
232type UserSecretData struct {
233	A *big.Int
234	B *big.Int
235
236	F *Point // public (in the paper is named R)
237}
238
239// Blind performs the blinding operation on m using signerR parameter
240func Blind(m *big.Int, signerR *Point) (*big.Int, *UserSecretData, error) {
241	if err := signerR.isValid(); err != nil {
242		return nil, nil, fmt.Errorf("signerR %s", err)
243	}
244
245	var err error
246	u := &UserSecretData{}
247	u.A, err = newRand()
248	if err != nil {
249		return nil, nil, err
250	}
251	u.B, err = newRand()
252	if err != nil {
253		return nil, nil, err
254	}
255
256	// (R) F = aR' + bG
257	aR := signerR.Mul(u.A)
258	bG := G.Mul(u.B)
259	u.F = aR.Add(bG)
260
261	if err := u.F.isValid(); err != nil {
262		return nil, nil, fmt.Errorf("u.F %s", err)
263	}
264
265	rx := new(big.Int).Mod(u.F.X, N)
266
267	// m' = a^-1 rx h(m)
268	ainv := new(big.Int).ModInverse(u.A, N)
269	ainvrx := new(big.Int).Mul(ainv, rx)
270	hBytes := crypto.Keccak256(m.Bytes())
271	h := new(big.Int).SetBytes(hBytes)
272	mBlinded := new(big.Int).Mul(ainvrx, h)
273	mBlinded = new(big.Int).Mod(mBlinded, N)
274
275	return mBlinded, u, nil
276}
277
278// Signature contains the signature values S & F
279type Signature struct {
280	S *big.Int
281	F *Point
282}
283
284// Compress packs a Signature to a byte array of 65 bytes, encoded in
285// little-endian.
286func (s *Signature) Compress() [65]byte {
287	var b [65]byte
288	sBytes := s.S.Bytes()
289	fBytes := s.F.Compress()
290	copy(b[:32], swapEndianness(sBytes))
291	copy(b[32:], fBytes[:])
292	return b
293}
294
295// DecompressSignature unpacks a Signature from the given byte array of 65 bytes
296func DecompressSignature(b [65]byte) (*Signature, error) {
297	s := new(big.Int).SetBytes(swapEndianness(b[:32]))
298	var fBytes [33]byte
299	copy(fBytes[:], b[32:])
300	f, err := DecompressPoint(fBytes)
301	if err != nil {
302		return nil, err
303	}
304	sig := &Signature{S: s, F: f}
305	return sig, nil
306}
307
308// Unblind performs the unblinding operation of the blinded signature for the
309// given the UserSecretData
310func Unblind(sBlind *big.Int, u *UserSecretData) *Signature {
311	// s = a s' + b
312	as := new(big.Int).Mul(u.A, sBlind)
313	s := new(big.Int).Add(as, u.B)
314	s = new(big.Int).Mod(s, N)
315
316	return &Signature{
317		S: s,
318		F: u.F,
319	}
320}
321
322// Verify checks the signature of the message m for the given PublicKey
323func Verify(m *big.Int, s *Signature, q *PublicKey) bool {
324	// TODO add pending checks
325	if err := s.F.isValid(); err != nil {
326		return false
327	}
328	if err := q.Point().isValid(); err != nil {
329		return false
330	}
331
332	sG := G.Mul(s.S) // sG
333
334	hBytes := crypto.Keccak256(m.Bytes())
335	h := new(big.Int).SetBytes(hBytes)
336
337	rx := new(big.Int).Mod(s.F.X, N)
338	rxh := new(big.Int).Mul(rx, h)
339	// do mod, as go-ethereum/crypto/secp256k1 can not handle scalars > 256 bits
340	rxhMod := new(big.Int).Mod(rxh, N)
341	// rxhG := G.Mul(rxh) // originally the paper uses G
342	rxhG := q.Point().Mul(rxhMod)
343
344	right := s.F.Add(rxhG)
345
346	// check sG == R + rx h(m) Q (where R in this code is F)
347	if bytes.Equal(sG.X.Bytes(), right.X.Bytes()) &&
348		bytes.Equal(sG.Y.Bytes(), right.Y.Bytes()) {
349		return true
350	}
351	return false
352}