Snl Restklassen In Der Praxis

Front 1

Restklasse

Back 1

Sei u ∈ ℕ \ {0} beliebig. Für die Äquivalenzklassen der Relation
R = {(a, b) ∈ ℕ x ℕ | a ≡ b (mod u)}
schreiben wir auch: [x]ᵤ
Wir nennen diese Äquivalenzklassen Restklassen. R unterteilt ℕ in diese Restklassen.

Man schreibt ℤᵤ für die Menge aller Restklassen mod u.

Alle Elemente einer Restklasse haben den gleichen Rest bei Division durch u.
Die u Restklassen haben offensichtlich keine gemeinsamen Elemente.

Die Verknüpfungen + und · in der Menge ℕ respektieren die Äquivalenzklasseneinteilung der modulo-Relation. Sie sind daher auch als Verknüpfungen in der Menge der Restklassen definiert.

{engl. residue class}

Front 2

Die Menge aller Restklassen mod u (ℤᵤ) bilden einen Körper, wenn ...

Back 2

... u eine Primzahl ist.

Für alle zusammengesetzten Zahlen u gibt es dagegen Elemente in ℤᵤ OHNE multiplikatives Inverses: Nämlich die Elemente [n]ᵤ, für die gilt: ggT(n,u) ≠ 1.

Hinweis: In einem Körper kann man Gleichungen mit Addition und Multiplikation lösen. Deshalb gibt es z.B. sicher eine Lösung (nämlich 4) für:
3 · x ≡ 2 (mod 5)
Wenn u keine Primzahl ist, gibt es dagegen nicht für alle Gleichungen eine Lösung. Bsp:
3 · x ≡ 2 (mod 6)

Front 3

−4 mod 5 =

Back 3

1

Bei positiven Zahlen kann man sagen, man zieht 5 ab, bis man im Bereich {0, 1, 2, 3, 4} ist.
Bsp: 13 − 2·5 = 3

Bei negativen Zahlen wird analog 5 addiert bis man im Bereich ist.
Bsp: −14 + 3·5 = 1

Front 4

3 + x ≡ 2 (mod 5)
auflösen nach x

Back 4

Zu beiden Seiten −3 addieren, damit links x übrigbleibt.
Es gilt: −3 ≡ 2 (mod 5)
Deshalb kann man 2 addieren.
x ≡ 2 + 2 (mod 5)
x ≡ 4 (mod 5)

Front 5

a ≡ b (mod q) ↔

Back 5

Wenn a und b kongruent sind modulo q, dann ist ihre Differenz ein ganzzahliges Vielfaches von q.

Bzw. q teilt die Differenz a − b:
q | a − b

Nützlich auch diese Schreibweise:
a = b + d · q

Front 6

Rechnen mit Restklassen

Back 6

Man will in ℤᵤ rechnen (d.h. mit den Restklassen [x]ᵤ).

Statt mit den Zahlen 0, ... , u − 1 kann man direkt mit Restklassen rechnen:
Zwei Restklassen werden z.B. addiert, indem man aus beiden Restklassen je ein beliebiges Element auswählt und die beiden Elemente addiert. Die Ergebnisrestklasse ist die, in der die so berechnete Zahl liegt.

Front 7

232 · 348 ≡ ? (mod 5)

Back 7

≡ 2 · 3 ≡ 6 ≡ 1 (mod 5)

Front 8

3^172 ≡ ? (mod 7)

Back 8

Wenn Exponent unhandlich, muss er in 2er-Potenzen zerlegt werden:
3^(128+32+8+4)
= 3^128 · 3^32 · 3^8 · 3^4

Exponenten immer ein Vielfaches von 2. Beim Aufschreiben einer vollständigen Tabelle braucht man für die nächste Zeile also bloss das Resultat (mod 7) der vorderen Zeile zu quadrieren:
3^2 = 9 ≡ 2 (mod 7)
3^4 ≡ 2^2 ≡ 4 (mod 7)
3^8 ≡ 4^2 ≡ 16 ≡ 2 (mod 7)
3^16 ≡ 2^2 ≡ 4 (mod 7)
3^32 ≡ 4^2 ≡ 16 ≡ 2 (mod 7)
3^64 ≡ 2^2 ≡ 4 (mod 7)
3^128 ≡ 4^2 ≡ 16 ≡ 2 (mod 7)

