cryptofun/README.md
README.mdRaw
1# cryptofun [](https://goreportcard.com/report/github.com/arnaucube/cryptofun)
2
3Crypto algorithms from scratch. Academic purposes only.
4
5
6
7- [RSA cryptosystem & Blind signature & Homomorphic Multiplication](#rsa-cryptosystem--blind-signature--homomorphic-multiplication)
8- [Paillier cryptosystem & Homomorphic Addition](#paillier-cryptosystem--homomorphic-addition)
9- [Shamir Secret Sharing](#shamir-secret-sharing)
10- [Diffie-Hellman](#diffie-hellman)
11- [ECC](#ecc)
12- [ECC ElGamal](#ecc-elgamal)
13- [ECC ECDSA](#ecc-ecdsa)
14- [Schnorr signature](#schnorr-signature)
15- [Bn128](#bn128)
16
17---
18
19## RSA cryptosystem & Blind signature & Homomorphic Multiplication
20- https://en.wikipedia.org/wiki/RSA_(cryptosystem)#
21- https://en.wikipedia.org/wiki/Blind_signature
22- https://en.wikipedia.org/wiki/Homomorphic_encryption
23
24- [x] GenerateKeyPair
25- [x] Encrypt
26- [x] Decrypt
27- [x] Blind
28- [x] Blind Signature
29- [x] Unblind Signature
30- [x] Verify Signature
31- [x] Homomorphic Multiplication
32
33
34#### Usage
35- Key generation, Encryption, Decryption
36```go
37// generate key pair
38key, err := GenerateKeyPair()
39if err!=nil {
40 fmt.Println(err)
41}
42mBytes := []byte("Hi")
43m := new(big.Int).SetBytes(mBytes)
44
45// encrypt message
46c := Encrypt(m, key.PubK)
47
48// decrypt ciphertext
49d := Decrypt(c, key.PrivK)
50if m == d {
51 fmt.Println("correctly decrypted")
52}
53```
54
55- Blind signatures
56```go
57// key generation [Alice]
58key, err := GenerateKeyPair()
59if err!=nil {
60 fmt.Println(err)
61}
62
63// create new message [Alice]
64mBytes := []byte("Hi")
65m := new(big.Int).SetBytes(mBytes)
66
67// define r value [Alice]
68rVal := big.NewInt(int64(101))
69
70// blind message [Alice]
71mBlinded := Blind(m, rVal, key.PubK)
72
73// Blind Sign the blinded message [Bob]
74sigma := BlindSign(mBlinded, key.PrivK)
75
76// unblind the blinded signed message, and get the signature of the message [Alice]
77mSigned := Unblind(sigma, rVal, key.PubK)
78
79// verify the signature [Alice/Bob/Trudy]
80verified := Verify(m, mSigned, key.PubK)
81if !verified {
82 fmt.Println("signature could not be verified")
83}
84```
85
86- Homomorphic Multiplication
87```go
88// key generation [Alice]
89key, err := GenerateKeyPair()
90if err!=nil {
91 fmt.Println(err)
92}
93
94// define values [Alice]
95n1 := big.NewInt(int64(11))
96n2 := big.NewInt(int64(15))
97
98// encrypt the values [Alice]
99c1 := Encrypt(n1, key.PubK)
100c2 := Encrypt(n2, key.PubK)
101
102// compute homomorphic multiplication with the encrypted values [Bob]
103c3c4 := HomomorphicMul(c1, c2, key.PubK)
104
105// decrypt the result [Alice]
106d := Decrypt(c3c4, key.PrivK)
107
108// check that the result is the expected
109if !bytes.Equal(new(big.Int).Mul(n1, n2).Bytes(), d.Bytes()) {
110 fmt.Println("decrypted result not equal to expected result")
111}
112```
113
114## Paillier cryptosystem & Homomorphic Addition
115- https://en.wikipedia.org/wiki/Paillier_cryptosystem
116- https://en.wikipedia.org/wiki/Homomorphic_encryption
117
118- [x] GenerateKeyPair
119- [x] Encrypt
120- [x] Decrypt
121- [x] Homomorphic Addition
122
123#### Usage
124- Encrypt, Decrypt
125```go
126// key generation
127key, err := GenerateKeyPair()
128if err!=nil {
129 fmt.Println(err)
130}
131
132mBytes := []byte("Hi")
133m := new(big.Int).SetBytes(mBytes)
134
135// encryption
136c := Encrypt(m, key.PubK)
137
138// decryption
139d := Decrypt(c, key.PubK, key.PrivK)
140if m == d {
141 fmt.Println("ciphertext decrypted correctly")
142}
143```
144
145- Homomorphic Addition
146```go
147// key generation [Alice]
148key, err := GenerateKeyPair()
149if err!=nil {
150 fmt.Println(err)
151}
152
153// define values [Alice]
154n1 := big.NewInt(int64(110))
155n2 := big.NewInt(int64(150))
156
157// encrypt values [Alice]
158c1 := Encrypt(n1, key.PubK)
159c2 := Encrypt(n2, key.PubK)
160
161// compute homomorphic addition [Bob]
162c3c4 := HomomorphicAddition(c1, c2, key.PubK)
163
164// decrypt the result [Alice]
165d := Decrypt(c3c4, key.PubK, key.PrivK)
166if !bytes.Equal(new(big.Int).Add(n1, n2).Bytes(), d.Bytes()) {
167 fmt.Println("decrypted result not equal to expected result")
168}
169```
170
171
172## Shamir Secret Sharing
173- https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
174
175- [x] create secret sharing from number of secrets needed, number of shares, random point p, secret to share
176- [x] Lagrange Interpolation to restore the secret from the shares
177
178#### Usage
179```go
180// define secret to share
181k := 123456789
182
183// define random prime
184p, err := rand.Prime(rand.Reader, bits/2)
185if err!=nil {
186 fmt.Println(err)
187}
188
189// define how many shares want to generate
190nShares := big.NewInt(int64(6))
191
192// define how many shares are needed to recover the secret
193nNeededShares := big.NewInt(int64(3))
194
195// create the shares
196shares, err := Create(
197 nNeededShares,
198 nShares,
199 p,
200 big.NewInt(int64(k)))
201assert.Nil(t, err)
202if err!=nil {
203 fmt.Println(err)
204}
205
206// select shares to use
207var sharesToUse [][]*big.Int
208sharesToUse = append(sharesToUse, shares[2])
209sharesToUse = append(sharesToUse, shares[1])
210sharesToUse = append(sharesToUse, shares[0])
211
212// recover the secret using Lagrange Interpolation
213secr := LagrangeInterpolation(sharesToUse, p)
214
215// check that the restored secret matches the original secret
216if !bytes.Equal(k.Bytes(), secr.Bytes()) {
217 fmt.Println("reconstructed secret not correspond to original secret")
218}
219```
220
221## Diffie-Hellman
222- https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
223
224- [x] key exchange
225
226## ECC
227- https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
228
229- [x] define elliptic curve
230- [x] get point at X
231- [x] get order of a Point on the elliptic curve
232- [x] Add two points on the elliptic curve
233- [x] Multiply a point n times on the elliptic curve
234
235#### Usage
236- ECC basic operations
237```go
238// define new ec
239ec := NewEC(big.NewInt(int64(0)), big.NewInt(int64(7)), big.NewInt(int64(11)))
240
241// define two points over the curve
242p1 := Point{big.NewInt(int64(4)), big.NewInt(int64(7))}
243p2 := Point{big.NewInt(int64(2)), big.NewInt(int64(2))}
244
245// add the two points
246q, err := ec.Add(p1, p2)
247if err!=nil {
248 fmt.Println(err)
249}
250
251// multiply the two points
252q, err := ec.Mul(p, big.NewInt(int64(1)))
253if err!=nil {
254 fmt.Println(err)
255}
256
257// get order of a generator point over the elliptic curve
258g := Point{big.NewInt(int64(7)), big.NewInt(int64(8))}
259order, err := ec.Order(g)
260if err!=nil {
261 fmt.Println(err)
262}
263```
264
265
266
267
268## ECC ElGamal
269- https://en.wikipedia.org/wiki/ElGamal_encryption
270
271- [x] ECC ElGamal key generation
272- [x] ECC ElGamal Encrypton
273- [x] ECC ElGamal Decryption
274
275
276#### Usage
277- NewEG, Encryption, Decryption
278```go
279// define new elliptic curve
280ec := ecc.NewEC(big.NewInt(int64(1)), big.NewInt(int64(18)), big.NewInt(int64(19)))
281
282// define new point
283g := ecc.Point{big.NewInt(int64(7)), big.NewInt(int64(11))}
284
285// define new ElGamal crypto system with the elliptic curve and the point
286eg, err := NewEG(ec, g)
287if err!=nil {
288 fmt.Println(err)
289}
290
291// define privK&pubK over the elliptic curve
292privK := big.NewInt(int64(5))
293pubK, err := eg.PubK(privK)
294if err!=nil {
295 fmt.Println(err)
296}
297
298// define point to encrypt
299m := ecc.Point{big.NewInt(int64(11)), big.NewInt(int64(12))}
300
301// encrypt
302c, err := eg.Encrypt(m, pubK, big.NewInt(int64(15)))
303if err!=nil {
304 fmt.Println(err)
305}
306
307// decrypt
308d, err := eg.Decrypt(c, privK)
309if err!=nil {
310 fmt.Println(err)
311}
312
313// check that decryption is correct
314if !m.Equal(d) {
315 fmt.Println("decrypted not equal to original")
316}
317```
318
319
320
321## ECC ECDSA
322- https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
323
324- [x] define ECDSA data structure
325- [x] ECDSA Sign
326- [x] ECDSA Verify signature
327
328
329#### Usage
330```go
331// define new elliptic curve
332ec := ecc.NewEC(big.NewInt(int64(1)), big.NewInt(int64(18)), big.NewInt(int64(19)))
333// define new point
334g := ecc.Point{big.NewInt(int64(7)), big.NewInt(int64(11))}
335
336// define new ECDSA system
337dsa, err := NewDSA(ec, g)
338if err!=nil {
339 fmt.Println(err)
340}
341
342// define privK&pubK over the elliptic curve
343privK := big.NewInt(int64(5))
344pubK, err := dsa.PubK(privK)
345if err!=nil {
346 fmt.Println(err)
347}
348
349// hash value to sign
350hashval := big.NewInt(int64(40))
351
352// define r
353r := big.NewInt(int64(11))
354
355// sign hashed value
356sig, err := dsa.Sign(hashval, privK, r)
357if err!=nil {
358 fmt.Println(err)
359}
360
361// verify signature
362verified, err := dsa.Verify(hashval, sig, pubK)
363if err!=nil {
364 fmt.Println(err)
365}
366if verified {
367 fmt.Println("signature correctly verified")
368}
369```
370
371## Schnorr signature
372- https://en.wikipedia.org/wiki/Schnorr_signature
373
374- [x] Hash[M || R] (where M is the msg bytes and R is a Point on the ECC, using sha256 hash function)
375- [x] Generate Schnorr scheme
376- [x] Sign
377- [x] Verify signature
378
379
380#### Usage
381```go
382// define new elliptic curve
383ec := ecc.NewEC(big.NewInt(int64(0)), big.NewInt(int64(7)), big.NewInt(int64(11)))
384// define new point
385g := ecc.Point{big.NewInt(int64(11)), big.NewInt(int64(27))} // Generator
386// define new random r
387r := big.NewInt(int64(23)) // random r
388
389// define new Schnorr crypto system using the values
390schnorr, sk, err := Gen(ec, g, r)
391if err!=nil {
392 fmt.println(err)
393}
394
395// define message to sign
396m := []byte("hola")
397
398// also we can hash the message, but it's not mandatory, as it will be done inside the schnorr.Sign, but we can perform it now, just to check the function
399h := Hash([]byte("hola"), c)
400if h.String() != "34719153732582497359642109898768696927847420320548121616059449972754491425079") {
401 fmt.Println("not correctly hashed")
402}
403
404s, rPoint, err := schnorr.Sign(sk, m)
405if err!=nil {
406 fmt.println(err)
407}
408
409// verify Schnorr signature
410verified, err := Verify(schnorr.EC, sk.PubK, m, s, rPoint)
411if err!=nil {
412 fmt.println(err)
413}
414if verified {
415 fmt.Println("Schnorr signature correctly verified")
416}
417```
418
419
420
421## Bn128
422
423This is implemented followng the info and the implementations from:
424- `Multiplication and Squaring on Pairing-Friendly
425Fields`, Augusto Jun Devegili, Colm Ó hÉigeartaigh, Michael Scott, and Ricardo Dahab https://pdfs.semanticscholar.org/3e01/de88d7428076b2547b60072088507d881bf1.pdf
426- `Optimal Pairings`, Frederik Vercauteren https://www.cosic.esat.kuleuven.be/bcrypt/optimal.pdf , https://eprint.iacr.org/2008/096.pdf
427- `Double-and-Add with Relative Jacobian
428Coordinates`, Björn Fay https://eprint.iacr.org/2014/1014.pdf
429- `Fast and Regular Algorithms for Scalar Multiplication
430over Elliptic Curves`, Matthieu Rivain https://eprint.iacr.org/2011/338.pdf
431- `High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves`, Jean-Luc Beuchat, Jorge E. González-Díaz, Shigeo Mitsunari, Eiji Okamoto, Francisco Rodríguez-Henríquez, and Tadanori Teruya https://eprint.iacr.org/2010/354.pdf
432- `New software speed records for cryptographic pairings`, Michael Naehrig, Ruben Niederhagen, Peter Schwabe https://cryptojedi.org/papers/dclxvi-20100714.pdf
433- https://github.com/zcash/zcash/tree/master/src/snark
434- https://github.com/iden3/snarkjs
435- https://github.com/ethereum/py_ecc/tree/master/py_ecc/bn128
436
437- [x] Fq, Fq2, Fq6, Fq12 operations
438- [x] G1, G2 operations
439- [x] preparePairing
440- [x] PreComupteG1, PreComupteG2
441- [x] DoubleStep, AddStep
442- [x] MillerLoop
443- [x] Pairing
444
445
446#### Usage
447First let's assume that we have these three basic functions to convert integer compositions to big integer compositions:
448```go
449func iToBig(a int) *big.Int {
450 return big.NewInt(int64(a))
451}
452
453func iiToBig(a, b int) [2]*big.Int {
454 return [2]*big.Int{iToBig(a), iToBig(b)}
455}
456
457func iiiToBig(a, b int) [2]*big.Int {
458 return [2]*big.Int{iToBig(a), iToBig(b)}
459}
460```
461
462
463- Pairing
464```go
465bn128, err := NewBn128()
466assert.Nil(t, err)
467
468big25 := big.NewInt(int64(25))
469big30 := big.NewInt(int64(30))
470
471g1a := bn128.G1.MulScalar(bn128.G1.G, big25)
472g2a := bn128.G2.MulScalar(bn128.G2.G, big30)
473
474g1b := bn128.G1.MulScalar(bn128.G1.G, big30)
475g2b := bn128.G2.MulScalar(bn128.G2.G, big25)
476
477pA, err := bn128.Pairing(g1a, g2a)
478assert.Nil(t, err)
479pB, err := bn128.Pairing(g1b, g2b)
480assert.Nil(t, err)
481assert.True(t, bn128.Fq12.Equal(pA, pB))
482```
483
484- Finite Fields (1, 2, 6, 12) operations
485```go
486// new finite field of order 1
487fq1 := NewFq(iToBig(7))
488
489// basic operations of finite field 1
490res := fq1.Add(iToBig(4), iToBig(4))
491res = fq1.Double(iToBig(5))
492res = fq1.Sub(iToBig(5), iToBig(7))
493res = fq1.Neg(iToBig(5))
494res = fq1.Mul(iToBig(5), iToBig(11))
495res = fq1.Inverse(iToBig(4))
496res = fq1.Square(iToBig(5))
497
498// new finite field of order 2
499nonResidueFq2str := "-1" // i/j
500nonResidueFq2, ok := new(big.Int).SetString(nonResidueFq2str, 10)
501fq2 := Fq2{fq1, nonResidueFq2}
502nonResidueFq6 := iiToBig(9, 1)
503
504// basic operations of finite field of order 2
505res := fq2.Add(iiToBig(4, 4), iiToBig(3, 4))
506res = fq2.Double(iiToBig(5, 3))
507res = fq2.Sub(iiToBig(5, 3), iiToBig(7, 2))
508res = fq2.Neg(iiToBig(4, 4))
509res = fq2.Mul(iiToBig(4, 4), iiToBig(3, 4))
510res = fq2.Inverse(iiToBig(4, 4))
511res = fq2.Div(iiToBig(4, 4), iiToBig(3, 4))
512res = fq2.Square(iiToBig(4, 4))
513
514
515// new finite field of order 6
516nonResidueFq6 := iiToBig(9, 1) // TODO
517fq6 := Fq6{fq2, nonResidueFq6}
518
519// define two new values of Finite Field 6, in order to be able to perform the operations
520a := [3][2]*big.Int{
521 iiToBig(1, 2),
522 iiToBig(3, 4),
523 iiToBig(5, 6)}
524b := [3][2]*big.Int{
525 iiToBig(12, 11),
526 iiToBig(10, 9),
527 iiToBig(8, 7)}
528
529// basic operations of finite field order 6
530res := fq6.Add(a, b)
531res = fq6.Sub(a, b)
532res = fq6.Mul(a, b)
533divRes := fq6.Div(mulRes, b)
534
535
536// new finite field of order 12
537q, ok := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208583", 10) // i
538if !ok {
539 fmt.Println("error parsing string to big integer")
540}
541
542fq1 := NewFq(q)
543nonResidueFq2, ok := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208582", 10) // i
544assert.True(t, ok)
545nonResidueFq6 := iiToBig(9, 1)
546
547fq2 := Fq2{fq1, nonResidueFq2}
548fq6 := Fq6{fq2, nonResidueFq6}
549fq12 := Fq12{fq6, fq2, nonResidueFq6}
550
551```
552
553- G1 operations
554```go
555bn128, err := NewBn128()
556assert.Nil(t, err)
557
558r1 := big.NewInt(int64(33))
559r2 := big.NewInt(int64(44))
560
561gr1 := bn128.G1.MulScalar(bn128.G1.G, bn128.Fq1.Copy(r1))
562gr2 := bn128.G1.MulScalar(bn128.G1.G, bn128.Fq1.Copy(r2))
563
564grsum1 := bn128.G1.Add(gr1, gr2)
565r1r2 := bn128.Fq1.Add(r1, r2)
566grsum2 := bn128.G1.MulScalar(bn128.G1.G, r1r2)
567
568a := bn128.G1.Affine(grsum1)
569b := bn128.G1.Affine(grsum2)
570assert.Equal(t, a, b)
571assert.Equal(t, "0x2f978c0ab89ebaa576866706b14787f360c4d6c3869efe5a72f7c3651a72ff00", utils.BytesToHex(a[0].Bytes()))
572assert.Equal(t, "0x12e4ba7f0edca8b4fa668fe153aebd908d322dc26ad964d4cd314795844b62b2", utils.BytesToHex(a[1].Bytes()))
573```
574
575- G2 operations
576```go
577bn128, err := NewBn128()
578assert.Nil(t, err)
579
580r1 := big.NewInt(int64(33))
581r2 := big.NewInt(int64(44))
582
583gr1 := bn128.G2.MulScalar(bn128.G2.G, bn128.Fq1.Copy(r1))
584gr2 := bn128.G2.MulScalar(bn128.G2.G, bn128.Fq1.Copy(r2))
585
586grsum1 := bn128.G2.Add(gr1, gr2)
587r1r2 := bn128.Fq1.Add(r1, r2)
588grsum2 := bn128.G2.MulScalar(bn128.G2.G, r1r2)
589
590a := bn128.G2.Affine(grsum1)
591b := bn128.G2.Affine(grsum2)
592assert.Equal(t, a, b)
593```
594
595
596---
597
598To run all tests:
599```
600go test ./... -v
601```