import math
import sys

#Read the s-boxes from the files sbox1.dat and sbox2.dat
def get_sbox(n):
  f = open("sbox%s.dat"%n, "r")
  sbox = []
  for line in f.readlines():
    for data in line.split(","):
      if data != '\n':
        data.replace('\n', '')
        data = bin(int(data, 0))
	data = data[2:]
	sbox.append(complete(data, 32))
  return sbox

#Apply xor to two binary strings
def xor(bin1, bin2):
  bin3 = ""
  if len(bin1) != len(bin2):
    print "Error length bin1 = %s, length bin2 = %s"%(len(bin1), len(bin2))
  else:
    for i in range(len(bin1)):
      if bin1[i] == " ":
        bin3 += " "
      elif bin1[i] != bin2[i]:
        bin3+= "1"
      else:
        bin3+= "0"
  return bin3

#Complete a binary string adding zeros
def complete(binary, n):
  if len(binary) < n:
    while len(binary) < n:
      binary  = "0" + binary
    return binary
  else:
    return binary


#G function defined in the pdf
def G(x, n):
  x = [x[0:8], x[8:16], x[16:24], x[24:32]]
  if n == 1:
    res1 = xor(sbox1[int(x[0], 2)], sbox1[int(x[1], 2)])
    res2 = xor(sbox1[int(x[2], 2)], sbox2[int(x[3], 2)])
    return xor(res1, res2)
  if n == 2:
    res1 = xor(sbox1[int(x[0], 2)], sbox1[int(x[1], 2)])
    res2 = xor(sbox2[int(x[2], 2)], sbox1[int(x[3], 2)])
    return xor(res1, res2)
  if n == 3:
    res1 = xor(sbox1[int(x[0], 2)], sbox2[int(x[1], 2)])
    res2 = xor(sbox1[int(x[2], 2)], sbox1[int(x[3], 2)])
    return xor(res1, res2)
  
#H function defined in the PDF
def H(x, n):
  x = [x[0:8], x[8:16], x[16:24], x[24:32]]
  if n == 1:
    res1 = xor(sbox2[int(x[0], 2)], sbox2[int(x[1], 2)])
    res2 = xor(sbox2[int(x[2], 2)], sbox1[int(x[3], 2)])
    return xor(res1, res2)
  if n == 2:
    res1 = xor(sbox2[int(x[0], 2)], sbox2[int(x[1], 2)])
    res2 = xor(sbox1[int(x[2], 2)], sbox2[int(x[3], 2)])
    return xor(res1, res2)
  if n == 3:
    res1 = xor(sbox2[int(x[0], 2)], sbox1[int(x[1], 2)])
    res2 = xor(sbox2[int(x[2], 2)], sbox2[int(x[3], 2)])
    return xor(res1, res2)


#F function used in the algorithm once per round.
def F(a, b, c, d, e ,f):
  #pre-mixing
  b = xor(b, a)
  d = xor(d, c)
  f = xor(f, e)
  c = bin((int(c, 2) + int(b, 2)) % int(math.pow(2, 32)))
  c = complete(c[2:], 32)
  e = bin((int(e, 2) + int(d, 2)) % int(math.pow(2, 32)))
  e = complete(d[2:], 32)
  a = bin((int(a, 2) + int(f, 2)) % int(math.pow(2, 32)))
  a = complete(a[2:], 32)
  #S-box 
  d = xor(d, G(a, 1))
  f = xor(f, G(c, 2))
  b = xor(b, G(e, 3))
  a = xor(a, H(b, 1))
  c = xor(c, H(d, 2))
  e = xor(e, H(f, 3))
  #print len(a), len(b), len(c), len(d), len(e), len(f)
  #Post-mixing
  dn = bin((int(d, 2) + int(a, 2)) % int(math.pow(2, 32)))
  dn = complete(dn[2:], 32)
  fn = bin((int(f, 2) + int(c, 2)) % int(math.pow(2, 32)))
  fn = complete(fn[2:], 32)
  bn = bin((int(b, 2) + int(e, 2)) % int(math.pow(2, 32)))
  bn = complete(bn[2:], 32)

  cn = xor(c, b)
  en = xor(e, d)
  an = xor(a, f)
  return (an, bn, cn, dn, en, fn)

