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