W5_Kodowanie i Kryptografia_Szyfry klasyczne_2g.pdf
(
578 KB
)
Pobierz
Microsoft PowerPoint - W5_Kodowanie i Kryptografia_Szyfry klasyczne_2g.ppt
Kryptografia
Kryptografia klasyczna
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. 3203083
e-mail:
robert.borowiec@ita.pwr.wroc.pl
www:
lstwww.ita.pwr.wroc.pl/
~
RB/
Wykład V
2-godziny
Rodzaje szyfrów
¾
Szyfry przestawieniowe
¾
Szyfry podstawieniowe
Ö
szyfry proste
Ö
szyfry homofoniczne
Ö
wieloalfabetowe
Ö
poligramowe
¾
Szyfry mieszane (podstawieniowo-
przestawieniowe)
© Robert Borowiec
Kryptografia, Wykład V, Strona 2/25
Szyfr przestawieniowy
te ks t ja wny
zapis
figura
odczyt
szyfrogram
1
2
3
4
5
6
Zapis tekstu jawnego
odbywa się wierszami, a
odczyt kolumnami.
Kluczem
kryptograficznym jest
długość wiersza,
K=6
1
m
a
t
e
m
a
2
t
y
k
a
t
o
3
k
r
ó
l
o
w
4
a
n
a
u
k
x
© Robert Borowiec
Kryptografia, Wykład V, Strona 3/25
Szyfr przestawieniowy
metoda okresowo-permutacyjna
Informacja jawna
M=m
1
m
2
...m
d
m
d+1
...m
zd
dzielona jest na
bloki o długości
d
znaków. Na każdym bloku dokonywane
jest przestawienie znaków według określonej funkcji
f.
Klucz
szyfru jest określony się przez
K=(d,f)
.
Przykład:
d
=4
; i
=1 2 3...4=
d
;
f(i)
=2 31 4.
m
1
m
2
m
3
m
4
m
1
m
2
m
3
m
4
m
1
m
2
m
3
m
4
m
1
....
c
1
c
2
c
3
c
4
c
1
c
2
c
3
c
4
c
1
c
2
c
3
c
4
c
1
....
© Robert Borowiec
Kryptografia, Wykład V, Strona 4/25
Metoda okresowo permutacyjna
oszacowanie długości krytycznej
¾
Okres szyfru wynosi
d
⇒ liczba możliwych przestawień
d!
¾
Entropia klucza
H(k)
=log
2
d!
¾
Redundancja języka
D
=3.2
bita/literę
(dla języka ang.)
¾
Przybliżenie Stirlinga:
log
d
!
≈
d
log
d
+
log
2
d
2
2
e
2
Krytyczna długość kodu
()
d
log
d
+
log
2
π
d
H
k
log
d
!
2
e
2
d
N
=
=
2
≈
≈
0
⋅
d
log
D
D
3
2
2
e
© Robert Borowiec
Kryptografia, Wykład V, Strona 5/25
Szyfr podstawieniowy
monoalfabetyczny
Szyfry podstawieniowe monoalfabetyczne zamieniają znak
alfabetu
A
określonego dla wiadomości jawnej na znak
alfabetu kryptogramu
C
.
f
:
A
→
C
Funkcja
f
jednoznacznie przyporządkowuje:
A
-alfabet
n
znakowy dla tekstów jawnych {
a
1
,
a
2
, ...,
a
n
} na
C
-alfabet
n
znakowy {
f(a
1
)
,
f(a
2
)
, ...,
f( a
n
)
}
Przykład:
A
:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
C
:
HARPSICODBEFGJKLMNQTUVWXYZ
M
=KRYPTOGRAFIA ⇒
E
K
(M)
=ENYLTKCNHIDH
© Robert Borowiec
Kryptografia, Wykład V, Strona 6/25
Szyfr podstawieniowy
monoalfabetyczny-przesunięciowy
Jeżeli funkcja
f
jest funkcją przesunięcia alfabetu
A
o
k
pozycji to jest to szyfr przesunięciowy i można go zapisać
formalnie w postaci:
f
(
a
)=(
a
+
k
) mod
n
..
X
Y
Z
A
B
C
D
E
..
n
-jest licznością
używanego alfabetu
k=3
..
X
Y
Z
A
B
C
D
E
..
© Robert Borowiec
Kryptografia, Wykład V, Strona 7/25
Szyfr podstawieniowy
inne szyfry oparte na przesunięciu alfabetu
¾
f
(
a
)=(
a
·
k
) mod
n,
warunek: NWD(
k,n
)
=
1
¾
f
(
a
)=(
a
·
k
1
+k
0
) mod
n,
warunek: NWD(
k
1
,n
)
=
1
¾
f
(
a
)=(
a
t
·
k
t
+ a
t-1
·
k
t-1
+.....+ a
1
·
k
1
) mod
n,
warunek:
NWD(
k
t
,n
)
=
1
gdzie:
NWD-największy wspólny podzielnik,
NWD=1-oznacza, że liczby są względnie pierwsze
© Robert Borowiec
Kryptografia, Wykład V, Strona 8/25
Szyfr podstawieniowy
oszacowanie długości krytycznej
Dla alfabetu
A
zawierającej
n
liter, liczba wszystkich
możliwych kluczy wynosi
n
!. W przypadku szyfrów bazujących
na przesunięciu alfabetów już tylko
n.
Krytyczna długość kodu
N
=
H
()
=
log
2
n
!
≈
28
-dla szyfrów podstawieniowych
D
D
N
=
H
()
=
log
2
n
≈
1
.
5
-dla szyfrów przesunięciowych
D
D
© Robert Borowiec
Kryptografia, Wykład V, Strona 9/25
Szyfr podstawieniowy
homofoniczny
Szyfr homofoniczny odzwierciedla każdą literę
alfabetu na zbiór homofonów. Litery częściej występujące w
tekście mają przydzieloną większą liczbę homofonów.
Litera alfabetu
A
Homofony
A
17 19 34 12 ..
B
05 09 11 ..
C
02 06 78 ..
D
04 55 ..
...
...
© Robert Borowiec
Kryptografia, Wykład V, Strona 10/25
k
k
Plik z chomika:
meandry
Inne pliki z tego folderu:
W6_Kodowanie i Kryptografia_Kody klasyczne_kryptoanaliza_1g.pdf
(418 KB)
kodowanie testy.rar
(2767 KB)
W10_Kodowanie i Kryptografia_Funkcje jednokierunkowe_15minut.pdf
(265 KB)
Kodowanie_zbior_pytan.doc
(101 KB)
W13_Kodowanie i Kryptografia_kody liniowe_cale_6g.pdf
(829 KB)
Inne foldery tego chomika:
Pliki dostępne do 01.06.2025
Pliki dostępne do 19.01.2025
! POJEDYNCZE POLSKIE (FLAC-APE)
# Polskie wersje światowych przebojów
[2015] Dark Before Dawn
Zgłoś jeśli
naruszono regulamin