# WOJCIECH ZACZEK- PRACA DOMOWA (ZADANIE 1 a))
#ETAP 1- NA PODSTAWIE DOSTĘPNYCH DANYCH, TZN. ZNAJOMOŚCI UŻYTEGO ALFABETU ORAZ DANYCH STATYSTYCZNYCH DOTYCZĄCYCH CZĘSTOTLIWOŚCI WYSTĘPUJĄCYCH DIGRAFÓW ("M ", "U ", "IH"), ORAZ ZAKŁADAJĄC, ŻE NAJCZĘŚCIEJ WYSTĘPUJĄCE DIGRAFY W ANGIELSKIM ALFABECIE TO "E ", "S ", " T", SZUKAMY TAKIEGO ODWZOROWANIA (DESZYFRUJĄCEGO ZASZYFROWANĄ AFINICZNIE WIADOMOŚĆ), KTÓRE PRZEKSZTAŁCA "M ", "U ", "IH"    W    "E ", "S ", " T", ODPOWIEDNIO.
    #przyporządkowujemy digrafom w zaszyfrowanym tekście odpiadające im liczby
        #"M " -> (indeks litery 'M')*(ilość liter w alfabecie) + (indeks znaku " " w alfabecie) = 12*30 + 26 = 386
        #"U " -> (indeks litery 'U')*(ilość liter w alfabecie) + (indeks znaku " " w alfabecie) = 20*30 + 26 = 626
        #"IH" -> (indeks litery 'I')*(ilość liter w alfabecie) + (indeks litery "H" w alfabecie) = 8*30 + 7 = 247
    #przyporządkowujemy digrafom występującym najczęściej w angielskim alfabecie odpiadające im liczby
        #"E " -> (indeks litery 'E')*(ilość liter w alfabecie) + (indeks znaku " " w alfabecie) = 4*30 + 26 = 146
        #"S " -> (indeks litery 'S')*(ilość liter w alfabecie) + (indeks znaku " " w alfabecie) = 18*30 + 26 = 566
        #" T" -> (indeks znaku ' ')*(ilość liter w alfabecie) + (indeks litery "T" w alfabecie) = 26*30 + 19 = 799
#ETAP 2- ROZWIĄZUJEMY UKŁAD KONGRUENCJI
    #(1)   386*a + b = 146 (mod 30^2)        ------------------------------------------------------------------------
    #(2)   626*a + b = 566 (mod 30^2)                                                                               |
    #(3)   247*a + b = 799 (mod 30^2)                                                                               |
    #                                                                                                               |
    #odejmujemy ( (2) - (1) )                                                                                       |
    #  240*a = 420 (mod 30^2)                                                                                       |
    #  gcd(240,900) = 60 <> 1, więc próbujemy inaczej i liczymy (1) - (3), i otrzymujemy                            |
    #  139*a = 247          -----------------------------------------------------------------------                 |
    #  gcd(139,900) = 1, więc korzystamy z rozszerzonego algorytmu Euklidesa i otrzymujemy         |                |
    #  xgcd(139,900) = (1,259,-40), tzn. 259*139 - 40*900 = 1, stąd mamy                           |                |
    #  259*139 = 1 (mod 30^2), zatem                                                               |                |
    #  a = 259*139*a = 259*247 (mod 30^2) = 73 (mod 30^2), więc a = 73        <---------------------                |
    #  b = 146 - 386*73 = 768 (mod 30^2)    <------------------------------------------------------------------------
    #  otrzymujemy funkcję deszyfrującą  dec(x) = 73*x + 768 (mod 30^2)
    #  KLUCZEM DESZYFRUJĄCYM JEST (73,768)

abec='ABCDEFGHIJKLMNOPQRSTUVWXYZ ?!`'
#zaszyfrowana wiadomość
wiad='DXM SCE DCCUVGX '
#dzielimy ilość liter na 2 w celu usprawnienia późniejszych obliczeń
k=len(wiad)/2
#deklarujemy tablicę 'inddig' do przechowywania liczb odpowiadających digrafom
inddig=[]

#dodajemy do listy 'inddig' liczby odpowiadające digrafom w zaszyfrowanej wiadomości, powtarzamy tę czynność 'k' razy (tzn. tyle razy, ile jest digrafów w zaszyfrowanym tekście)
for i in range(k):
    inddig.append(abec.find(wiad[2*i])*len(abec)+abec.find(wiad[2*i+1]))
inddig

#deklarujemy tablicę 'ind2' do przechowywania liczb odpowiadających odszyfrowanym digrafom
ind2=[]
#deklarujemy tablicę 'txt' do przechowywania odszyfrowanych znaków
txt=[]