(Praktischerweise periodisch: Grösse des Moduls = maximale Anzahl Varianten bis zur periodischen Wiederholung. Hier schon vorher.)

Somit:
≡ 2 · 2 · 2 · 4 (mod 7)
≡ 32 (mod 7)
≡ 4 (mod 7)

(Solche Berechnungen braucht es in der Kryptographie. Mit Floats reicht die Präzision nicht, denn es geht ja um die hintersten Stellen.)

Front 9

7^6 ≡ ? (mod 5)

Back 9

Die Basis darf durch die Restklasse repräsentiert werden. D.h. statt 7 darf man 2 (mod 5) verwenden:
7^6 ≡ 2^6 (mod 5)
Weil 2 · 2 · 2 ≡ 3 (mod 5) gilt:
2^6 (mod 5) ≡ 3 · 3 ≡ 4 (mod 5)

Front 10

Addition von Restklassen

Back 10

[a]ᵤ + [b]ᵤ = [a + b]ᵤ

Man kann mit beliebigen Vertretern rechnen.

Front 11

Multiplikation von Restklassen

Back 11

[a]ᵤ · [b]ᵤ = [a · b]ᵤ

Man kann mit beliebigen Vertretern rechnen.

Front 12

Wann ist diese lineare diophantische Gleichung lösbar (a,b,c ∈ ℤ)?

ax + by = c

Back 12

Genau dann lösbar, wenn ggT(a,b) | c

Man sucht also zuerst den ggT(a,b) und prüft, ob er c teilt. Nur dann wird man Lösungen (x,y) finden können.
Unter dieser Voraussetzung liefert der erweiterte euklidische Algorithmus eine Lösung (eine der unendlich vielen).

Front 13

Solving a linear Diophantine equation (in two variables x and y).
a · x + b · y = c
(where a, b, c ∈ ℤ)

238x + 168y = 126

Back 13

238x + 168y = 126

Euklidischer Algorithmus (schwarze Zahlen):
ggT (rot) von a (238) und b (168) bestimmen:
Faktor q und Rest r herausfinden:
a = qb + r
Dann wird b zum nächsten a und r zum neuen b.

Der gefundene ggT 14 muss c, also 126, teilen. Nur dann hat die Gleichung Lösungen.

Erweiterter Euklidischer Algorithmus (blaue Zahlen):
Dann rechnet man von der untersten Zeile zurück und bestimmt x und y so, dass auf jeder Zeile gilt:
ax + by = ggT(a,b)
Unterste Zeile 0 und 1 einsetzen.
Ab der zweituntersten Zeile:
Das x der neuen oberen Zeile ist einfach das y der unteren (blauer Pfeil).
Das y der oberen Zeile wird aus dem x und y der unteren Zeile und dem q der oberen Zeile bestimmt (grün):
φ − λθ

Oberste Zeile löst
ax + by = ggT(a,b)
nämlich
238 · 5 + 168 · (−7) = 14

Lösung ursprüngliche Gleichung:
238 · (5 · 9) + 168 · (−7 · 9) = 14 · 9
238 · 45 + 168 · (−63) = 126
→ x = 45, y = −63

Wenn es eine Lösung gibt, dann gibt es unendlich viele, die daraus abgeleitet werden können.

Front 14

ALLE Lösungen einer diophantischen Gleichung ableiten, wenn man eine Lösung (x₀, y₀) gefunden hat.

ax + by = c

Back 14

Für beliebge i ∈ ℤ:
xᵢ = x₀ + i · b / ggT(a,b)
yᵢ = y₀ − i · a / ggT(a,b)

Front 15

Wie löst man das?

5x − 17y = −4

Back 15

Es wird als diophantische Gleichung geschrieben mit Pluszeichen:

5x + 17y = −4

