Best of Criptography Slides

Best of Criptography Slides

Adatbiztonság és Kriptográfia PPKE-ITK 2008. Top szlájdok egy helyen ☺ 1

Szimmetrikus kulcsú rejtjelezés Általában a rejtjelező kulcs és a dekódoló kulcs megegyezik, de nem feltétlenül. Általában: eből d, illetve d-ből e meghatározása "könnyű" PÉLDA: A: {A, Á, B, C,..., Z} M, C: 5 hosszúságú karakterlánc e: egy permutációja A-nak lehet d=e, vagy eltérő, de elég e-t kiosztani a kiosztás a legnagyobb probléma

2

Nyilvános kulcsú titkosítás Titkosítás: c=Ee(m) e: titkosító kulcs ennek, illetve az Ee titkosító leképezésnek ismerete alapján c-ből m "nehezen" meghatározható Trapdoor one-way függvény Trapdoor információ: d megfejtő kulcs m=Dd (c)

3

Nyilvános kulcsú titkosítás

4

Nyilvános kulcsú digitális aláírás Reverzibilis nyilvános kulcsú eljárás: nemcsak Dd(Ee(m))=m minden m-re hanem Ee(Dd(m))=m is ahol (e, d) a nyilvános kulcsú titkosítás kulcspárja Aláírás: s=Dd(m) Ellenőrzés: érvényes, ha Ee(s)=m

Feltételek: • s a.cs.a. érvényes, ha Ee(s)=m • "existential forgery" nehéz "existential forgery" TTP hitelesen ismeri e-t, mint "A" saját kulcsát -> "message recovery" • d csak "A" számára hozzáférhető -> M' részhalmaza M- •

nek

5

Szimmetrikus vagy nyilvános? Nyilvános kulcsú: Szimmetrikus kulcsú: • csak a magán kulcs titkos • nagy sebesség (on-the-fly) • hosszú kulcs élettartam • rövid kulcsok (kimerítő keresés) • hatékony digitális aláírás • konstrukciós lehetőségek • kevesebb kulcspár • hosszú (?) múlt de: de: • nyilvános kulcs hitelessége • kulcs titkos mindkét félnél • lassú • sok kulcs kell (páronként) • nagy kulcsméret (faktorizáció) • rendszeres kulcscsere • számelméleti alap megdőlhet (mindig?) • rövid(?) múlt alkalmazás: • titkosítás • integritásvédelem

alkalmazás: • kulcsmenedzsment • letagadhatatlanság

6

Lenyomatoló függvény Definíció: tetszőleges hosszúságú bitsorozatot fix hosszúságú bitsorozatra képez

Típusai: • modification detection codes (MDC): kulcs nélkül • message authentication code (MAC): kulccsal

Kriptográfiai használathoz: • "nehéz" két, egyforma eredményt adó inputot találni • "nehéz" adott eredményhez inputot találni Alkalmazás: • digitális aláírás • integritás védelme • jelszó védelme

7

VélGenFunkMod

8

Backtracking, prediction Backtracking resistance:

Prediction resistance:

Ismertté vált állapot alapján • a korábbi állapotok nem állíthatók elő • korábbi output nem különböztethető meg a véletlentől

Ismertté vált állapot alapján • későbbi állapotok nem állíthatók elő • későbbi output nem különböztethető meg a véletlentől

Ez mindig elvárható.

Ez nem várható el mindig. Ha szükséges, akkor reseeding kell minden alkalommal.

9

BlumBlumShub generátor

10

AdFolyRjz – Osztályozás szinkron álvéletlen bitsorozat a nyílt (rejtjelezett) szövegtől független

önszinkronizáló álvéletlen bitsorozat a rejtjelezett üzenet bitjeiből

• szinkronizálja magát leggyakrabban: h = XOR • szinkronizálni kell (törlés: reinicializáció, markerek, offszetek) • nincs hibaterjedés (módosul) • aktív támadás (elvesz: kiesik a szinkronból, módosít: nem)

