### # Shamir's Secret Sharing

```# `cat shamir_secret_sharing.py`
import random
import sys

secret = int(sys.argv[1])
components = int(sys.argv[2])
at_least = int(sys.argv[3])

def is_prime(number):
return all(number % i for i in xrange(2, int(number ** 0.5) + 1))

def get_next_prime(number):
next_number = number + 1
while not is_prime(next_number):
next_number += 1
return next_number

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
return None  # modular inverse does not exist
else:
return x % m

def split(prime, number, available, needed):
coef = [number]
shares = []
for i in xrange(1, needed):
coef.append(random.randrange(0, prime))
for x in xrange(1, available + 1):
# coef[0]x^0 + coef[1]x^1 + ... + coef[n]x^n
accum = coef[0]
for e in xrange(1, needed):
accum += ((coef[e] * pow(x, e, prime)) % prime)
accum = accum % prime
shares.append((x, accum))
return coef, shares

def get_random_shares(available, number, shares):
newshares = []
selected = []
for i in xrange(0, number):
r = random.randrange(0, available)
while r in selected:
r = random.randrange(0, available)
selected.append(r)
newshares.append(shares[r])
return newshares

def merge(prime, shares):
accum = 0
# Lagrange's interpolation
for formula in xrange(0, len(shares)):
numerator = denominator = 1
for count in xrange(0, len(shares)):
if formula == count:
continue
startpos = shares[formula][0]
nextpos = shares[count][0]
numerator = (numerator * -1 * nextpos) % prime
denominator = (denominator * (startpos - nextpos)) % prime
value = shares[formula][1]
accum = (prime + accum + (value * numerator * modinv(denominator, prime))) % prime
return accum

print 'Secret =', secret
prime = get_next_prime(secret)
print 'Prime =', prime
coef, shares = split(prime, secret, components, at_least)
print 'Coefficients =', coef
print 'Subsecrets =', shares
newshares = get_random_shares(components, at_least, shares)
print 'Random subsecrets =', newshares
secret = merge(prime, newshares)
print 'Recovered secret =', secret

# `python shamir_secret_sharing.py 1337 7 3`
Secret = 1337
Prime = 1361
Coefficients = [1337, 255, 752]
Subsecrets = [(1, 983), (2, 772), (3, 704), (4, 779), (5, 997), (6, 1358), (7, 501)]
Random subsecrets = [(6, 1358), (4, 779), (7, 501)]
Recovered secret = 1337```

Reference

https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

### # ElGamal algorithm

```# `cat elgamal.py`
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
return None  # modular inverse does not exist
else:
return x % m

p = 467 # prime
g = 2 # generator
ru = 127 # random
pu = g**ru % p # public
m = 100 # message

print '[+] Encryption'
print
print 'm =', m
re = 140 # random
pe = g**re % p # public
c = (pu**re * m) % p # cipher
print 'c =', c
print

print '[+] Decryption (c, p, g, pe)'
print
print 'c =', c
# m = (c / (pe**r1)) % p
m = (c * pe**(p - 1 - ru)) % p
print 'm =', m
print

print '[+] Signature'
print
hm = m * 2 # 'hash'
print 'h(m) =', hm
rs = 213 # random
ps = g**rs % p
s = ((hm - (ru*ps)) * modinv(rs, p - 1)) % (p - 1) # sign
print 's =', s
print

print '[+] Verification (hm, s, p, g, pu, ps)'
print
print 'h(m) =', hm
print 's =', s
v1 = g**hm % p
v2 = (pu**ps * ps**s) % p
if v1 == v2:
print 'v1 = v2 =', v1, '- Signature is ok'

# `python elgamal.py`
[+] Encryption

m = 100
c = 391

[+] Decryption (c, p, g, pe)

c = 391
m = 100

[+] Signature

h(m) = 200
s = 279

[+] Verification (hm, s, p, g, pu, ps)

h(m) = 200
s = 279
v1 = v2 = 229 - Signature is ok```