Dann gefundene x und y mit −1 multiplizieren entsprechend gemachter Vorzeichen-Anpassung (betrifft hier nur y). So stimmt es wieder mit der originalen Gleichung.

Merken:
· Diophantische Gleichungen ohne negative Vorzeichen darstellen.
· Der erste Schritt beim Lösen der diophantischen Gleichung tauscht die 5 und 17, so dass die grössere Zahl vorne steht.

Eine der Lösungen:
x = −28
y = −8

Front 16

Inverses Element der Multiplikation für eine Restklasse bestimmen.

(allgemein)

Back 16

Gesucht: Das inverse Element 3⁻¹ zu 3 in ℤ₇.
Also: 3 · 3⁻¹ ≡ 1 (mod 7)
(1/3 ist eine andere Schreibweise für 3⁻¹)

Umwandlung:
3 · y ≡ 1 (mod 7)
3 · y = 1 + 7 · x
3 · y − 7 · x = 1
Das kann als diophantische Gleichung ausgedrückt und gelöst werden:
7x + 3y = 1
Das gefundene y ist dann ein Vertreter für die Restklasse, die als 3⁻¹ funktioniert.

Für dieses Beispiel findet man y = −2 und somit:
[3]₇⁻¹ = [−2]₇ = [5]₇

HINWEIS: Es gibt nur dann ein Inverses zu a, wenn a und das Modul m teilerfremd sind, also hier ggT(3,7)=1 ist. Nur dann hat die diophantische Gleichung eine Lösung.

Wozu? Der private Key im RSA ist ein multiplikatives Inverses!

Front 17

Inverses Element der Multiplikation für eine Restklasse bestimmen.

(einfacher Fall)

Back 17

Gesucht: Das inverse Element 9⁻¹ zu 9 in ℤ₁₀.

9 ≡ −1 mod 10
Das Inverse ist nun tatsächlich das Potenzieren mit −1. Angewendet auf beide Seiten:
9⁻¹ ≡ (−1)⁻¹ mod 10

Variante A: Man überlegt sich ganz einfach, was das multiplikative Inverse zu −1 ist: Womit muss man −1 multiplizieren, damit das neutrale Element 1 rauskommt?
→ Natürlich mit −1 selbst.

Variante B: Man darf stur ausrechnen:
(−1)⁻¹
= 1/(−1¹) = 1/−1 = −1

Das multiplikative Inverse 9⁻¹ zu [9]₁₀ ist also −1 bzw. die [9]₁₀ selbst:

9⁻¹ ≡ −1 ≡ 9 mod 10

Merke:
a⁻ⁿ = 1/aⁿ [für a ≠ 0]

Front 18

Division von Restklassen

Back 18

Multiplikation mit dem Inversen der Multiplikation des Divisors. Nur definiert wenn ℤᵤ ein Körper ist, d.h. u ist prim.

[4]₇ / [3]₇ = [4]₇ · [3]₇⁻¹ = [4]₇ · [5]₇ = [20]₇ = [6]₇

Front 19

Bestimme x:

20x ≡ 7 (mod 53)

Back 19

Man bestimmt das multiplikative Inverse für 20 (nämlich [8]₅₃) und multipliziert die Gleichung damit:

8·20x ≡ 8·7 (mod 53)
x ≡ 8·7 (mod 53)
x ≡ 56 ≡ 3 (mod 53)

Also ist x = [3]₅₃

Ein solche Gleichung ist nur dann eindeutig lösbar, wenn das Modul (hier 53) eine Primzahl ist.
Dagegen hat
3x ≡ 12 mod 87
mehrere Lösungen (4, 33 und 62), weil 87 nicht prim ist.

Front 20

ac ≡ bc mod m

Unter welcher Bedingung darf man diese Gleichung durch c dividieren?

Back 20

Nur wenn c und m teilerfremd sind, d.h. ggT(c, m) = 1.
Wenn das Modul m eine Primzahl ist, trifft das natürlich für alle c zu, d.h. Division erlaubt.

Addition, Subtraktion und Multiplikation sind beim Rechnen mit Restklassen nicht eingeschränkt. Aber die Division ist speziell.