• korlátozott hibaterjedés (törlés és módosulás) • aktív támadás

11

Linear Feedback Shift Registers

visszacsatolási (karakterisztikus) polinom:

12

LFSR adatfolyam rejtjelezők

13

BlokkRjz. – Működési módok / ECB ECB: Electronic Codebook jellemzők: • azonos nyílt szöveg -> azonos rejtjelezett szöveg • átrendezhető • hiba esetén csak egy blokk hibás korlátozásokkal alkalmazható véletlen "padding" segít

14

Működési módok / CBC CBC: Cipher-block Chaining jellemzők: • azonos nyílt szöveg -> eltérő rejtjelezett szöveg véletlen IV-vel • dekódoláshoz kell az előző rejtjelszöveg • hiba esetén csak két dekódolt blokk hibás IV lehet nyílt, de integritása szükséges (1. blokk biztonságos dekódolása miatt)

15

Működési módok / CFB CFB: Cipher Feedback jellemzők: • azonos nyílt szöveg -> eltérő rejtjelezett szöveg véletlen IV-vel • dekódoláshoz kell az előző néhány rejtjelszöveg • hiba esetén csak néhány dekódolt blokk hibás • alacsonyabb hatásfok r
IV lehet nyílt

Működési módok / OFB OFB: Output Feedback jellemzők: • azonos nyílt szöveg -> eltérő rejtjelezett szöveg véletlen IV-vel • dekódoláshoz kell az előző néhány rejtjelszöveg • hiba esetén csak egy dekódolt blokk hibás IV lehet nyílt, de változtatni kell a kulcs újbóli használatakor Visszacsatolás helyett lehet egy számláló is (CTR mode)

17

DES

Feistel rejtjelező: iterált rejtjelező, mely azáltal lesz invertálható, hogy minden lépésben tetszőleges f-re:

Feistel rejtjelező blokkméret: n=64 kulcsméret: k=64 bit, de a tényleges méret: 56 bit 8 paritás bit miatt 16 iteratív lépés

18

DVB – Conditional Access

19

DVB – Common Scrambling Algorithm

20

DVB – Common Scrambling Algorithm

21

GSM – Authentication and Encryption Scheme Mobile Station

Radio Link

GSM Operator

Challenge RAND

SIM Ki

A3

A3 Signed response (SRES)

SRES A8 Kc

Fn mi

A5

Ki

Authentication: are SRES values equal? Encrypted Data

SRES A8 Kc A5

Fn mi

22

Logical A5 Implementation BTS

Mobile Station Fn (22 bit)

Kc (64 bit)

Fn (22 bit)

A5

Kc (64 bit)

A5 114 bit

Data (114 bit)

114 bit

Ciphertext (114 bit) XOR

Data (114 bit) XOR

Real A5 output is 228 bit for both directions 23

A5/1 : Operation

24

A5/1 : Operation

25

Advanced Encryption Standard Minimum feltételek: nyilvános, licensz mentes, szimmetrikus kulcsú, blokk kódoló, blokk méret: 128 bit, kulcs méret: 128/192/256 bit Értékelési szempontok: biztonság, SW/HW számítási hatékonyság, memóriaszükséglet, rugalmasság (blokk és kulcsméret, számítási platform, konstrukciók: PRNG stb.), egyszerűség 128 bites blokk: 16 byte 4x4-es tömbbe rendezve:

a byte-okat polinomként kezeli: összeadás, szorzás: GF(28)-ben AES-ben használt modulus:

26

Advanced Encryption Standard 4 byte-ból word képezhető: az együtthatók GF(28) -beliek összeadás: szorzás modulo (x4+1): mátrix alakban:

27

Advanced Encryption Standard helyettesítés (SubBytes): inverz GF(28)-ban, majd leképezés:

28

Advanced Encryption Standard sor eltolás (ShiftRows):

29

