====== Kryptografia - Lista 1. ======

===== Zadanie 1. ======

==== Szyfr podstawieniowy ====

  I MAY NOT BE ABLE TO GROW FLOWERS BUT MY GARDEN PRODUCES
   JUST AS MANY DEAD LEAVES OLD OVERSHOES PIECES OF ROPE AND
   BUSHELS OF DEAD GRASS AS ANYBODY S AND TODAY I BOUGHT
   A WHEELBARROW TO HELP IN CLEARING IT UP I HAVE ALWAYS LOVED
   AND RESPECTED THE WHEELBARROW IT IS THE ONE WHEELED VEHICLE
   OF WHICH I AM PERFECT MASTER

==== Szyfr Vigenere ====

Klucz: CRYPTO

  ILEARNEDHOWTOCALCULATETHEAMOUNTOFPAPERNEEDEDF
  ORAROOMWHENIWASATSCHOOLYOUMULTIPLYTHESQUAREFO
  OTAGEOFTHEWALLSBYTHECUBICCONTENTSOFTHEFLOORAN
  DCEILINGCOMBINEDANDDOUBLEITYOUTHENALLOWHALFTH
  ETOTALFOROPENINGSSUCHASWINDOWSANDDOORSTHENYOU
  ALLOWTHEOTHERHALFFORMATCHINGTHEPATTERNTHENYOU
  DOUBLETHEWHOLETHINGAGAINTOGIVEAMARGINOFERRORA
  NDTHENYOUORDERTHEPAPER

==== Szyfr afiniczny ====

  OCANADATERREDENOSAIEUX
  TONFRONTESTCEINTDEFLEURONSGLORIEUX
  CARTONBRASSAITPORTERLEPEE
  ILSAITPORTERLACROIX
  TONHISTOIREESTUNEEPOPEE
  DESPLUSBRILLANTSEXPLOITS
  ETTAVALEURDEFOITREMPEE
  PROTEGERANOSFOYERSETNOSDROITS"

$a^{-1} = 11$\\
$b = 4$

Kod w Haskellu:
<code>
a = $TESKT_TAJNY
let af a b x = chr $ (+65) $ (`mod`26) $ (*a) $ (+(-b)) $ (+(-65)) $ ord x 
mapM_ print $ map (\(a',b,f) -> (a',b,map f a)) $ map (\(a,b) -> (a,b,af a b)) [(x,y)|x<-[0..25],y<-[0..25]]   
</code>

==== Szyfr nieznany ====

Vigenere, z kluczem THEORY

    I GREW UP AMONG SLOW TALKERS. MEN IN PARTICULAR WHO DROPPED
    WORDS A FEW AT A TIME LIKE BEANS IN A HILL. AND WHEN I GOT
    TO MINNEAPOLIS WHERE PEOPLE TOOK A LAKE WOBEGON COMMA
    TO MEAN THE END OF A STORY I COULDNT SPEAK A WHOLE
    SENTENCE IN COMPANY AND WAS CONSIDERED NOT TOO BRIGHT.
    SO I ENROLLED IN A SPEECH COURSE TAUGHT BY ORVILLES AND THE
    FOUNDER OF REFLEXIVE RELAXOLOGY, A SELF HYPNOTIC TECHNIQUE
    THAT ENABLED A PERSON TO SPEAK UP TO THREE
    HUNDRED WORDS PER MINUTE

===== Zadanie 2. =====

Klucze w szyfrze Hilla w $26$-literowym alfabecie o blokach długości $m$ to macierze nieosobliwe wymiarów $m \times m$ modulo $26$.

Macierze nieosobliwe wymiarów $m \times m$ modulo $2$ tworzą grupę $GL(m,2)$, czyli grupę macierzy nieosobliwych $m\times m$ modulo $2$. Tak samo dla $13$ jest to grupa $GL(m,13)$.

Liczba elementów grupy $GL(m,q)$, gdzie $q$ jest pierwsze to

$(q^m - 1)(q^m - q)(q^m - q^2)\cdots(q^m-q^{m-1})$. 

W pierwszej kolumnie macierzy nie może być wektor zerowy, więc ze wszystkich możliwych kolumn go wyrzucamy - mamy narazie $q^m - 1$ możliwości. W drugiej kolumnie mogą być wszystkie wektory oprócz wielokrotności pierwszego wektora, więc z $q^m$ możliwych kolumn wyrzucamy $q$ kolumn będących wielokrotnościami pierwszej. W trzeciej kolumnie nie może być wektorów będących liniową kombinacją dwóch pozostałych, itd. Stąd wzór.

Teraz trzeba to skleić w 26.

==== Lemat 1 ====

Mnożenie macierzy zachowuje równoważność modularną. To znaczy:

Jeśli $A, B$ są macierzami z $M_{r \times s}(Z)$ oraz $X, Y$ macierzami z $M_{s\times t}(Z)$, to jeśli $A \equiv_m B$ i $X \equiv_m Y$ to $AX \equiv_m BY$.