Front 21

Diese spezielle diophantische Gleichung hat 1 auf der rechten Seite.
Wann ist sie lösbar?
Und warum ist das interessant?

ax + uy = 1

Back 21

Nur lösbar wenn a und u teilerfremd sind.
Grund: ggT(a,u) muss die rechte Seite (also 1) teilen.

Solche Gleichungen muss man lösen, um das multiplikative Inverse zu a beim Rechnen mit Modul u zu bestimmen.
Damit für jedes beliebige [a]ᵤ (Restklassen modulo u) eine Lösung existiert, muss (ℤᵤ, +, ·) ein Körper sein, d.h. u muss eine Primzahl sein.

Da die Gleichung multipliziert werden kann, ist jede beliebige ganze Zahl als Linearkombination von a und u darstellbar, wenn a und u teilerfremd sind!

Front 22

Was kann man über die Resultate r und u sagen?
r = a / ggT(a,b)
u = b / ggt(a,b)

Back 22

Die Resultate r und u sind teilerfremd.

Front 23

Chinesischer Restsatz

Back 23

x ≡ a mod m
x ≡ b mod n

1) Multiplikative Inverse i und k "übers Kreuz" bestimmen, so dass:
m · i ≡ 1 mod n
n · k ≡ 1 mod m
(Die Inversen existieren nur wenn n und m teilerfremd sind.)

2) x = a · n · k + b · m · i

3) Die unendlich vielen Lösungen sind:
x + z · m · n
für z ∈ ℤ beliebig

Beispiel:
Bei der Verteilung von x Gummibärchen auf 4 Leute bleiben 2 übrig. Bei der Verteilung auf 7 Leute bleiben 3 übrig. Bestimme x.

x ≡ 2 mod 4
x ≡ 3 mod 7

4 · i ≡ 1 mod 7 → i = 2
7 · k ≡ 1 mod 4 → k = 3

x = 2 · 7 · 3 + 3 · 4 · 2 = 66

Übrige Lösungen:
4 · 7 = 28
→ 66 + z · 28
66 + −2 · 28 = 10
66 + −1 · 28 = 38
66 + 1 · 28 = 94
66 + 2 · 28 = 122
etc.

{engl. Chinese Remainder Theorem}

Front 24

Wie findet man x mit:

x ≡ 6 (mod 9)
x ≡ 8 (mod 11)

Back 24

Chinesischer Restsatz. Oder alternativ so:

Mit k,m ∈ ℤ gilt:

x ≡ 6 (mod 9) → x = 6 + 9k
x ≡ 8 (mod 11) → x = 8 + 11m

6 + 9k = 8 + 11m
9k − 11m = 2

Diophantische Gleichung lösen:
9k + 11m = 2
→ k = 10, m = −8

Vorzeichen angepasst für ursprüngliche Gleichung:
k = 10
m = 8

Einsetzen in eine der ursprünglichen Gleichungen:
x = 6 + 9k
x = 6 + 9 · 10 = 96

Übrige Lösungen:
x + z · 9 · 11
für z ∈ ℤ beliebig

Front 25

Sei u eine beliebige Primzahl.
Was kann man über die Gleichung
a · x + b = c
sagen für beliebige a, b, c ∈ ℤᵤ mit a ≠ 0?

Back 25

Die Gleichung ist stets eindeutig lösbar.
Die eindeutige Lösung lautet:
x = a−¹ · (c − b)

Front 26

Prüfziffer für 10-stellige ISBN-Nummer
(ISBN-10)

Back 26

9 Ziffern plus 1 Prüfziffer.
Beispiel (Prüfziffer 5):
0-672-31208-5

d₁₀ = vorderste Ziffer
d₂ = letzte vor der Prüfziffer
d₁ = Prüfziffer

Zwei gleichwertige Formeln für Prüfziffer (kommt 10 raus, schreibt man X):

