#        Nicodemus X-correlation...........



import string

import sys

from random import randrange



fr_eng = [8.0,1.0,3.0,4.0,13.0,3.0,1.0,6.0,7.0,0,0,4.0,3.0,7.0,8.0,2.0,0,6.0,6.0,9.0,3.0,1.0,1.0,0,2.0,0]



ciphertext = '''OBNAA GKFGR HGXPI DVPNL GTBGP VFFVG JTFZI JSYWC CETTC HFGUG

XRLEQ ZTPZY FNGAB CBVSJ CJZKV GSUZG UJRAI JKHPY TWXMO LWVNO FEOXB HZSWT VKRGV

HMWKK L'''         #  noc=8 ACEHNORS  is correct Vigenere key



noc=8

code= ''

shift = [None]*30

Xkey =  ['A'] * 30



#..set up c_grid[30][30]

c_grid = [None ]*30

for i1 in range(30):

  c_grid[i1]=[None]*30

  for i2 in range(30):

    c_grid[i1][i2]= 0



#..set up f[30][26]    

f = [0.0000 ]*30

for i1 in range(30):

  f[i1]=[0.0000]*30

  for i2 in range(26):

    f[i1][i2]= 0

   









length=len(ciphertext)

t=0

for j in range (length):

    if(ciphertext[j]>='A' and ciphertext[j]<='Z'):

        code= code + ciphertext[j]; t=t+1

length=t



print "ciphertext = ",code

print







block=noc*5;  nob=length/block;  nor= nob*5

len_new=nob*noc*5

#...put code into c-grid[][] which has noc cols & nor rows.....

t=-1

for blk in range(nob):

    start_row=blk*5

    for col in range(noc):

        for row in range(start_row,start_row+5,1):

            t=t+1

            c_grid[row][col]=code[t]

print "Cipher grid is: "

for row in range(nor):

    for col in range(noc):

        print c_grid[row][col],

    print

print

#..find letter frequencies in each column....

for col in range(noc):

    for m in range(26):

        f[col][m] = 0



for col in range(noc):

    for row in range(nor):

        x=ord(c_grid[row][col])-65

        f[col][x]=f[col][x]+1.0000



#..calculate chi....

print "Cross Correlation results are :"        

for col in range(noc):

    maxi=0

    for k in range(26):

        top=0.0; bot=0.0; chi=0.0

        for j in range(26):

            x=j+k

            if(x>25): x=x-26

            top=top+fr_eng[j] * f[col][x]

            bot=bot+fr_eng[j]

        chi=1000*top/(bot*bot)

        if(chi>maxi):

            maxi=chi

            shift[col]=k

    primus=chr(shift[col]+65)

    print "col=",col,"  chi=",chi,"  shift=",shift[col],"  letter=",primus

    Xkey[col]=primus

print

print"Vigenere key from Cross Correlation = ",

for j in range(noc):

    print Xkey[j],