ET1206/Lectures

From FUKTwiki

[edit] 2007-11-05

[edit] 3.1 Kryptering

ke = hemlig nyckel
m = meddelande
c = krypterad text
m → (ke,m) → c
c = E (ke,m) ⇒ c send
E = krypterings funktioner (algoritmer)
Rx ← In = c
m = D (ke, c)
D = dekrypterings funktion
resultat m.

Exempel: "sjörövarspråket" m = Ronneby ke = o krypteringsfunktionen = E = ett ke skall införas efter varje konsonant och konsonanten före varje ke skall repeteras efter varje ke.

c = rorononnoneboby

skicka c

dekrypteringsfunktin = D = för varje hittat ke, kolla om det är en konsonant före och efter varje ke. om de är lika, tag bort första + ke

resultat = m = D("o", "roronnoneboby") = Ronneby

[edit] Kerckhoffs' principle

There is an article about this subject on Wikipedia, the free online encyclopedia.

The security of the encryption scheme depends on the secrecy of ke, not on how public the information of how E or D works.

Fortfarande möjligt

att byta hela meddelandet
ta bort meddelandet
ändra ordningen

[edit] 3.2 Autentisering, verifiering

ka = Authentication key
Tx ← m = medelande
a = MAC = message authentication code
a = MAC = h(ka,m)

Send: a,m

Rx ← In a,m

beräkna a

a = h(ka,m)

Resultat: Mottagit a och beräknat a.

[edit] 3.3 Public key encryption (publika nycklar)

Problem: Hur ska vi dela med oss nycklarna på ett säkert sätt?

2-persons	byt nycklar, snigelpost
3	3 byten
4	6 byten
1000	$\frac{1000\times (1000-1)}{2} = 499500$ byten

Lösning: använd publika nycklar

Bob generates 2 nycklar
Hemlig nyckel $k s b o b$
Publik nyckel $k p b o b$

$k p b o b$ publiceras av Bob

Alice ska skicka till meddelande till Bob.

Hämta publika nyckeln $k p b o b$
Kryptera meddelandet $C = E (k p b o b, m)$

Bob får meddelandet

Använder sin hemliga nyckel $k s b o b$
Dekryptera meddelandet $m = D (k s b o b, c)$

$k_{pbob} \neq k_{sbob}$
$k p b o b$ kan inte i praktiken räknas fram från $k p b o b$
Enklare för större grupper att kommunicera säkert

[edit] 3.4 Digitala signaturer

Alice genererar två nycklar. $k p a l i c e$ $k s a l i c e$

Alice genererar sedan en signatur.

Genom att använda hemliga nyckeln $k s a l i c e$

$S = σ(k s a l i c e, m)$

Alice skickar S, m (och sin publika nyckel $k p a l i c e)$ )

Bob tar emot S, m

Använder publika nyckeln $k p a l i c e$
Verifierar signaturen $S = v (k p a l i c e, m)$
Jämför beräknad signatur med mottagen

[edit] 2007-11-06

kryptering, hemlig nyckel

$k e$ $C = E (k e, m)$

$\frac{1000\times 999}{2}$

$\frac{M \times M-1}{2}$

[edit] Publika nycklar

$k p b o b, k s b o b$

$C = E (k p b o b, m)$

$m = D (k s b o b, c)$

[edit] 3.5 PKI, Public Key Infrastructure

Problem: hur vet vi att $k p b o b$ verkligen tillhör Bob?

Lösning: CA = Certified[sic] Authority

CA använder en digital signatur för att säkerställa att verkligen $k p b o b$ tillhör Bob.

Certifikat

[edit] 3.6 Attacker

[edit] 1 Ciphertext only

Attackera den krypterade texten

[edit] 2 Known plain text

Attackera och försök komma åt nyckeln

Exempel: Du kommer åt både c, m
någon skickar ett mail där du är en av mottagarna.

[edit] 3 Chosen plain text

Attackera och försök få nyckeln.

Exempel: Jag skickar meddelande till Alice som forwardar krypterat.

[edit] 4 Chosen Ciphertext

?

[edit] Collision attacks

Birthday attack

23 personer $P (två har samma födelsedag) > 0,5$

$22+21+30+\ldots+3+2+1=253$

365 dagar på ett år ⇒ $\frac{253}{365} \approx 0,7 > 0,5$

Attacker som grundar sig på att kopior på nycklar och meddelande uppkommer fortare än man tror.

[edit] 4 Blockkryptering

Block cipher: krypteringsfunktion för en fix blockstorlek, t.ex. 128 bitar.

Blockstorlek av originaltext och krypterad text lika stora.
Storleken av nyckeln är oftast 128 eller 256 bitar

$C = E (K, p)$
$P = D (K, c)$
$E (K, p) = E k (p)$ krypteringsfunktion publik

If $P > 128$ , use block cipher mode (kapitel 5).

$E k (p)$

P	c
00	11
01	00
10	01
11	10

$D k (c)$

c	p
00	01
01	10
10	11
11	00

En tabell för varje nyckel

$Block length = 2 (block size) = 2 2 = 4rows$

Verkligheten: $\mbox{Block length} = 2^{128} \approx 3.4 \times 10^{38}$

Attacker: för att få bra resultat använd chosen plain text

$E k (p)$

P	$c 1$	$c 2$
00	11	00
01	00	11
10	01	01
11	10	10

[edit] 4.3 The Ideal block cipher

För varje ny nyckel: slumpmässig look-up-tabell

[edit] 4.5 Real block ciphers

Hitta ej på er egen algoritm

Egenskaper:

Använd XOR för att addera på nyckeln
Använd S-box för att lägga till non-linearity
Vänd och vrid på bitarna för att skapa oordning (mål: En liten ändring i klartexten ska göra stor ändring i kryptotexten)
Kör algoritmen flera "rounds"

[edit] DES

Data Encryption Standard (1970-talet)

(Gammal, obsolete)

Nyckelstorlek = 56 bitar

Blockstorlek = 64 bitar

64 bitar, 32L och 32H.

Runda 0:

$L 0 = 32 L$
$R 0 = 32 R$

Runda 1:

$R_1 = L_0 \oplus F(k, R_0) = L_1$
$L 1 = R 0$

Funktion F

Expandera R från 32 → 48 bitar
XOR med nyckeln $k i$ som är 48 bitar och olika för varje rounds.
The S-box: 8 st $8\times 6 \to \mbox{lookup table} \to 8 \times 4$
Blanda de 32 bitarna
Klart för en runda till

Denna struktur kallas Feistel construction

Nycklar så väljs $k j$ (48 bitar) ut på ett speciellt sätt från originalnyckeln på 56 bitar.

[edit] 2007-11-07

[edit] 4

Blockstorlek 128 in ⇒ 128 bitar ut

00	01
01	11
10	00
11	10

$2128$

DES (Data encryption Standard)

key 56

Blocks = 64

3DES

key 128

Nackdelar:

Fortfarande blockstorlek 64
Långsam
Vad händer om $k = 0$ (alla bitar 0)?

Fördel:

Använder samma hårdvara för kryptering som dekryptering

$1 \oplus 0 =$

[edit] AES

NIST (National Institute of Standards and Technology)

AES (Advanced Encryption Standard)

krav:

Blockstorlek 128 bitar
Nyckelstorlek: 128, 192 eller 256

15 förslag ⇒ 5 finalister

2001 ⇒ Rijndael

Rijndael var det möjligt att variera blockstorleken [128], 192, 256

[edit] Lineraritet

