Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
44
Rozdział2.Klasycznakryptografia
Załóżmy,żeoznaczymyczęstotliwościA,B,C,ł,Zwxprzezf
0,f
1,...,f
25(odpo-
wiednio).Możemywybraćdwaelementyxna
istnieją+
§
¨
©
2
f
i
·
¸sposobywyboruobuelementów,któremająbyći.Stądmamywzór
¹
I
c
()
x1
¦
i
25
1
0
§
§
¨
©
n
2
·
f
i
·
¸
¹
1
§
¨
©
¦
i
25
1
n
2
0
nn
·
¸sposoby
¹
(
ff
i
(
-
i
1
-
)
1
)
.
3.Dlakażdegoi,0≤i≤25,
¨
©
2
¸
¹
Załóżmy,żexjestciągiemtekstowymwjęzykuangielskim.Oznaczmyoczekiwanepraw-
dopodobieństwawystąpienialiterA,B,ł,Zztabeli2.1odpowiednioprzezp
0,ł,p
25.
Wówczasmożemysięspodziewać,że
I
c
()
x|
¦
i
25
1
0
p
i
2
1
0065
,
,
ponieważprawdopodobieństwo,żeobaelementylosowetoAwynosip
0
2,aprawdopo-
dobieństwo,żeobatoBwynosip
1
2itd.Tosamorozumowaniemazastosowanie,jeżelix
jestciągiemszyfrogramuotrzymanymprzyużyciudowolnegoszyfrumonoalfabetycznego.
Wtymprzypadkuposzczególneprawdopodobieństwabędąpodlegaćpermutacji,alewiel-
kość∑p
i
2pozostanieniezmieniona.
Załóżmyteraz,żezaczynamyodciąguszyfrogramuy=y
1y
2ły
n,któryzostałzbu-
dowanyprzyużyciuszyfruVigenère3a.Zdefiniujmympodciągówy,oznaczonychy
1,y
2,
ł,y
mprzezprzepisanieszyfrogramuwkolumnachwprostokątnejmacierzyowymiarach
m×(n/m).Wierszetejmacierzysąpodciągamiy
i,1≤i≤m.Innymisłowy,mamy
y
y
1
2
1
1
iii
yy
yy
1
2
m
m
+
+
12
22
y
y
m
m
+
+
1
2
ł
ł
,
,
y
m
1
yy
m
2
m
y
3
m
ł
.
Jeśliy
1,y
2,ł,y
msąskonstruowanewtensposób,amjestfaktyczniedługościąsłowa
kluczowego,tokażdawartośćI
c(y
i)powinnabyćwprzybliżeniurówna0,065.Zdrugiej
strony,jeślimniejestdługościąsłowakluczowego,topodciągiy
ibędąwyglądałyowiele
bardziejlosowo,ponieważzostanąuzyskaneprzezszyfrowanieprzesuwającezróżnymi
kluczami.Zauważmy,żecałkowicielosowyciągznakówbędziemiał
I
c|
26
§
¨
©
26
1
·
¸1
¹
2
26
1
1
0038
.
,
Dwiewartości0,065i0,038sąnatyleodległeodsiebie,żeczęstobędziemywstanietą
metodąokreślićprawidłowądługośćsłowakluczowego(lubpotwierdzićodgadniecie,które
zostałojużdokonanezapomocątestuKasiskiego).
zezbiorunobiektów.
3SymbolNewtona
§
¨
©
n
k
·
¸=n!/(k!(n-k)!)wyznaczaliczbęsposobówwybraniapodzbiorukobiektów
¹
