UVOD U
KRIPTOLOGIJU
Aleksandar Jovičić
[email protected]
Definicija
= skriveno
ΛOΓΟΣ = nauka
=>
??? ... Nauka o skrivanju?!?!??? 
Kriptologija
ΚΡΥΠΤOΣ
Nauka o skrivenom pisanju i
neovlašćenom tumačenju
nečega skriveno napisanog
A čemu to služi?
●
Skriveno pisanje ...
♦ Zaštita podataka pri prenosu
○
Kriptologija
○
●
od gledanja (pasivan napad)
od falsifikovaja (aktivan napad)
♦
Zaštita tajnosti lozinke (password-a)
♦
Zaštita autorskih prava
Neovlašćeno tumačenje ...
♦ Otkrivanje destruktivnih namera protivnika
♦
Testiranje sopstvenih sistema zaštite
♦
“Kontakt” sa ALF-om 
i starim civilizacijama
A čemu to služi?
●
Skriveno pisanje ...
♦ Zaštita podataka pri prenosu
○
Kriptologija
○
●
od gledanja (pasivan napad)
od falsifikovaja (aktivan napad)
♦
Zaštita tajnosti lozinke (password-a)
♦
Zaštita autorskih prava
Neovlašćeno tumačenje ...
♦ Otkrivanje destruktivnih namera protivnika
♦
Testiranje sopstvenih sistema zaštite
♦
“Kontakt” sa ALF-om 
i starim civilizacijama
Kriptologija
Terminologija
●
Skriveno pisanje = Kriptografija
●
Neovlašćeno tumačenje = Kriptoanaliza
●
Kriptografija = Steganografija +
Kriptografija u užem smislu
●
Steganografija = veština SKRIVANJA
poruke od Interceptera
●
Intercepter = Neželjeni primalac informacije
Kriptologija
Kriptologija
i teorija informacija
pošiljalac
primalac
Predajnik
Predajnik
kanal veze
Prijemnik
Prijemnik
Kriptologija
Kriptologija
i teorija informacija
INTERCEPTER
pošiljalac
primalac
Predajnik
Predajnik
kanal veze
Prijemnik
Prijemnik
Kriptologija
i teorija informacija
Kriptologija

INTERCEPTER
pošiljalac
primalac
Predajnik
Predajnik
kanal veze
?
Prijemnik
Prijemnik
?
kriptovanje
dekriptovanje
otvoreni tekst
šifrat
otvoreni tekst
(plain text)
(ciphertext)
(plain text)
Kriptologija
i teorija informacija
Kriptologija
kriptoanaliza

INTERCEPTER
pošiljalac
primalac
Predajnik
Predajnik
kanal veze
?
Prijemnik
Prijemnik
?
kriptovanje
dekriptovanje
otvoreni tekst
šifrat
otvoreni tekst
(plain text)
(ciphertext)
(plain text)
Steganografija
●
Kriptologija
●
Tehnička (nevidljivo mastilo, mikrotačka, ...)
Lingvistička
 Semagrami
 Otvoreni

k ôd
Žargon (promena smisla)


(označavanje slova, reči,...)
Lozinka (najava akcije preko radija, ...)
Maskiranje


Sistem rešetke (upisivanje u tačno odredjena polja)
Sistem dodavanja null-vrednosti (svako n-to ...)
Kriptologija
Kripto-sistemi
V - skup karaktera otvorenog teksta
W - skup karaktera šifrata
 - “prazna” reč
V*, W* - skup reči formiranih od V i W
Zn  Z* - skup reči dužine n
Z(n) = {}  Z  Z1  Z2 ...  Zn
X : V*  W* - kriptovanje (encryption) ...
xy
X-1 : W *  V* - dekriptovanje (decryption) ... x  y
( x  z )  ( y  z )  (x = y) - jednoznačnost
M - kripto-system
M = {0, 1, 2, ... n } i : V(ni)  W(mi)
i - “korak” kriptovanja
Kripto-sistemi
●
Transpozicijski sistemi
Kriptologija
 Prosta
transpozicija
 Anagrami
●
Supstitucijski sistemi
 Monoalfabetska
supstitucija
 Poligrafska supstitucija i kodovi
 Polialfabetska supstitucija
Kripto-sistemi
●
Kompozitni sistemi
Kriptologija
 DES
 IDEA
●
Asimetrični sistemi (public key systems)
 RSA
●
Kombinovani sistemi
 PGP