Variante 1:
[d₁]₁₁ = [1 · d₁₀ + 2 · d₉ + ... + 8 · d₃ + 9 · d₂]₁₁
(Modulo 11 der Summe der Ziffern d₁₀ bis d₂, wobei die Ziffern aufsteigend mit 1 bis 9 multipliziert werden.)

Variante 2:
[d₁]₁₁ = 11 − [10 · d₁₀ + 9 · d₉ + ... + 3 · d₃ + 2 · d₂]₁₁

Oder Validierung unter Einbeziehung der Prüfziffer:
[0]₁₁ = [10 · d₁₀ + 9 · d₉ + ... + 3 · d₃ + 2 · d₂ + 1 · d₁]₁₁

[ISBN = International Standard Book Number]

Front 27

Prüfziffer für 13-stellige ISBN-Nummer
(ISBN-13, eine EAN mit Prefix 978 oder 979)

Back 27

12 Ziffern plus 1 Prüfziffer.
Beispiel (Prüfziffer 4):
978-3-8006-4636-4

d₁₃ = vorderste Ziffer
d₂ = letzte vor der Prüfziffer
d₁ = Prüfziffer

Zwei gleichwertige Formeln für Prüfziffer:

Variante 1:
[d₁]₁₀ = [9 · d₁₃ + 7 · d₁₂ + ... + 9 · d₃ + 7 · d₂]₁₀
(Modulo 10 der Summe der Ziffern d₁₃ bis d₂, wobei die Ziffern abwechslungsweise mit 9 und 7 multipliziert werden.)

Variante 2:
[d₁]₁₀ = 10 − [1 · d₁₃ + 3 · d₁₂ + ... + 1 · d₃ + 3 · d₂]₁₀

Oder Validierung unter Einbeziehung der Prüfziffer:
[0]₁₀ = [1 · d₁₃ + 3 · d₁₂ + ... + 1 · d₃ + 3 · d₂ + 1 · d₁]₁₀

[EAN = European Article Number]

Front 28

Sei p ∈ ℕ eine Primzahl, a, b ∈ ℤ beliebig,
gerechnet mit Modul p

Back 28

Front 29

Eulersche Phi–Funktion

Back 29

φ(n) = |{a ∈ ℕ | 1 <= a <= n ^ ggT(a,n) =1 }|

n ∈ ℕ

Einfach die Anzahl Zahlen zwischen 1 und n (Grenzen eingeschlossen), die zu n teilerfremd sind. (Entspricht der Anzahl der Elemente mit multiplikativem Inversen in der Menge der Restklassen mod n.)
Verschiedene n können natürlich das gleiche φ ergeben.

φ(0) = |{}| = 0 (Konvention)
φ(1) = |{1}| = 1
φ(2) = |{1}| = 1
φ(3) = |{1, 2}| = 2
φ(4) = |{1, 3}| = 2
φ(5) = |{1, 2, 3, 4}| = 4

{engl. Euler's totient function (or phi function)}

Front 30

Eulersche Phi–Funktion einer Primzahl p?

Back 30

φ(p) = p − 1

Gilt nur wenn p prim ist.

Front 31

φ(m · n) = ?

Multiplikationsregel für Eulersche Phi–Funktion, unter diesen Bedingungen:
m, n ∈ ℕ \ {0]
ggT(m, n) = 1

Back 31

φ(m · n) = φ(m) · φ(n)

Gilt aber NICHT, wenn m und n nicht teilerfremd sind:
4 = φ(8) ≠ φ(2) · φ(4) = 1 · 2

Front 32

Wie wird die Eulersche Phi–Funktion für die n-te Potenz einer Primzahl p berechnet?

φ(p^n) = ?

p ∈ ℕ
n ∈ ℕ \ {0]

Back 32

Front 33

Eulersche Phi–Funktion für eine beliebige Zahl?
φ(n)

Back 33

φ(n) am Beispiel φ(12)

1) Primfaktorzerlegung von n:
12 = 2^2 · 3^1

2) Danach Regel für Eulersche Phi–Funktion für die n-te Potenz einer Primzahl p:
φ(2^2) = 2^(2 − 1) · (2 − 1) = 2
φ(3^1) = 3^(1 − 1) · (3 − 1) = 2

