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
Klucz: CRYPTO
ILEARNEDHOWTOCALCULATETHEAMOUNTOFPAPERNEEDEDF ORAROOMWHENIWASATSCHOOLYOUMULTIPLYTHESQUAREFO OTAGEOFTHEWALLSBYTHECUBICCONTENTSOFTHEFLOORAN DCEILINGCOMBINEDANDDOUBLEITYOUTHENALLOWHALFTH ETOTALFOROPENINGSSUCHASWINDOWSANDDOORSTHENYOU ALLOWTHEOTHERHALFFORMATCHINGTHEPATTERNTHENYOU DOUBLETHEWHOLETHINGAGAINTOGIVEAMARGINOFERRORA NDTHENYOUORDERTHEPAPER
OCANADATERREDENOSAIEUX TONFRONTESTCEINTDEFLEURONSGLORIEUX CARTONBRASSAITPORTERLEPEE ILSAITPORTERLACROIX TONHISTOIREESTUNEEPOPEE DESPLUSBRILLANTSEXPLOITS ETTAVALEURDEFOITREMPEE PROTEGERANOSFOYERSETNOSDROITS"
a^{-1} = 11
b = 4
Kod w Haskellu:
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]]
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
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.
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.
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).
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.
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.
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)
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
\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
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ą.