Advanced Encryption Standard oszlop keverés (MixColumns): az oszlop polinom szorzása

30

Advanced Encryption Standard kulcs hozzáadás (AddRoundKey):

Nb(Nr+1) 4 byte-os kulcsot képez az Nk x 4 byte-os kulcsból kulcs kiterjesztés (Key Expansion):

31

Nyilv.K.Rjz. – New directions in Cryptography

32

33

34

A method for Obtaining Digital Signatures and Public-Key Cryptosystems

35

A method for Obtaining Digital Signatures and Public-Key Cryptosystems

36

A method for Obtaining Digital Signatures and Public-Key Cryptosystems

37

Elliptikus görbék Az ECC sokkal kisebb kulcsmérettel is biztonságos: • gyorsabb algoritmusok • kevesebb továbbítandó és kezelendő adat • kisebb tárigény • kisebb tanúsítványok.

Elliptikus görbe: y2= f(x) alakú egyenlettel definiált síkbeli görbe, ahol Használatuk a nyilvános kulcsú eljárásokon kívül: f(x) egy x3+ax+ b alakú kifejezés • prímtényezőkre bontás x, y valós változók (egyelőre) • prímteszt a, b egész számok (egyelőre) a görbe nemszinguláris Általános képlet: y2 + a1xy + a2y = x3 + a3x2 + a4x + a5 38 Izomorfizmus erejéig visszavezethető az előbbire.

Műveletek

A görbe pontjain műveletet értelmezünk.

Az ideális pontról feltételezzük, hogy rajta van minden függőleges (az y-tengellyel párhuzamos) egyenesen és hogy az xtengelyre vonatkozó tükörképe önmaga. A görbe P és Q pontjainak P + Q összege: a P, Q pontokon átmenő egyenes és a görbe harmadik metszéspontja -R; ennek az xtengelyre való R tükörképe (ami szintén pontja a görbének) a P + Q összeg. R + -R =? az ideális pont (O)

39

Műveletek

Ha P = Q, akkor az összekötő egyenesükön a görbe P-beli érintőjét kell érteni.

Ha -R megegyezik a P, Q pontok valamelyikével, ekkor az egyenes -Rben érinti a görbét.

O+O=O P+O=P 2*E = E + E = O 3*E = E + E + E = E 4*E = E + E + E + E = O Csoport: Van egységelem: O Van inverz: tükörkép Asszociatív: (A + B) + C = A + (B + C)

(nem bizonyítjuk)

40

Algebrai formula az összegre Ha P: (xP, yP) Q: (xQ, yQ) R: (xR, yR) R = P + Q esetén: xR = m2 - xP - xQ yR = m*(xP - xR) - yP ahol: m = (xP - xQ) / (yP - yQ) az átmenő egyenes meredeksége

Ha yP <> 0

(az érintő nem függőleges) :

R = 2*P: (xR, yR) xR = m2 - 2*xP yR = m*(xP - xR) - yP ahol: m = (3*xP2 + a) / (2*yP) 41

Elliptikus görbék mod p – A "görbe" alakja x, y mod p egészek a, b mod p egészek ahol p: prím Legyen p = 11, a = 1, b = 0 y2 ≡ x3 + x mod 11 11 pont (nem mindig p-vel egyenlő!) az x = y = 0 kivételével szimmetrikus (minden x-hez 2 y érték)

Műveletek: P: (xP, yP) Q: (xQ, yQ) R: (xR, yR) R = P + Q esetén:

xR ≡ m2 - xP - xQ mod p yR ≡ m*(xP - xR) - yP mod p ahol: m ≡ (xP - xQ) * (yP - yQ)-1 mod p

-P: (xP, -yP mod p) R = 2*P : (xR, yR) xR ≡ m2 - 2*xP mod p yR ≡ m*(xP - xR) - yP mod p P: (xP, yP)

42

ahol: m ≡ (3*xP2 + a) * (2*yP)-1 mod p