# simple_crpto.py DMQ 28-Jan-10
'''
Python is great for crypto.
1) Easy interactive environment for prototyping and experimentation.
2) Long integers for public keys, etc.
Run this file in Python. Try the commands in the >>> examples.
'''
### Random Bits
from random import getrandbits
a,b,m = getrandbits(512), getrandbits(512), getrandbits(384) # long integers
'''
>>> a
87638194511408989261438753250719754638828743912429765499507120091357674569882808
90862859998699808605307665820696568046132523175744106743803372585080828726L
>>> b
57579891920620594921553065324099857848201813159629630310669085501543819427295796
09887603084816533251318617299467986239404540879435342090928431485352784952L
>>> m
33980144669810108281160822352744739279623941703077092883034667556498921065193304
60680842427694402677672470050075321L
'''
# Exponentials like a ** b (mod m) are common in crpto systems.
exp = pow(a, b, m) # pow() is a function written in C - very fast.
'''
>>> pow(a, b, m)
26616164385017850397090293477494464399221960596510492575571803619978316656538353
42475518596170907523282061732994456L
'''
### Substitution Cipher
import string
smap = string.maketrans('ABCDEFGHIJKLMNOPQRSTUVWXYZ', # translation table
'dlryvohezxwptbgfjqnmuskaci')
ctext = 'MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA' # ciphertext from Stinson p.8
ptext = ctext.translate(smap)
'''
>>> ptext
'thisciphertextcannotbedecrypted'
'''
### Message Digest
from Crypto.Hash import SHA # 160-bit hash function (SHA1)
md = SHA.new() # a new message digest object
md.update('abcde') # stir in some text
md1 = md.hexdigest() # snapshot of the digest
md.update('f') # a little more text
md2 = md.hexdigest() # digest is completely changed
# diffusion of entropy is excellent
'''
>>> print md1, '\n', md2
03de6c570bfe24bfc328ccd7ca46b76eadaf4334
1f8ac10f23c5b5bc1167bda84b833e5c057a77d2
'''
### Games of Chance
from random import randint, choice, sample, shuffle
r3 = randint(100, 999) # random 3-digit integer
print r3
hand = ['Jack H', 'Queen D', 'King C', 'Ace S', 'Joker']
pick = choice(hand)
print pick
samp = sample(xrange(10000000), 8) # random sample, 8 items
print samp
shuffle(samp) # shuffle in place
print samp
### Define functions
def factors(N): return [n for n in xrange(2, N//2 + 1) if N % n == 0]
'''
>>> factors(9999)
[3, 9, 11, 33, 99, 101, 303, 909, 1111, 3333]
'''
def factorial(N):
'''
>>> factorial(6)
720
'''
## if N == 1:
## return 1
## else:
## return N * factorial(N-1)
f = 1
for n in range(2, N):
f *= n
return f
def primes(N):
'''Return a list of the 10 largest prime numbers less than N.
>>> primes(1000)
[937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
'''
workset = [2, 3, 5, 7] # start with all primes less than 11
for n in xrange(11, N, 2): # check every odd number starting with 11
for p in workset:
if n % p == 0: # remainder of n//p is zero, therefore
break # n is not a prime
else:
workset.append(n) # append n to the workset
return workset[-10:] # return just the last 10 numbers
def primefactors(N):
'''Return a list of the prime factors of N, including multiple factors.
>>> primefactors(9999)
[3, 3, 11, 101]
'''
for n in xrange(2, N//2 + 1): # look for the smallest factor
q,r = divmod(N, n)
if r == 0: # n is a factor
pf = [n]
pf.extend(primefactors(q)) # recursive call
return pf
return [N]
def eulerphi(N):
'''Return the number of integers less than N that are coprime to N.
>>> eulerphi(999) # (37-1) * (3*3*3 - 3*3)
648
'''
pf = primefactors(N) # assume a list with at least one element
# [ 3, 3, 3, 37]
L = len(pf) # ^ ^
left = right = 0 # left right
phi = 1
while right < L:
while pf[right] == pf[left]:
right += 1
if right == L: break
p = pf[left]; e = right - left
left = right
phi *= (p**e - p**(e-1))
return phi
def inverse(k, m):
'''Return the multiplicative inverse in Zm of an integer k. Return 0 if
there is no inverse.
>>> inverse(5, 26)
21
>>> inverse(-19, 26)
15
>>> inverse(13, 26)
0
'''
for j in range(m): # trial and error
if k*j % m == 1: return j
return 0
from copy import deepcopy # needed for copying matrices
def determinant(K, m):
'''Find the determinant of square matrix K, modulo m.
>>> determinant([[10, 5, 12], [3, 14, 21], [8, 9, 11]], 26)
7
'''
size = len(K)
assert len(K[0]) == size # matrix must be square
assert size >= 2 # and it must be at least 2 x 2
if size == 2: return ( K[0][0] * K[1][1] - K[1][0] * K[0][1] ) % 26
i = 0; det = 0
for j in range(size):
coeff = (-1)**(i + j) * K[i][j]
Kij = deepcopy(K) # fresh copy for each recursion
Kij.pop(i) # delete row i
[Kij[n].pop(j) for n in range(size-1)] # delete column j
## print coeff, Kij
det = (det + coeff * determinant(Kij, m) ) % m
return det
from math import log
def entropy(Pn):
'''Return the entropy of probability distibution Pn, a list of the
probabilities of each element.
>>> entropy([(1/2.), (1/3.), (1/6.)])
1.459
'''
H = 0.0
for P in Pn:
H -= P * log(P, 2)
return H
from math import sqrt, pi, e
def stirl(n):
'''Return an estimate of n! using Stirling's formula
'''
return sqrt(2*pi*n) * pow(n/e, n)