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.do/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/rand"
 15	"fmt"
 16	"math/big"
 17
 18	"github.com/btcsuite/btcd/btcec"
 19	"github.com/ethereum/go-ethereum/crypto"
 20)
 21
 22// TMP
 23// const (
 24//         // MinBigIntBytesLen defines the minimum bytes length of the minimum
 25//         // accepted value for the checked *big.Int
 26//         MinBigIntBytesLen = 20 * 8
 27// )
 28
 29var (
 30	zero *big.Int = big.NewInt(0)
 31
 32	// B (from y^2 = x^3 + B)
 33	B *big.Int = btcec.S256().B
 34
 35	// P represents the secp256k1 finite field
 36	P *big.Int = btcec.S256().P
 37
 38	// Q = (P+1)/4
 39	Q = new(big.Int).Div(new(big.Int).Add(P,
 40		big.NewInt(1)), big.NewInt(4)) // nolint:gomnd
 41
 42	// G represents the base point of secp256k1
 43	G *Point = &Point{
 44		X: btcec.S256().Gx,
 45		Y: btcec.S256().Gy,
 46	}
 47
 48	// N represents the order of G of secp256k1
 49	N *big.Int = btcec.S256().N
 50)
 51
 52// Point represents a point on the secp256k1 curve
 53type Point struct {
 54	X *big.Int
 55	Y *big.Int
 56}
 57
 58// Add performs the Point addition
 59func (p *Point) Add(q *Point) *Point {
 60	x, y := btcec.S256().Add(p.X, p.Y, q.X, q.Y)
 61	return &Point{
 62		X: x,
 63		Y: y,
 64	}
 65}
 66
 67// Mul performs the Point scalar multiplication
 68func (p *Point) Mul(scalar *big.Int) *Point {
 69	x, y := btcec.S256().ScalarMult(p.X, p.Y, scalar.Bytes())
 70	return &Point{
 71		X: x,
 72		Y: y,
 73	}
 74}
 75
 76func (p *Point) isValid() error {
 77	if !btcec.S256().IsOnCurve(p.X, p.Y) {
 78		return fmt.Errorf("Point is not on secp256k1")
 79	}
 80
 81	if bytes.Equal(p.X.Bytes(), zero.Bytes()) &&
 82		bytes.Equal(p.Y.Bytes(), zero.Bytes()) {
 83		return fmt.Errorf("Point (%s, %s) can not be (0, 0)",
 84			p.X.String(), p.Y.String())
 85	}
 86	return nil
 87}
 88
 89// Compress packs a Point to a byte array of 33 bytes
 90func (p *Point) Compress() [33]byte {
 91	xBytes := p.X.Bytes()
 92	odd := byte(0)
 93	if isOdd(p.Y) {
 94		odd = byte(1)
 95	}
 96	var b [33]byte
 97	copy(b[32-len(xBytes):32], xBytes)
 98	b[32] = odd
 99	return b
100}
101
102func isOdd(b *big.Int) bool {
103	return b.Bit(0) != 0
104}
105
106// DecompressPoint unpacks a Point from the given byte array of 33 bytes
107// https://bitcointalk.org/index.php?topic=162805.msg1712294#msg1712294
108func DecompressPoint(b [33]byte) (*Point, error) {
109	x := new(big.Int).SetBytes(b[:32])
110	var odd bool
111	if b[32] == byte(1) {
112		odd = true
113	}
114
115	// secp256k1: y2 = x3+ ax2 + b (where A==0, B==7)
116
117	// compute x^3 + B mod p
118	x3 := new(big.Int).Mul(x, x)
119	x3 = new(big.Int).Mul(x3, x)
120	// x3 := new(big.Int).Exp(x, big.NewInt(3), nil)
121	x3 = new(big.Int).Add(x3, B)
122	x3 = new(big.Int).Mod(x3, P)
123
124	// sqrt mod p of x^3 + B
125	y := new(big.Int).ModSqrt(x3, P)
126	if y == nil {
127		return nil, fmt.Errorf("not sqrt mod of x^3")
128	}
129	if odd != isOdd(y) {
130		y = new(big.Int).Sub(P, y)
131		// TODO if needed Mod
132	}
133
134	// check that y is a square root of x^3 + B
135	y2 := new(big.Int).Mul(y, y)
136	y2 = new(big.Int).Mod(y2, P)
137	if !bytes.Equal(y2.Bytes(), x3.Bytes()) {
138		return nil, fmt.Errorf("invalid square root")
139	}
140
141	if odd != isOdd(y) {
142		return nil, fmt.Errorf("odd does not match oddness")
143	}
144
145	p := &Point{X: x, Y: y}
146	return p, nil
147}
148
149// WIP
150func newRand() *big.Int {
151	var b [32]byte
152	_, err := rand.Read(b[:])
153	if err != nil {
154		panic(err)
155	}
156	bi := new(big.Int).SetBytes(b[:])
157	return new(big.Int).Mod(bi, N)
158}
159
160// PrivateKey represents the signer's private key
161type PrivateKey big.Int
162
163// PublicKey represents the signer's public key
164type PublicKey Point
165
166// NewPrivateKey returns a new random private key
167func NewPrivateKey() *PrivateKey {
168	k := newRand()
169	sk := PrivateKey(*k)
170	return &sk
171}
172
173// BigInt returns a *big.Int representation of the PrivateKey
174func (sk *PrivateKey) BigInt() *big.Int {
175	return (*big.Int)(sk)
176}
177
178// Public returns the PublicKey from the PrivateKey
179func (sk *PrivateKey) Public() *PublicKey {
180	Q := G.Mul(sk.BigInt())
181	pk := PublicKey(*Q)
182	return &pk
183}
184
185// Point returns a *Point representation of the PublicKey
186func (pk *PublicKey) Point() *Point {
187	return (*Point)(pk)
188}
189
190// NewRequestParameters returns a new random k (secret) & R (public) parameters
191func NewRequestParameters() (*big.Int, *Point) {
192	k := newRand()
193	return k, G.Mul(k) // R = kG
194}
195
196// BlindSign performs the blind signature on the given mBlinded using the
197// PrivateKey and the secret k values
198func (sk *PrivateKey) BlindSign(mBlinded *big.Int, k *big.Int) (*big.Int, error) {
199	// TODO add pending checks
200	if mBlinded.Cmp(N) != -1 {
201		return nil, fmt.Errorf("mBlinded not inside the finite field")
202	}
203	if bytes.Equal(mBlinded.Bytes(), big.NewInt(0).Bytes()) {
204		return nil, fmt.Errorf("mBlinded can not be 0")
205	}
206	// TMP
207	// if mBlinded.BitLen() < MinBigIntBytesLen {
208	//         return nil, fmt.Errorf("mBlinded too small")
209	// }
210
211	// s' = dm' + k
212	sBlind := new(big.Int).Add(
213		new(big.Int).Mul(sk.BigInt(), mBlinded),
214		k)
215	sBlind = new(big.Int).Mod(sBlind, N)
216	return sBlind, nil
217}
218
219// UserSecretData contains the secret values from the User (a, b) and the
220// public F
221type UserSecretData struct {
222	A *big.Int
223	B *big.Int
224
225	F *Point // public (in the paper is named R)
226}
227
228// Blind performs the blinding operation on m using signerR parameter
229func Blind(m *big.Int, signerR *Point) (*big.Int, *UserSecretData, error) {
230	if err := signerR.isValid(); err != nil {
231		return nil, nil, fmt.Errorf("signerR %s", err)
232	}
233
234	u := &UserSecretData{}
235	u.A = newRand()
236	u.B = newRand()
237
238	// (R) F = aR' + bG
239	aR := signerR.Mul(u.A)
240	bG := G.Mul(u.B)
241	u.F = aR.Add(bG)
242
243	// TODO check that F != O (point at infinity)
244	if err := u.F.isValid(); err != nil {
245		return nil, nil, fmt.Errorf("u.F %s", err)
246	}
247
248	rx := new(big.Int).Mod(u.F.X, N)
249
250	// m' = a^-1 rx h(m)
251	ainv := new(big.Int).ModInverse(u.A, N)
252	ainvrx := new(big.Int).Mul(ainv, rx)
253	hBytes := crypto.Keccak256(m.Bytes())
254	h := new(big.Int).SetBytes(hBytes)
255	mBlinded := new(big.Int).Mul(ainvrx, h)
256	mBlinded = new(big.Int).Mod(mBlinded, N)
257
258	return mBlinded, u, nil
259}
260
261// Signature contains the signature values S & F
262type Signature struct {
263	S *big.Int
264	F *Point
265}
266
267// Unblind performs the unblinding operation of the blinded signature for the
268// given the UserSecretData
269func Unblind(sBlind *big.Int, u *UserSecretData) *Signature {
270	// s = a s' + b
271	as := new(big.Int).Mul(u.A, sBlind)
272	s := new(big.Int).Add(as, u.B)
273	s = new(big.Int).Mod(s, N)
274
275	return &Signature{
276		S: s,
277		F: u.F,
278	}
279}
280
281// Verify checks the signature of the message m for the given PublicKey
282func Verify(m *big.Int, s *Signature, q *PublicKey) bool {
283	// TODO add pending checks
284	if err := s.F.isValid(); err != nil {
285		return false
286	}
287	if err := q.Point().isValid(); err != nil {
288		return false
289	}
290
291	sG := G.Mul(s.S) // sG
292
293	hBytes := crypto.Keccak256(m.Bytes())
294	h := new(big.Int).SetBytes(hBytes)
295
296	rx := new(big.Int).Mod(s.F.X, N)
297	rxh := new(big.Int).Mul(rx, h)
298	// rxhG := G.Mul(rxh) // originally the paper uses G
299	rxhG := q.Point().Mul(rxh)
300
301	right := s.F.Add(rxhG)
302
303	// check sG == R + rx h(m) Q (where R in this code is F)
304	if bytes.Equal(sG.X.Bytes(), right.X.Bytes()) &&
305		bytes.Equal(sG.Y.Bytes(), right.Y.Bytes()) {
306		return true
307	}
308	return false
309}