hacktracking: February 2016

# 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