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 pairing](#bn128)
16- [BLS signature](#bls)
17
18---
19
20## RSA cryptosystem & Blind signature & Homomorphic Multiplication
21- https://en.wikipedia.org/wiki/RSA_(cryptosystem)#
22- https://en.wikipedia.org/wiki/Blind_signature
23- https://en.wikipedia.org/wiki/Homomorphic_encryption
24
25- [x] GenerateKeyPair
26- [x] Encrypt
27- [x] Decrypt
28- [x] Blind
29- [x] Blind Signature
30- [x] Unblind Signature
31- [x] Verify Signature
32- [x] Homomorphic Multiplication
33
34
35#### Usage
36- Key generation, Encryption, Decryption
37```go
38// generate key pair
39key, err := GenerateKeyPair()
40if err!=nil {
41 fmt.Println(err)
42}
43mBytes := []byte("Hi")
44m := new(big.Int).SetBytes(mBytes)
45
46// encrypt message
47c := Encrypt(m, key.PubK)
48
49// decrypt ciphertext
50d := Decrypt(c, key.PrivK)
51if m == d {
52 fmt.Println("correctly decrypted")
53}
54```
55
56- Blind signatures
57```go
58// key generation [Alice]
59key, err := GenerateKeyPair()
60if err!=nil {
61 fmt.Println(err)
62}
63
64// create new message [Alice]
65mBytes := []byte("Hi")
66m := new(big.Int).SetBytes(mBytes)
67
68// define r value [Alice]
69rVal := big.NewInt(int64(101))
70
71// blind message [Alice]
72mBlinded := Blind(m, rVal, key.PubK)
73
74// Blind Sign the blinded message [Bob]
75sigma := BlindSign(mBlinded, key.PrivK)
76
77// unblind the blinded signed message, and get the signature of the message [Alice]
78mSigned := Unblind(sigma, rVal, key.PubK)
79
80// verify the signature [Alice/Bob/Trudy]
81verified := Verify(m, mSigned, key.PubK)
82if !verified {
83 fmt.Println("signature could not be verified")
84}
85```
86
87- Homomorphic Multiplication
88```go
89// key generation [Alice]
90key, err := GenerateKeyPair()
91if err!=nil {
92 fmt.Println(err)
93}
94
95// define values [Alice]
96n1 := big.NewInt(int64(11))
97n2 := big.NewInt(int64(15))
98
99// encrypt the values [Alice]
100c1 := Encrypt(n1, key.PubK)
101c2 := Encrypt(n2, key.PubK)
102
103// compute homomorphic multiplication with the encrypted values [Bob]
104c3c4 := HomomorphicMul(c1, c2, key.PubK)
105
106// decrypt the result [Alice]
107d := Decrypt(c3c4, key.PrivK)
108
109// check that the result is the expected
110if !bytes.Equal(new(big.Int).Mul(n1, n2).Bytes(), d.Bytes()) {
111 fmt.Println("decrypted result not equal to expected result")
112}
113```
114
115## Paillier cryptosystem & Homomorphic Addition
116- https://en.wikipedia.org/wiki/Paillier_cryptosystem
117- https://en.wikipedia.org/wiki/Homomorphic_encryption
118
119- [x] GenerateKeyPair
120- [x] Encrypt
121- [x] Decrypt
122- [x] Homomorphic Addition
123
124#### Usage
125- Encrypt, Decrypt
126```go
127// key generation
128key, err := GenerateKeyPair()
129if err!=nil {
130 fmt.Println(err)
131}
132
133mBytes := []byte("Hi")
134m := new(big.Int).SetBytes(mBytes)
135
136// encryption
137c := Encrypt(m, key.PubK)
138
139// decryption
140d := Decrypt(c, key.PubK, key.PrivK)
141if m == d {
142 fmt.Println("ciphertext decrypted correctly")
143}
144```
145
146- Homomorphic Addition
147```go
148// key generation [Alice]
149key, err := GenerateKeyPair()
150if err!=nil {
151 fmt.Println(err)
152}
153
154// define values [Alice]
155n1 := big.NewInt(int64(110))
156n2 := big.NewInt(int64(150))
157
158// encrypt values [Alice]
159c1 := Encrypt(n1, key.PubK)
160c2 := Encrypt(n2, key.PubK)
161
162// compute homomorphic addition [Bob]
163c3c4 := HomomorphicAddition(c1, c2, key.PubK)
164
165// decrypt the result [Alice]
166d := Decrypt(c3c4, key.PubK, key.PrivK)
167if !bytes.Equal(new(big.Int).Add(n1, n2).Bytes(), d.Bytes()) {
168 fmt.Println("decrypted result not equal to expected result")
169}
170```
171
172
173## Shamir Secret Sharing
174- https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
175
176- [x] create secret sharing from number of secrets needed, number of shares, random point p, secret to share
177- [x] Lagrange Interpolation to restore the secret from the shares
178
179#### Usage
180```go
181// define secret to share
182k := 123456789
183
184// define random prime
185p, err := rand.Prime(rand.Reader, bits/2)
186if err!=nil {
187 fmt.Println(err)
188}
189
190// define how many shares want to generate
191nShares := big.NewInt(int64(6))
192
193// define how many shares are needed to recover the secret
194nNeededShares := big.NewInt(int64(3))
195
196// create the shares
197shares, err := Create(
198 nNeededShares,
199 nShares,
200 p,
201 big.NewInt(int64(k)))
202assert.Nil(t, err)
203if err!=nil {
204 fmt.Println(err)
205}
206
207// select shares to use
208var sharesToUse [][]*big.Int
209sharesToUse = append(sharesToUse, shares[2])
210sharesToUse = append(sharesToUse, shares[1])
211sharesToUse = append(sharesToUse, shares[0])
212
213// recover the secret using Lagrange Interpolation
214secr := LagrangeInterpolation(sharesToUse, p)
215
216// check that the restored secret matches the original secret
217if !bytes.Equal(k.Bytes(), secr.Bytes()) {
218 fmt.Println("reconstructed secret not correspond to original secret")
219}
220```
221
222## Diffie-Hellman
223- https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
224
225- [x] key exchange
226
227## ECC
228- https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
229
230- [x] define elliptic curve
231- [x] get point at X
232- [x] get order of a Point on the elliptic curve
233- [x] Add two points on the elliptic curve
234- [x] Multiply a point n times on the elliptic curve
235
236#### Usage
237- ECC basic operations
238```go
239// define new ec
240ec := NewEC(big.NewInt(int64(0)), big.NewInt(int64(7)), big.NewInt(int64(11)))
241
242// define two points over the curve
243p1 := Point{big.NewInt(int64(4)), big.NewInt(int64(7))}
244p2 := Point{big.NewInt(int64(2)), big.NewInt(int64(2))}
245
246// add the two points
247q, err := ec.Add(p1, p2)
248if err!=nil {
249 fmt.Println(err)
250}
251
252// multiply the two points
253q, err := ec.Mul(p, big.NewInt(int64(1)))
254if err!=nil {
255 fmt.Println(err)
256}
257
258// get order of a generator point over the elliptic curve
259g := Point{big.NewInt(int64(7)), big.NewInt(int64(8))}
260order, err := ec.Order(g)
261if err!=nil {
262 fmt.Println(err)
263}
264```
265
266
267
268
269## ECC ElGamal
270- https://en.wikipedia.org/wiki/ElGamal_encryption
271
272- [x] ECC ElGamal key generation
273- [x] ECC ElGamal Encrypton
274- [x] ECC ElGamal Decryption
275
276
277#### Usage
278- NewEG, Encryption, Decryption
279```go
280// define new elliptic curve
281ec := ecc.NewEC(big.NewInt(int64(1)), big.NewInt(int64(18)), big.NewInt(int64(19)))
282
283// define new point
284g := ecc.Point{big.NewInt(int64(7)), big.NewInt(int64(11))}
285
286// define new ElGamal crypto system with the elliptic curve and the point
287eg, err := NewEG(ec, g)
288if err!=nil {
289 fmt.Println(err)
290}
291
292// define privK&pubK over the elliptic curve
293privK := big.NewInt(int64(5))
294pubK, err := eg.PubK(privK)
295if err!=nil {
296 fmt.Println(err)
297}
298
299// define point to encrypt
300m := ecc.Point{big.NewInt(int64(11)), big.NewInt(int64(12))}
301
302// encrypt
303c, err := eg.Encrypt(m, pubK, big.NewInt(int64(15)))
304if err!=nil {
305 fmt.Println(err)
306}
307
308// decrypt
309d, err := eg.Decrypt(c, privK)
310if err!=nil {
311 fmt.Println(err)
312}
313
314// check that decryption is correct
315if !m.Equal(d) {
316 fmt.Println("decrypted not equal to original")
317}
318```
319
320
321
322## ECC ECDSA
323- https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
324
325- [x] define ECDSA data structure
326- [x] ECDSA Sign
327- [x] ECDSA Verify signature
328
329
330#### Usage
331```go
332// define new elliptic curve
333ec := ecc.NewEC(big.NewInt(int64(1)), big.NewInt(int64(18)), big.NewInt(int64(19)))
334// define new point
335g := ecc.Point{big.NewInt(int64(7)), big.NewInt(int64(11))}
336
337// define new ECDSA system
338dsa, err := NewDSA(ec, g)
339if err!=nil {
340 fmt.Println(err)
341}
342
343// define privK&pubK over the elliptic curve
344privK := big.NewInt(int64(5))
345pubK, err := dsa.PubK(privK)
346if err!=nil {
347 fmt.Println(err)
348}
349
350// hash value to sign
351hashval := big.NewInt(int64(40))
352
353// define r
354r := big.NewInt(int64(11))
355
356// sign hashed value
357sig, err := dsa.Sign(hashval, privK, r)
358if err!=nil {
359 fmt.Println(err)
360}
361
362// verify signature
363verified, err := dsa.Verify(hashval, sig, pubK)
364if err!=nil {
365 fmt.Println(err)
366}
367if verified {
368 fmt.Println("signature correctly verified")
369}
370```
371
372## Schnorr signature
373- https://en.wikipedia.org/wiki/Schnorr_signature
374
375- [x] Hash[M || R] (where M is the msg bytes and R is a Point on the ECC, using sha256 hash function)
376- [x] Generate Schnorr scheme
377- [x] Sign
378- [x] Verify signature
379
380
381#### Usage
382```go
383// define new elliptic curve
384ec := ecc.NewEC(big.NewInt(int64(0)), big.NewInt(int64(7)), big.NewInt(int64(11)))
385// define new point
386g := ecc.Point{big.NewInt(int64(11)), big.NewInt(int64(27))} // Generator
387// define new random r
388r := big.NewInt(int64(23)) // random r
389
390// define new Schnorr crypto system using the values
391schnorr, sk, err := Gen(ec, g, r)
392if err!=nil {
393 fmt.println(err)
394}
395
396// define message to sign
397m := []byte("hola")
398
399// 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
400h := Hash([]byte("hola"), c)
401if h.String() != "34719153732582497359642109898768696927847420320548121616059449972754491425079") {
402 fmt.Println("not correctly hashed")
403}
404
405s, rPoint, err := schnorr.Sign(sk, m)
406if err!=nil {
407 fmt.println(err)
408}
409
410// verify Schnorr signature
411verified, err := Verify(schnorr.EC, sk.PubK, m, s, rPoint)
412if err!=nil {
413 fmt.println(err)
414}
415if verified {
416 fmt.Println("Schnorr signature correctly verified")
417}
418```
419
420
421
422## Bn128
423Implementation of the bn128 pairing.
424Code moved to https://github.com/arnaucube/go-snark/tree/master/bn128
425
426
427## BLS
428Boneh–Lynn–Shacham (BLS) signature scheme implemented in Go.
429https://en.wikipedia.org/wiki/Boneh%E2%80%93Lynn%E2%80%93Shacham
430
431This package uses the BN128 Go implementation from https://github.com/arnaucube/go-snark/tree/master/bn128
432
433### Usage
434```go
435bls, err := NewKeys()
436assert.Nil(t, err)
437
438fmt.Println("privK:", bls.PrivK)
439fmt.Println("pubK:", bls.PubK)
440
441m := []byte("test")
442sig := bls.Sign(m)
443fmt.Println("signature:", sig)
444
445verified := bls.Verify(m, sig, bls.PubK)
446assert.True(t, verified)
447
448/* out:
449privK: 28151522174243194157727175362620544050084772361374505986857263387912025505082855947281432752362814690196305655335201716186584298643231993241609823412370437094839017595372164876997343464950463323765646363122343203470911131219733598647659483557447955173651057370197665461325593653581904430885385707255151472097067657072671643359241937143381958053903725229458882818033464163487351806079175441316235756460455300637131488613568714712448336232283394011955460567718918055245116200622473324300828876609569556897836255866438665750954410544846238847540023603735360532628141508114304504053826700874403280496870140784630677100277
450pubK: [528167154220154970470523315181365784447502116458960328551053767278433374201 18282159022449399855128689249640771309991127595389457870089153259100566421596 19728585501269572907574045312283749798205079570296187960832716959652451330253]
451signature: [[12832528436266902887734423636380781315321578271441494003771296275495461508593 6964131770814642748778827029569297554111206304527781019989920684169107205085] [6508357389516441729339280841134358160957092583050390612877406497974519092306 12073245715182483402311045895787625736998570529454024932833669602347318770866] [13520730275909614846121720877644124261162513989808465368770765804305866618385 19571107788574492009101590535904131414163790958090376021518899789800327786039]]
452verified: true
453*/
454```
455
456
457---
458
459To run all tests:
460```
461go test ./... -v
462```