Handouts - Prof. Dr. Christoph Karg

Transcrição

Kryptografische Protokolle
Lerneinheit 1: Zufallszahlengeneratoren
Prof. Dr. Christoph Karg
Studiengang Informatik
Hochschule Aalen
Sommersemester 2016
1.4.2016
Einleitung
Einleitung
Zufallszahlen spielen in der Kryptografie eine wichtige Rolle. Die
Sicherheit vieler Verfahren (z.B. RSA) hängt von der Qualität der
eingesetzten Zufallszahlengeneratoren ab.
Folgende Themen werden behandelt:
• Anforderungen an Zufallszahlengeneratoren
• Lineare-Kongruenzen Generator
• Blum-Blum-Shub Generator
• Fortuna Generator auf Basis von AES
Die Lerneinheit basiert auf Kapitel 8 von Stinson: Cryptography
Theory and Practice und Kapitel 10 von Ferguson, Schneier:
Practical Cryptography
Prof. Dr. C. Karg (HS Aalen)
Zufallszahlengeneratoren
2 / 96
Einleitung
Unterscheidung
• Echte Zufallsdaten
. Messung von physikalischen Ereignissen z.B. zeitlichen
Abständen von Tastatureingaben
. Erzeugung in der Regel aufwändig
. Zufallsdaten nicht immer verfügbar
• Pseudo Zufallsdaten
. Berechnung mit einem (deterministischen) Algorithmus
. Zufallsfolge hängt ausschließlich von einem Initialwert
(Seed) ab
. Voraussetzung: Geheimhaltung des Seed
Einleitung
3 / 96
Definition Bit Generator
(k, `)-bit Generator
Definition. Seien k, ` positive ganze Zahlen, so dass ` ≥ k + 1.
Ein (k, `)-bit Generator ist eine Funktion f : {0, 1}k 7→ {0, 1}` , die in
Polynomialzeit berechenbar ist.
Die Eingabe s0 ∈ {0, 1}k nennt man einen Seed, die Ausgabe f (s0 )
wird als erzeugte Bitfolge bezeichnet.
4 / 96
Einleitung
Definition Bit Generator
(k, `)-bit Generator (Forts.)
Bemerkungen:
• Die erzeugte Bitfolge ist mindestens ein Bit länger als der Seed
• Da f deterministisch ist, hängt die erzeugte Bitfolge
ausschließlich vom Seed ab
• Ziel: Konstruktion von (k, `)-bit Generatoren, deren erzeugte
Bitfolge zufällig aussieht. Einen derartigen Generator nennt man
dann Pseudo-Random Bit Generator (PRBG)
Einleitung
5 / 96
Linearer Kongruenzgenerator
Definition (k, `)-bit Linearer Kongruenzgenerator.
Sei m ≥ 2 eine ganze Zahl und seien a, b ganze Zahlen mit
1 ≤ a, b ≤ m − 1.
Sei k = dlog2 me und sei ` ≥ k + 1 eine ganze Zahl.
Der Seed ist eine ganze Zahl s0 ∈ {0, 1, . . . , m − 1}.
Für i = 1, . . . , ` ist si definiert als:
si = (a · si−1 + b) mod m
Die erzeugte Bitfolge ist f (s0 ) = (z1 , z2 , . . . , z` ), wobei zi = si mod 2
6 / 96
Einleitung
Algorithmus LKG(a, b, m, s0)
LKG(a, b, m, s0 )
Input: k-bit Zahl m, a, b ∈ {1, . . . , m}, s0 ∈ {0, . . . , m − 1}
Output: `-bit Folge (z1 , . . . , z` )
1 for i := 1 to ` do
2
si := (a · si−1 + b) mod m
3
zi := si mod 2
4 return (z1 , . . . , z` )
Einleitung
7 / 96
Beispiel Linearer Kongruenzgenerator
Konstruktion eines (5, 10)-bit Generators:
Wähle m = 31, a = 3, b = 5. Die Zufallsbitfolge wird unter Einsatz
der Funktion s 7→ (3s + 5) mod 31 berechnet
Die interne Zufallsfolge durchläuft 2 Zyklen:
1. 0 → 5 → 20 → 3 → 14 → 16 → 22 → 9 → 1 → 8 → 29
→ 30 → 2 → 11 → 7 → 26 → 21 → 6 → 23 → 12 → 10
→ 4 → 17 → 25 → 18 → 28 → 27 → 24 → 15 → 19 → 0
2. 13 → 13
Der Wert 13 ist offensichtlich nicht als Seed geeignet
8 / 96
Einleitung
Beispiel Linearer Kongruenzgenerator (Forts.)
Zufallsbits von Zyklus 1:
i si−1 si
1
0
2
5
3 20
4
3
5 14
6 16
7 22
8
9
9
1
10 8
mod 2
1
0
1
0
0
0
1
1
0
1
i si−1 si
11 29
12 30
13 2
14 11
15 7
16 26
17 21
18 6
19 23
20 12
mod 2
0
0
1
1
0
1
0
1
0
0
Einleitung
i si−1 si
21 10
22 4
23 17
24 25
25 18
26 28
27 27
28 24
29 15
30 19
mod 2
0
1
1
0
0
1
0
1
1
0
9 / 96
Seeds mit den jeweiligen erzeugten Bitfolgen:
Seed
Bitfolge
Seed
Bitfolge
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1010001101
0100110101
1101010001
0001101001
1100101101
0100011010
1000110010
0101000110
1001101010
1010011010
0110010110
1010100011
0011001011
1111111111
0011010011
1010100011
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0110100110
1001011010
0101101010
0101000110
1000110100
0100011001
1101001101
0001100101
1101010001
0010110101
1010001100
0110101000
1011010100
0011010100
0110101000
10 / 96
Einleitung
Häufigkeit der Bitfolgen:
Bitfolge
Seeds
Bitfolge
Seeds
1111111111
1010100011
0110101000
1100101101
1000110100
0001100101
1010011010
1010001100
1010001101
0100011010
1011010100
0110100110
0010110101
0101000110
13
11, 15
27, 30
4
20
23
9
26
0
5
28
16
25
7, 19
0011001011
1001011010
0110010110
0011010100
1000110010
0100011001
1101010001
1101001101
0101101010
0001101001
0011010011
1001101010
0100110101
12
17
10
29
6
21
2, 24
22
18
3
14
8
1
Einleitung
11 / 96
RSA Generator
Der RSA Generator ist ein (k, `)-Generator, der ist folgendermaßen
aufgebaut ist:
Seien p, q zwei verschiedene (k/2)-bit Primzahlen
Sei n = p · q. Sei e ∈ {2, . . . φ(n) − 2} eine Zahl mit gcd(e, φ(n)) = 1
Der Seed ist eine Zahl s0 ∈ {2, . . . , n − 2}. Definiere
e
mod n
si = si−1
zi = si mod 2
für i = 1, . . . , ` und f (s0 ) = (z1 , . . . , z` )
12 / 96
Einleitung
Beispiel RSA Generator
Ziel ist die Konstruktion eines (32, 48)-bit RSA Generators.
Hierzu werden die 16-bit Primzahlen p = 49853 und q = 50023
ausgewählt.
Die Werte von n und φ(n) sind:
n = p · q = 2493796619
φ(n) = (p − 1) · (q − 1) = 2493696744
Als Exponent wird e = 5 gewählt
Offensichtlich gilt gcd(e, φ(n)) = 1, denn 2493696744 ist kein
Vielfaches von 5
Einleitung
13 / 96
Beispiel RSA Generator (Forts.)
Bitfolge für den Seed s0 = 133:
i
si
si mod 2
i
si
si mod 2
1
2
3
4
5
6
7
8
9
10
11
12
1715049989
125151210
111607254
1286485940
1757925661
1231273517
629651831
2110340527
2444573424
310341634
1044210194
2351172386
1
0
0
0
1
1
1
1
0
0
0
0
13
14
15
16
17
18
19
20
21
22
23
24
704525673
2217923578
1246194714
2268344913
1293816839
1142308995
640358470
2201746057
2247054200
214965552
1568366061
147756434
1
0
0
1
1
1
0
1
0
0
1
0
14 / 96
Einleitung
Beispiel RSA Generator (Forts.)
Bitfolge für den Seed s0 = 133 (Teil 2):
i
si
si mod 2
i
si
si mod 2
25
26
27
28
29
30
31
32
33
34
35
36
1263833740
1212176274
2284028447
412716439
1291977567
1423793022
1432131289
1104879508
1285559980
1462305071
1982001190
1825221129
0
0
1
1
1
0
1
0
0
1
0
1
37
38
39
40
41
42
43
44
45
46
47
48
1061153640
1230173667
2475540485
1339296228
2371312881
1721175376
2128133478
115842642
545991434
1094191503
971577659
296897324
0
1
1
0
1
0
0
0
0
1
1
0
Anforderungen an PRBGs
15 / 96
Anforderungen
Anforderungen
Zwei Anforderungen an PRBGs:
• Sicherheit
es ist mit vertretbarem Aufwand nicht möglich,
eine erzeugte Bitfolge von einer echten Zufallsfolge zu
unterscheiden
• Geschwindigkeit
die Berechnung der Bitfolgen muss effizient
durchführbar sein
16 / 96
Wahrscheinlichkeitsverteilungen
Definition. Eine Wahrscheinlichkeitsverteilung über der Menge
{0, 1}k ist eine Funktion µ : {0, 1}k 7→ [0, 1] mit
X
µ(x) = 1.
x∈{0,1}k
Steht die Zufallsvariable X für das Ereignis
Ziehen eines Worts aus {0, 1}k“,
”
dann ist
Probµ [X = x] = µ(x)
die Wahrscheinlichkeit, dass das Wort x gezogen wird.
17 / 96
Gleichverteilung über {0, 1}`
Die Gleichverteilung µu über der Menge {0, 1}` weist jedem Wort
dieselbe Wahrscheinlichkeit zu.
Es gilt für alle x ∈ {0, 1}` :
µu (x) =
1
2`
Bemerkung: Aus kryptografischer Sicht ist die Gleichverteilung eine
ideale Wahrscheinlichkeitsverteilung
18 / 96
Verteilung eines (k, `)-bit Generators
Gegeben: (k, `)-bit Generator f
Annahme: Der Seed wird unter Gleichverteilung aus {0, 1}k gezogen.
Ansatz: Sei x ∈ {0, 1}` beliebig gewählt. Die Menge Seed (x) enthält
alle Seeds, für die f die Bitfolge x erzeugt. Formal:
Seed (x) = {s ∈ {0, 1}k | f (s) = x}
Die Wahrscheinlichkeit, dass f das Wort x ∈ {0, 1}` erzeugt, ist gleich
µf (x) =
X
µu (s) =
s∈Seed(x)
kSeed (x)k
.
2k
19 / 96
Unterscheidbarkeit von Wahrscheinlichkeitsverteilungen
Intuitive Idee
Gegeben: Wahrscheinlichkeitsverteilungen µ0 und µ1 über {0, 1}`
Frage: Gibt es einen Algorithmus DST mit folgenden Eigenschaften?
• DST berechnet eine Funktion von {0, 1}` nach {0, 1}
• DST hat polynomiale Laufzeit
• Auf Eingabe eines Wortes x ∈ {0, 1}` kann DST mit einer
gewissen Chance korrekt entscheiden, ob x gemäß µ0 oder µ1
erzeugt wurde
20 / 96
ε-Unterscheidbarkeit
Definition. Seien µ0 und µ1 Wahrscheinlichkeitsverteilungen über der
Menge {0, 1}` . Sei DST : {0, 1}` 7→ {0, 1} eine Funktion und ε > 0.
Definiere für i = 0, 1 den Wert EDST (µi ) als
X
EDST (µi ) =
µi (x)
x∈{0,1}` :DST(x)=1
Die Funktion DST ist ein ε-Unterscheider von µ0 und µ1 , falls
|EDST (µ0 ) − EDST (µ1 )| ≥ ε
Falls DST in Polynomialzeit berechenbar ist, dann nennt man DST
einen Polynomialzeit ε-Unterscheider.
21 / 96
ε-Unterscheidbarkeit (Forts.)
Definition. Seien µ0 und µ1 Wahrscheinlichkeitsverteilungen über
der Menge {0, 1}` .
• µ0 und µ1 sind ε-unterscheidbar, falls es einen ε-Unterscheider
DST für µ0 und µ1 gibt.
• µ0 und µ1 sind in Polynomialzeit ε-unterscheidbar, falls es einen
Polynomialzeit ε-Unterscheider DST für µ0 und µ1 gibt.
22 / 96
Anwendung von ε-Unterscheidbarkeit
Gegeben: (k, `)-bit Generator f
Annahme: Jeder Seed erzeugt eine andere Bitfolge.
Für die aus f abgeleitete Wahrscheinlichkeitsverteilung µf gilt:
• Es gibt 2k Wörter in {0, 1}` , die jeweils mit Wahrscheinlichkeit
erzeugt werden.
• Es gibt 2` − 2k Wörter in {0, 1}` , die nicht erzeugt werden.
1
2k
Konsequenz: µf unterscheidet sich stark von der Gleichverteilung µu
über {0, 1}` .
Anforderung: f gilt als kryptografisch sicherer PRBG, falls für alle
ε > 0 gilt, dass µf nicht ε-unterscheidbar von µu ist.
23 / 96
Zur Illustration ein Beispiel
Beispiel. Gegeben ist ein (k, `)-bit Generator f , der ausschließlich
Bitfolgen erzeugt, in denen die Anzahl Nullen gleich der Anzahl
Einsen ist.
Definiere
1(
DST(x1 . . . x` ) =
0(
µf ) falls x1 . . . x` genau
µu ) sonst
`
2
Nullen enthält
24 / 96
Zur Illustration ein Beispiel (Forts.)
Es gilt
`
`/2
2`
EDST [µu ] =
und
EDST [µf ] = 1
Wegen der Eigenschaft
lim
`→∞
`
`/2
2`
=0
sind µu und µf für jedes ε, 0 < ε < 1, ε-unterscheidbar, falls `
hinreichend groß ist
25 / 96
Beispiel: Linearer Kongruenzgenerator
Gegeben ist ein (5, 10)-bit Linearer Kongruenzgenerator mit den
Parametern a = 3, b = 5 und m = 31
Der Unterscheidungsalgorithmus basiert auf folgender Funktion:
1 falls x`−1 6= x` ,
DST(x1 . . . x`−1 x` ) =
0 sonst.
DST ordnet demnach x1 . . . x` dem Generator f zu, wenn die letzten
beiden Bits verschieden sind.
26 / 96
Beispiel: Linearer Kongruenzgenerator (Forts.)
Bitfolgen x mit DST(x) = 1:
Bitfolge
Häufigkeit
1100101101
1
0001100101
1
1010011010
1
1010001101
1
0100011010
1
0110100110
1
0010110101
1
0101000110
2
1001011010
1
Bitfolge
Häufigkeit
0110010110
1
1000110010
1
0100011001
1
1101010001
2
1101001101
1
0101101010
1
0001101001
1
1001101010
1
0100110101
1
Gesamthäufigkeit: 18
27 / 96
Anhand der Tabelle berechnet man:
X
EDST (µf ) =
µf (x) =
x∈{0,1}` :DST(x)=1
18
31
Wird ein `-bit Wort zufällig unter Gleichverteilung gezogen, dann sind
mit einer Wahrscheinlichkeit von 21 die letzten beiden Bits
verschieden.
X
1
EDST (µu ) =
µu (x) =
2
`
x∈{0,1} :DST(x)=0
28 / 96
Hieraus folgt:
18 1 |EDST (µf ) − EDST (µu )| = − 31 2
36 31 = − 62 62
5
=
62
Ergebnis: DST ist ein
5
-Unterscheider
62
für µf und µu
29 / 96
Next Bit Predictors
Vorhersage des nächsten Bits
Frage: Ist es ohne Kenntnis des Seeds möglich, für einen (k, `)-bit
Generator vorherzusagen, welchen Wert das i-te Bit hat, wenn man
die Bits x1 , . . . , xi−1 kennt?
Antwort: Falls ja, dann ist der Generator nicht als sicher einzustufen
Ziel: Formalisierung dieses Konzepts
30 / 96
Next Bit Predictors
Definition Next Bit Predictor
Definition. Sei f ein (k, `)-bit Generator. Angenommen,
1 ≤ i ≤ ` − 1.
Die Funktion NBP : {0, 1}i−1 → {0, 1} ist ein ε-Next Bit Predictor für
Bit i, falls NBP auf Eingabe von x1 . . . xi−1 das i-te Bit xi korrekt
berechnet mit einer Wahrscheinlichkeit von 12 + ε, wobei ε > 0.
31 / 96
Next Bit Predictors
Anpassung der Wahrscheinlichkeitsverteilungen
Sei µ eine Wahrscheinlichkeitsverteilung über {0, 1}` . Sei
i ∈ {0, . . . , `} fest gewählt.
Betrachte ein beliebiges Wort x1 . . . xi ∈ {0, 1}i . Die Menge aller
Wörter in {0, 1}` mit Präfix x1 . . . xi ist
Prefix (x1 . . . xi ) = {x1 . . . xi w | w ∈ {0, 1}`−i }
Die Wahrscheinlichkeit, dass ein Wort mit Präfix x1 . . . xi auftritt, ist:
X
µi (x1 . . . xi ) =
µ(z)
z∈Prefix (x1 ...xi )
32 / 96
Next Bit Predictors
Ein wichtiger Satz
Betrachte einen (k, `)-bit Generator f .
Die Zufallsvariable Xi steht für den Wert des i-ten Bits einer
Zufallsfolge, die gemäß µf auftritt
Definiere für eine Funktion NBP : {0, 1}i−1 7→ {0, 1}
i
pNBP
(x1 . . . xi−1 ) = Prob[Xi = NBP(x1 . . . xi−1 )|x1 . . . xi−1 ]
Satz. Eine Funktion NBP ist genau dann ein ε-Next Bit Predictor
für Bit i von f , wenn
X
i
µi−1
f (x1 . . . xi−1 ) · pNBP (x1 . . . xi−1 ) ≥
x1 ...xi−1 ∈{0,1}i−1
1
+ε
2
33 / 96
Next Bit Predictors
Beispiel: Linearer Kongruenzgenerator
Beispiel. Betrachte für ein i ∈ {1, 2, . . . , 9} einen NBP, der folgende
Funktion berechnet:
NBP(x1 . . . xi−1 ) = 1 − xi−1
Die Vorhersage ist also, dass auf eine 0 vermutlich eine 1 folgt, und
umgekehrt
Anwendung auf den linearen Kongruenzgenerator mit den Parametern
a = 3, b = 5, m = 31
34 / 96
Next Bit Predictors
Analyse der Tabelle von Folie 11 für i = 5:
x
b = NBP(x)
0010
1
0011
0
0100
1
0101
0
0110
1
1000
1
1001
0
1010
1
1011
0
1100
1
1101
0
Seeds
#Seeds
25
1
12, 14, 29
3
1
1
7, 19
2
16, 27, 30
3
6, 20
2
17
1
11, 15
2
28
1
4
1
2, 22, 24
3
35 / 96
Next Bit Predictors
Die Wahrscheinlichkeit, dass NBP(x) das Bit i = 5 korrekt
vorhersagt, ist:
20
40
31 + 9
1
9
=
=
= +
31
62
62
2 62
Also ist NBP(x) ein
9
-Next
62
Bit Predictor für das Bit i = 5
Durch Analyse der Tabelle von Folie 11 stellt man fest, dass diese
9
Funktion für alle i ein 62
-Next Bit Predictor ist
36 / 96
Zusammenhänge
Zusammenhänge
Satz. Sei f ein (k, `)-bit Generator. Angenommen, es gibt einen
Polynomialzeit ε-Next Bit Predictor für ein Bit i ∈ {1, . . . , `} von f .
Dann sind µu und µf ε-unterscheidbar.
Satz. Sei f ein (k, `)-bit Generator. Angenommen, µu und µf sind
ε-unterscheidbar. Dann existiert für mindestens ein i ∈ {1, . . . , `} ein
Polynomialzeit ε` -Next Bit Predictor für Bit i von f .
Quadratische Reste
37 / 96
Einleitung
Definition Quadratischer Rest
Definition. Sei p eine ungerade Primzahl. Die Zahl a ∈ Zp , a 6= 0,
ist ein quadratischer Rest modulo p, falls eine Zahl x ∈ Zp existiert,
so dass
x 2 ≡ a (mod p)
Ist a kein quadratischer Rest, dann nennt man a quadratischen
Nicht-Rest.
38 / 96
Quadratische Reste
Einleitung
Beispiel zu Quadratischen Resten
Betrachte Z11 .
a 1 2 3 4 5 6 7 8 9 10
a2 1 4 9 5 3 3 5 9 4 1
Also ist die Menge der quadratischen Reste modulo 11 gleich
{1, 3, 4, 5, 9}
Die Menge der quadratischen Nicht-Reste ist
{2, 6, 7, 8, 10}
Quadratische Reste
39 / 96
Einleitung
Anzahl der Quadratwurzeln
Sei p eine ungerade Primzahl und sei a ein quadratischer Rest
modulo p.
Frage: Wieviele Lösungen hat die Gleichung
x2 ≡ a
(mod p)?
Sei y 6= 0 eine der Lösungen (eine solche muss existieren, da a ein
quadratischer Rest ist)
Umformen:
x2
≡ a
2
⇔ x −a
≡ 0
⇔ (x + y )(x − y ) ≡ 0
(mod p)
(mod p)
(mod p)
Also gibt es mit x ≡ ±y (mod p) mindestens zwei quadratische
Reste
40 / 96
Quadratische Reste
Einleitung
Anzahl der Quadratwurzeln (Forts.)
Zu zeigen bleibt, dass x ≡ ±y (mod p) die beiden einzigen Lösungen
sind.
Angenommen, es gibt einen weiteren quadratischen Rest z ∈ Zp mit
z 6≡ ±y (mod p).
Da p eine Primzahl ist, folgt wegen ZTK (Satz 5.2) aus
(z + y )(z − y ) ≡ 0 (mod p),
dass p |(z + y ) oder p |(z − y )
Quadratische Reste
41 / 96
Einleitung
Anzahl der Quadratwurzeln (Forts.)
Fall 1: p |(z + y ). Also ist z + y ein Vielfaches von p. Wegen der
Wahl von z gilt:
0 < z + y < 2p − 1
Also muss z + y = p und somit z = p − y gelten. Widerspruch!
Fall 2: p |(z − y ). Analog zu Fall 1.
Ergebnis:
• Die Gleichung x 2 ≡ a (mod p) besitzt genau zwei Lösungen
• Die eine Lösung ist die Negation der anderen modulo p
42 / 96
Quadratische Reste
Euler Kriterium
Euler Kriterium
Satz. Sei p eine ungerade Primzahl. Die Zahl a ∈ Zp ist genau dann
ein quadratischer Rest, wenn
a(p−1)/2 ≡ 1 (mod p)
Bemerkung: Mit dem Algorithmus zur modularen Exponentiation
kann man effizient überprüfen, ob a ein quadratischer Rest modulo p
ist.
Quadratische Reste
43 / 96
Euler Kriterium
Euler Kriterium (Forts.)
Beweis. Angenommen, x 2 ≡ a (mod p) für ein x ∈ Zp .
Unter Einsatz des Satzes von Fermat folgt:
a(p−1)/2 ≡ (x 2 )(p−1)/2
≡ x p−1
≡ 1
(mod p)
(mod p)
(mod p)
44 / 96
Quadratische Reste
Euler Kriterium
Euler Kriterium (Forts.)
Angenommen, a(p−1)/2 ≡ 1 (mod p). Sei b ein erzeugendes Element
von Z∗p . Dann existiert ein i mit b i ≡ a (mod p).
Es gilt:
a(p−1)/2 ≡ (b i )(p−1)/2
≡ b i(p−1)/2
≡ 1
(mod p)
(mod p)
(mod p)
Da b die Ordnung p − 1 hat, muss (p − 1) |(i(p − 1)/2) gelten.
Folglich ist i eine gerade Zahl und deshalb sind ±b i/2 mod p die
beiden Quadratwurzeln von a.
Quadratische Reste
45 / 96
Legendre Symbol
Legendre Symbol
Definition. Angenommen, p ist eine ungerade Primzahl.
Für eine
a
beliebige ganze Zahl a ist das Legendre Symbol p definiert als


falls a ≡ 0 (mod p)
0
a
= 1
falls a quadratischer Rest modulo p ist

p

−1 falls a quadratischer Nicht-Rest modulo p ist
Satz. Sei p eine ungerade Primzahl. Dann gilt
a
≡ a(p−1)/2 (mod p)
p
für alle ganzen Zahlen a.
46 / 96
Quadratische Reste
Zusammengesetzte Zahlen als Modul
Quadratwurzeln von zusammengesetzten Zahlen
Definition. Sei n eine beliebige ungerade ganze Zahl. Sei a eine
ganze Zahl, die teilerfremd zu n ist, d.h., gcd(a, n) = 1. Falls es eine
ganze Zahl y mit
y 2 ≡ a (mod n)
gibt, dann nennt man a einen quadratischen Rest modulo n.
Andernfalls ist a ein quadratischer Nicht-Rest modulo n.
Zu klären:
• Welche a sind quadratische Reste modulo n?
• Wieviele Quadratwurzeln hat ein quadratischer Rest modulo n?
Quadratische Reste
47 / 96
Primzahlpotenzen
Satz. Sei p eine ungerade Primzahl und sei k eine ganze Zahl mit
k > 0. Sei a eine zu p teilerfremde Zahl, d.h., gcd(a, p) = 1.
Angenommen, es existiert eine Zahl b ∈ Z∗p , so dass
b2 ≡ a
(mod p k−1 ).
Dann existiert genau ein x ∈ Zpk mit:
(1) x 2 ≡ a (mod p k )
(2) x ≡ b (mod p k−1 )
48 / 96
Quadratische Reste
Primzahlpotenzen (Forts.)
Beweis. Sei p eine ungerade Primzahl und a ∈ Z∗p .
Annahme: Es gibt b ∈ Z∗p , so dass b 2 ≡ a (mod p k−1 )
Existenz von x: Laut Annahme ist
b 2 = j · p k−1 + a
für eine ganze Zahl j.
Laut (2) muss x = i · p k−1 + b für eine ganze Zahl i sein.
Einsetzen in (1) führt zu folgender Gleichung:
(i · p k−1 + b)2 ≡ a
(mod p k )
Quadratische Reste
49 / 96
Umformen:
(i · p k−1 + b)2 ≡ a
(mod p k )
⇔ (i · p k−1 )2 + 2 · b · i · p k−1 + b 2 ≡ a
(mod p k )
⇔
2 · b · i · p k−1 + b 2 ≡ a
(mod p k )
⇔
2 · b · i · p k−1 + j · p k−1 + a ≡ a
(mod p k )
⇔
2 · b · i · p k−1 ≡ −j · p k−1
(mod p k )
50 / 96
Quadratische Reste
Wegen ZTK (Korollar 6.3) folgt:
2 · b · i · p k−1 ≡ −j · p k−1
(mod p k )
2 · b · i ≡ −j
(mod p)
⇔
⇔
⇔
i ≡ −j · (2 · b)−1
i · p k−1 ≡ −j · (2 · b)−1 p k−1
(mod p)
(mod p k )
Also ist x = (−j · (2 · b)−1 ) · p k−1 + b eine Quadratwurzel von a
modulo p k
Quadratische Reste
51 / 96
Eindeutigkeit von x: Angenommen, es gibt zwei verschiedene x1 und
x2 . die beide die Eigenschaften des Satzes erfüllen.
Wegen (2) gilt x1 = i1 · p k−1 + b und x2 = i2 · p k−1 + b für zwei
verschiedene ganze Zahlen i1 und i2
Wegen (1) folgt:
x12
⇔ (i1 · p k−1 + b)2
⇔ 2 · b · p k−1 · i1
⇔
2 · b · i1
i1
≡
≡
≡
≡
≡
x22
(i2 · p k−1 + b)2
2 · b · p k−1 · i2
2 · b · i2
i2
(mod
(mod
(mod
(mod
(mod
pk )
pk )
pk )
p)
p)
Widerspruch!
52 / 96
Quadratische Reste
Satz. Sei p eine ungerade Primzahl, k > 0 eine ganze Zahl und a
k
2
k
eine ganze Zahl mit gcd(a,
p) = 1. Die Kongruenz y ≡ a (mod p )
hat keine Lösungen, falls pa = −1, und genau zwei Lösungen, falls
a
= 1.
p
Beweis. Induktion über k und Verwendung des vorheriges Satzes
Quadratische Reste
53 / 96
Zusammengesetzte Zahlen
Satz. Sei n > 1 eine ungerade ganze Zahl mit der
Primfaktorzerlegung
Ỳ e
n=
pi i .
i=1
Angenommen, gcd(a, n) = 1.
Falls pai = 1 für alle i = {1, . . . , `} gilt, dann besitzt die Kongruenz
x2 ≡ a
(mod n)
genau 2` Lösungen modulo n. Andernfalls besitzt die Kongruenz
keine Lösung modulo n.
54 / 96
Quadratische Reste
Zusammengesetzte Zahlen (Forts.)
Beweis. Betrachte eine ungerade ganze Zahl n mit der
Primfaktorzerlegung
Ỳ `
n=
pi i .
i=1
e
Da gcd(piei , pj j ) = 1 für alle i 6= j gilt, folgt mit dem Chinesischen
Restsatz (ZTK (Satz 9.1)), dass
y2 ≡ a
(mod n)
genau dann lösbar ist, wenn
y2 ≡ a
(mod piei )
für alle i = 1, . . . , ` lösbar ist
Quadratische Reste
55 / 96
Zusammengesetzte Zahlen (Forts.)
ei
2
Laut dem
vorherigen Satz ist y ≡ a (mod pi ) genau dann lösbar,
wenn pai = 1. In diesem Fall gibt es genau 2 Lösungen.
Angenommen, es ist pai = 1 für alle i = 1, . . . , `.
Es gibt 2` Möglichkeiten, die Teillösungen zu einer Lösung modulo n
zu kombinieren. Folglich gibt es 2` Lösungen
56 / 96
Quadratische Reste
Das Jacobi Symbol
Seien n > 0 eine ungerade ganze Zahl mit der Primfaktorzerlegung
n=
Ỳ
piei .
i=1
Sei a eine ganze Zahl. Das Jacobi Symbol
a
n
=
a
n
ist definiert als
Ỳ a ei
i=1
pi
Blum-Blum-Shub Generator
57 / 96
Definition
Aufbau Blum-Blum-Shub Generator
Der Blum-Blum-Shub (BBS) Generator ist ein (k, `)-Generator f , der
wie folgt aufgebaut ist.
Seien p, q zwei verschiedene (k/2)-bit Primzahlen mit p ≡ q ≡ 3
(mod 4). Definiere n = p · q.
Sei s0 ein quadratischer Rest modulo n. Definiere
2
si = si−1
mod n
zi = si mod 2
für alle i = 1, . . . , ` und f (s0 ) = (z1 , . . . , z` ).
Beachte: Anstatt eines quadratischen Rests s0 wählt man in der
2
Regel eine beliebige Zahl s−1 ∈ Z∗n und setzt s0 = s−1
mod n
58 / 96
Definition
Beispiel: Blum-Blum-Shub Generator
Sei p = 383, q = 503, n = p · q = 192649 und
s0 = 1013552 mod n = 20749.
Die ersten erzeugten 20 Bits sind:
i
si
zi
0 20749 −
1 143135 1
2 177671 1
3 97048 0
4 89992 0
5 174051 1
6 80649 1
i
7
8
9
10
11
12
13
si
54663
69442
186894
177046
137922
123175
8630
zi
1
0
0
0
0
1
0
i
14
15
16
17
18
19
20
si
114386
14863
133015
160065
45870
137171
48060
zi
0
1
1
1
0
1
0
59 / 96
60 / 96
Algorithmen
BBS Algorithmen
Initialisierung des Generators:
BBSInit(ninit , sinit )
Input: Modul ninit , Seed sinit
1 n := ninit
2
2 s := sinit mod n
Berechnung des nächsten Bits:
BBSGetBit()
Output: Pseudo-zufälliges Bit
2
1 s := s mod n
2 return s mod 2
Algorithmen
BBS Algorithmen (Forts.)
Berechnung des nächsten Bytes:
BBSGetByte()
Output: Pseudo-zufälliges Byte
1 b := 0
2 for i := 1 to 8 do
3
b := 2 · b + BBSGetBit()
4 return b
61 / 96
Sicherheitsbewertung
Beobachtung
Seien p und q zwei verschiedene ungerade Primzahlen. Sei n = p · q.
Für alle ganzen Zahlen a 6= 0 gilt:


0
falls gcd(a,


n)
> 1

a
a
1
a 
falls p = q = 1 oder pa = qa = −1
=
a

n
−1 falls ein Wert von p und qa gleich 1 und





der andere gleich −1 ist
Beachte: a ist ein quadratischer Rest modulo n falls
a
a
=
=1
p
q
Aus na = 1 kann man nicht folgern, dass a ein quadratischer Rest
modulo n ist
62 / 96
Entscheidungsproblem QR
Problem Quadratic Residues (QR)
Gegeben:
• Eine ganze Zahl n, die das Produkt zweier ungerader Primzahlen
p und q ist
• Eine ganze Zahl a ∈ Z∗n mit na = 1
Gefragt: Ist a ein quadratischer Rest modulo n?
Bemerkungen:
• Bis heute ist kein Polynomialzeit Algorithmus für QR bekannt
• Kann man n effizient faktorisieren, dann ist QR ebenfalls
effizient lösbar
63 / 96
Monte Carlo Algorithmen
Ein Monte Carlo Algorithmus A ist ein Algorithmus mit folgenden
Eigenschaften:
• A berechnet eine Funktion f : {0, 1}∗ 7→ {0, 1}
• A hat Zugriff auf einen Generator, der gleichverteilte Zufallsbits
liefert
• Das von A berechnete Ergebnis ist korrekt mit einer
Wahrscheinlichkeit von mindestens 12 + ε für ein ε > 0.
Formal: Für alle x ∈ {0, 1}∗ gilt:
1
+ε
2
Die Fehlerwahrscheinlichkeit von A auf Eingabe x ist
1
Prob[A(x) 6= f (x)] ≤ − ε
2
Prob[A(x) = f (x)] ≥
64 / 96
Monte Carlo Algorithmen (Forts.)
MajorityA(x , n)
Input: Wort x ∈ {0, 1}∗
Output: 0 oder 1
1 y := 0
2 for i := 1 to n do
3
if A(x) = 1 then
4
y := y + 1
5 if y ≥ n/2 then
6
return 1
7 else
8
return 0
65 / 96
Satz. Angenommen, A ist ein Monte Carlo Algorithmus mit einer
Fehlerwahrscheinlichkeit von höchstens 12 − ε. Sei n = 2m + 1 für
eine ganze Zahl m > 0.
Dann ist MajorityA(·, n) ein Monte Carlo Algorithmus mit einer
Fehlerwahrscheinlichkeit von höchstens
(1 − 4ε2 )m
2
66 / 96
Beweis. Sei x ∈ {0, 1}∗ .
Die Wahrscheinlichkeit, dass A(x) exakt i-mal ein korrektes Ergebnis
liefert, ist
i n−i
n
1
1
+ε
−ε
i
2
2
Die Wahrscheinlichkeit, dass MajorityA(x, n) nicht korrekt ist, ist:
Prob[Fehler] ≤
m X
n
1
i=0
i
i 2m+1−i
1
+ε
−ε
2
2
= #
67 / 96
m+1 X
m−i
m 1
−ε
1
n
2
−ε
1
2
i
+ε
i=0
| 2 {z
}
1
+ε
2
m 1
+ε
2
m 1
2
1
+ε
2
m 1
2
# =
≤1
=
=
m+1 X
m n
−ε
i
i=0
m+1
−ε
22m
= #
68 / 96
m 1
1
1
+ε
−ε
− ε 22m
2
2
2
m 1
1
− ε2
− ε 22m
4
2
m
1 − 4ε2
1
− ε 4m
4
2
1
m
1 − 4ε2
−ε
2
(1 − 4ε2 )m
2
# =
=
=
=
≤
69 / 96
Anwendung des Satzes: Angenommen, die Fehlerwahrscheinlichkeit
von A soll auf einen Wert 0 < γ < 12 − ε verkleinert werden.
Dann muss m so gewählt werden, dass
(1 − 4ε2 )m
≤γ
2
Hieraus folgt:
1 + log2 γ
m=
log2 (1 − 4ε2 )
70 / 96
Sicherheit des BBS-Generators
Es gilt:
ein (k, `)-bit BBS Generator ist ε-unterscheidbar von µu
⇓
es gibt einen (ε/`) Previous Bit Predictor für
den (k, `)-bit BBS Generator
⇓
es gibt einen Monte Carlo Algorithmus für QR mit einer
Fehlerwahrscheinlichkeit von höchstens 21 − ε`
⇓
es gibt einen Monte Carlo Algorithmus für QR mit einer
Fehlerwahrscheinlichkeit von höchstens γ für alle γ > 0
71 / 96
Sicherheit des BBS-Generators (Forts.)
Vermutung: Es existiert kein Monte Carlo Algorithmus für QR mit
einer Fehlerwahrscheinlichkeit von höchstens γ für alle γ > 0
Konsequenz: Ein (k, `)-bit BBS Generator ist nicht ε-unterscheidbar
von der Gleichverteilung für alle ε > 0
Sicherheitsanforderung: Die Primzahlen p und q sowie der Seed
müssen geheim gehalten werden
Bemerkung: Der BBS-Generator ist selbst dann noch sicher, wenn
log2 log2 k Bits in einem Schleifendurchlauf abgreift
72 / 96
Fortuna Pseudo Random Number Generator
Einleitung
•
•
•
•
Entwicklung von Niels Ferguson und Bruce Schneier
Weiterentwicklung des Yarrow PRNG
Prinzip: Block Chiffre im Counter Mode
Interner Zustand:
. 256 bit Schlüssel einer Blockchiffre
. 128 bit Zähler
• Fortuna erzeugt beliebig lange Byte Folgen
• Einsatz von AES und SHA-256 zur Verarbeitung des internen
Zustands
• Ebenfalls geeignet: Serpent und Twofish
73 / 96
Eigenschaften
Eigenschaften
• Um zu verhindern, dass ein Angreifer anhand des internen
Zustands Informationen über bereits erzeugte Byte-Folgen
erlangen kann, wird der Schlüssel nach jeder Erzeugung
gewechselt
• Um zu garantieren, dass die erzeugte Byte-Folge statistisch
zufällig aussieht, wird die Anzahl Bytes, die in einem Aufruf
erzeugt werden können, auf 220 = 1048576 beschränkt
• Regelmässiges Reseeding verhindert, dass ein Angreifer anhand
des internen Zustands zukünftige Byte-Folgen berechnen kann
74 / 96
Counter Mode
Counter Mode
Aufgabe: Erzeugen eines Bitstroms unter Einsatz einer Blockchiffre
Gegeben: Block Chiffre E , Schlüssel k, Klartext x1 , . . . , x` bestehend
aus ` Blöcken, Initialisierungswert n
Verschlüsselung: Zwei Schritte: Für i = 1, . . . , `:
1. Berechne Blockschlüssel ki = E (k, n||i)
2. Berechne Geheimtextblock yi = xi ⊕ ki
Ergebnis: Geheimtext y1 , . . . , y`
75 / 96
Counter Mode
Bemerkungen zum Counter Mode
• Die Wortlänge von n und i orientiert sich an der Blocklänge des
Kryptosystems E
• Ist die Anzahl der zu verschlüssenden Blöcke nicht bekannt,
dann wird i als interner Zähler implementiert, der nach jeder
Verschlüsselung inkrementiert wird
• Die Kombination aus Schlüssel k und Initialwert Nonce darf nur
einmal benutzt werden
• Die Laufzeit des Counter Modes hängt im Wesentlichen von der
eingesetzten Blockchiffre E ab
76 / 96
Counter Mode
Aufbau des Initialisierungswerts
Beispiel. Block Chiffre mit einer Blocklänge von 128 Bit
Parameterwahl für den CTR Mode:
• Initialisierungswert, zusammengesetzt aus:
. Message ID (48 bit)
Vergabe anhand der zu
übertragenden Nachricht
. Nonce (16 bit)
einmal zu verwendendes Wort
• Counter (64 bit)
Ergebnis:
• Pro Schlüssel können 248 verschiedene Nachrichten verschlüsselt
werden
• Die Länge einer Nachricht ist beschränkt auf höchstens 264 Byte
77 / 96
Interner Zustand
Interner Zustand von Fortuna
Fortuna besitzt einen internen Zustand bestehend aus
• Schlüssel key (256 bit)
• Zähler cntr (128 bit)
Der Zähler cntr wird entweder als Byte Array oder als natürliche
Zahl in Least Significant Byte First (LSBF) Darstellung interpretiert.
Ist cntr in dem Byte-Block p0 , . . . , p15 abgespeichert, dann berechnet
man die zugehörige Zahl als
cntr =
15
X
pi · 28i
i=0
78 / 96
Algorithmen
Initialisierung
InitializeGenerator()
Output: G = (key, cntr ) Initialwerte für Schlüssel und Zähler
1 key := 0
2 cntr := 0
3 G := (key, cntr )
4 return G
Beachte: Nach der Initialisierung ist der PRNG nicht einsatzbereit
79 / 96
Algorithmen
Reseeding
Reseed(G, s)
Input: Interner Zustand G = (key, cntr ), Seed s
1 key := SHA-256(key||s)
2 cntr := cntr + 1
Beachte: Der interne Zustand wird während des Reseedings
verändert
80 / 96
Algorithmen
Generierung von 16-Byte-Blöcken
GenerateBlocks(G, k )
Input: Interner Zustand G = (key, cntr ),
Anzahl k der zu generierenden Blöcke
Output: r Pseudo-Zufallsfolge mit 16k Bytes
1 if cntr = 0 then
2
error PRNG wurde nicht korrekt initialisiert.“
”
3 r := ε
4 for i := 1 to k do
5
r := r ||AES(key, cntr )
6
cntr := cntr + 1
7 return r
Beachte: Der interne Zustand wird während der Generierung
verändert
81 / 96
Algorithmen
Generierung von beliebigen Byte-Folgen
PseudoRandomData(G, n)
Input: Interner Zustand G = (key, cntr ),
Anzahl n der zu generierenden Bytes
Output: Pseudo-Zufallsfolge r mit n Bytes
20
1 if n < 0 or n > 2
then
2
error Inkorrekte Länge.“
n
”
3 b := GenerateBlocks(G,
)
16
4 r := erste n Bytes von b
5 key := GenerateBlocks(G, 2)
6 return r
Beachte: Der interne Zustand wird während der Generierung
verändert
82 / 96
Algorithmen
Bemerkungen zu PseudoRandomData()
• Die Länge der erzeugten Byte-Folge wird beschränkt, um
statistische Abweichungen zu echten Zufallsfolgen zu vermeiden
• Der Schlüssel wird erneuert, um zu verhindern, dass man die
erzeugte Zufallsfolge rekonstruieren kann
• Um ein Datenleck zu verhindern, sollte die Implementierung
. keine Kopie von r zwischenspeichern und
. den für b und r benutzten Speicher überschreiben
• Eine Folge mit mehr als 220 Bytes kann durch wiederholtes
Ausführen von PseudoRandomData() erzeugt werden
83 / 96
Akkumulator
Akkumulator
Aufgabe: Sammeln von echten Zufallsdaten, die zum Reseeding
eingesetzt werden
Idee: Je mehr Quellen beim Reseeding berücksichtigt werden, desto
geringer ist die Chance, dass ein Angreifer den neuen Seed berechnen
kann
Umsetzung: Der Akkumulator wird in den Generator integriert
Mögliche Zufallsquellen:
• Dauer von Tastaturklicks
• Mausbewegungen und -klicks
• Zugriffszeit einer Festplatte
• Internet Zugriffe (Pings, etc.)
84 / 96
Akkumulator
Zufallsquellen und Random Pools
Eigenschaften einer Zufallsquelle:
• Jede Quelle erhält eine eindeutige Nummer aus {0, . . . , 255}
• Eine Quelle liefert als Event eine kleine Anzahl echt zufälliger
Bytes zurück
• Es besteht die Möglichkeit, mehrere Events zu einer längeren
Byte-Folge zu konkatenieren
Random Pools
• Es gibt 32 Pools, die mit P0 , P1 , . . . , P31 bezeichnet werden
• Jeder Pool liefert eine Byte-Folge unbeschränkter Länge
• Diese Folge wird durch wiederholte Anwendung einer
kryptografischen Hashfunktion berechnet
85 / 96
Akkumulator
Ablauf des Reseedings
• Die Daten einer Quelle werden zyklisch über alle Pools verteilt
• Bei Zuteilung einer Quelle an den Pool Pi wird der Event an die
Daten von Pi angehängt
• Das Reseeding wird durchgeführt, wenn P0 genügend Daten
vorrätig hat
• Die Reseedings werden mit r = 1, 2, 3, . . . durchnummeriert
• Pool Pi wird beim Reseeding r berücksichtigt, wenn 2i ein Teiler
von r ist
• Konsequenz: P0 wird immer benutzt, P1 wird jedes zweite Mal
benutzt, P2 wird jedes vierte Mal benutzt, usw.
• Wird ein Pool Pi zum Reseeding benutzt, dann werden
anschließend seine Daten gelöscht
86 / 96
Akkumulator
Sicherheitsbetrachtung
Angriffspunkte:
• Der Angreifer hat Zugriff auf mehrere (aber nicht alle) Pools
• Der Angreifer kann selbst gefälschte Events einschleusen
Ansatz:
• Da der Pool Pi nur jedes 2i -te Mal benutzt wird, um so mehr
Daten hält er vor
• Falls es eine Zufallsquelle gibt, die der Angreifer nicht kennt,
dann gibt es immer einen Pool, der genügend Daten sammelt,
die gegen einen Angriff resistent sind
• Das System erholt sich von einer Kompromittierung innerhalb
von einer kurzen Zeit von selbst
87 / 96
88 / 96
PRNG mit Akkumulator
Initialisierung
InitializePRNG()
Output: Interner Zustand R
1 for i := 0 to 31 do
2
Pi := ε
3 reseed cntr := 0
4 G := InitializeGenerator()
5 R := (G, reseed cntr , P0 , . . . , P31 )
6 return R
Generierung von Byte-Folgen
RandomData(R, n)
Input: Interner Zustand R = (G, reseed cntr , P0 , . . . , P31 )
Anzahl n der zu generierenden Bytes
Output: Pseudo-Zufallsfolge mit n Bytes
1 if length(P0 ) ≥ min pool size and last reseed > 100ms then
2
reseed cntr := reseed cntr + 1
3
s := ε
4
for i ∈ {0, 1, . . . , 31} do
5
if 2i | reseed cntr then
6
s := s||SHA-256(Pi )
7
Pi := ε
8
Reseed(G, s)
9 return PseudoRandomData(G, n)
89 / 96
Hinzufügen eines Events
AddRandomEvent(R, s, i, e)
Input: Interner Zustand R,
Nummer der Quelle s ∈ {0, 1, . . . , 255},
Nummer des Pools i ∈ {0, 1, . . . , 31},
Daten des Events e (Folge von höchstens 32 Bytes)
1 if 1 ≤ length(e) ≤ 32 and 0 ≤ s ≤ 255 and 0 ≤ i ≤ 31 then
2
Pi := Pi ||s||length(e)||e
3 else
4
error Fehlerhafte Parameter“
”
90 / 96
Seed Dateien
Anlegen einer Seed Datei
Problem: Nach dem Booten des Rechners ist der PRNG nicht in der
Lage, gute Zufallszahlen zu erzeugen, da zu wenige Events vorliegen
Vorschlag:
• Abwarten, bis sich der Pool gefüllt hat
• Auslesen eines guten Seeds aus einer Datei, die beim
Herunterfahren gespeichert wurde
Sicherheitsvorkehrungen: Der Inhalt der Seed Datei
• muss geheim gehalten werden
• darf nur einmal benutzt werden
91 / 96
92 / 96
Seed Dateien
Lesen und Schreiben der Seed Datei
WriteSeedFile(R, f )
Input: Interner Zustand R, Datei Handle f
1 write RandomData(G, 64) to f
UpdateSeedFile(R, f )
Input: Interner Zustand R, Datei Handle f
1 read f to s
2 if length(s) < 64 then
3
error Zu wenig Daten für Reseed“
”
4 Reseed(G, s)
5 write RandomData(G, 64) to f
Seed Dateien
Bemerkungen zu Seed Dateien
• Die Seed Datei sollte bei Start des Systems gelesen werden
• Beim Herunterfahren des Rechners muss ein Update der Seed
Datei erfolgen
• Es empfiehlt sich, die Seed Datei regelmäßig zu aktualisieren
• Vorsicht ist beim Backup eines Systems geboten, da man damit
die Seed Datei wieder herstellen kann
• Eine weitere Gefahr besteht darin, dass in der Regel die Daten
nicht sofort auf die Festplatte geschrieben werden. Dies kann zu
Inkonsistenzen führen
• Bei der Installation eines Computers muss darauf geachtet
werden, dass die Seed Datei beim ersten Reboot nicht benutzt
wird oder dass eine geeignete Datei erstellt wird
Abschließende Bemerkungen
93 / 96
Hinweise zur Arbeit mit PRNGs
Hinweise zur Arbeit mit PRNGs
• Die PRNGs von Programmiersprachen und Betriebssystemen
erfüllen in der Regel nicht die Anforderungen an einen
kryptografisch sicheren Pseudo-Zufallszahlengenerator
• Gute Quellen mit hoher Entropie sind oft schwer zu finden.
Daher sollten möglichst viele Quellen angezapft werden. Fortuna
ist gegen schlechte Quellen immun
• Der Einsatz von Seed Dateien ist einfach zu verstehen, aber
schwierig zu implementieren. In der Regel sind Eingriffe in das
Betriebssystem und sogar in die Firmware der Komponenten
notwendig, um die Implementierung sicher zu gestalten
94 / 96
Abschließende Bemerkungen
Generierung von Zahlen
Generierung von gleichverteilten Zahlen
Aufgabe: Generiere unter Gleichverteilung eine Zahl
x ∈ {0, 1, . . . , n − 1}, wobei n eine natürliche Zahl und keine
Zweierpotenz ist
Ansatz 1: Generiere zufällig eine Zahl y ∈ {0, 1, . . . , 2dlog2 ne − 1} und
berechne x = y mod n
Ergebnis: die resultierende Verteilung ist keine Gleichverteilung und
somit nicht sicher
Ansatz 2: Generiere solange zufällig eine Zahl
x ∈ {0, 1, . . . , 2dlog2 ne − 1}, bis x ∈ {0, 1, . . . , n − 1}
Ergebnis: Die resultierende Verteilung ist eine Gleichverteilung, aber
es sind gelegentlich mehrere Versuche notwendig, bis eine Zufallszahl
vorliegt
95 / 96
Zusammenfassung
Zusammenfassung
• Die Kryptografie stellt hohe Anforderungen an
Pseudo-Zufallszahlengeneratoren
• Der Blum-Blum-Shub Generator gilt als der sicherste PRNG
• Fortuna ist ein PRNG, der auf AES im Counter Mode basiert
• Zufallsquellen mit hoher Entropie verbessern die Qualität der
Zufallszahlen von Fortuna
• Für weitere Informationen zum Thema Zufallszahlen empfiehlt
sich RFC 4086 (Randomness Requirements for Security) der
Internet Engineering Task Force (IETF)
96 / 96

Handouts - Prof. Dr. Christoph Karg

Transcrição

Documentos relacionados

heute tagesessen heute tagesessen heute

01 SPGT SP 20150829 Prod-Nr 26241 Seite 9 28. 8. 2015 20:25:13

a... chter märz internationaler frauentag 2008

47 Sportförderungsrichtlinien der Stadt Aalen

medizinalfachberufe (ba) medizinalfachberufe

Ausgabe 3 - 2013 - Lebenshilfe Aalen

Mod. ASP-1

Hochschule Aalen- Technik und Wirtschaft

Presse - Theater der Stadt Aalen

So erreichen Sie uns - Portal Diakonie Stetten

Cosma Shiva – einfach lovely!

Informationen für die Eltern Wir wünschen euch eine schöne