#Convert the key to a easily used string
def convert_key(key):
  parts = key.split(" ")
  bin_key = ""
  for part in parts: 
    bin_key += complete(str(bin(int(part, 16))).replace("0b", ""), 32) + " "
  bin_key = bin_key[0:len(bin_key)-1]
  #k = bin_key.split(" ")
  return bin_key

#Initialisation of the key
def init(k, iv):
  k = k + " " + xor(k, iv) + " "+ neg(xor(k, iv)) + " " + iv
  k = k.split(" ")
  
  w = split_list(k, 4)

  M = '0x0000447261676F6E'
  M = bin(int(M, 16))
  M = M[2:]
  M = complete(M, 32)
  for i in range(16):
    tmp = xor(w[0], w[6])
    tmp = xor(tmp, w[7])
    arr = []
    a = ""
    for j in range(len(tmp)):
      a += tmp[j]
      if len(a) == 32:
        arr.append(a)
        a = ""
    arr.append(M[0:(len(M)/2)])
    arr.append(M[(len(M)/2):])
    for index in range(len(arr)):
      arr[index] = complete(arr[index], 32)
    a, b, c, d, e, f = F(arr[0], arr[1], arr[2], arr[3], arr[4], arr[5])
    t = complete(bin((int(a, 2) + int(b, 2) + int(c, 2) + int(d, 2)))[2:], 128)
   
    w[0] = xor(t, w[4])
    for i in range(len(w)-1, -1, -1):
      w[i] = w[i-1]
    M = e + f
      
  new_w = ""
  for byte in w:
    new_w += byte
  b = []
  tmp = ""
  for i in range(len(new_w)):
    tmp += new_w[i]
    if len(tmp) == 32:
      b.append(tmp)
      tmp = ""
  #print len(M)
  return b, M

#Generation of the keystream
def keystream_gen(b, M):
  Ml = M[0: len(M) / 2]  
  Mr = M[len(M) / 2:len(M)]
  an, bn, cn, dn, en, fn = b[0], b[9], b[16], b[19], xor(b[30], Ml), xor(b[31], Mr)
  an, bn, cn, dn, en, fn = F(an, bn, cn, dn, en, fn)
  b[0], b[1] = bn, cn
  for i in range(len(bn)-1, 1, -1):
    b[i] = b[i-2]
  #print M, len(M)
  M = bin(int(M, 2) + 1)
  M = complete(M[2:], 64)
  k = an + en
  #print len(k)
  k = int(k, 2) % int(math.pow(2, 64))
  print hex(k)
  #print M, len(M)
  return b, M


def neg(bin_str):
  res = ""
  for bit in bin_str:
    if bit == "0":
      res+= "1"
    elif bit == "1":
      res+="0"
    elif bit == " ":
      res+=" "
  return res

def split_list(tmp, parts):
  j = -1
  w = []
  for i in range(len(tmp)):
    if i% parts == 0:
      w.append(tmp[i])
      j+=1
    else:
      w[j]+= tmp[i]
  return w


if __name__ == "__main__":
  n = int(sys.argv[1])
  #Read de sboxes from the files
  sbox1 = get_sbox(1)
  sbox2 = get_sbox(2)
  #Key and initialization vector provided in the pdf
  key = "00001111 22223333 44445555 66667777 88889999 AAAABBBB CCCCDDDD EEEEFFFF"
  iv =  "00001111 22223333 44445555 66667777 88889999 AAAABBBB CCCCDDDD EEEEFFFF"
  k = convert_key(key)
  iv = convert_key(iv)
  #Internal state initialization
  b, M = init(k, iv)
  #Keystream generation
  for i in range(n):
    b, M = keystream_gen(b, M)