import random
def str_to_bin(n,i):
    b=bin(ord(n))
    s=b[2:].zfill(i)
    return s
def bin_to_str(n):
    return chr( int(n,2))
def bin_to_string(chaine):
    i=0
    c=''
    while(i<len(chaine)):
        c=c+bin_to_str(chaine[i:i+8])
        i=i+8
    return c
def binaire(chaine):
    i=0
    st=''
    while(i<len(chaine)):
        st=st+str_to_bin(chaine[i],8)
        i=i+1
    return st
def bin16(n):
    chaine=bin(n)[2:].zfill(16)
    return chaine
def decomposition(chaine):
    i=0
    l=[]
    ch=binaire(chaine)
    a=len(ch)%64
    v=(64-a)//8
    if(a!=0):
        ch=ch+v*'00000000'
    while(i<len(ch)):
        l.append(ch[i:i+64])
        i=i+64
    return l
def decomposition16(chaine):
    l=[]
    i=0
    while(i<len(chaine)):
        l.append(chaine[i:i+16])
        i=i+16
    i=0
    while(i<len(l)):
        l[i]=int(l[i],2)
        i=i+1
    return l
def addition(x,y):
    return (x+y)%2**16
def multiplication(x,y):
    return (x*y)%(2**16+1)
def xor(x,y):
    return x^y
def rotation(chaine):
    
    ch=''
    ch=chaine[25:]+chaine[0:25]
    return ch
def bin_to_int(ch):
    return int(ch,2)
def keygen():
    i=0
    c=''
    while(i<128):
        c=c+str(random.randint(0,1))
        i=i+1
    key=[]
    i=0
    j=0
    while(i<7):
        while(j<len(c)):
            key.append(c[j:j+16])
            j=j+16
        j=0
        c=rotation(c)
        i=i+1
    key=key[0:52]
    i=0
    while(i<len(key)):
        key[i]=bin_to_int(key[i])
        i=i+1
    return key
def code16(x):
    b=bin(x)[2:].zfill(16)
    return b
def idea(texte,key):
    x1=int(texte[0:16],2)
    x2=int(texte[16:32],2)
    x3=int(texte[32:48],2)
    x4=int(texte[48:64],2)
    i=0
    j=0
    while(i<8):
        p1=multiplication(x1,key[j])
        a1=addition(x2,key[j+1])
        a2=addition(x3,key[j+2])
        p2=multiplication(x4,key[j+3])
        x1=xor(p1,a2)
        x2=xor(a1,p2)
        p3=multiplication(x1,key[j+4])
        a3=addition(x2,p3)
        p4=multiplication(a3,key[j+5])
        a4=addition(p3,p4)
        x1=xor(p1,p4)
        x2=xor(a2,p4)
        x3=xor(a1,a4)
        x4=xor(p2,a4)
        i=i+1
        j=j+6
    y1=multiplication(key[48],x1)
    y2=addition(key[49],x3)
    y3=addition(key[50],x2)
    y4=multiplication(key[51],x4)

    c=bin16(y1)+bin16(y2)+bin16(y3)+bin16(y4)
    #print(c)
    return bin_to_string(c)
  

def chiffrement():
    ch=input("donner le message a chiffrer:\n")
    d=decomposition(ch)
    c=''
    i=0
    key=keygen()
    while(i<len(d)):
        c=c+idea(d[i],key)
        i=i+1
    print(c)
    
    v=decomposition(c)
    t=''
    i=0
    l=inv_keygen(key)
    while(i<len(d)):
        t=t+idea(v[i],l)
        i=i+1
    print(t)

def inv_add(n):
    return (-n)%2**16
def inv_multi(n):
    r=0
    i=0
    if(n<2):
        return n
    else:
        while(r!=1):
            r=multiplication(n,i)
            i=i+1
        return i-1
def inv_keygen(k):
    key=[]
    key.append(inv_multi(k[48]))
    key.append(inv_add(k[49]))
    key.append(inv_add(k[50]))
    key.append(inv_multi(k[51]))
    i=42
    while(i>=0):
        key.append((k[i+4]))
        key.append((k[i+5]))
        key.append(inv_multi(k[i]))
        key.append(inv_add(k[i+2]))
        key.append(inv_add(k[i+1]))
        key.append(inv_multi(k[i+3]))
        
        i=i-6
    return key