Klasyczna kryptologia wstęP. Proste kryptosystemy



Pobieranie 0,69 Mb.
Strona8/9
Data14.02.2018
Rozmiar0,69 Mb.
1   2   3   4   5   6   7   8   9

Kryptoanaliza szyfru Vigenere’a

Pierwszym etapem jest określenie długości klucza m. Punktem wyjścia jest obserwacja, że dwa identyczne bloki tekstu jawnego są szyfrowane na te same bloki szyfrogramu, jeśli odległość między początkami tych segmentów jest równa d, gdzie d jest podzielne przez m. Odwrotnie, jeśli zaobserwujemy dwa identyczne segmenty szyfrogramu (o długości minimum trzy litery - zakładamy, że używamy kluczy o takiej minimalnej długości), wtedy jest duże prawdopodobieństwo, że odpowiadają one identycznym fragmentom tekstu jawnego. Powyższa metoda pochodząca od F. Kasiskiego (1863) realizowana jest w następujący sposób. W szyfrogramie szukamy par identycznych fragmentów tekstu i określamy odległości między początkami tych segmentów. Jeśli znajdziemy kilka takich par i ich odległości równe są odpowiednio wtedy możemy postawić hipotezę, że długość klucza m dzieli największy wspólny dzielnik liczb . Następną metodą potwierdzenia wartości m jest obliczenie tzw. indeksu koincydencji wprowadzonego przez W. Friedmana w 1920 roku.



Definicja

Niech x = będzie ciągiem n-literowym. Indeksem koincydencji ciągu x, oznaczanym , nazywamy prawdopodobieństwo tego, że dwa losowe elementy ciągu x są identyczne. Oznaczmy częstości występowania poszczególnych liter alfabetu A, B,..., Z w ciągu x przez . Dwa elementy ciągu x możemy wybrać na sposoby. Dla każdego jest sposobów wybrania dwóch elementów równych i . Wtedy oczekujemy, że

= .

Niech x będzie tekstem w języku angielskim. Oznaczmy prawdopodobieństwa występowania liter alfabetu podane w tabeli 1 przez . Wtedy oczekujemy, że



,

ponieważ prawdopodobieństwo, że dwie losowo wybrane litery są równe A jest , są równe B jest , itd. W ten sam sposób wnioskujemy, że dla szyfrogramu x otrzymanego przy pomocy szyfru monoalfabetycznego prawdopodobieństwa występowania poszczególnych liter będą przepermutowane , ale suma wszystkich prawdopodobieństw nie zmieni się.



Załóżmy teraz, że mamy szyfrogram otrzymany przy pomocy szyfru Vigenere’a. Definiujemy m podciągów ciągu y przez zapisanie szyfrogramu kolumnami w tablicy o wymiarach Wiersze tej tablicy są podciągami . Jeśli m jest rzeczywiście długością klucza, wtedy indeks koincydencji dla każdego pociągu powinien w przybliżeniu być równy 0,065. Z drugiej strony, jeśli m nie jest długością klucza, wtedy podciągi mają bardziej losowy charakter, ponieważ są otrzymane przez szyfrowanie z różnymi kluczami. Dla ciągu całkowicie losowego indeks koincydencji równy jest

Dwie liczby 0,065 i 0,038 są dość odległe tak, że jesteśmy w stanie stwierdzić, że przyjęte m jest właściwą długością klucza lub potwierdzić, że m otrzymane przy pomocy testu Kasiskiego jest szukaną długością klucza.



Dla znalezienia klucza o ustalonej wcześniej długości m wprowadzamy pojęcie indeksu koincydencji dwóch ciągów.

Definicja

Niech x = , y = , będą ciągami odpowiednio n i n’ literowymi. Wzajemny indeks koincydencji ciągów x i y (the mutual indeks of coincidence), oznaczany (x, y), jest zdefiniowany jako prawdopodobieństwo tego, że losowy element ciągu x jest równy losowemu elementowi ciągu y. Jeśli oznaczymy częstości występowania liter alfabetu A, B, ..., Z w ciągu x i y odpowiednio przez i wtedy

(x, y) = .

Niech ) będzie szukanym kluczem. Rozpatrywane wcześniej podciągi otrzymujemy przez szyfrowanie będące przesunięciem w alfabecie o pozycji. Rozważmy losowo wybraną literę w ciągu i losowo wybraną literę w ciągu . Prawdopodobieństwo, że są one literą A jest równe , prawdopodobieństwo, że są one literą B jest równe itd., gdzie indeksy są redukowane modulo 26 a prawdopodobieństwa dane są w Tablicy 1. Wzajemny indeks koincydencji równy jest w przybliżeniu:

.

Wartość ta zależy tylko od różnicy (mod 26, którą nazywamy względnym przesunięciem podciągów . Zauważmy, że



,

czyli względne przesunięcie l daje tą samą wartość jak względne przesunięcie 26 - l. Poniższa tabela podaje wartości indeksu dla l w zakresie od 0 do 13.



Względne przesunięcie

Wartość

Względne przesunięcie

Wartość

0

.065

7

.039

1

.039

8

.034

2

.032

9

.034

3

.034

10

.038

4

.044

11

.045

5

.033

12

.039

6

.036

13

.043


Zauważmy, że jeśli względne przesunięcie nie jest zerem to wartości znajdują się między 0,031 a 0,045, następnie względne przesunięcie zero daje wartość 0,065 dla . Możemy powyższe fakty wykorzystać dla określenia wartości względnego przesunięcia ciągów oraz . Ustalmy jeden ciąg i rozważmy przesunięcia ciągu o liczbę przesunięć 0, 1, ... i oznaczmy przesunięte ciągi przez Obliczamy odpowiadające indeksy , , ze wzoru

= .

Jeśli , wtedy powinno być bliskie 0,065, ponieważ względne przesunięcie oraz jest zero. Natomiast dla wartość powinna być zawarta między 0,031 i 0,045. Metoda ta pozwala wyznaczyć względne przesunięcia dowolnych ciągów . Daje to 26 możliwych kluczy i właściwy klucz znajdujemy metodą prób.

Wykorzystując powyższą metodę kryptoanalizy odnaleziono klucze do poniższych szyfrogramów:


1. Szyfrogram:

KCCPK

BGUFD

PHQTY

AVINR

RTMVG

RKDNB

VFDET

DGILT

XRGUD

DKOTF

MBPVG

EGLTF

CKQRA

CQCWD

NAWCR

XIZAK

FTLEW

RPTYC

QKYVX

CHKFT

PONCQ

QRHJV

AJUWE

TMCMS

PKQDY

HJVDA

HCTRL

SVSKC

GCZQQ

DZXGS

FRLSW

CWSJT

BHAFS

IASPR

JAHKJ

RJUMV

GKMIT

ZHFPD

ISPZL

VLGWT

FPLKK

EBDPG

CEBSH

CTJRW

XBAFS

PEZQN

RWXCV

YCGAO

NWDDK

ACKAW

BBIKF

TIOVK

CGGHJ

VLNHI

FFSQE

SVYCL

ACNVR

WBBIR

EPBBV

FEXOS

CDYGZ

WPFDT

KFQIY

CWHJV

LNHIQ

IBTKH

JVNPI

ST






Klucz: CRYPTO


Tekst jawny:

I learned how to calculate the amount of paper need for a room. When I wer at school you multiply the square footage of the walls by the cubic contents of the floor and ceiling combined and double it. You then allow half the total for openings such as windows and doors. Then you allow the other half for matching the pattern. Then you double the whole thing gain to give a margin of error and then you order paper.

2. Szyfrogram:


CHREE

VOAHM

AERAT

BIAXX

WTNXB

EEOPH

BSBQM

QEQER

BWRVX

UOAKK

AOSXX

WEAHB

WGJMM

QMNKG

RFVGX

WTRZX

WIAKL

XFPSK

AUTEM

NDCMG

TSXNX

BTUIA

DNGMG

PSREL

XNJEL

XVRVP

RTULH

DNUWT

WDTYG

BPHXT

FALJH

ASVBF

XNGLL

CHRZB

WELEK

MSJIK

NBHWR

JGNMG

JSGLX

FEYPH

AGNRB

IEQJT

AMRVL

CRREM

NDGLX

RRIMG

NSNRW

CHRQH

AEYEV

TAQEB

BIPEE

WEVKA

KOEWA

DRENX

NTBHH

CHRTK

DNVRZ

CHRCL

QOHPW

QAIIW

XNRMG

WOIIF

KEE

Klucz : JANET

Tekst jawny:

The almond tree was in tentative blossom. The days were longer often ending with magnificent evenings of corrugated pink skies. The hunting season was over with hound sand gunsput away for six months. The vine yards were busy again as the well organized farmers treated their vine sand. The more lack a daisical neighbors hurried to do the pruning, they should done in November.





1   2   3   4   5   6   7   8   9


©operacji.org 2017
wyślij wiadomość

    Strona główna