Gdzie $A \equiv_m B$ oznacza $\forall_i \forall_j a_{ij} \equiv_m b_{ij}$.

Dowód

Niech $C = AX$ oraz $D = BY$.

$c_{ij} \equiv_m \sum_{k=1}^s a_{ik}x_{kj}$ oraz $d_{ij} \equiv_m \sum_{k=1}^s b_{ik}b_{kj}$

Ponieważ dla każdego $i, j, k$ $a_{ik} \equiv_m b_{ik}$ oraz $x_{kj} \equiv_m y_{kj}$, $c_{ij} \equiv_m d_{ij}$ dla każdego $i, j$.

Czyli $C \equiv_m D$.

==== Lemat 2 ====

Niech $\phi : M_{d \times d}(Z_m) -> \bigoplus_{i=1}^z M_{d\times d}(Z_{{p_i}^{n_i}})$ będzie zdefiniowane tak:

$\phi(A) = \bigoplus \phi_i(A)$, gdzie $\phi_i(A) = A \; \mathrm{mod} \; {p_i}^{n_i}$.

Wtedy $\phi$ jest izomorfizmem (pierścieni).

Dowód

To, że $\phi$ jest bijekcją wynika bezpośrednio z chińskiego twierdzenia o resztach.

Teraz udowodnimy homomorficzność $\phi$:

Niech $A$ i $B$ będą maczierzami z $M_{d\times d}(Z_m)$.

I niech $\phi(A) = (A^{(1)}, A^{(2)}, \dots, A^{(z)})$ i $\phi(B) = (B^{(1)}, B^{(2)}, \dots, B^{(z)})$

Zauważmy, że $A^{(i)}B^{(i)} = (AB)^{(i)}$ dla każdego $i$ ponieważ mnożenie macierzy zachowuje modularną równoważność.

Teraz $\phi(A)\phi(B) = (A^{(1)}, A^{(2)}, \dots, A^{(z)})(B^{(1)}, B^{(2)}, \dots, B^{(z)})$

$= (A^{(1)}B^{(1)}, A^{(2)}B^{(2)}, \dots, A^{(z)}B^{(z)})$

$= ((AB)^{(1)}, (AB)^{(2)}, \dots, (AB)^{(z)})$

$= \phi(AB)$.
==== Lemat 3 ====

Macierz $A$ z $Z_m$ jest odwracalna wtw gdy $\phi(A)$ jest odwracalna.

Dowód.

Jeśli $A$ jest odwracalna modulo $M$, to $\phi(A)\phi(A^{-1}) = \phi(AA^{-1}) = \phi(I)$, a $\phi(I)$ jest identycznością w kodomenie $\phi$, więc jest odwracalna.\\ W drugą stronę to zachodzi, ponieważ $\phi$ jest izomorfizmem.

==== Twierdzenie 4 ====

Liczba macierzy $d \times d$ odwracalnych modulo $m = \prod_i p_i$ to

$\displaystyle\prod_i \prod_{k=0}^{d-1} (p_i^d - p_i^k)$.

Dowód

Niech $\phi$ będzie takie jak w lematach. Żeby krotka w kodomenie $\phi$ była odwracalna, każda jej macierz składowa musi być odwracalna. Dla każdej macierzy składowej mamy wzór będący wewnętrznym produktem. A więc liczba odwracalnych krotek to iloczyn liczb możliwości każdej składowej. Z lematu 3 wiemy, że jeśli krotka jest odwracalna, to jej koleżanka z dziedziny $\phi$ też jest. Ponieważ $\phi$ jest bijekcją, to liczba macierzy odwrotnych modulo $m$ jest jak powyżej.

Czyli jeśli chcemy policzyć wszystkie klucze w szyfrze Hilla modulo 26, musimy obliczyć:

$(2^m-1)(13^m-1)(2^m-2)(13^m-13)\cdots(2^m-2^{m-1})(13^m-13^{m-1})$.

Dla $m=2$ jest to $(2^2-1)(13^2-1)(2^2-2)(13^2-13) = 157248$.

===== Zadanie 3. ======

Trzeba policzyć macierze które są inwolucjami. Dowody są skomplikowane, więc podam wyniki i odwołania:

(Hodges, 1958) Liczba $T(d,p)$ macierzy $d \times d$ modulo $p$, gdzie $p$ to nieparzysta liczba pierwsza to

$\displaystyle T(d,p) = \sum_{t=0}^d \frac 1 {g_tg_{d-t}}$, gdzie

$g_t = \prod_{i=0}^{t-1} (p^t-p^i)$

Dla $p = 2$:

$\displaystyle T(d, 2) = g_d\sum_{t=0}^{\lfloor d/2 \rfloor} \frac {2^{-t(2d-3t)}}{g_tg_{d-2t}}$

I dla liczb pierwszych $p_1, p_2, \dots, p_n$ i ich iloczynu $q$:

$T(d, q) = \prod_{i=0}^{n}T(d, p_i)$