3) φ(m · n) = φ(m) · φ(n) anwenden:
φ(12) = φ(2^2) · φ(3^1) = 2 · 2 = 4

Front 34

Satz von Euler

Back 34

ggT(z, n) = 1
n ∈ ℕ \ {0} beliebig
z ∈ ℤ

Front 35

Summatorische Funktion der Eulerschen Phi-Funktion

Back 35

Wenn man alle Teiler d einer Zahl n nimmt, für jedes d φ(d) bestimmt und diese alle summiert, dann gibt das n.

12 hat diese Teiler:
1 2 3 4 6 12
φ(1) = 1
φ(2) = 1
φ(3) = 2
φ(4) = 2
φ(6) = 2
φ(12) = 4
Total 12

Front 36

Fermat’s Little Theorem

Der kleine Satz von Fermat

Back 36

Let a be an integer and p be a prime.

Das ist einfach ein Spezialfall des Satzes von Euler, nämlich wenn das Modul p eine Primzahl ist und damit φ(p) immer gleich p − 1.

Beispiele:
8^13 ≡ 8 mod 13
29^(13 − 1) ≡ 1 mod 13

Kann für die Berechnung hoher Potenzen mod p verwendet werden, indem man den Exponenten entweder mit p − 1 (Resultat ist 1) oder p (Resultat ist a) ausdrückt.

x ≡ 7^987654321 mod 11
≡ 7^(10 · 98765432 + 1) mod 11
≡ 7^(10 · 98765432) · 7^1 mod 11
≡ (7^10)^98765432 · 7^1 mod 11
≡ 1^98765432 · 7^1 mod 11
≡ 1 · 7^1 mod 11
≡ 7 mod 11

Erinnerung: Die Basis (nicht der Exponent!) darf durch die Restklasse repräsentiert werden.

Front 37

Anwendung von Fermats kleinem Satz, um das multiplikative Inverse a⁻¹ zu einer Zahl a bezüglich Restklasse p (prim) zu berechnen.

Back 37

Die Gleichung aus Fermats kleinem Satz wird umgewandelt, indem man zuerst ein a aus der Potenz herausholt (obere Gleichung) und dann mit dem Inversen zu a (a⁻¹) multipliziert (untere Gleichung).

Inverses zu [2]₅
≡ 2^(5 − 2) ≡ 2^3 ≡ 8
≡ 3 mod 5
Somit: [3]₅ ist das Inverse zu [2]₅

Wenn p nicht gross ist, kann dies der schnellere Weg sein als der erweiterte Euklidische Algorithmus, um das multiplikative Inverse von a zu berechnen.

Front 38

Vereinfache!

Back 38

Wenn ggT(a,n) = 1, dann gilt die Gleichung auf dem Bild für alle k ≥ 1.

Bsp:
4^1007 mod 5

φ(5) = 4 (5 ist prim)

Somit:
4^(1007 mod 4)
≡ 4^3
≡ 64
≡ 4 (mod 5)

Oder in diesem Fall kann die Basis a auch trivial im Modul 5 ausgedrückt werden:

4 ≡ −1 (mod 5)

Und damit:

4^1007

≡ (−1)^1007

≡ −1

≡ 4 mod 5

Front 39

The Fermat test for primality

Back 39

In Fermat's little theorem, if p is not prime, then, in general, most of the numbers a < p will not satisfy the above relation.

Algorithm for testing primality:
Given a candidate number p, pick a random number a < p and compute the remainder of a^p modulo p.
If the result is not equal to a, then p is certainly not prime.
If it is a, then chances are good that n is prime.
Now pick another random number a and test it with the same method. If it also satisfies the equation, then we can be even more confident that n is prime.

Front 40

Aus φ(x) wieder x zurückgewinnen?

Back 40

Das φ(x) in Faktoren zerlegen und solche Ausdrücke mit Primzahlen p anstreben:

p − 1
wegen φ(p) = p − 1

p · (p − 1)
wegen φ(p^2) = p^(2 − 1) · (p − 1)

