""" bomba.py 2006-09-14 CJ Odenthal """ import operator from string import ascii_uppercase as UPPER from string import ascii_lowercase as LOWER from copy import deepcopy from permutations import Permutation from enigma import Rotor,Enigma identity = Permutation(UPPER) def char2int(key): try: c = key.upper() return UPPER.index(c) except: return key def gcd(a,b): try: return gcd(b,a%b) except: return abs(a) def lcm(a,b=1): return abs(a*b)/gcd(a,b) # This class still needs to be checked to see if it performs correctly. class DoubleEnigma(object): def __init__(self, config, wheels = None, # 3 regular wheels thin = None, # 0 or 1 thin wheel UKW = None, # Reflector ringstellung = None, # Ring setting grundstellung = None, # Ground setting stecker = None, # stecker ): """ config is a dictionary with the following keys: 'wheels' (aka rotors) A dictionary 'thin' (thin rotors) A dictionary (for 4 wheel enigmas) 'UKWs' (aka reflectors) A dictionary 'ETW' (aka QWERTZU) A 'Permutation' 'stecker' (True or False) Is there a stecker? 'dblstep' (True or False) Double stepping of middle rotors? 'UKWring' (True of False) Ring setting for UKW? 'UKWstep' (True of False) Does UKW step? The wheel list should be given from slowest to fastest: W_L, W_M, W_R. The ringstellung and grundstellung are given as strings, e.g. 'ACX'. Any valid options not given during initialization are prompted for. """ self.ETW = config['ETW'] # Get the wheels. if not wheels: wheels = raw_input("Choose 3 wheels (slow middle fast) from %s: " % config['wheels'].keys()) wheels = str(wheels).replace(' ','') # Get the thin wheel if needed. if config['thin']: if not thin: thin = raw_input("Choose a thin wheel from %s: " % config['thin'].keys()) thin = thin.upper() else: thin = '' # Get the reflector. if len(config['UKWs']) > 1: if not UKW: UKW = raw_input("Choose a reflector from %s: " % config['UKWs'].keys()) UKW = UKW.upper() else: UKW = '' # Get the stecker if needed. if config['stecker']: if not stecker: stecker = raw_input("Choose an even number of letters to swap in pairs for your stecker board: ") stecker = stecker + ' ' else: stecker = ' ' self.setStecker(stecker) # Count the wheels with rings. nR = len(wheels)+len(thin) if config['UKWring']: nR += 1 # Get the ringstellung. if not ringstellung: ringstellung = raw_input("Choose a %s character 'ringstellung': " % (nR,)) ringstellung = ringstellung.replace(' ','').upper() # Make sure that they're both set with the fast wheel of the # second enigma 3 steps advanced from that of the first enigma. rLst = [0]*(nR-len(ringstellung)) + map(char2int,ringstellung) ringstellung1 = "".join([UPPER[k] for k in rLst]) rLst[-1] = (rLst[-1] + 3) % 26 ringstellung2 = "".join([UPPER[k] for k in rLst]) # Get the grundstellung. if not grundstellung: grundstellung = raw_input("Choose a %s character 'grundstellung': " % (nR,)) grundstellung = grundstellung.replace(' ','').upper() # Make sure they're both set. grundstellung = 'A'*(nR-len(grundstellung)) + grundstellung # Make a doubled enigma machine self.Enigmas = [Enigma(config=config, wheels=wheels, thin=thin, UKW=UKW, ringstellung=ringstellung1, grundstellung=grundstellung, stecker=' '), Enigma(config=config, wheels=wheels, thin=thin, UKW=UKW, ringstellung=ringstellung2, grundstellung=grundstellung, stecker=' ')] self.setPermutation() def __repr__(self): return repr(self.permutation) def __str__(self): return str(self.permutation) def __call__(self,text): return "".join(map(self.encipher,text)) def setStecker(self,stecker): try: steck = stecker.replace(' ','').upper() steck = map(UPPER.index,steck) N = len(steck) stecker = [(steck[2*k],steck[2*k+1]) for k in range(N/2)] except AttributeError: pass try: self.stecker = Permutation(stecker) except IndexError: self.stecker = identity except TypeError: self.stecker = stecker self.ES = self.ETW * self.stecker def setKeys(self,grundstellung): for E in self.Enigmas: E.setKeys(grundstellung) # A new key setting requires recalculation of the permutation. self.setPermutation() def setPermutation(self): for E in self.Enigmas: E.setPermutation() self.factors = [E.permutation for E in self.Enigmas] self.permutation = (reduce(operator.mul,self.factors) << self.ES) def keys(self): return self.Enigmas[0].keys() def turnovers(self): self.Enigmas[0].turnovers() def encipher(self,c): if c.upper() in UPPER: return self.permutation.encipher(c) else: return c # This class still needs to be checked to see if it performs correctly. class Bomba(object): def __init__(self, config, wheels = None, # 3 regular wheels thin = None, # 0 or 1 thin wheel UKW = None, # Reflector grundstellung = None, # Ground setting stecker = None, # stecker ): """ config is a dictionary with the following keys: 'wheels' (aka rotors) A dictionary 'thin' (thin rotors) A dictionary (for 4 wheel enigmas) 'UKWs' (aka reflectors) A dictionary 'ETW' (aka QWERTZU) A 'Permutation' 'stecker' (True or False) Is there a stecker? 'dblstep' (True or False) Double stepping of middle rotors? 'UKWring' (True of False) Ring setting for UKW? 'UKWstep' (True of False) Does UKW step? The wheel list should be given from slowest to fastest: W_L, W_M, W_R. The ringstellung and grundstellung are given as strings, e.g. 'ACX'. Any valid options not given during initialization are prompted for. """ self.ETW = config['ETW'] # Get the wheels. if not wheels: wheels = raw_input("Choose 3 wheels (slow middle fast) from %s: " % config['wheels'].keys()) wheels = str(wheels).replace(' ','') # Get the thin wheel if needed. if config['thin']: if not thin: thin = raw_input("Choose a thin wheel from %s: " % config['thin'].keys()) thin = thin.upper() else: thin = '' # Get the reflector. if len(config['UKWs']) > 1: if not UKW: UKW = raw_input("Choose a reflector from %s: " % config['UKWs'].keys()) UKW = UKW.upper() else: UKW = '' # Get the stecker if needed. if config['stecker']: if not stecker: stecker = raw_input("Choose an even number of letters to swap in pairs for your stecker board: ") stecker = stecker + ' ' else: stecker = ' ' self.setStecker(stecker) # Count the wheels with rings. nR = len(wheels)+len(thin) if config['UKWring']: nR += 1 # Get all of the ringstellung. # Make sure that they're set with the fast wheel of the second double # enigma 1 step advanced from that of the provided ringstellung and # the fast wheel of the third double enigma 2 steps advanced from the # provided ringstellung. ringstellung1 = raw_input("Choose the first %s character 'ringstellung': " % (nR,)) ringstellung1 = ringstellung1.replace(' ','').upper() ringstellung1 = 'A'*(nR-len(ringstellung1)) + ringstellung1 ringstellung2 = raw_input("Choose the second %s character 'ringstellung': " % (nR,)) ringstellung2 = ringstellung2.replace(' ','').upper() ringstellung2 = 'A'*(nR-len(ringstellung2)) + ringstellung2 rLst = map(char2int,ringstellung2) rLst[-1] = (rLst[-1] + 1) % 26 ringstellung2 = "".join([UPPER[k] for k in rLst]) ringstellung3 = raw_input("Choose the third %s character 'ringstellung': " % (nR,)) ringstellung3 = ringstellung3.replace(' ','').upper() ringstellung3 = 'A'*(nR-len(ringstellung3)) + ringstellung3 rLst = map(char2int,ringstellung3) rLst[-1] = (rLst[-1] + 2) % 26 ringstellung3 = "".join([UPPER[k] for k in rLst]) self.ringstellungs=[ringstellung1,ringstellung2,ringstellung3] # Get the grundstellung. #if not grundstellung: #grundstellung = raw_input("Choose a %s character 'grundstellungs': " % (nR,)) #grundstellung = grundstellung.replace(' ','').upper() #grundstellung = 'A'*(nR-len(grundstellung)) + grundstellung grundstellung = 'A'*nR # Make a tripled DoubleEnigma machine self.DoubleEnigmas = [DoubleEnigma(config=config, wheels=wheels, thin=thin, UKW=UKW, ringstellung=ringstellung1, grundstellung=grundstellung, stecker=' '), DoubleEnigma(config=config, wheels=wheels, thin=thin, UKW=UKW, ringstellung=ringstellung2, grundstellung=grundstellung, stecker=' '), DoubleEnigma(config=config, wheels=wheels, thin=thin, UKW=UKW, ringstellung=ringstellung3, grundstellung=grundstellung, stecker=' ')] self.setPermutations() def __repr__(self): return repr(self.permutation) def __str__(self): return str(self.permutation) def __call__(self,text): return "".join(map(self.encipher,text)) def setStecker(self,stecker): try: steck = stecker.replace(' ','').upper() steck = map(UPPER.index,steck) N = len(steck) stecker = [(steck[2*k],steck[2*k+1]) for k in range(N/2)] except AttributeError: pass try: self.stecker = Permutation(stecker) except IndexError: self.stecker = identity except TypeError: self.stecker = stecker self.ES = self.ETW * self.stecker def setKeys(self,grundstellung): for D in self.DoubleEnigmas: D.setKeys(grundstellung) # A new key setting requires recalculation of the permutation. self.setPermutations() def setPermutations(self): for D in self.DoubleEnigmas: D.setPermutation() self.permutations = [D.permutation for D in self.DoubleEnigmas] def fixedPoints(self): return [P.fixedPoints() for P in self.permutations] def commonFixedPoints(self): fpL = self.fixedPoints() fp = deepcopy(fpL[0]) for s in fpL: fp.intersection_update(s) return fp def keys(self): return self.DoubleEnigmas[0].keys() def turnovers(self): self.DoubleEnigmas[0].turnovers() def encipher(self,c): if c.upper() in UPPER: return self.permutation.encipher(c) else: return c def run(self): fixedDict = {} for a in UPPER: for b in UPPER: for c in UPPER: key = a+b+c self.setKeys(key) if len(self.commonFixedPoints()) > 0: fixedDict[key] = [UPPER[k] for k in self.commonFixedPoints()] return fixedDict def run1(self): for a in UPPER: key = "AA"+a self.setKeys(key) if len(self.commonFixedPoints()) > 0: print key, '\t', [UPPER[k] for k in self.commonFixedPoints()] def run2(self): for a in UPPER: for b in UPPER: key = "A"+a+b self.setKeys(key) if len(self.commonFixedPoints()) > 0: print key,'\t', [UPPER[k] for k in self.commonFixedPoints()] def run3(self): fixedDict = {} for a in UPPER: for b in UPPER: key = 'A'+a+b self.setKeys(key) if len(self.commonFixedPoints()) > 0: fixedDict[key] = [UPPER[k] for k in self.commonFixedPoints()] return fixedDict #-------------------------------------------------------------------- class BaseRotor(object): """ This rotor is always written in disjoint cycle notation. The rotors are permutatins of 0,1,...,25. Note: permutations act on the left! """ def __init__(self, cycles): """ An input must be a permutation of [0, 1, ..., 25] written in disjoint cycle notation. One-cycles must be written explicitely. """ self.cycles = [list(c) for c in cycles] def __repr__(self): self.cycles.sort() repr = [(len(c),c) for c in self.cycles] repr.sort() self.repr = [c for (l,c) in repr] return str(self.repr) def __str__(self): self.__repr__() cL = [" ".join([LOWER[k] for k in c]) for c in self.repr] return "(" + ")(".join(cL) + ")" def __mul__(left,right): """ left * right Since permutationss act on the left this is first 'right' and then 'left'. """ # We'll store the list of the products cycles in 'CL'. CL =[] L = range(26) while L: # If we're not working on a cycle, pop an entry # off the list 'L' for the start of the next cycle. x = L.pop() cycle = [x] while 1: # Look for the next item in the current cycle, # remove the item from 'L' and add it to the cycle. # But, if we're back at the start, close the cycle. try: x = left.image(right.image(x)) L.remove(x) cycle.append(x) except ValueError: CL.append(cycle) break return BaseRotor(CL) def __invert__(self): """ ~self returns the inverse. """ CL = deepcopy(self.cycles) for c in CL: c.reverse() return BaseRotor(CL) def __div__(left,right): """ left / right returns the left times the inverse of the right. """ return left * (~right) def __pow__(base,expo): """ base ** expo """ # Negative exponents are OK too. if expo < 0: return (~base)**(-expo) b=deepcopy(base) e=expo while e>0: q,r=divmod(e,2) if r==1: try: a*=b except: a=deepcopy(b) b*=b e=q return a def __eq__(left,right): """ left == right """ try: for k in range(26): if left.image(k) != right.image(k): return False return True except: return False def __ne__(left,right): """ right != left """ return not left==right def __lshift__(base,exp): """ x< i(y)*x*y i.e. right action of y on x via conjugation. """ CL = [[exp.invImage(i) for i in cycle] for cycle in base.cycles] return BaseRotor(CL) def __rshift__(exp,base): """ x>>y -> x*y*i(x) i.e. left action of x on y via conjugation. """ CL = [[exp.image(i) for i in cycle] for cycle in base.cycles] return BaseRotor(CL) def __len__(self): orders = map(len,self.cycles) return reduce(lcm,orders) def image(self,k): for cyc in self.cycles: if k in cyc: return cyc[(cyc.index(k) + 1) % len(cyc)] def invImage(self,k): for cyc in self.cycles: if k in cyc: return cyc[(cyc.index(k) - 1) % len(cyc)] def cycleStructure(self): structure = map(len,self.cycles) structure.sort() return structure def fixedPoints(self): return set([cyc[0] for cyc in self.cycles if len(cyc)==1]) def step(self,k=1): self.cycles = [[(x-k) % 26 for x in cyc] for cyc in self.cycles] # Some sample BaseRotors to play with: BR1 = BaseRotor([range(26)]) BR2 = BaseRotor(((0,3,4,8,11,23),(2,),(25,),(1,5,6,7,9,10,12,13,14,15,16,17,18,19,20,21,22,24))) #-------------------------------------------------------------------- class BaseBomba(object): def __init__(self, config, wheels = None, # 3 regular wheels thin = None, # 0 or 1 thin wheel UKW = None, # Reflector grundstellungs = None, # Ground setting ): self.ETW = config['ETW'] self.noETW == True for k in range(26): if self.ETW.image(k) != k: self.noETW == False break # Get the wheels. if not wheels: wheels = raw_input("Choose 3 wheels (slow middle fast) from %s: " % config['wheels'].keys()) wheels = str(wheels).replace(' ','') wheels = map(int,list(wheels)) wheels = [BaseRotor(config['wheels'][w].C) for w in wheels] # Get the thin wheel if needed. if config['thin']: if not thin: thin = raw_input("Choose a thin wheel from %s: " % config['thin'].keys()) thin = thin.upper() wheels.insert(0,BaseRotor(config['thin'][thin].C)) # Get the reflector. if len(config['UKWs']) > 1: if not UKW: UKW = raw_input("Choose a reflector from %s: " % config['UKWs'].keys()) UKW = UKW.upper() else: UKW = 'A' wheels.insert(0,BaseRotor(config['UKW'][UKW].C)) # Count the wheels with rings. nR = len(wheels) if not config['UKWring']: nR -= 1 # The ringstellung is what we're looking for. We are going to # try out all 26**nR possibilities and see which, if any, of # them produce fixed points in the appropriate positions. # Get all of the grundstellung. # Make sure that they're set with the fast wheel of the second double # enigma 1 step advanced from that of the provided grundstellung and # the fast wheel of the third double enigma 2 steps advanced from the # provided grundstellung. grundstellung = range(nR) for i,s in zip(grundstellung,('first','second','third','fourth')): grundstellung[i] = raw_input("Choose the %s %s character 'grundstellung': " % (s,nR,)) grundstellung[i] = grundstellung[i].replace(' ','').upper() grundstellung[i] = 'A'*(nR-len(grundstellung[i])) + grundstellung[i] enigmaBank = [] for k in range(2*nR): enigmaBank.append(deepcopy(wheels)) for i in range(nR): print i # Make a tripled DoubleEnigma machine self.DoubleEnigmas = [DoubleEnigma(config=config, wheels=wheels, thin=thin, UKW=UKW, ringstellung=ringstellung1, grundstellung=grundstellung, stecker=' '), DoubleEnigma(config=config, wheels=wheels, thin=thin, UKW=UKW, ringstellung=ringstellung2, grundstellung=grundstellung, stecker=' '), DoubleEnigma(config=config, wheels=wheels, thin=thin, UKW=UKW, ringstellung=ringstellung3, grundstellung=grundstellung, stecker=' ')] self.setPermutations() def __repr__(self): return repr(self.permutation) def __str__(self): return str(self.permutation) def __call__(self,text): return "".join(map(self.encipher,text)) def setStecker(self,stecker): try: steck = stecker.replace(' ','').upper() steck = map(UPPER.index,steck) N = len(steck) stecker = [(steck[2*k],steck[2*k+1]) for k in range(N/2)] except AttributeError: pass try: self.stecker = Permutation(stecker) except IndexError: self.stecker = identity except TypeError: self.stecker = stecker self.ES = self.ETW * self.stecker def setKeys(self,grundstellung): for D in self.DoubleEnigmas: D.setKeys(grundstellung) # A new key setting requires recalculation of the permutation. self.setPermutations() def setPermutations(self): for D in self.DoubleEnigmas: D.setPermutation() self.permutations = [D.permutation for D in self.DoubleEnigmas] def fixedPoints(self): return [P.fixedPoints() for P in self.permutations] def commonFixedPoints(self): fpL = self.fixedPoints() fp = deepcopy(fpL[0]) for s in fpL: fp.intersection_update(s) return fp def keys(self): return self.DoubleEnigmas[0].keys() def turnovers(self): self.DoubleEnigmas[0].turnovers() def encipher(self,c): if c.upper() in UPPER: return self.permutation.encipher(c) else: return c def run(self): fixedDict = {} for a in UPPER: for b in UPPER: for c in UPPER: key = a+b+c self.setKeys(key) if len(self.commonFixedPoints()) > 0: fixedDict[key] = [UPPER[k] for k in self.commonFixedPoints()] return fixedDict def run1(self): for a in UPPER: key = "AA"+a self.setKeys(key) if len(self.commonFixedPoints()) > 0: print key, '\t', [UPPER[k] for k in self.commonFixedPoints()] def run2(self): for a in UPPER: for b in UPPER: key = "A"+a+b self.setKeys(key) if len(self.commonFixedPoints()) > 0: print key,'\t', [UPPER[k] for k in self.commonFixedPoints()] def run3(self): fixedDict = {} for a in UPPER: for b in UPPER: key = 'A'+a+b self.setKeys(key) if len(self.commonFixedPoints()) > 0: fixedDict[key] = [UPPER[k] for k in self.commonFixedPoints()] return fixedDict """ self.config = config # Set the entry wheel. self.ETW = config['ETW'] # Get the wheels. if not wheels: wheels = raw_input("Choose 3 wheels (slow middle fast) from %s: " % config['wheels'].keys()) else: wheels = str(wheels).replace(' ','') wheels = map(int,list(wheels)) self.wheelnumbers = wheels wheels = [deepcopy(config['wheels'][i]) for i in wheels] # Get the thin wheel if needed. if config['thin']: if not thin: thin = raw_input("Choose a thin wheel from %s: " % config['thin'].keys()) self.thin = [deepcopy(config['thin'][thin.upper()])] else: self.thin = [] # Get the reflector. if len(config['UKWs']) > 1: if not UKW: UKW = raw_input("Choose a reflector from %s: " % config['UKWs'].keys()) self.UKW = [deepcopy(config['UKWs'][UKW.upper()])] else: self.UKW = [deepcopy(config['UKWs']['A'])] # Assemble all the wheels. self.basewheels = self.UKW + self.thin + wheels # Get the number of rings. self.nR = len(self.basewheels) if not config['UKWring']: self.nR -= 1 # Make 'nR' copies of the doubled enigma machine ######################################## # Get the grundstellung. if not grundstellung: grundstellung = raw_input("Choose %s different %s character 'grundstellungs': " % (self.nR,)) grundstellung = grundstellung.replace(' ','').upper() self.setKeys(grundstellung) # Set up the correct stepping function if config['dblstep']: self.step = self.__step2 else: # Do some tweaking, then set the step function. self.turnSets = [set(W.turnover) for W in self.wheels[1-self.nR:]] self.holdSets = [set() for k in range(self.nR-1)] self.step = self.__step1 def __repr__(self): return repr(self.permutation) def __str__(self): return str(self.permutation) def __call__(self,text): return "".join(map(self.encipher,text)) def setStecker(self,stecker): try: steck = stecker.replace(' ','').upper() steck = map(UPPER.index,steck) N = len(steck) stecker = [(steck[2*k],steck[2*k+1]) for k in range(N/2)] except AttributeError: pass try: self.stecker = Permutation(stecker) except IndexError: self.stecker = identity except TypeError: self.stecker = stecker self.ES = self.ETW * self.stecker def __setRings(self,ringstellung): # Convert ring setting letters to numbers. ringstellung = map(char2int,ringstellung) # All ring settings default to 'A'. nS = len(ringstellung) ringstellung = (0,)*(self.nR - nS) + tuple(ringstellung) for k,R in enumerate(self.basewheels[-self.nR:]): R.setRing(ringstellung[k]) def setKeys(self,grundstellung): # Get base set of wheels in 'AAA...' configuration. self.wheels = tuple([deepcopy(R) for R in self.basewheels]) # Convert key setting letters to numbers. grundstellung = map(char2int,grundstellung) # All key settings default to 'A'. nK = len(grundstellung) grundstellung = (0,)*(self.nR - nK) + tuple(grundstellung) for k,R in enumerate(self.wheels[-self.nR:]): R.setKey(grundstellung[k]) # A new key setting requires recalculation of the permutation. self.setPermutation() def setPermutation(self): self.permutation = (reduce(operator.lshift,self.wheels) << self.ES) def keys(self): keyList = [R.key for R in self.wheels[-self.nR:]] return "".join(keyList) def turnovers(self): for R in self.wheels[-self.nR:]: print R.turnover, def __step1(self): # This implements the 'single stepping' used in the Abwehr enigma. # Something mysterious is going on here with the 'holdSets'. # I'm blindly hoping it isn't screwing things up. nR = self.nR for i in range(1-nR, 0): k = self.wheels[i].key if k in self.turnSets[i]: if i<-1: self.turnSets[i].discard(k) self.holdSets[i].add(k) self.wheels[i-1].step() if i > 1-nR: self.turnSets[i-1].update(self.holdSets[i-1]) self.holdSets[i-1] = set() self.wheels[-1].step() self.setPermutation() def __step2(self): # This implements the famous 'double stepping' nR = self.nR F = nR - 1 motion = [0]*nR for i in range(-F,0): if self.wheels[i].trigger(): motion[i-1] = 1 motion[i] = 1 break motion[-1] = 1 for i in range(nR): if motion[i]: self.wheels[i-nR].step() self.setPermutation() def encipher(self,c): if c.upper() in UPPER: self.step() return self.permutation.encipher(c) else: return c """