#stosujemy wyznaczoną wcześniej funkcję deszyfrującą k razy (tyle jest digrafów w zaszyfrowanej wiadomości), deszyfrując tym samym k digrafów
for i in range(k):
    ind2.append((73*inddig[i]+768)%((len(abec))^2))
    #wyznaczamy pierwszą literę digrafu (w naszym alfabecie ma ona indeks równy ilości całości z dzielenia ind2/len(abec) w naszym alfabecie)
    txt.append(abec[(ind2[i])//(len(abec))])
    #wyznaczamy drugą literę digrafu (w naszym alfabecie ma ona indeks równy reszcie z dzielenia ind2/len(abec) w naszym alfabecie)
    txt.append(abec[(ind2[i])%(len(abec))])
#przekształcamy tablicę liter w tekst
txt=''.join(txt)
print wiad,'->',txt

#ZASZYFROWANA WIADOMOŚĆ TO 'ARE YOU JOKING?'

#( ZADANIE 1 b) )    SZUKAMY FUNKCJI SZYFRUJĄCEJ

abec='ABCDEFGHIJKLMNOPQRSTUVWXYZ ?!`'

#enc(y) = c*y + d
#SZUKAMY TAKICH LICZB c,d, że enc(dec(x)) = x, czyli
#c*(73*x + 768) + d = x, czyli
#c*73*x + c*768 + d = x, czyli
#c*73 = 1 (mod 30^2) oraz d = -c*768 (mod 30^2)
#rozwiązujemy układ powyższych dwóch kongruencji stosując formułę solve_mod([c*73==1,d==-c*768],900)
#otrzymujemy c=37, oraz d=384, tak więc
#funkcja szyfrująca przyjmuje postać enc(y) = 37*c + 384
#KLUCZEM SZYFRUJĄCYM JEST (37,384)

c=var('c')
d=var('d')
solve_mod([c*73==1,d==-c*768],900)

#SZYFRUJEMY WIADOMOŚĆ 'M' WEDŁUG POWYŻSZEGO KLUCZA
M='YES I`M JOKING!'
if (len(M)%2)<>0: M=M+'X'
    #dzielimy ilość liter (teraz już parzystą) w alfabecie przez 2 w celu ułatwienia późniejszych obliczeń. Otrzymany wynik przypisujemy zmiennej 'k'
k=len(M)/2
    #deklarujemy listę, w której będą przechowywane wartości liczbowe odpowiadające digrafowi
inddig=[]
    #deklarujemy zmienną tekstową 'm', która będzie przechowywać ,zaszyfrowany już, tekst
m=''

#definiujemy pętlę
for i in range(k):
    #dodajemy do listy 'inddig' wartość liczbową odpowiadającą digrafowi o indeksie i (ilość digrafów wynosi k=len(M)/2)
    inddig.append(abec.find(M[2*i])*len(abec)+abec.find(M[2*i+1]))
    #wykonujemy działanie a*inddig+b(MOD len(abec)^2), gdzie a, b- zadeklarowane liczby całkowite, inddig[i] jest wartością liczbową                     odpowiadającą digrafowi o indeksie 'i', oraz len(abec)^2 jest kwadratem ilości liter w zdefiniowanym alfabecie 'abec'
    n=(37*inddig[i]+384)%((len(abec))^2)
    #dodajemy do zmiennej tekstowej 'm' pierwszy zaszyfrowany już znak (drugą literę) digrafu; (abec[n//len(abec)] zwraca literę w alfabecie             'abec', o ineksie odpowiadającym całości z dzielenia n/len(abec), która zostaje dodana do 'm'
    m=m+(abec[n//(len(abec))])
    #dodajemy do zmiennej tekstowej 'm' drugi zaszyfrowany już znak (drugą literę) digrafu, (abec[n%len(abec)]) zwraca literę w alfabecie               'abec', o ineksie odpowiadającym reszcie z dzielenia n/len(abec), która zostaje dodana do 'm'
    m=m+(abec[n%(len(abec))])
#wyświatlamy wiadomość przed, oraz po, zaszyfrowaniu
print M,'->',m

#ZACZEK WOJCIECH- FUNKCJA SZYFRUJĄCA (ZADANIE 2)
def encipher(M,a,b):
    #definiujemy alfabet ('abec')
    abec='ABCDEFGHIJKLMNOPQRSTUVWXYZ ?!`'

    #sprawdzamy parzystość ilości liter  alfabecie (w przypadku nieparzystości dodajemy do wiadomości literę "X")
    if (len(M)%2)<>0: M=M+'X'
    
    #dzielimy ilość liter (teraz już parzystą) w alfabecie przez 2 w celu ułatwienia późniejszych obliczeń. Otrzymany wynik przypisujemy zmiennej 'k'
    k=len(M)/2
    #deklarujemy listę, w której będą przechowywane wartości liczbowe odpowiadające digrafowi
    inddig=[]
    #deklarujemy zmienną tekstową 'm', która będzie przechowywać zaszyfrowany już tekst
    m=''

    #definiujemy pętlę
    for i in range(k):
        #dodajemy do listy 'inddig' wartość liczbową odpowiadającą digrafowi o indeksie i (ilość digrafów wynosi k=len(M)/2)
        inddig.append(abec.find(M[2*i])*len(abec)+abec.find(M[2*i+1]))
        #wykonujemy działanie a*inddig+b(MOD len(abec)^2), gdzie a, b- zadeklarowane liczby całkowite, inddig[i] jest wartością liczbową odpowiadającą digrafowi o indeksie 'i', oraz len(abec)^2 jest kwadratem ilości liter w zdefiniowanym alfabecie 'abec'
        n=(a*inddig[i]+b)%((len(abec))^2)
        #dodajemy do zmiennej tekstowej 'm' pierwszy zaszyfrowany już znak (drugą literę) digrafu; (abec[n//len(abec)] zwraca literę w alfabecie 'abec', o ineksie odpowiadającym całości z dzielenia n/len(abec), która zostaje dodana do 'm'
        m=m+(abec[n//(len(abec))])
        #dodajemy do zmiennej tekstowej 'm' drugi zaszyfrowany już znak (drugą literę) digrafu, (abec[n%len(abec)]) zwraca literę w alfabecie 'abec', o ineksie odpowiadającym reszcie z dzielenia n/len(abec), która zostaje dodana do 'm'
        m=m+(abec[n%(len(abec))])
        #funkcja zwraca wiadomość przed (w przypadku nieparzystej ilości liter w wiadomości dodawana jest litera 'X'), oraz po, zaszyfrowaniu
    print M,'->',m
#PRZYKŁAD ZASTOSOWANIA- po zastosowaniu funkcji 'encipher' dla danych z zadania 1 b) otrzymujemy taki sam wynik, jaki uzyskaliśmy wcześniej
encipher('YES I`M JOKING!',37,384)