""" indicators.py Data taken from "Machine Cryptography and Modern Cryptanalysis" by Deavours and Kruh. 82 observed encrypted doubled indicators from the same day. ABW BFO GJN CVD MSQ NWV SUP YPG ACC BIS GMX COJ NWJ JOB TLB GRL AKJ BTB GSG CWK NTA JLX TMV GOM ARS BXA HDL ZKR NYM JHF (2) TQO GUN AWB BCL HIU ZMY (4) DHZ XNC UGU ICY BAS QJA HXU ZEY PGW OCQ UQT IUP (3) BIQ QMV IAM WJF PHA DNX VIY TMH CCB KIL IHE WNO PXA DEX WLL ORR CKP KTG IQR WUE QAP HJG WNT OYP CNZ KYC IVB WAL QFR HZE WWP OGG CPB KDL IXJ WEB QGX HCJ WZY OSH CVC KAC JKI RTU QIE HMW XFF LZT DDH PKW JKZ RTC QMS HOA XQK LUI DMB POL JZA RSX QYZ HHC XQR LUE DUE PPO KOG EBK RAA VJX YAP SJG EEH FQW LIH AMW RFQ VZX YFV SZM EHZ FNC LOX ABJ RRN VXD YQQ SUV EOH FBW LPK ADI RSD VWZ YSG SWK (3) EUR FPE LQJ AUB RWZ VGC ZMD UOZ GCS CIA MBZ NFC SRO YXN ZPZ UDC GHG CNK MLW NRQ (4) We can use the above information to construct the following permutations, where Pk is the permutation undergone by the kth letter. P1*P4 = (d p)(s y)(a b q h z u i w o x l)(m n j r v t g c k e f) P2*P5 = (a j v)(h n y)(b f z s w g c i m o)(d k t l r x e q u p) P3*P6 = (a x j b l r e o n d z c s)(i u y h w q v m f t p g k) Now Rejewski's Theorem gives us some information about how these permutations MIGHT Factor. For example, in P1*P4 the two transpositons (d p) and (s y) tell us that when we write the Pk as products of disjoint transpositions, among the factors of P1 are the pair (d y)(p s) or the pair (d s)(p y). Whichever pair P1 has, P4 has the other. The fact that there are some key sequences that occur multiple times indicates that they are, perhaps, easy to guess. Maybe repeated characters such as 'aaa', 'bbb', etc? 1) Guess that the key for the repeated YSG SWK is from one of these 'constant' keys. Since 'Y' is the image of the first character under P1 and P1 either swaps 'Y' with 'D' or with 'P' we can guess either 'ddd' or 'ppp' as the key. 2) Looking at the cycles of P2*P5 we see that P2 can't move 'p' to 's' since 'p' and 's' are in different cycles of P2*P5, so our key can only be 'ddd', if it is in fact a repeated key. 3) Under this assumption, the factorization of P1 contains (d y), the factorization of P2 contains (d s) and the factorization of P3 contains (d g). 4) This gives the line ups P1: (d p) P2: (b f z s w g c i m o) P3: (a x j b l r e o n d z c s) (y s) (l t k d p u q e x r) (m v q w h y u i k g p t f) And the factors P1: (d y)(p s).... P2: (b l)(f t)(z k)(s d)(w p)(g u)(c q)(i e)(m x)(o r)... P3: (a m)(x v)(j q)(b w)(l h)(r y)(e u)(o i)(n k)(d g)(z p)(c t)(s f) 5) We can now decipher another of the repeats: UQT IUP. This reads as '?cc'. We'll take this as good news and assume the original key was 'ccc'. So we have the factor (c u) in P1. 6) This gives the line up P1: (a b q h z u i w o x l) (n m f e k c g t v r j) And the factors P1: (a n)(b m)(q f)(h e)(z k)(u c)(i g)(w t)(o v)(x r)(l j) 7) We only lack three of the factors of P2. The repeat NYM JHF reads as 'a?a' so we assume that P2 swaps 'Y' and 'A'. 8) This gives the line up P2: (a j v) (y n h) And the factors P2: (a y)(j n)(v h) 9) We have all three permutations. P1 = (d y)(p s)(a n)(b m)(q f)(h e)(z k)(u c)(i g)(w t)(o v)(x r)(l j) P2 = (b l)(f t)(z k)(s d)(w p)(g u)(c q)(i e)(m x)(o r)(a y)(j n)(v h) P3 = (a m)(x v)(j q)(b w)(l h)(r y)(e u)(o i)(n k)(d g)(z p)(c t)(s f) -------------------------------------------------------------------------------------- Another example day. From doubled key we have the products: P1*P4 = (dvpfkxgzyo)(eijmunqlht)(bc)(rw)(a)(s) P2*P5 = (blfqveoum)(hjpswizrn)(axt)(cgy)(d)(k) P3*P6 = (abviktjgfcqny)(duzrehlxwpsmo) From terrible setting choices we have the permutations: P1 = (as)(br)(cw)(di)(ev)(fh)(gn)(jo)(kl)(my)(pt)(qx)(uz) P2 = (ay)(bj)(ct)(dk)(ei)(fn)(gx)(hl)(mp)(ow)(qr)(su)(vz) P3 = (ax)(bl)(cm)(dg)(ei)(fo)(hv)(ju)(kr)(np)(qs)(tz)(wy) P4 = (as)(bw)(cr)(dj)(ep)(ft)(gq)(hk)(iv)(lx)(mo)(nz)(uy) P5 = (ac)(bp)(dk)(ez)(fh)(gt)(io)(jl)(ms)(nq)(rv)(uw)(xy) P6 = (aw)(bx)(co)(df)(ek)(gu)(hi)(jz)(lv)(mq)(ns)(py)(rt) Plugboard setting courtesy of Hans Schmidt. S = (ap)(bl)(cz)(fh)(jk)(qu) """ from permutations import Permutation a = 'a'; b='b'; c='c'; d='d'; e='e'; f='f'; g='g'; h='h'; i='i'; j='j'; k='k'; l='l'; m='m' n = 'n'; o='o'; p='p'; q='q'; r='r'; s='s'; t='t'; u='u'; v='v'; w='w'; x='x'; y='y'; z='z' # The cyclic permutation C = Permutation(range(1,26)+[0]) #P1P4 = Permutation(((d,p),(s,y),(a,b,q,h,z,u,i,w,o,x,l),(m,n,j,r,v,t,g,c,k,e,f))) #P2P5 = Permutation(((a,j,v),(h,n,y),(b,f,z,s,w,g,c,i,m,o),(d,k,t,l,r,x,e,q,u,p))) #P3P6 = Permutation(((a,x,j,b,l,r,e,o,n,d,z,c,s),(i,u,y,h,w,q,v,m,f,t,p,g,k))) #P1 = Permutation(((d,y),(p,s),(a,n),(b,m),(q,f),(h,e),(z,k),(u,c),(i,g),(w,t),(o,v),(x,r),(l,j))) #P2 = Permutation(((b,l),(f,t),(z,k),(s,d),(w,p),(g,u),(c,q),(i,e),(m,x),(o,r),(a,y),(j,n),(v,h))) #P3 = Permutation(((a,m),(x,v),(j,q),(b,w),(l,h),(r,y),(e,u),(o,i),(n,k),(d,g),(z,p),(c,t),(s,f))) P1P4 = Permutation(((d,v,p,f,k,x,g,z,y,o),(e,i,j,m,u,n,q,l,h,t),(b,c),(r,w),(a,),(s,))) P2P5 = Permutation(((b,l,f,q,v,e,o,u,m),(h,j,p,s,w,i,z,r,n),(a,x,t),(c,g,y),(d,),(k,))) P3P6 = Permutation(((a,b,v,i,k,t,j,g,f,c,q,n,y),(d,u,z,r,e,h,l,x,w,p,s,m,o))) P1 = Permutation(((a,s),(b,r),(c,w),(d,i),(e,v),(f,h),(g,n),(j,o),(k,l),(m,y),(p,t),(q,x),(u,z))) P2 = Permutation(((a,y),(b,j),(c,t),(d,k),(e,i),(f,n),(g,x),(h,l),(m,p),(o,w),(q,r),(s,u),(v,z))) P3 = Permutation(((a,x),(b,l),(c,m),(d,g),(e,i),(f,o),(h,v),(j,u),(k,r),(n,p),(q,s),(t,z),(w,y))) #(as)(bw)(cr)(dj)(ep)(ft)(gq)(hk)(iv)(lx)(mo)(nz)(uy) #(ac)(bp)(dk)(ez)(fh)(gt)(io)(jl)(ms)(nq)(rv)(uw)(xy) #(aw)(bx)(co)(df)(ek)(gu)(hi)(jz)(lv)(mq)(ns)(py)(rt) P4 = P1 * P1P4 P5 = P2 * P2P5 P6 = P3 * P3P6 # Plug board setting S = Permutation(((a,p),(b,l),(c,z),(f,h),(j,k),(q,u))) Q1 = P1^(S*C) Q2 = P2^(S*C**2) Q3 = P3^(S*C**3) Q4 = P4^(S*C**4) Q5 = P5^(S*C**5) Q6 = P6^(S*C**6) Q1Q2 = Q1*Q2 Q2Q3 = Q2*Q3 Q3Q4 = Q3*Q4 Q4Q5 = Q4*Q5 Q5Q6 = Q5*Q6 # Suppose P=(a_1 .... a_13)(b_1 .... b_13) and # Q=(c_1 .... c_13)(d_1 .... d_13). The next # function checks to see if the permutation that # takes a_k to c_k+m and b_k to d_k+n is a cyclic # permutation. def iscylclic(P,Q,m,n,swap=False): P0,P1 = P.C Q0,Q1 = Q.C Q0 = Q0[m:] + Q0[:m] Q1 = Q1[n:] + Q1[:n] if swap: Q0,Q1 = Q1,Q0 L0 = [(P0[k],Q0[k]) for k in range(13) ] L1 = [(P1[k],Q1[k]) for k in range(13) ] L = L0+L1 L.sort() L = [y for (x,y) in L] R = Permutation(L) if len(R.cyclestructure())==1: return R else: return False # Suppose that P and Q are both products of two disjoint # 13-cycles. This next function finds all permutations R # consisting of a single 26-cycle that satisfy Q = P^R. def seekconjugator(P,Q): successes = [] for m in range(13): for n in range(13): R = iscylclic(P,Q,m,n) if R: successes.append((str(R),R)) R = iscylclic(P,Q,m,n,swap=True) if R: successes.append((str(R),R)) successes.sort() return [R for (s,R) in successes] C12 = seekconjugator(Q1Q2,Q2Q3) C23 = seekconjugator(Q2Q3,Q3Q4) #C34 = seekconjugator(Q3Q4,Q4Q5) #C45 = seekconjugator(Q4Q5,Q5Q6) # This function finds the unique 26-cycle that satisfies # both Q2*Q3 = (Q1*Q2)^P.and Q3*Q4 = (Q2*Q3)^P. def uniqueconjugator(): return [R for R in C12 for Q in C23 if R==Q][0] # The next function finds all possible configurations of the # fast rotor N. This only works if the permutation P that we # input satisfies (Q1*Q2)^P=Q2*Q3, (Q2*Q3)^P=Q3*Q4, etc. # We use the relation C=P^N where C=(a b c ... y z). def fastrotor(P): splices = [] P = P.C[0] Q = C.C[0] for m in range(26): Q = Q[m:] + Q[:m] L = zip(P,Q) L.sort() L = [y for (x,y) in L] R = Permutation(L) splices.append(R) return splices def step1(): print print "Here are all the 26-cycles P that satisfy Q2*Q3 = (Q1*Q2)^P." print for R in C12: print R print print "Here are all the 26-cycles P that satisfy Q3*Q4 = (Q2*Q3)^P." print for R in C23: print R def step2(): P = uniqueconjugator() print print "Here is the unique 26-cycle that satisfies both" print "Q2*Q3 = (Q1*Q2)^P and Q3*Q4 = (Q2*Q3)^P." print print P def step3(): print print "Here are all the possibilities for the fast rotor N." print "These were found using the relationship C=P^N where" print "C = (a b c ... x y z) and P is the unique 26-cycle that" print "satisfies both Q2*Q3 = (Q1*Q2)^P and Q3*Q4 = (Q2*Q3)^P." print for N in fastrotor(uniqueconjugator()): print N print print "If N is on the list, then the rest of the list is of the" print "form N*(C**k) = (P**k)*N for some integer k=0,1,2,...,25." def findQ(N): """ This finds the internal Q that goes with the fast rotor N. If N is replaced with the alternate fast rotor NC then Q is replaced with Q^C. """ return Q1^(N*(~C)) def checkPk(N,k): Q = findQ(N) print Q^~(S*(C**k)*N*(C**-k))