Reference

https://en.wikipedia.org/wiki/ElGamal_encryption

### # Diffie-Hellman key exchange

```# `cat diffie-hellman.py`
import math

# Zp*
# |Z9*| = totien(9) = 9(1 - 1/3) = 6
# a        1  2  4  5  7  8
# ord(a)   1  6  3  6  3  2
# generators: 2 and 5

g = 2 # generator
p = 9 # prime

print '1. [Alice] and [ Bob ] agree to use g = %d and p = %d' % (g, p)
print

a = 15 # alice secret
A = (g**a) % p
print '2. [Alice] Generates a = %d and sends A = %d' % (a, A)
print

b = 7 # bob secret
B = (g**b) % p
print '3. [ Bob ] Generates b = %d and sends B = %d' % (b, B)
print

a_shared_secret = (B**a) % p
print '4. [Alice] Computes the shared_secret = %d' % a_shared_secret
print

b_shared_secret = (A**b) % p
print '5. [ Bob ] Computes the shared_secret = %d' % b_shared_secret
print

print '6. [Alice] and [ Bob ] now share the same secret'
print

print '-' * 50 + '\n'

def brute_force(shared):
for i in xrange(0, 100):
if (g**i) % p == shared:
print str(i),
print

ea = (math.log(A, g)) % p
print '7. [ Eve ] Tries to find a, knowing (A, g and p)'
print 'Logarithm >> a = %d' % ea
print 'Brute force >>',
brute_force(A)
print
eb = (math.log(B, g)) % p
print '8. [ Eve ] Tries to find b, knowing (B, g and p)'
print 'Logarithm >> b = %d' % eb
print 'Brute force >>',
brute_force(B)

# `python diffie-hellman.py`
1. [Alice] and [ Bob ] agree to use g = 2 and p = 9

2. [Alice] Generates a = 15 and sends A = 8

3. [ Bob ] Generates b = 7 and sends B = 2

4. [Alice] Computes the shared_secret = 8

5. [ Bob ] Computes the shared_secret = 8

6. [Alice] and [ Bob ] now share the same secret

--------------------------------------------------

7. [ Eve ] Tries to find a, knowing (A, g and p)
Logarithm >> a = 3
Brute force >> 3 9 15 21 27 33 39 45 51 57 63 69 75 81 87 93 99

8. [ Eve ] Tries to find b, knowing (B, g and p)
Logarithm >> b = 1
Brute force >> 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97```

Reference

https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

### # Fermat primality test

Fermat's little theorem

a**p =~ a (mod p)
a**p mod p = a mod p

Algorithm

```# `cat FermatPrimalityTest.go`
package main

import "fmt"
import "math/big"
import "os"
import "strconv"

func add(x, y int) int {
return x + y
}

func main() {
prime, err1 := strconv.Atoi(os.Args[1])
limit, err2 := strconv.Atoi(os.Args[2])
if err1 == nil && err2 == nil {
for i := 1; i < limit; i++ {
exp := new(big.Int).Exp(big.NewInt(int64(i)), big.NewInt(int64(prime)), nil)
left := new(big.Int).Mod(exp, big.NewInt(int64(prime)))
right := new(big.Int).Mod(big.NewInt(int64(i)), big.NewInt(int64(prime)))
if left.Cmp(right) != 0 {
fmt.Printf("%d != %d\n", left, right)
fmt.Printf("Not prime!\n");
return
}
}
}
fmt.Printf("Prime!\n");
}

# `go build FermatPrimalityTest.go`

# `./FermatPrimalityTest 7 1000`
Prime!
# `carmichael_number_1=561`
# `carmichael_number_2=41041`
# `./FermatPrimalityTest \$carmichael_number_1 1000`
Prime! <-- False
# `./FermatPrimalityTest \$carmichael_number_2 1000`
Prime! <-- False```

References

https://en.wikipedia.org/wiki/Carmichael_number