Kriptográfia I Szimmetrikus kulcsú titkosítás
Kriptorendszerek • Nyíltszöveg üzenettér: M • Titkosított üzenettér: C • Kulcs tér: K, K’ • Kulcsgeneráló algoritmus: • Titkosító algoritmus: • Visszafejt! algoritmus: • Titkosítás és visszafejtés: ! c = E ke (m)
m = Dkd (c)!
G:!"K!K' E :M "K ! C D : C " K# ! M
Dkd (E ke (c)) = m
• Szimmetrikus és aszimmetrikus kulcsú !
kriptorendszerek: !ke " K, kd " K#, !
!
ke = kd ill. ke $ kd 2
Kriptorendszerek (folyt.) Nyílt szöveg
Nyílt szöveg
Titkosított szöveg Titkosítás
Visszafejtés
kd
ke Kulcsgenerálás
3
Elvárások, tulajdonságok
• E,D algoritmusok nem tartalmaznak titkos részeket • E egyenletesen teríti szét az üzeneteket a titkosított üzenettérben (esetleg véletlen elosztással) lim ! F n R = $ n "#
n
• A megfelel! kulccsal E, D hatékonyan üzemeltethet! ! nehézségét a kulcs mérete • A visszafejtés
(s) határozza meg, ideje p(s)-nél rosszabb 4
Helyettesítéses titkosítás
!
E k (m) Helyettesít! függvény
":M !C
Dk (c) Fordított helyettesít! függvény
" #1 : C ! M
!
Például:
!
M=C="26
!
Kulcstér mérete 26!=4*1026
A=0, B=1,...Z=25
!
E k (m)
" 0 1 2 ... 25% $ ' #21 12 25 ... 6 &
Dk (c)
" 0 1 2 ... 25% $ ' 2& #24 21 15
!
Gyenge titkosítás: term. nyelvek frekvencia analízésével megfejthet! 5
!
!
Eltolásos titkosítás K = M =C N :=# M $ E k (m) " m + k (mod N) % & Dk (c) " c # k (mod N) Caesar titkosítás: k=3 Ha lnko(k,N)=1, akkor minden m
!
$ E k (m) " k1m + k 2 (mod N) % #1 & Dk (c) " k1 (c - k 2 ) (mod N)
$ E k (m) " km (mod N) % #1 & Dk (c) " k c (mod N)
6
!
!
Polialfabetikus titkosítás
• A nyílt szöveg elemek több titkosított üzenettér elemre képz!dnek le
• Vigenère titkosítás • m hosszúságú kulcs • nyílt szöveg felosztása m hosszúságú blokkokra • eltolásos titkosítás blokkonként (eltolások a kulcs alapján)
7
Vernam titkosítás m = b1b2 ...bn " {0,1}
n
k = k1k 2 ...k n "U {0,1}
n
c i = bi # k i Helyettesítéses titkosítás speciális esete
*
M = C = K = {0,1}
! Egyszer használt kulccsal információ-elméletileg er!s titkosítás. !
8
Transzpozíciós titkosítás
• Permutációs titkosítás • üzenet elemeinek átrendezése " = (" (1), " (2),..." (b)) • kulcs: ) = (x , x • titkosás: "e (x(" ,(i))x ,...x = i,i = 1,2,...b • visszafejtés: "
1
2
b
" (1)
" (2)
,...x " (b ) )
#1
! !
d" (y1, y 2 ,...y b ) = (y " #1 (1), y " #1 (2),...y " #1 (b ) )
!
9
A Feistel architektúra • Üzenet blokkok • Kulcs (adott mérettel) • Számítási menetek (rögzített szám) • alkulcsok • gyorsan elvégezhet! m"veletek
Blokk Kulcs
M!velet
M!velet
...
M!velet
Titkosított blokk
10
A DES • Data Encryption Standard - United States’ National Bureau of Standards 1977 • Blokk titkosítás M = C = {0,1} K = {0,1} • 3 lépéses m"ködés permutáció • kezdeti (L ,R !) " IP(InputBlock) ! (i = 1,2,...16) • 16 menet L "R 56
64
0
!
i
0
ki menet kulcs 48 bit f: S-box
i#1
Ri " Li#1 $ f (Ri#1,k i )
• végs! ! permutáció
OutputBlock " IP #1 (R16 ,L16 )
!
11
!
A DES (folyt.) Kezdeti permutáció
Round 1
Round 2
…
56-bit kulcs
Round 16
Vég permutáció
12
A DES egy lépése
13
A DES biztonsága • Az S-box nem-lineáris m"ködése fontos, a di#erenciális kriptoanalízis megel!zésére Rövid kulcshossz brute force támadás Deep Crack 1998 56 óra Triple DES séma
• • • •
Nyílt szöveg
DES titkosítás
Kulcs 1
DES visszafejtés
Kulcs 2
DES titkosítás
Kulcs 3
Titkos szöveg
14
Az AES • Advanced Encription Standard - NIST 2000 • Rijndael algoritmus • Változtatható blokk és kulcsméret (128,192,256 bit)
15
A Rijndael titkosítás • 128 bites blokkok InputBlock = m0 m1 ...m15 InputKey = k 0 k1 ...k15
• 10 menet !
" m0 $ m InputBlock = $ 1 $ m2 $ # m3
m4 m5 m6 m7
m8 m9 m10 m11
m12 % ' m13 ' m14 ' ' m15 &
Round(State,RoundKey){ ! SubBytes(State); ShiftRows(State); MixColumns(State); AddRoundKey(State,RoundKey); }
• Invertálható transzformáció a visszafejtéshez
16
A Rijndael titkosítás (folyt.)
• Bels! függvények véges test felett m"ködnek RijndaelField(2 ) • SubBytes x " (F ) y = Ax + b • ShiftRows • transzpozíció ! • MixColumns ! • 4 oszlopra polialfabetikus helyettesítés • AddRoundKey • bitenkénti XOR a kulccsal • key schedule séma szerint 8
*
28
"1
17
Rijndael jellemz!k • Gyors implementáció lehet!sége • véges test feletti m"veletekhez logaritmus lookup táblázatok • timing analízis kizárása • Származtatott jól használható hash függvények
18
Blokk titkosítások biztonságának javítása
• Elektronikus kódkönyv mód (ECB) • üzenet szegmensek egymástól független kódolása • Kódblokk láncolás mód (CBC) • blokk kódolása függ az el!z! blokkoktól • Titkosított blokk visszacsatolás (CFB) • el!z! titkosított blokk visszacsatolása • Kimenet visszacsatolás (OFB) • blokk titkosítás kimenetének visszacsatolása
19
CBC C0 " IV Ci " E(Pi # Ci$1 )
!
IV
P1
P2
P3
+
+
+
E
E
E
C1
C2
C3
20
CFB I1 " IV
Shift left
Ii " LSBn#s (Ii#1 ) Ci#1 Oi " E(Ii ) Ci " Pi $ MSBs (Oi )
/n E
/s
/n Select MSBs
!
/s C
/s
+
/s
P
21
OFB I1 " IV Ii " Oi#1 Oi " E(Ii ) Ci " Pi $ Oi
Shift left
/n
/n
E
/n
! P
/n
+
/n
C
22
Kulcscsatornák
• Hagyományos technikák • Nyílvános kulcsú technikák
23
