"""
Clubhouse crypto:  simple substitution, easily cracked
(but useful for learning purposes).

Permutation class S appended to facilitate group theory
approach to permutations as per this thread archived
at the Math Forum:

http://www.mathforum.com/epigone/mathedu/swexprundwand
"""
import string, random

def permute(pool):
    """
    Randomly permute whatever list is passed in as pool
    """
    oldlist = []+list(pool)
    newlist = []
    for i in range(len(oldlist)): # = range(26)
        randitem = random.choice(oldlist)
        oldlist.remove(randitem)
        newlist.append(randitem)
    return newlist

def mkdict(n=0):
    """
    Pair uppercase alphabet or integers 1...n with
    randomly permuted version of same
    """
    if n>0:  pool = range(1,n+1)
    else:    pool = string.uppercase
    tuples = zip(pool,permute(pool))
    codedict = {}
    for pair in tuples:
        codedict[pair[0]]=pair[1]
    return codedict

def mkkey(codedict):
    """
    Return key as a list of cyclic tuples, e.g.
    [('A','R','C'),('D','Q')...]
    """
    dictkeys = codedict.keys()
    result = []
    for i in dictkeys[:]:  # using copy of dictkeys
        newtuple = ()      
        if i in dictkeys and not codedict[i]==i:
            initval,nextval = i,i
            while 1:
               newtuple += (nextval,)
               dictkeys.remove(nextval)               
               nextval = codedict[nextval]
               if nextval==initval:  # cycle complete
                   break
            result.append(newtuple)
    return result

def gendict(keytuples):
    """
    generate a dictionary from a list of cyclic tuples
    """
    result = {} # return a dictionary
    for cycle in keytuples:
        rot1 = (cycle+(cycle[0],))[1:]
        for i in range(len(cycle)):
            result[cycle[i]]=rot1[i]
    return result

def revkey(keytuples):
    """
    Reverse all the cyclic tuples in a list of tuples
    """
    result = []
    for i in keytuples:
        temp = list(i)
        temp.reverse()
        result.append(tuple(temp))
    return result
    
def encrypt(filename):
    """
    Use a permuted alphabet to encrypte a .txt file --
    saving the key and file separately.  Save file
    as filename.cpt, the codekey as filename.key
    """
    encfile = filename[:string.rfind(filename,".")]+".cpt"
    keyfile = filename[:string.rfind(filename,".")]+".key"
    
    print "Writing to " + encfile
    print "Saving key as " + keyfile

    txtfileobj = open(filename,'r')    
    encfileobj = open(encfile,'w')
    keyfileobj = open(keyfile,'w')
    
    thedict = mkdict()
    
    for line in txtfileobj.readlines():
        uline = string.upper(line)
        encline = ""
        for char in uline:
            if char in string.uppercase:
               encline = encline + thedict[char]
            else:
               encline = encline + char            
        encfileobj.write(encline)
    
    keyfileobj.write(str(mkkey(thedict)) + "\n")
        
    txtfileobj.close()
    encfileobj.close()
    keyfileobj.close()
    
def decrypt(filename):
    """
    Use a codekey to decrypt a file (see encrypt)
    """

    txtfile  = filename[:string.rfind(filename,".")]+".dcp"
    keyfile  = filename[:string.rfind(filename,".")]+".key"
    
    print "Reading from " + filename
    print "Writing to " + txtfile
    print "Using key " + keyfile
    print ""

    encfileobj = open(filename,'r')
    txtfileobj = open(txtfile,'w')    
    keyfileobj = open(keyfile,'r')

    temp    = eval(keyfileobj.readline())
    thekey  = revkey(temp)    # reverse the key tuples
    thedict = gendict(thekey) # generate reverse lookup dictionary

    for line in encfileobj.readlines():
        dcpline = ""        
        for char in line:
            if char in thedict.keys():
               dcpline = dcpline + thedict[char]
            else:
               dcpline = dcpline + char
        print dcpline[:-1]
        txtfileobj.write(dcpline)
    
    encfileobj.close()
    txtfileobj.close()
    keyfileobj.close()

def gcd(a,b):
   """Return greatest common divisor using Euclid's Algorithm."""
   while b:      
	a, b = b, a % b
   return a

def lcm(a,b):
   """
   Return lowest common multiple."""
   return (a*b)/gcd(a,b)

def LCM(terms):
   "Return lcm of a list of numbers."   
   return reduce(lambda a,b: lcm(a,b), terms)

class S:
    """
    Defines a permuation and operations therewith
    """

    def __init__(self,n=0,dict={}):
        # specify n>0 for permutation of integers 1...n
        # specify dict={...} to initialize w/ specific dictionary
        # p1 = S() defaults to permutation of uppercase A-Z
        if len(dict.keys())>0:
            self.dict = dict
        elif n==0:
            self.dict = mkdict()
        else:
            self.dict = mkdict(n)

    def __mul__(self,other):
        newdict = {}
        for i in other.dict.keys():
            newdict[i] = self.dict[other.dict[i]]
        return S(dict=newdict)

    def __repr__(self):
        return str(mkkey(self.dict))
    
    def __pow__(self,n):
        r = S(dict=self.dict)
        if n==0:  # return identity 
            return r*r.inv()
        elif abs(n)>1:
            for i in range(1,abs(n)):
               r *= S(dict=self.dict)
        if n<0:
            r = r.inv()
        return r

    def __eq__(self,other):  # new syntax ver. 2.1
        rtn = 1
        for i in self.dict.keys():
            if self.dict[i] != other.dict[i]:
                rtn = 0
                break
        return rtn

    def len(self):
        return len(self.dict)
    
    def inv(self):
        newdict = {}
        for i in self.dict.keys():
            newdict[self.dict[i]] = i
        return S(dict=newdict)
    
    def order(self):
        tuples = mkkey(self.dict)
        return LCM(map(len,tuples))