$\begin{align} A & \to & [F] & \to & AA \\ B & \to & [F] & \to & BB \\ A+B & \to & [F] & \to & AA+BB \end{align}$

$\begin{align} A & \to & [F] & \to & A^2 & \\ B & \to & [F] & \to & BB & \to \mbox{Detta är EJ LINJÄRT!} \\ A+B & \to & [F] & \to & AA+BB & \end{align}$

[edit] Subbytes

8 bitar → Sbox → 8 bitar

Alla S-boxar är identiska

[edit] Shiftrows

Byter "bytes" i samma rad plats genom att skifta 1-3 positioner beroende på rad

[edit] Mix Columns

Varje kolumn i blocket multipliceras med en förutbestämd matris så att varje "byte" får ett nytt värde.

[edit] Add Round Key

Xor med data och nyckel (permutation av originalnyckeln; olika varje runda).

AES	rounds
128	9
192	12
256	14

[edit] Fördel mot DES

Större nyckel
Större blockstorlek
AES är mindre komplex än 3DES

[edit] Serpent

Alternativ till AES

Säkrare än AES ⇒ mer komplex

[edit] Twofish

Mellanting mellan AES och Serpent

Snabbt att kryptera, långsamt att byta nyckel och i början med ny nyckel

[edit] Attacker

[edit] XSL - equation solving attacks

Exempel: AES 128 blir 8000 ekvationer med 16000 variabler

[edit] Which block cipher should I use?

AES
Standard
Serpent
Mycket säker men långsam
Twofish
Är säker och snabb

[edit] Vilken nyckelstorlek ska jag använda?

Minst betydelse
⋮
128 bitar	Bra nog, men se upp med collision attacks
⋮
256 bitar	AES 256 är mycket långsammare än AES 128
⋮
Mest betydelse

Rule: For a security level of $n$ bits, every cryptographic value should be at least $2 n$ bits long.

[edit] 2007-11-12

[edit] 5 Block Cipher Modes

Det är problem om två krypterade block $C i$ är lika.

$C i = E (K, P i)$

$C k = E (K, P k)$

$C i = C k$ ⇒ $P i = P k$ , vilket blir mycket lättare att knäcka.

[edit] Kollisionsrisk för två $C i$ block

[128 bitar] ↔ [128 bitar]

Sannolikheten att dessa två block är lika är $\frac{1}{2^{128}}$ .

Om vi skickar $M$ block över kanalen, vad är sannolikheten att två av dessa är lika? $\frac{M \times (M-1)}{2} \times \frac{1}{2^{128}}$

meddelandet är längre än 1 block (oftast 128 bitar – 16 ”byte”).

[edit] 5.1 Padding

Bara addera nollor på slutet är ingen bra idé. Det är svårt att veta hur många som ska tas bort vid dekrypteringen.

Vi behöver något padding-schema.

$P = plaintext$

$l (P) = längden av meddelandet$

$b = blockstorleken i ”bytes”$

[edit] Schema

"Meddelande" + bin(128) + bin(0)+ upp till b ”bytes”.

Exempel:

"AB" ⇒ (om b = 4) ⇒ "AB", bin(128), 0

Detta fungerar inte där ”byten” 128 kan förekomma.

[edit] Schema 2

Beräkna hur många padding-”bytes” som behövs för att få ett fullt block. $1 \le n \le b$

Lägg till meddelandet med $n$ ”bytes” av värde bin( $n$ ).

Exempel: ”AB” → ”AB” + bin(2) + bin(2)

[edit] 5.2 ECB – Electronic Code Book

(Ska ej användas.)

$C i = E (K, P i)$ för $i = 1 \ldots k$

Om två $P i$ är lika ⇒ två $P i$ lika.

Inte bra för en attack.

[edit] XOR

Meddelande = p =		0100
Kod	⊕	0101
c =		0001

[edit] 5.3 CBC – Cipher Block Chaining

$C_i = E(k, P_i \oplus C_{i-1})$

Löser problemet med att om två $C i = C k$ ⇒ $P i = P k$

Problem? Hur hittar vi $C 0$ = Initialization Vector, IV?

$C_{n+1} = E(C_n \oplus P_{n+1})$

[edit] 1 Fix IV eller $C 0$

Om flera meddelanden har samma start:

$P 1$ kommer vara samma ⇒ $C 1$ kommer att vara samma.

Inte bra ur en attacksynpunkt.

[edit] 2 Counter IV

$I V = 0$ för första meddelandet, $I V = 1$ för andra, o.s.v.

Om skillnaderna är små i meddelandet är det risk att XOR inte ger så stora skillnader.

[edit] 3 Random IV

Slumpmässig $C 0$ , mottagaren måste också veta samma $C 0$ .

$C 0 = random block value$

$C_i = E(K, P_i \oplus C_{i-1})$ $i = 1 \ldots k$

Dekryptering:

$P_i = D(k, C_i) \oplus C_{i-1}$ $i = 1 \ldots k$

$P_1 \oplus C_0 \oplus C_0 = P_1$

Nackdel:

Slumpgenerator behövs
Vår krypterade text förlängs med ett block

[edit] 2007-11-13

[edit] CBC – Cipher Block Chaining (forts.)

[edit] Nonce generated IV

Number used only once

Så att $C 0$ får bara användas en gång med varje nyckel $K$ .

(Varje meddelande har oftast redan ett löpnummer.)

Konstruera ett nonce (128 bitar)
Kryptera $E (k, n o n c e) = C 0$
Kryptera hela meddelandet genom att använda CBC
Dekryptera meddelandet och kontrollera nonce

Exempel:

p = "HEJ"

blockstorlek två ”bytes”

CBC

$C 0$ = random = 0000111100001111

$k = 0101010101010101$

$E(k, P_1 \oplus C_{i-1}) = (0101010101010101) \oplus (P_i \oplus C_{i-1})$

$P 1$ = (ASCII(H) = 72, ASCII(E) = 69)

$P 2$ = (ASCII(J) = 74, padding)

ASCII	Dec	Bin
H	72	01001000
E	69	01000101
J	74	01001010

Padding = 128

$P 1 = 0100100001000101$

$P 2 = 0100101010000000$

$C_1 = E(k, P_1 \oplus C_0)$ $= E(K, 0100100001000101 \oplus 0000111100001111)$ $= E (K,0100011101001010)$ $= 0101010101010101 \oplus 0100011101001010$ $= 0001001000011111$

$C_2 = E(k, P_2, \oplus C_1)$ $= E(K, 0100101010000000 \oplus 0001001000011111)$ $= E (K,0101100010011111)$ $= 0101010101010101 \oplus 0101100010011111$ $= 0000110111001010$

Dekryptering:

$P_1 = D(k, C_0 \oplus C_1)$ $= D(k, 0000111100001111 \oplus 0001001000011111)$ $= D (k,0001110100010000)$ $= 0101010101010101 \oplus 0001110100010000$ $= 0100100001000101$

$P_2 = D(k, C_1 \oplus C_2)$ $= D(k, 0001001000011111 \oplus 0000110111001010)$ $= D (k,0001111111010101)$ $= 0101010101010101 \oplus 0001111111010101$ $= 0100101010000000$

[edit] Stream Ciphers

Vi använder inte blockkrypteringen på meddelandet $P 1$ , utan vi använder blockkrypteringen för att skapa en pseudorandom sekvens av bitar som vi sedan kör XOR på meddelandet

[edit] OFB – Output Feedback Mode

$K 0 = I V$

IV skapas enligt ovan

$k i = E (K, k i - 1)$ för $i = 1 \ldots M$