Kriptologija
Prosta transponzicija
ich bin der doktor eisenbart
ichbin derdok toreis enbart
ichbin
derdok
toreis
enbart
IDTECEONHRRBBDEAIOIRNKST
Kriptologija
Anagrami
admonition = domination
algorithms = logarithms
excitation = intoxicate
compressed = decompress
impression = permission
...
plava riba, kljukana dinastija,
svastikin but, trt, trt, trt ...
!?!?????
Monoalfabetska supstitucija
otvorni tekst
Cezarova šifra
Kriptologija
a
Y
b
Z
c
A
d
B
e
C
f
D
šifrat
bez tačke
a
d
g
.
b
e
h
sa tačkom
c
f
i
j
m
p
.
k
n
q
bez tačke
=>
h
F
...
...
d ac a
BYAY
sa tačkom
l
s
w
o t
u x
z
v
r
.
g
E
= ???
y
Masonska šifra
Monoalfabetska supstitucija
otvorni tekst
Cezarova šifra
Kriptologija
a
Y
b
Z
c
A
d
B
e
C
f
D
šifrat
bez tačke
a
d
g
.
b
e
h
sa tačkom
c
f
i
j
m
p
.
k
n
q
bez tačke
=>
h
F
...
...
d ac a
BYAY
sa tačkom
l
s
w
o t
u x
z
v
r
.
g
E
= MINER
y
Masonska šifra
Nedostaci monoalfabetske
supstitucije
Kriptologija
Analiza frekvencija + ...
A
4%
B
10 %
a
10 %
e
9.4 %
C
1%
o
9%
D
1.2 %
k
6.2 %
E
2%
F
9%
G
0.4 %
H
-
i
6%
t
r
u
5.9 % 5.4 % 3 %
...
...
...
...
... malo pogadjanja = ...
(the, then, all ...)
PROVALJENA ŠIFRA!!!
Još jednostavnije ...
Analiza frekvencije dvoznaka + ...
Kriptologija
F[%%]
a
b
c
...
a
1
8
44
b
32
c
39
...
12
... još manje pogadjanja = ...
PROVALJENA ŠIFRA!!!
Kriptologija
Višestruka
monoalfabetska supstitucija
1
2
3
4
5
6
7
8
9
4,5,6,7,8,9,0
e
t
a
o
n
i
r
s
h
2,3
b
c
d
f
g
j
k
l
m
1
p
q
u
v
w
x
y
z
daca -> 23 43 22 83
Kriptologija
Višestruka
monoalfabetska supstitucija
1
2
3
4
5
6
7
8
9
4,5,6,7,8,9,0
e
t
a
o
n
i
r
s
h
2,3
b
c
d
f
g
j
k
l
m
1
p
q
u
v
w
x
y
z
daca -> 23 43 22 83
... medjutim uz malo statistike, pogadjanja i
malo više teksta ...
PROVALJENA ŠIFRA!!!
Poligrafska supstitucija
Kriptologija
a
b
c
d
e
f
g
h
i
a
XZ KJ YH HP PL EL VB CI DW
b
LP QT HE RS UR CR ZH GV WC
c
DX MN AO NH SF
da ca -> HP YH
GI WL MN AH
Poligrafska supstitucija
Kriptologija
a
b
c
d
e
f
g
h
i
a
XZ KJ YH HP PL EL VB CI DW
b
LP QT HE RS UR CR ZH GV WC
c
DX MN AO NH SF
GI WL MN AH
da ca -> HP YH
... setimo se frekvencije dvoznaka,
posmatrajmo ovo kao veći alfabet,
uz dovoljno materijala i malo sreće ...
PROVALJENA ŠIFRA!!!
Kriptologija
Kôdovi
napad ....
zora .....
tenk .....
svekrva ..
avioni ...
daca .....
1023
1045
3450
6889
9502
2352
daca -> 2352
... ako kodove posmatramo kao veoma veliki alfabet, nad njima možemo
primeniti istu statistiku koju smo primenili na šiframa ... medjutim, ovde nam
treba dooosta materijala ... Generalno gledano ... matematičari su korisniji
za kriptoanalizu šifara a lingvisti kodova ... uz sreću i više napora ...
PROVALJENA ŠIFRA!!!
Kriptologija
Polialfabetska supstitucija
a
a Z
b D
c Q
...
Otvoreni tekst a
Ključ b
Šifrat D
b
Y
M
R
c ...
X
R
F
b b a
c a b
R Y D
... ovde već nema šale, ... ako je ključ
dovoljno dugačak i ako ga šifrer koristi
pravilno ...
PROVALJENA ŠIFRA!!!
Kriptologija
Polialfabetska supstitucija
a
a Z
b D
c Q
...
Otvoreni tekst a
Ključ b
Šifrat D
b
Y
M
R
c ...
X
R
F
b b a
c a b
R Y D
... medjutim ako retko menja ključeve ili
koriste previše kratke ključeve ...
PROVALJENA ŠIFRA!!!
DES i IDEA
●
●
●
●
●
Kriptovanje 8-bajtnih blokova
DES je (bio) standard u USA
IDEA je registrovana marka
Sistem kriptovanja se zasniva na
operacijama nad bitovima u bajtu
DES JE PROVALJEN!!!
RSA
(Rivest, Shamir, Adleman)
• Asimetričan šifarski sistem
• A, B – Veliki prosti brojevi
• P – Javni ključ
• Q – Tajni ključ
P = AB
Q = ( k (A-1)(B-1) + 1) / n
deljivo sa n bez ostatka
Q = ( 2 (A-1)(B-1) + 1) / 3
najprostiji oblik
• C – otvoreni tekst
C = DQ mod P
• D – šifrat
D = C3 mod P
“Elektronski potpis”
Koriste se asimetrični šifarski sistemi
●
1 - pošiljalac kriptuje svojim tajnim ključem
●
2 - zatim kriptuje primaočevim javnim ključem
●
1-1 - primalac dekriptuje svojim tajnim ključem
●
2-1 - zatim dekriptuje pošiljaočevim javnim ključem
PGP
(Pretty Good Privacy)
Otvoreni
tekst
RSA
IDE
A
Još malo o kriptoanalizi ...
„Nikad ne reci nikad“
●
Šenonova maksima
○
●
Kerkhofsov princip
○
●
„Dobar kriptosistem je siguran čak i kad su poznati svi
njegovi detalji ... osim ključa“
Najslabiji deo kripto-sistema je čovek
○
●
„Neprijatelj zna sistem“
I najsnažniji kripto-sistem može da „padne“ zbog
nepravilne upotrebe
Komplikovano šifrovanje ne znači i
komplikovana kriptoanaliza
Alati
●
„Ako neće, uzmi veći čekić“ (Brute Force)
○
○
○
●
Analiza frekvencija
○
○
○
●
Pokušati sve moguće kombinacije ključa
Efikasno za kratke (loše izabrane) ključeve
Povećanje računarskih performansi prouzrokuje
potrebu za povećanjem dužine ključa i kod sistema
koji su nekada bili „sigurni“
Govorni jezik je „predvidiv“
Neka slova se pojavljuju češće od drugih, to važi i za
parove slova ... a i za reči pa čak i delove rečenica
I jaki sistemi sa loše izabranim ključem otkrivaju
osobine teksta
„Eci-peci-pec“
Tip napada: „Poznat samo šifrat“
●
U slučaju monoalfabetske supstitucije dovoljna
je uglavnom analiza frekvencija
○
●
Polialfabetska supstitucija sa kratkim ključem
može biti potpuno razbijena
○
●
sve poruke su čitljive
većina poruka je čitljiva
Ako se isti ključ primeni na dve ili više poruke,
čak i polialfabetska supstitucija sa beskonačnim
ključem može biti oslabljena
○
○
E(A) xor E(B) = (A xor C) xor (B xor C) = A xor B xor C xor
C = A xor B
neke poruke su čitljive
Tip napada: „Poznat je i otvoreni tekst“
●
●
Telegram sa otvorenim tekstom može biti
ukraden ili greškom objavljen
Pogadjanje tipičnih reči
○
○
●
Česte reči ili formalizovana zaglavlja poruka
„Vremenska prognoza“
Provokacija da se pošalju nama poznate
informacije
○
Akcija koja navodi neprijatelja da javi poziciju i opis
Tip napada: „Napad izabranim tekstom“
●
●
Slabosti sistema se otkrivaju proizvoljnim brojem
poznatih poruka šifrovanih od strane kriptoanalitičara
„Zašto bi neko dobrovoljno pristao da šifruje naše
poruke?“
○
●
●
Asimetrični šifarski sistemi funkcionišu tako što je ključ
za šifrovanje svakom poznat
Zavisno od sistema primenjuje se napad poznatim
otvorenim tekstom ili poznatim šifratom
Provokacija da se pošalje tekst koji nam je poznat
○
Podmetanje „vrlo važne“ informacije
Kako prepoznati sistem?
●
●
●
●
Entropija alfabeta
Entropija dvoznaka (i većih grupa)
Uslovna entropija
Kasiski test
○
●
Ponavljanje grupe od 3 i više karaktera
Fridman test (Kappa test)
○
Indeks podudarnosti
Još malo teorije informacija ...
- ENTROPIJA n
z    pi log2 pi
i 1
zmax  log2 n
• z - entropija
• p - frekvencija
• n - veličina uzorka
Zapamtite !!!
Koliko god Vam se Vaša šifra
činila savršenom,
ona je zadovoljavajuća
samo ako prodje test
kriptoanalize
Literatura
F.L.Bauer, “DECRYPTED SECRETS”
Springer-Verlag Berlin Heidelberg, New York, 1997.
D.Kahn, “CODEBREAKERS”
Macmillan, New York, 1967.
UVOD U
KRIPTOLOGIJU
Aleksandar Jovičić
[email protected]
http://www.jovicic.name/isp/crypto.pdf
Download

Aleksandar Jovičić - M-71 Aleksandar Jovicic (R)