# 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(abm)  # 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 randintchoicesampleshuffle

r3 = randint(100999)              # 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(2N//2 + 1if 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(2N):
        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 = [2357]   # start with all primes less than 11
    
    for n in xrange(11N2):  # 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(2N//2 + 1):  # look for the smallest factor
        
        q,r = divmod(Nn)
        
        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 == Lbreak
            
        p = pf[left]; e = right - left
        left = right
        
        phi *= (p**e - p**(e-1))

    return phi

def inverse(km):
    '''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(Km):
    '''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 = 0det = 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(jfor n in range(size-1)] # delete column j

        ## print coeff, Kij        
        det = (det + coeff * determinant(Kijm) ) % 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(P2)

    return H

from math import sqrtpie
def stirl(n):
    '''Return an estimate of n! using Stirling's formula
    '''
    return sqrt(2*pi*n) * pow(n/en)