$C_i = P_i \oplus k_i$

IV genereras och skickas.

Fördelar: kryptering samma som dekryptering

$P = C \oplus k = (P \oplus k) \oplus k = P \oplus 0 = P$

Behöver ingen padding. ”Bra för små meddelanden”, står det i boken.

Nackdel: Om man använder samma IV ( $K 0$ ) så kommer två meddelanden att kodas med samma ström.

Två meddelanden $p$ och $p'$ kodas med samma ström $k i$ ⇒ två krypton $C$ och $C'$

Attackeraren gör följande:

$C_i \oplus C'_i = (P_i \oplus k_i) \oplus (P'_i \oplus k_i) = P_i \oplus P'_i$

[edit] CTR – Counter Mode

$k_i = E(k, Nonce\|i)$ för $i = 1 \ldots M$

$C_i = P_i \oplus k_i$

Där Nonce är unik för varje meddelande

$i$ är blocknummer i meddelandet

Typiskt:

48 bitar	meddelandenummer
16 bitar	nonce
64 bitar	för räknaren $i$

[edit] 2007-11-14

[edit] CTR – Counter Mode (forts.)

$k_i = E(k, Nonce \| i)$

$C_i = P_i \oplus k_i$

[edit] OFB

$K 0 = I V$

$K i = E (K, k i - 1)$

[edit] Exempel

$E(k, Nonce \| i) = (K + nonce + i \times 5) mod 11$

Blockstorlek 8 bitar, $K = 3$ , $n o n c e = 7$ , $i = 0$

i		$k i$	$k i$ binärt
i=0	$3+7+5\times 0 = 10$	10	00001010
i=1	$3+7+5\times 1 = 15$	4	00000100
i=2	$3+7+5\times 2 = 20$	9	00001001

P = "HEJ" = ASCII(H), ASCII(E), ASCII(J) = 0x48, 0x45, 0x4A

$P 0 = 01001000$

$P 1 = 01000101$

$P 2 = 01001010$

$C_0 = P_0 \oplus k_0 = 01000010$

$C 1 = 01000001$

$C 2 = 01000011$

Vi ska använda CBC eller CTR

	CBC	CTR
Padding	Ja	nej
Hastighet	Snabb	Snabbare, ty parallel processing
Implementering	både E och D	bara E
Robust	läcker information om första blocket	läcka information om hela meddelandet
Nonce	Behövs, ev. random	Behövs

[edit] 5.8 Läckor

ECB (Electronic Code Book): Om $P_i \Rightarrow C_i = C_j$
CBC (Cipher Block Chaining): Om $C_i = C_j \Rightarrow C_{i-1} \oplus C{j-1} \Rightarrow P_i \oplus P_j$ $C_i = E(K, P_i, \oplus C_{i-1})$

$C i = C j$

$E(K, P_i \oplus C_{i-1})$ $= E(K, P_j \oplus C_{j-1})$

$P_i \oplus C_{i-1} = P_j \oplus C_{j-1}$ ...

CTR: Om $P i = P j$ blir inte $C i = C j$

Däremot så om $C_i \neq C_j$ så är $P_i \neq P_j$ ⇒ väldigt lite information som läcks.

[edit] Risk för kollision

M block skickas, varje block har längden n bitar.

$\frac{M\times(M-1)}{2} \times \frac{1}{2^n} = \frac{M^2}{2^{n+1}}$

Detta $\approx 1$ om $M = 2 n / 2$ . Om $n = 128$ så får vi kollision om $M = 2 64$

[edit] 6 Hashfunktioner (kryptografiska hash functions)

Används för authentication (verifiering) digitala signaturer

Godtycklig mängd → hash → begränsad mängd, t.ex. 512 bitar

Istället för att signera $m$ direkt så signerar man $m' = h (m)$ där $h$ är hashfunktionen.

[edit] 6.1 Säkerhet med hashfunktioner

En-vägs funktion, inte möjligt att skapa $m$ från $m'$
Kollision: $m_i, m_j \Rightarrow h(m_i) = h(m_j)$

Kollisionsresistenta funktioner = Även om kollisioner finns så inträffar de aldrig.

Ideal hashfunktion = slumpmässig mappning från alla möjliga insignaler till en begränsad mängd utsignaler.

hashfunktioner ⇒ ingen nyckel behövs

[edit] Praktiska hashfunktioner

Iterativa hashfunktioner som MD5 och SHA-familjen.

Dela upp meddelandet i block, $k$ stycken (plus ev. padding).
Varje block processas för sig

Start: $H 0$

$H i = h'(H i - 1, m i)$ där $m$ = meddelandeblock $i$ och $H k$ är slutgiltiga resultatet.

[edit] Fördelar med iterativa hashfunktioner

Enklare att implementera
Kan börja köra innan hela $m$ mottagits

[edit] MD5

128 bitars output
Meddelandet delas upp i block om 512 bitar
Sista blocket innehåller meddelandets längd och padding

$h'$ rekursiv den körs 4 rundor där varje runda innehåller additioner, booleansk algebra och blandning (permutering)

Nackdel: $h'$ har kollisioner ⇒ $H$ har kollisioner.

[edit] SHA-1

160 bitars output
2-3 gånger långsammare än MD5
Blockstorleken är 128 bitar

SHA-256, SHA-384, SHA-512: Storleken på output för dessa varianter är 256, 384 respektive 512.

[edit] 2007-11-19

[edit] 6 Hashfunktioner

"Hash" = hacka sönder, röra om

$m : h (m) = H$

[edit] Iterativa hashfunktioner

Kan pipe-line:as.

$m$ delas upp i block om $n$ bitar, t.ex. 512.

$H 0$

$H i = h'(H i - 1, m i)$

$H = H k$ där

[edit] 6.3 Svagheter hos hashfunktioner

[edit] Length extensions

Första meddelandet $m$ innehåller $k$ block (och ev. delblock).

Andra meddelandet $m'$ innehåller $k + 1$ block och de första $k$ blocken är lika som i meddelande $m$ .

$m$
A	B	C
$m'$
A	B	C	p

Första meddelandet: $H = h (m)$