Beispiel:
φ(x) = 660 = 2 · 2 · 3 · 5 · 11
Faktoren kombinierbar zu:
6 · 10 · 11
6 = φ(7)
10 · 11 = φ(11^2)
→ x = 7 · 11^2 = 847
wegen φ(m · n) = φ(m) · φ(n)
Beachte: Das ist nur eins der möglichen x. Eine andere Lösung wäre z.B. die Primzahl 661.

Front 41

Der grosse Satz von Fermat

Back 41

a^n + b^n = c^n

a, b, c ∈ ℤ
n ∈ ℕ

"Es gibt keine a,b,c ≠ 0, welche diese Gleichung lösen für n ≥ 3"

Es dauerte 300 Jahre, um einen (komplexen) Beweis zu finden...

Front 42

Wie prüft man, ob diese Aussage wahr ist?

Back 42

1) Das Modul 49 ist keine Primzahl (also kleiner Fermat nicht anwendbar)

2) Aber 37 und 49 sind teilerfremd. Deshalb Satz von Euler anwendbar.

3) Man berechnet φ(49) und bekommt 42.

4) Exponent 8442126 so aufteilen, dass φ(49) als Faktor vorkommt:
8442126 = 42 · 201003

5) Satz von Euler:
37^φ(49) ≡ 1 mod 49
Somit:
(37^φ(49))^201003 − 1
≡ 1^201003 − 1
≡ 1 − 1
≡ 0 mod 49
Die Aussage stimmt!

Front 43

x = 5^254 mod 196

Back 43

1) Das Modul 196 ist keine Primzahl (also kleiner Fermat nicht anwendbar)

2) Aber 5 und 196 sind teilerfremd. Deshalb Satz von Euler anwendbar.

3) Man berechnet φ(196) und bekommt 84.

4) Exponent aufteilen, so dass φ(196) als Faktor vorkommt:
254 = 84 · 2 + 2

5) Satz von Euler:
5^84 = 5^φ(196) ≡ 1 mod 196
Somit:
x = 5^254
≡ 5^(84 · 2 + 2)
≡ (5^84)^2 · 5^2
≡ 1^2 · 5^2
≡ 25 mod 196

Front 44

Der RSA ist ...

Back 44

... ein asymmetrisches Verschlüsselungsverfahren, von Ron Rivest, Adi Shamir und Leonard Adleman.

Alice verteilt ihren public Key. Jeder kann ihr damit verschlüsselte Daten senden. Nur mit dem private Key von Alice können diese Daten entschlüsselt werden.

Will Bob von Alice Daten empfangen, braucht er selbst ein eigenes private/public Key Paar.

Vorteil: Kein Austausch eines geheimen Schlüssels nötig!

Normalerweise nicht zur Verschlüsselung grosser Messages verwendet, sondern zur Verschlüsselung eines symmetrischen Keys, der mit RSA sicher ausgetauscht wird. Die eigentliche Payload wird mit einem symmetrischen Verfahren verschlüsselt.

Front 45

RSA Key Generierung

Back 45

1) Wähle zufällig (!) zwei grosse Primzahlen p und q (100 und mehr Stellen)

2) Bilde das RSA-Modul N = p · q (für Modulo Rechnung)

3) Bestimme φ(N) = φ(p · q) = φ(p) · φ(q) = (p − 1) · (q −1)
(Anwendung Eulersche Phi–Funktion)

4) Wähle eine Zahl e:
1 < e < φ(N) und ggT(e, φ(N)) = 1
(e also z.B. eine Primzahl)
Jetzt bilden (e, N) den öffentlichen Schlüssel.
Aber p, q und φ(N) bleiben geheim.

5) Wegen ggT(e, φ(N)) = 1 gilt: Es gibt ein multiplikatives Inverses d zu e beim Rechnen mit Modul φ(N).
e · d ≡ 1 mod φ(N)
↔ φ(N) | (e · d − 1)
↔ ∃z ∈ ℤ so dass φ(N) · z = e · d − 1
Somit: e · d − φ(N) · z = 1
Mit dem erweiterten Euklidischen Algorithmus diese lineare diophantische Gleichung lösen (y steht für −z):
e · d + φ(N) · y = 1
Die Unbekannten sind d und y, wobei y gar nicht interessiert.
Jetzt bilden (d, N) den privaten Schlüssel.