===== Zadanie 4. ======

Mamy $12$ par litera jawna/tajna. Musimy mieć dostatecznie dużo redundantnych par, by ułożyć układ równań dla każdego wiersza macierzy szyfrowania. Można szybko policzyć, że maksymalnie możemy łatwo zgadnąć macierz $3\times 3$. Czyli mamy do wyboru $m \in \{2,3\}$.

Spróbujmy $m=2$. Wiemy, że:

$\pmatrix{
x_{11} & x_{12} \cr
x_{21} & x_{22}
}
\pmatrix{ B \cr R }
=
\pmatrix{ R \cr U }$

,

$\pmatrix{
x_{11} & x_{12} \cr
x_{21} & x_{22}
}
\pmatrix{ E \cr A }
=
\pmatrix{ P \cr O }$

oraz

$\pmatrix{
x_{11} & x_{12} \cr
x_{21} & x_{22}
}
\pmatrix{ T \cr H }
=
\pmatrix{ T \cr E }$


$\cases{
x_{11}\cdot 1 + x_{12}\cdot 17 = 17 \cr
x_{11}\cdot 4 + x_{12}\cdot 0 = 15 \cr (*)
x_{11}\cdot 19 + x_{12}\cdot 7 = 19 \cr
}$

oraz

$\cases{
x_{21}\cdot 1 + x_{22}\cdot 17 = 20 \cr
x_{21}\cdot 4 + x_{22}\cdot 0 = 14 \cr
x_{21}\cdot 19 + x_{22}\cdot 7 = 4 \cr
}$

Dość wcześnie okazuje się, że nie istnieje w $Z_{26}$ element $z$ taki, że $4z \equiv_{26} 15$, więc mamy pecha i musimy spróbować $m=3$.

Tym razem mamy:

X = $\pmatrix{
x_{11} & x_{12} & x_{13} \cr
x_{21} & x_{22} & x_{23} \cr
x_{31} & x_{32} & x_{33} 
}$

$X \pmatrix{ B & E & H \cr R & A & T \cr E & T & A} = \pmatrix{ R & O & N \cr U & T & T\cr P & E & O}$

A więc

$X = \pmatrix{ R & O & N \cr U & T & T\cr P & E & O} \pmatrix{ B & E & H \cr R & A & T \cr E & T & A}^{-1}$

$X = \pmatrix{3&4&6 \cr 21&15&14 \cr 20&23&5} = \pmatrix{D&E&G\cr V&P&O \cr U&X&E}$

Przydatna tabelka:
   0  1  2  3  4  5  6  7  8  9 10 11 12
   A  B  C  D  E  F  G  H  I  J  K  L  M
   
  13 14 15 16 17 18 19 20 21 22 23 24 25
   N  O  P  Q  R  S  T  U  V  W  X  Y  Z  

===== Zadanie 5. ======
===== Zadanie 6. ======
===== Zadanie 7. ======
===== Zadanie 8. ======
===== Zadanie 9. ======

$\cases{
x \equiv 3 \; \mathrm{mod} \; 7 \cr
x \equiv 5 \; \mathrm{mod} \; 11 \cr
x \equiv 4 \; \mathrm{mod} \; 12}$

Wyliczymy $x$ z chińskiego twierdzenia o resztach.

$N = 7\cdot11 \cdot 12 = 924.$

$(\frac N 7)^{-1} \; \mathrm{mod} \; 7 = -1$

$(\frac N 11)^{-1} \; \mathrm{mod} \; 11 = -3$

$(\frac N 12)^{-1} \; \mathrm{mod} \; 12 = 5$

$x \equiv_N 3 \cdot \frac N 7 \cdot (\frac N 7)^{-1} + 5 \cdot \frac N {11} \cdot (\frac N {11})^{-1} + 4 \cdot \frac N {12} \cdot (\frac N {12})^{-1} \equiv_N 3 \cdot 132 \cdot (-1) + 5 \cdot 84 \cdot (-3) + 4 \cdot 77 \cdot 5 \equiv_N -116$

===== Zadanie 10. ======
===== Zadanie 11. ======
===== Zadanie 12. ======
===== Zadanie 13. ======
===== Zadanie 14. ======
===== Zadanie 15. ======

Lemat

Jeśli $a^m = 1$, to $n|m$, gdzie $n = ord(a)$.

Niech $q$ i $r$ będą takie, że $0 \leq r < n$ oraz $m = qn + r$.

$1 = a^m = a^{qn+r} = (a^n)^q \cdot a^r = a^r$. $r=0$ wynika z minimalności $ord(a)$.

Twierdzę, że jeśli $q$ jest pierwsze, to jeśli $a^q = 1$, to $ord(a) = q$.

Założmy niewprost, że $p < q$ jest takie, że $ord(a) = p$. Z lematu wynika, że $p | q$. Mamy więc sprzeczność z założeniem, że $q$ jest większą od $p$ liczbą pierwszą.

===== Zadanie 16. ======