Andra meddelandet: $H$ för de första $k$ blocken $= h (m)$ , $H$ för alla block $h(m') = h'\Big(h(m), m_{k+1}\Big)$

MAC

$m_k \| k$

[edit] 6.3.2 Partial message collision

Meddelande m

Verifiering av meddelandet (MAC) $h(m \| k)$

$k$ = nyckel

Attacker

Brute force to find $k$

Om en iterativ hashfunktion används för att räkna ut H då kan vi göra en bättre attack.

Leta efter två meddelande $m$ och $m'$ som ger en "kollision", d.v.s. som har samma $H$ .

$2 n / 2$ försök behövs, vilket är mycket enklare är att finna $k$ .

[edit] Fix av svagheterna

kör hashfunktionen två gånger

$m \to H = h(m)$

$m \to H = h\Big(h(m) \| m\Big)$

Löser svagheterna

Långsamt
Behöver buffra hela meddelandet

En bättre fix

Bibehålla hastigheten (tidskomplexiteten)

$H = h (m)$

$H = h\Big(h(m)\Big)$ vi använder bara $n / 2$ bitar för att bibehålla hastigheten.

kallas $h d$ t.ex. SHA_d-256.

[edit] 7 Message Authentication Codes (MAC)

Kryptering hindrar Eva från att läsa meddelande, men inte att manipulera dem.

Authenticering hindrar att Eva kan manipulera med meddelanden, men inte att läsa dem.

Alice

$a = M A C (k, m)$

$a, m$ skickas

Bob

$a' = M A C (k, m)$ jämför $a$ och $a'$ .

[edit] 7.4 CBC-MAC

Kombinera Block cipher mode och MAC.

Kryptera meddelandet $m$ genom att använda CBC
Kasta bort alla krypterade block $C i$ utom det sista $C k = a$

Meddelande $p = p_1 \ldots p_k$

$H 0 = I V$

$H_i = E(k, p_i \oplus H_{i-1})$

$a = M A C = H k$

$I V$ som vanligt $I V = 0$ $I V = r a n d o m$

OBS! Använd inte samma nyckel vid kryptering och verifiering.

Säkerhet på 128 bitar använder CBC-MAC om 256 bitar.

[edit] 7.5 HMAC (Hash MAC)

Ej ideal hashfunktion ⇒ Hashsäkerhet = $n / 2$ bitar

”Bra” MAC: $h(k \| m)$ om $h$ är bra.

$\mbox{MAC}(K, m) = \operatorname{SHA-256}\Big(\operatorname{SHA-256}(K \| m)\Big)$

[edit] 7.6 UMAC

Samma som HMAC fast snabbare.

T.ex. UMAC-STD-30, UMAC-MMX-30

Horton principle: Man ska ska authenticera vad som menas, inte vad som sägs.

T.ex. verifiera inte bara på IP-paket-nivå, då vet vi ju inte hur mailprogrammet tolkar data.

[edit] 2007-11-20

[edit] 8 The Secure Channel

$K$ är bara känd av Alice och Bob.
Varje gång man sätter upp en ny kanal genereras ett nytt värde från nyckeln $K$ för att Eva inte ska kunna använda meddelande från äldre sektioner.
Key negotiation protocol

[edit] Trafikanalys

Alice ↔ Bob

Storlek på m
Tidpunkt
Vem skickar meddelande till vem

[edit] 8.2 Ordningen på kryptering och verifiering

[edit] Kryptering först

Kryptering först för sändaren, verifiering först för mottagaren.

”Teoretiska resultat visar att kryptering först är bäst.”
Mer effektivt vid fejkade meddelanden.

[edit] Autentifiering (verifiering) först

MAC krypteras också. Det viktigaste är att skydda MAC.
Authenticate what is being meant (klartexten), not what is being said (krypterade texten).

Recommended: Verifiera först, kryptera sedan.

[edit] 8.3 Hur sätter vi upp en säker kanal?

Meddelandenumreringen – nonce
Verifiering
Kryptering

[edit] 8.3.1 Meddelandenumrering

Källa för att finna IV
Säkerställa att Bob får meddelandena i rätt ordning

Unika
Monotont växande

Använd 32 bitar ⇒ max antal meddelanden $232 - 1$ , därefter byt nyckel.

$m$ är index; meddelandenummer.

[edit] Authentication (verifieringen)

Använd HMAC – SHA-256

Insignal $p m$ meddelande och $x m$ är extra verifieringsdata (protokoll, typ av meddelande).

MAC code = $a m$

$l (.)$ = längden av en sträng i ”bytes”

$a_m = \operatorname{MAC}\Big(m, \| l(x_m) \| x_m \| p_m \Big)$

[edit] Krypteringen

AES (Advanced Encryption Standard) in CTR mode with nonce.

Blockstorlek 128 bitar (16 ”bytes”).

Maxstorlek på varje meddelande $16\times 2^{32}$ bytes ⇒ blockräknare på 32 bitar med index $i$ .

$k_i = E(K, Nonce \| i) = E(k, \underbrace{\mbox{blocknummer}}_{\mbox{32 bitar}} \| \underbrace{\mbox{meddelandenummer}}_{\mbox{32 bitar}} \| \underbrace{0\ldots 0}_{\mbox{64 bitar}})$

$C_i = p_i \oplus k_i$

$k_1 = E\Big(K, (1 \| 1 \| 0)\Big)$

[edit] 2007-11-21

[edit] 10 Generera slumptal

Mättal för slumpmässighet ”entropy”

Exempel: 32 bitars tal ⇒ entropy = 32 bitar

Om 31 bitar + en bit paritet ⇒ entropy = 31 bitar

[edit] 10.1.2 Pseudorandom data (PRNG)

p(x) ↑
     │
     │
   1 ├──┐
     │░░│
     │░░│
     └──┴──→
    0   1  x

Slumptal framräknade med en matematisk algoritm från ett startvärde (seed) är slumpmässiga från en statistisk synvinkel, dock inte från en kryptografisk synvinkel.

[edit] 10.3 Fortuna

Ett riktigt slumptal för att beräkna startvärdet (seed)
Använd startvärdet för att beräkna en riktig pseudorandom sekvens av valfri längd.
Ibland byt startvärde och starta generera igen.

[edit] 10.4 Generatorn ska vara en CTR mode

$k i = E (K, i)$

$E$ ska implementeras av t.ex. AES-algoritmen.

Blockstorlek 256 bitar och räknaren $i$ ska vara 128 bitar.

$\underbrace{\mbox{slumptal}}_{\mbox{1000 stycken}}$

$\underbrace{\mbox{256 bitar}}_{\mbox{Används som ny nyckel K vid nästa anrop}}$

Glöm inte bort att ta bort den gamla nyckeln.

Om vi genererar $2128$ block med slumpdata så är två block lika ⇒ Begränsa antal block till högst $216$ i varje anrop.

[edit] 10.4.1 Initialisering

$K = 0$ $C = counter = 0$

[edit] 10.4.2 Reseed

När en viss tid eller viss mängd data överförts.

$K = new K$

Nytt $K$ kan beräknas med en hash t.ex. SHA-256.

$C = C + 1$

[edit] 10.4.3 Generate Blocks

Genom att använda CTR

$r = E (K, c)$ ( $c$ = counter)

Generera två extra block av $r$ som används som ny nyckel.

[edit] 10.5 Accumulator

Används som insignal till ”reseed”.

Man lägger ihop data från olika källor.

[edit] 10.5.2 Pool

Mängd av händelser som används som input till Ackumulatorn, t.ex. zenerdiodbrus, muspekare.

Viktigt

Lita aldrig på algoritmer i operativsystemet som genererar slumptal.
Använd så många händelser som möjligt för att bygga upp ”original”-slumptalet.

[edit] 2007-11-26

[edit] 11 Primtal

Används för generering av publika nycklar

Delbarhet $a | b$ ⇒ $a$ är en delare till $b$ ⇒ Vi kan dela $b$ med $a$ utan att få en rest.

Exempel: $7 | 35$ Ja, det är en delare

Primtal: $a | 11$

Primtal: Om det bara finns två delare: primtalet själv och 1.

Eratosthenes’ såll

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Stryk 1

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Stryk varannat tal efter två:

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Stryk var tredje tal efter tre:

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Stryk var femte tal efter fem:

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Vi kan sluta vid 5, eftersom det är det största tal vars kvadrat är mindre än det högsta tal som ska undersökas.

Lemma 1: $a | b$ och $b|c \Rightarrow a|c$

Bevis: Om $a | b$ så måste det finnas ett heltal $s$ så att $a \times s = b$ .

Om $b | c$ så måste det finnas ett heltal $t$ så att $b \times t = c$ .

⇒ $C = b \times t = a \times s \times t \Rightarrow a|c$

Lemma 2: Låt $n$ vara ett positivt heltal $> 1$ Låt $d$ vara den minsta delaren till $n > 1$ ; då är $d$ ett primtal.

Teorem: Det finns oändligt många primtal.

OBS! Det finns ingen exakt formel för att räkna ut primtal i ett visst intervall.

Goldbach’s conjecture: Varje jämt heltal $> 2$ är en summa av två primtal.

[edit] 11.3 Moduloräkning med primtal

Exempel: $25mod 7 = 4$

$25/7 = 3,3714\ldots = \frac{21}{7}+\frac{4}{7}$

Att finna $(a mod b)$ hitta heltalen $q$ och $r$ så att $a = q b + r$ $0\leq r < b$ då är $(a mod b) = r$

[edit] Addition och Subtraktion

$(a + b)mod p$ $0 \leq a, b < p$

$(a + b)$ är större än $p$ : då blir resultatet $a + b - p$

Exempel: Om $p = 7$

$5 + 3 - 7 = 1$

[edit] Finita fält

Är ett antal heltal modulo ett primtal. Kallas $(mod p)-fält$ eller bara $(mod p)$

Exempel: Grupp $0,1,2,3,4$ och $p = 5$

Alla resultat kommer att vara i området $a,1\ldots p-1$ oberoende av operation.

$\mathbb{Z}_p =$ finit fält modulo $p$

Grupp: Ett antal heltal samt en operation:

Exempel: $\mathbb{Z}_p$ och addition blir en grupp.

Exempel: En grupp: { 0, 1, 2, 3, 4, 5, 6, 7 } modulo 8

Detta är inte ett finit fält eftersom 8 inte är ett primtal.

En undergrupp { 0, 2, 4, 6 }

$\mathbb{Z}_7$ , multiplikativ grupp

{ 0, 1, 2, 3, 4, 5, 6 }

A subgroup: { 1, 2, 4 }

Exempel: $2 \times 4 = 1 \pmod 7$

$1 \times 2 = 2 \pmod 7$

[edit] GCD (Största gemensamma delare )

GDC av $(a, b)$ alltså det största $k$ som uppfyller $k | a$ och $k | b$

$(a, b) = (21,30)$

$= \left \{ \begin{array}{rcl} b \bmod a & = & a \\ a & = & b \end{array} \right.$

så länge som $a \neq 0$

$30mod 21 = 9$

$(a 1, b 1) = (9,21)$

$21mod 9 = 3$

$(a 2, b 2) = (3,9)$

$9mod 3 = 0$

$(a 3, b 3) = (0,3)$

Exempel:

$(23,35) = (a 0, b 0)$

[edit] 2007-11-27

[edit] 12.1

[edit] Grupper och undergrupper

{ 0, 1, 2, 3, 4, 5, 6, 7 } $(mod 8)$ är en additiv grupp, men ej ett finit fält eftersom 8 ej är ett primtal.

{ 0, 2, 4, 6 } $(mod 8)$ är också en giltig additiv grupp eftersom man bara kan få någon medlem i gruppen när man adderar medlemmar i gruppen.

$\{ 1, 2, 3, 4, 5, 6 \} \pmod 7 = \mathbb{Z}^+_7$

Noll får inte vara med i multiplikativa grupper.

${1,6}$

[edit] Diffie och Hellman

1976

10 användare behöver byta $\frac{10\times(10-1)}{2} = 45$ nycklar.

Diffie och Hellman ⇒ Kryptering ≠ Dekryptering

$p$ ska vara ett stortprimtal någonstans i området 2000-4000 bitar.

Finit grupp $\mathbb{Z}^\times_p = 1, \ldots, p-1$ tillsammans med multiplikation modulo $p$ .

Skapa en serie: $1, g, g^2, g^3, \ldots \pmod p$

$g$ ska vara ett element i gruppen.

Det är en oändlig serie men en finit grupp.

Exempel: $\mathbb{Z}^\times_7 = \{ 1, 2, 3, 4, 5, 6 \}$

$g = 2$

Serien: $\{ 2^0, 2^1, 2^2, 2^3, 2^4, \ldots, 2^\infty \} \pmod 7 = \{ 1, 2, 4, 8, 16, \ldots \} \pmod 7 = \{ 1, 2, 4, 1, 2, 4, \ldots \}$

Antag att värdena börjar repeteras vid $g i = g j$

$i < j$

Dividera båda sidor med $g i$ ⇒ $1 = g i - j$ Vi kan finna ett värde $q = j - i$ som ger $g q mod p = 1$

Minsta möjliga $q$ = ordningen av $g$ ⇒ $\{ 1, g, g^2, g^3, \ldots, g^{q-1} \}$

Nästa tal i ordningen är då $g q = 1$

Exemplet ovan $(\mathbb{Z}^\times_7)$

$g = 2$ genererar serien ${1,2,4}$ ordning $q = 3$

Det är alltid möjligt att hitta en generator $g$ som kan generera hela gruppen $\mathbb{Z}^\times_p = \{ 1, 2, 3, \ldots, p-1 \}$

Den generator $g$ som genererar hela gruppen kallas ett primitivt element.

Andra värden på $g$ kommer att generera undergrupper vars storlek är intressant ur en attacksynvinkel.

Välj $g$ som ska vara ett primitivt element (som kan generera hela gruppen).

Välj $h$ som är ett godtyckligt element i gruppen.

⇒ $h = g x$ där $x$ ännu inte är valt.

Element som genereras med hjälp av $h$ : $1, h, h^2, h^3, \ldots$

Ordningen av $h$ : det minsta $q$ för vilket $h q = 1$ $[ h = g^x ] \Rightarrow g^{xq} = 1$

Om $x q = 0(mod p - 1)$

Detta händer.

$q = \frac{p-1}{\mbox{gcd}(x, p-1)}$

⇒ $q$ är en faktor i $p - 1$

$p = 7 \Rightarrow \mathbb{Z}^\times_7 = \{ 1, 2, 3, 4, 5, 6 \}$

$g = primitivt element = 3$

Serien $\{1, 3, 9, 27, 81, 243, \ldots \} \pmod 7$

$= \{ 1, 3, 2, 6, 4, 5, 1, \ldots \}$

Välj $h = 2 \Rightarrow \{ 1, h, h^2, h^3, h^4, \ldots \} \pmod 7$ $= \{ 1, 2, 4, 6, 16, 32, \ldots \} \pmod 7$ $= \{ 1, 2, 4, 1, \ldots \}$ = en subgrupp av ordning 3

$h = 6 \Rightarrow q = 2$

Ordningen av subgrupperna är en faktor av $(p - 1)$

[edit] 12.2

Exempel

Välj ett primtal: $p = 7$

Välj ett primitivt element $g = 3$

$p$ och $g$ är publika.

${1,2,3,4,5,6}$

Typisk tentafråga

[edit] Alice

$x \in \mbox{rand} \mathbb{Z}^\times_p$ Exempel $x = 4$

$x$ är hemlig.

Beräkna $g x = 3 4 mod 7 = 4$

$g x$ är publik

$K = (g y) x mod 7 = 2 4 mod 7 = 2$

[edit] Bob

$y \in \mbox{rand} \mathbb{Z}^\times_p$ Exempel $y = 2$

$y$ är hemlig.

Beräkna $g y = 3 2 mod 7 = 2$

$g y$ är publik

$K = (g x) y = 4 2 mod 7 = 2$

2 är den gemensamma nyckeln som används vid kommunikationen.

Är det möjligt att beräkna $g x y$ från $g$ , $p$ , $g x$ och $g y$ ?

Diffie-Hellman-problemet inte möjligt att lösa om $p$ är ett primtal och om $g$ är ett primitivt element.

Anfallaren känner till $p$ , $g$ och ser $g x$ och $g y$ ; känner ej till $x$ och $y$ .

[edit] 2007-12-03

(Cancelled due to illness.)

[edit] 2007-12-04

[edit] Diffie-Hellman

Välj $p = 7$ , välj $g = 3$

$\mathbb{Z}^\times_p = \{ 1, 2, 3, 4, 5, 6 \}$

[edit] Alice

Väljer $x$

Publicerar $g x$ .

$k = (g y) x$

[edit] Bob

Väljer $y$

Publicerar $g y$

$k = (g x) y$

[edit] 12.3 Man in the middle

[edit] 12.4 Fallgropar

Fallgrop A: $g = 1$ ej bra ty $k$ är alltid $= 1$; Lösning: kolla om $g x = 1$ eller $g y = 1$

Fallgrop B: Generator $g \neq$ primitivt element, $g$ har en liten subgrupp ⇒ få möjliga nycklar; Lösning: Kolla så att $p =$ primtal och $g =$ primitivt element eller ger tillräckligt stor subgrupp

OBS. Storleken på subgrupperna är delare till $p - 1$ så se till att undvika primtal med små delare.

[edit] 12.5 Safe Primes

$2 q + 1$ där $q$ också är ett primtal.

Subgrupper som är möjliga

Storlek 1: Enkel att testa
Storlek 2: Nummer 1 och $p - 1$
Storlek $q$ Välj denna
Storlek $2 q$ (fulla gruppen)

[edit] Problem med den fulla gruppen

Exakt hälften av alla tal i en full grupp är ”squares” $(mod p)$

Exempel: $\mathbb{Z}^\times_7 = \{ 1, 2, 3, 4, 5, 6 \}$

”squares” $= {1,4,9,16,25,36,}(mod 7)$ $= {1,4,2,2,4,1}$

Non-squares $= {3,5,6}$

Om en generator $g =$ ”square” ⇒ $g$ är inte ett primitivt element.

$p = 2 q + 1$

Om $g x$ är genererat från en non-square-generator så kan Eve använda sig av Legendre symbol-funktion för att bestämma om $x$ är jämn eller udda.

Lösning: använd $g$ som är ”squares” $(mod p)$ d.v.s. en subgrupp av storlek $q$

[edit] Algoritm för att använda ett säkert primtal $(p, q, g)$

Välj $p$ och $q$ så att både $p$ och $q$ är primtal. $p = 2 q + 1$
Välj $g$ som är en ”square” så att $g x$ tillhör halva mängden. Hur? Välj $α$ $2\leq \alpha \leq p-2$ ska uppfylla $g = α 2 (mod p)$
Kolla så att $g \neq 1$ och $g \neq p-1$

Exempel: $q = 5$

$p = 2 \times 5 + 1 = 11$

$α = 2$

$g = 2 2 = 4mod 11 = 4$

$4 \neq 1$ så OK

$4 \neq p-1 = 4 \neq 10$ så OK

$1 \ldots 10$

$g x$ ger samma möjliga nycklar som $(g x) y$

$g x$ (ordning $q = 5$ ) $= \{ g^0, g^1, g^1, g^2, g^3, \ldots g^10 \}$ $= \{ 1, 4, 16 \bmod 11, 4^3 \bmod 11, 4^4 \bmod 11, \ldots \}$ $= {1,4,5,9,3}$

När man tar emot ett $g x$ se till att $g x$ kommer från en subgrupp med ordning $q$

$g \neq 1$ och $(g x) q mod p = 1$

Exempel: $p = 11$ $q = 5$ $g = 4$

$x = 1$ ⇒ $g x = 4$

$(g x) q mod p = (4 5)mod 11 = 1024mod 11 = 1$ ⇒ OK

Om $g x = 8$

$85 mod 11 = 32768mod 11 = 10$ ⇒ inte OK $g x$

Säkra primtal har en nackdel att de är beräkningskrävande ⇒ mindre subgrupper.

Hur:

Hitta ett primtal $q$ minst 256 bitar
Hitta ett mycket större primtal $p = N q + 1$ (om $N$ är primtal är $p$ garanterat primtal)
Hitta lämpligt $g$ , välj $\alpha \in \mathbb{Z}^\times_p$ $g = α N$ kolla så att $g\neq 1$ och $g q = 1$

[edit] 2007-12-10

[edit] 13 RSA

Mest kända och använda publika nyckel-krypteringsalgoritmer.
Både kryptering och digitala signaturer
Bygger på svårigheten att faktorisera stora primtalsprodukter

[edit] Diffie-Hellman

$p$ och $q$ givna

Lätt att beräkna $g x mod p$ om man vet $x$ , mycket svårt i motsatt riktning.

[edit] RSA

Givet $n$ och $e$ - (publika)

$n=p\times q$ - (inte modulo)

$p$ och $q$ - (stora primtal, minst tusen bitar)

Kryptering: $m e mod n$

[edit] 13.2 CRT – The Chinese Remainder Theorem

Diffie-Hellman: Beräkningar modulo ett primtal $p$

RSA: Beräkningar modulo en primtalsprodukt $n=p\times q$

Teoremet: $(a, b) = (x mod p, x mod q)$

Är $a$ och $b$ kända samt $p$ och $q$ så kan $x$ bestämmas.

[edit] 13.2.1 Garner’s Formula

$x = \left(\left((a-b)(q^{-1} \bmod p)\right) \bmod p\right) q + b$

Hur ska vi använda CRT?

Kan användas för att spara beräkningskraft när vi räknar $(mod n)$ .

Addition $(x + y)mod n$ kan representeras av $(x + y)mod p,(x + y)mod q$ $= (x mod p + y mod p),(x mod q + y mod q)$

$x + y \bmod n = \begin{cases} (x+y) \bmod p \\ (x+y) \bmod q \end{cases}$ $= \begin{cases} (x \bmod p + y \bmod p) \bmod p \\ (x \bmod q + y \bmod q) \bmod q \end{cases}$ $= \begin{cases} a \\ b \end{cases}$

$p$ primtal: $x p - 1 = 1(mod p)$

$x t = 1mod n$

⇒ $x t = 1(mod q)$ och $x t = 1(mod p)$ eftersom $n=p\times q$

$p - 1$ ska vara en delare till till $t$ och $q - 1$ ska vara en delare till $t$ .

$t$ = minsta gemensamma multipeln till $(p - 1, q - 1)$ $= \frac{(p-1)(q-1)}{\gcd(p-1, q-1)}$

$n = p \times q$

$p$ och $q$ stora och olika primtal.

$m e (mod n)$

Definiera två exponenter $e$ och $d$

$e\times d \bmod t = 1$

Välj en publik exponent $e$ = till ett litet och udda tal.

$d$ ska beräknas = inversen till $e mod t$ ⇒ $e \times d = 1 \pmod t$

Kryptering $c = m e mod n$

Dekryptering $m = c d mod n$

$(m^e)^d = m^{(e\times d)} \left[ \begin{array}{l} (e \times d) \bmod t = 1 \\ (e \times d) + k \times t = 1 \\ \mbox{k är ett heltal} \end{array} \right]$

$= m^{kt+1} = (m^t)^k \times m = 1^k \times m$ $= m (mod n)$

$m t = 1(mod n)$

$m t = 1mod p$ $m t = 1mod q$

om $n = p \times q$

[edit] Exempel

Dekryptering och kryptering med RSA

$p = 17$ $q = 19$

Beräkna $n = p \times q = 323$ (publik)

lcm = Least Common Multiple

Beräkna $t = \operatorname{lcm} (p-1, q-1) = 144$ (hemlig)

$= \frac{(p-1)(q-1)}{\gcd((p-1)(q-1))} = \frac{16 \times 18}{2} = 144$

$e \times d \bmod t = 1$

$e = 5$ (publik)

$e \times d \bmod 144 = 1$

$145 = e \times d$ ⇒ $d = 29$ (hemlig)

$5 \times 29 \bmod 144 = 1$

$m = 201$

$c = m e mod n = 201 5 mod 323$ $= 328080401001mod 323 = 216$

Dekryptering:

$c d = 216 29 mod 323$ $= 50021738714629030177311081962496059484833406150976385567830453518336mod 323$ $= 201$

[edit] 2007-12-11

[edit] RSA

Kryptering $c = m e mod n$

Dekryptering $m = c d mod n = c 1 / e mod n$

$e = 17$

$d = 2753$

$n = 3233$

$m = 123$

$c = 123 1 7mod 3233 = 337587917446653715596592958817679803mod 3233$ $= 855$

$m = 855 2753 mod 3233 = 123$

Börja välj $p$ och $q$

$n = p \times q$

$n$ är publik.

$t$ = minsta gemensamma multipeln av $p - 1$ och $q - 1$ .

$p = 17$

$q = 19$

$p - 1 = 16$

$q - 1 = 18$

$16\times k_1 = 144$

$18\times k_2 = 144$

$t = \frac{(p-1)(q-1)}{\gcd(p-1, q-1)}$

Välj $e$ . Litet udda tal $< t$

$e$ ska inte ha gemensam faktor med $t$ då vi inte hittar ett $d$ .

Beräkna $d$ från $e \times d \bmod t$

$x t = 1$

Fermats lilla sats

$x p - 1 = 1(mod p)$ om $p$ är ett primtal

$x^t = 1 \pmod n = \left\{ \begin{array}{l} x^t = 1 \pmod p \\ x^t = 1 \pmod q \end{array} \right.$

[edit] Tentauppgift kan vara

Ta fram RSA-parametrarna om $p = 47$ och $q = 59$

[edit] Svar:

$n = p \times q = 2773$

$t = \operatorname{lcm}(46, 58)$ $= \frac{46\times 58}{\gcd(\underbrace{46}_{23 \times 2}, \underbrace{58}_{2 \times 29})}$ $= \frac{46 \times 58}{2} = 1334$

$e$ ska inte ha gemensam faktor med $t$

$e = 3$

Kolla att $\frac{1334}{3} = 444,6666\ldots$

Beräkna d: $e \times d \bmod t = 1$

$3 \times d \bmod 1334 = 1$ ⇒ $3 \times d = 1335$ ⇒ $d = 445$

Publika nycklar: $n, e$

Hemliga nycklar: $p, q, d, t$

$c = m e mod n$

$m = c d mod n = c 1 / e mod n$

$(m e mod n) 1 / e mod n$

Om $m e < n$ då gäller $(m e) 1 / e mod n = m$

En viktig fallgrop är detta ⇒ undvik små $m$

[edit] Signera ett meddelande

Till exempel $\left\{ \begin{array}{l} e = 3 \\ e = 5 \end{array} \right.$

$\left\{ \begin{array}{l} e = 17 \\ e = 65537 \end{array} \right.$

$s = m 1 / e mod n = m d mod n$

Skicka $m, s$

$\hat{s} = m^e$

Jämför $\hat{s}$ och mottaget $s$ .

⇒ Använd två värde på $e$ , ett för signaturen och ett för krypteringen.

Storleken på $n$ ska vara från 2048 till 4096 bitar, samma som för Diffie-Hellman.

Kryptering: I praktiten används inte RSA för att kryptera meddelanden eftersom $m < n$ därför används RSA för att kryptera nycklar.

[edit] 13.6

Välj slumpmässig nyckel $K$ + eventuell padding
Kryptera $K$ med RSA
Använd ett block cipher mode för att kryptera meddelandet
Skicka RSA-krypterad nyckel $K$ och krypterat meddelande. $\operatorname{E}_{RSA}(K)$ , $\operatorname{E}(K, m)$ istället för att $\operatorname{E}_{RSA}(m)$

[edit] 13.4.3 Hemliga nycklar

Om man känner till en av de hemliga nycklarna $(p, q, t, d)$ och de publika, då är det enkelt att knäcka RSA.

Två fallgropar vid signering

[edit] 1

Använd inte samma $e$ vid kryptering och signering $s = m 1 / e mod n$

[edit] 2

Alice skickar två meddelanden som hon signerar $(m 1, s 1)$ $(m 2, s 2)$

Eve konstruerar ett meddelande som uppfyller $m_3 = m_1 \times m_2 \bmod n$

signera genom att $s_3 = s_1 \times s_2 \bmod n = \left(m_1^{1/e} \times m_2^{1/e}\right) \bmod n$ $= \left(m_1 \times m_2\right)^{1/e} \bmod n$

[edit] Uppgift

Ta fram RSA-parametrar om $p = 11$ och $q = 89$ välj $e$ större än 3 och kryptera $m = 68$

[edit] 2007-12-17

[edit] 14 Inledning till kryptografiska protokoll

Utbyte meddelande
- T.ex. Diffie-Hellman

[edit] A. Roller

Kom ihåg att alla kan anta olika roller, t.ex. man in the middle, DH

[edit] B. Förtroende

Inte svart-vitt

lita på någon att hantera t.ex. 10000kr.

kryptotillämpningar

minimera mängden förtroende.

Antal människor vi behöver lita på
Hur mycket förtroende vi behöver ge dessa människor

[edit] 14.5

[edit] C. Meddelande, steg

Specifikationerna av ett protokoll

inte för detaljerad
inte för enkel
dela protokollet i flera steg

[edit] Transportlagret

Ett givet antal bitar skall från punkt A till B. T.ex. TCP
- Ingen säker kanal, ur ett kryptoperspektiv

[edit] Protokoll och meddelandeidentifiering

Protokollinformation
- Vilken version
- Vilket protokoll
Meddelandenumrering

[edit] 14.5 Meddelandekryptering

Konvertera från datasymboler till bitsekvenser och kryptera.

[edit] Felhantering

Hantera fel varsamt
T.ex. pinkoder om 4 siffror
- $\frac{1}{10000} \times 5 \mbox{försök} = \frac{1}{2000}$

[edit] 15 Key negotiation protocols

Använde nyckelutbytnadsprotokollet för att sätta upp en "session key", K
- "Session key" tenderar att vara beräkningskrävande
Använd $k$ för en säker och effektiv kanal

Varför använda en "session key" om vi redan har en säker nyckel?

Om vi förlorar en ”session key” så är ändå t.ex. gårdagens information säker.

[edit] 15.2 DH + added authentication

Alice vet $[p, q, g]$

Väljer $x$ från $1\ldots q-1$

$g x$ beräknas och skickas

Bob vet $[p, q, g]$

Väljer $y$

Beräknar $g y$ och $k = (g x) y$

Skickar tillbaka $g y$

Alice kan nu beräkna $k = (g y) x$

och beräkna $a = \operatorname{Auth}(k)$

$a = \operatorname{mac}(m, k)$

Alice skickar $a$ och $m$

Bob kollar $a'$ och jämför $a = a'$

$b = \operatorname{Auth}(k)$

Bob skickar $b$ och $m$

Alice kollar $b = b'$

[edit] Problem

Samma nyckel används vid kryptering och verifiering ⇒ verifieringen ger oss inget nytt
Inte bra att ha givna $(p, q, g)$
4 meddelande behövs, för många går att göra på 3

[edit] Verifiering: Hur ska vi välja $m$ ?

$m$ ska vara all information som är skickad upp till nu.

Skriver Auth då menas all information som är sänt genom t.ex. en hashfunktion.

[edit] Alice

Väljer $(p, q, g)$

Välj $x$ ⇒ $g x$

$\mbox{Auth}_A = \operatorname{hash}(p, q, g, g^x)$

$Auth A$ och $g x$ skickas.

[edit] Bob

Får reda på $(p, q, g)$

Välj $y$ ⇒ $g y$

Beräknar $Auth' A$ , jämför med mottagna $Auth A$

Beräknar $\mbox{Auth}_B = \operatorname{hash}(p, q, g, g^x, g^y)$

$Auth B$ och $g y$ skickas

[edit] Alice

Beräknar $Auth' B$ och jämför med mottagna $Auth B$

[edit] Problem

Problem vid verifiering och $p, q, g$ kan vara felaktigt valda

Alice skickar slumptal + minsta $p,Auth$
Bob väljer parametrar, beräknar $g x + Auth$
Alice beräknar $g y$ och $Auth$

Alice	↔	Bob
Väljer minsta storleken på $p = s$		Väjer $p, q, g$
Väljer slumptal (Nonce) på 256 bitar = $N a$	$S, N a$ →	väljer $x$ ⇒ $g x$
	← $p, q, g, g x,Auth A$	Beräknar $Auth A (s, N a, p, q, g, g x)$
Kolla $(p, q, g)$
välj $y = g y$
Beräkna $Auth' A$ och jämför.
Beräkna $Auth B$ och $k$ (30 bitar)	$g y,Auth B$ →	Kolla $Auth B$ , beräkna $k$

Ytterligare förbättring för att få $k$ till 256 bitar ⇒ $K = \operatorname{SHA}_{256}\Big((g^x)^y\Big)$

[edit] 2007-12-18

[edit] 17 The Clock

Begränsar varaktigheten av ett dokument
nonce
använd klockan för att inte förväxla gamla meddelanden som nya

[edit] 18 Key Servers

Organisation som man litar på som handhar publika nycklar eller delar ut en säker nyckel samt vet vem som är vem.

Alla användare sätter upp en publik nyckel hos "key server".

Alice, $k A$ och Bob, $k B$

[edit] 18.2 Kerberos

Alice vill kommunicera med Bob.

"key server" har då $k A$ och $k B$

$k A B$ = session key

Alice	Request “Bob” →	Key Server
	← $E K A (K A B)$
	← $E K A (E K B (K A B))$
	$E K B (K A B)$ →	Bob

Verkar enkelt ⇒ komplicerat protokoll
Servern måste hålla reda på alla använda $k A B$ , session keys

[edit] 18.3 Secure Connection

Förenklad version

Förutsätter att det finns en säker kanal mellan key server och Alice samt mellan key server och Bob.

Alice vill kommunicera med Bob

key server och Alice har nyckel $k A$

Alice använder ett nyckelförhandlingsprotokoll för att förhandla en session key $\hat{k_A}$
Alice använder nu $\hat{k_A}$ för att kommunicera med key server
Bob gör som punkt 1 och för $\hat{k_B}$
Bob kommunicerar med key server med nyckel $\hat{k_B}$
All kommunikation via nyckelservern

[edit] 19 Public Key Infrastructure (PKI)

CA - Central Authority

CA har en egen privat och publik nyckel. Den publika publiceras. (RSA används, oftast).

"Gå med i PKI"

Alice genererar sin publika/private nyckel.
Alice skickar sin publika nyckel ( $P k A$ ) till CA
CA utfärdar ett Certifikat som säger att $P k A$
CA publicerar $P k A$ på sin officiella lista
Bob samma förfarande

kommunicera Alice ↔ Bob

Alice skickar sin publika nyckel $P k A$ till Bob
Bob kollar med CA om $P k A$ är samma
Bob skickar…
Alice kollar…

[edit] 19.2 Universell PKI

Omöjlig

[edit] 19.3 Multilevelcertificat

Säkerhetskedja – Bankvärlden

T.ex. Mastercard ← Firstcard →

[edit] 19.4 Bäst före-datum

Använd inte samma nyckel en längre tid
Behöver också certifikat bytas

ET1206/Lectures

From FUKTwiki

Contents

[edit] 2007-11-05

[edit] 3.1 Kryptering

[edit] Kerckhoffs' principle

[edit] 3.2 Autentisering, verifiering

[edit] 3.3 Public key encryption (publika nycklar)

[edit] 3.4 Digitala signaturer

[edit] 2007-11-06

[edit] Publika nycklar

[edit] 3.5 PKI, Public Key Infrastructure

[edit] 3.6 Attacker

[edit] 1 Ciphertext only

[edit] 2 Known plain text

[edit] 3 Chosen plain text

[edit] 4 Chosen Ciphertext

[edit] Collision attacks

[edit] 4 Blockkryptering

[edit] 4.3 The Ideal block cipher

[edit] 4.5 Real block ciphers

[edit] DES

[edit] 2007-11-07

[edit] 4

[edit] AES

[edit] Lineraritet

[edit] Subbytes

[edit] Shiftrows

[edit] Mix Columns

[edit] Add Round Key

[edit] Fördel mot DES

[edit] Serpent

[edit] Twofish

[edit] Attacker

[edit] XSL - equation solving attacks

[edit] Which block cipher should I use?

[edit] Vilken nyckelstorlek ska jag använda?

[edit] 2007-11-12

[edit] 5 Block Cipher Modes

[edit] Kollisionsrisk för två Ci block

[edit] 5.1 Padding

[edit] Schema

[edit] Schema 2

[edit] 5.2 ECB – Electronic Code Book

[edit] XOR

[edit] 5.3 CBC – Cipher Block Chaining

[edit] 1 Fix IV eller C0

[edit] 2 Counter IV

[edit] 3 Random IV

[edit] 2007-11-13

[edit] CBC – Cipher Block Chaining (forts.)

[edit] Nonce generated IV

[edit] Stream Ciphers

[edit] OFB – Output Feedback Mode

[edit] CTR – Counter Mode

[edit] 2007-11-14

[edit] CTR – Counter Mode (forts.)

[edit] OFB

[edit] Exempel

[edit] 5.8 Läckor

[edit] Risk för kollision

[edit] 6 Hashfunktioner (kryptografiska hash functions)

[edit] 6.1 Säkerhet med hashfunktioner

[edit] Praktiska hashfunktioner

[edit] Fördelar med iterativa hashfunktioner

[edit] MD5

[edit] SHA-1

[edit] 2007-11-19

[edit] 6 Hashfunktioner

[edit] Iterativa hashfunktioner

[edit] 6.3 Svagheter hos hashfunktioner

[edit] Length extensions

[edit] 6.3.2 Partial message collision

[edit] Fix av svagheterna

[edit] 7 Message Authentication Codes (MAC)

[edit] 7.4 CBC-MAC

[edit] 7.5 HMAC (Hash MAC)

[edit] 7.6 UMAC

[edit] 2007-11-20

[edit] 8 The Secure Channel

[edit] Kollisionsrisk för två $C i$ block

[edit] 1 Fix IV eller $C 0$

[edit] Algoritm för att använda ett säkert primtal $(p, q, g)$