Basiert darauf, dass die Primfaktorzerlegung von N schwierig ist. Aus (e, N) können weder p und q noch φ(N) in nützlicher Frist bestimmt werden.

Front 46

RSA Verschlüsselung und Entschlüsselung

Back 46

T = Klartext
G = Geheimtext
(e, N) = öffentlicher Schlüssel
(d, N) = privater Schlüssel

Front 47

Beweis, dass RSA Verschlüsselung + Entschlüsselung wieder den Klartext ergibt.

(T^e)^d ≡ T (mod N)

T = Klartext
(e, N) = öffentlicher Schlüssel
(d, N) = privater Schlüssel

Back 47

z = beliebige, positive, ganze Zahl

Zeilen 1+2: Bekannt von Key Generierung.

Zeilen 3 bis 5: T verschlüsselt und entschlüsselt gibt wieder T. Übergang auf letzte Zeile erfordert Fallunterscheidung:
a) ggT(T, N) = 1
→ Satz von Euler:
T^φ(N) ≡ 1 (mod N)
b) ggT(T, N) = ggT(T, p · q) ≠ 1
→ T muss eine der Primzahlen p, q als Faktor enthalten (r < q und s < p). Aus beiden Varianten folgert jeweils, dass T teilerfremd mit dem anderen Faktor ist.
T = r · p → ggt(T, q) = 1
T = s · q → ggt(T, p) = 1
Mit Satz von Euler darf z.B. für die erste Variante gesagt werden:
T^φ(q) ≡ 1 (mod q)
bzw.
(T^φ(q))^z ≡ 1^z ≡ 1 (mod q)
Vorletzte Zeile wandeln bis man einsetzen kann:
(T^φ(N))^z
= (T^φ(p · q))^z
= (T^(φ(p) · φ(q))^z
= T^(φ(p) · φ(q) · z)
= T^(φ(q) · z · φ(p))
= (T^φ(q))^z)^φ(p)
≡ (1^z)^φ(p)
≡ 1^φ(p)
≡ 1 (mod q)
Von Definition Modulo q (u ein Integer):
(T^φ(N))^z = 1 + u · q
mal T
(T^φ(N))^z · T = T + T · u · q
= T + r · p · u · q
= T + r · u · p · q
= T + r · u · N
≡ T (mod N)
→ letzte Zeile

Front 48

Digitale Signatur

Back 48

Arbeitet mit RSA Verschlüsselung.
m = Message
s = Signatur
(e, N) = öffentlicher Schlüssel
(d, N) = privater Schlüssel

Signatur mit privatem Schlüssel:
s ≡ m^d (mod N)

Verifikation mit öffentlichem Schlüssel:
s^e ≡ m (mod N)

Front 49

RSA Message Grösse

Back 49

Since a message m is only unique up to the size of the modulus N, we cannot encrypt more than b bits with one RSA encryption, where b is the bit length of N.

Der binäre Wert für Message m muss kleiner sein als das Modul N, welches für private und public Key verwendet wird.
Sinnvollerweise ist die Zahl, welche m repräsentiert, auch grösser 1, da 1^e natürlich immer 1 wäre.

Front 50

43^7 mod 55 ohne Taschenrechner?

Back 50

43^7
≡ −12^7
≡ −12^4 · −12^2 · −12^1 (mod 55)

Es gilt:
12^2 = 144
≡ 34 ≡ −21 (mod 55)

Und weiter:
12^4 = 12^2 · 12^2
≡ (−21)^2 (mod 55)
= 21^2
= (20+1)^2
= 400 + 40 + 1
= 441
≡ 1 (mod 55)

Einsetzen:
43^7
= −(1) · −(−21) · −12
= −1 · 21 · −12
= 21 · 12
= 210 + 42
= 252
≡ 32 (mod 55)