ENDLICHE

KÖRPER

RSA – VERFAHREN

KÖRPER

Ein Körper K mit den zwei Operationen “+“ und “∙“ ist bestimmt durch:

1.Je zwei Elementen a, b ϵ K ist eindeutig ein Element a + b ϵ K zugeordnet, das Summe von a und b heißt.

2.Für a, b, c ϵ K gilt bezüglich “+“ das Assoziativgesetz: a + (b + c) = (a + b) + c

3.Es gibt ein Element 0 ϵ K, so daß für alle a ϵ K gilt: a + 0 = a

4.Zu jedem a ϵ K gibt es ein x ϵ K mit a + x = 0

5.Für a, b ϵ K gilt das Kommutativgesetz: a + b = b + a

6.Je zwei Elementen a, b ϵ K ist eindeutig ein Element a ∙ b ϵ K zugeordnet, das Produkt von a und b heißt.

7.Für a, b, c gilt bezüglich “∙“ das Assoziativgesetz: a(bc) = (ab)c

8.Es gibt ein Element 1 ϵ K ohne 0, sodass für alle a ϵ K gilt: a ∙ 1 = a

9.Zu jedem a ϵ K ohne 0 gibt es ein x ϵ K mit a ∙ x = 1.

10.Für a, b ϵ K gilt das Kommutativgesetz: ab = ba

11.Für a, b, c gilt das Distributivgesetz: (a + b)c = ac + bc

KÖRPERAXIOME

(K, +, ∙) ein Körper:

Bezüglich “+“:

Summe ist in K, Assoziativgesetz, Nullelement, Inverses, Kommutativgesetz

Bezüglich “∙“:

Produkt ist in K, Assoziativgesetz, Einselement, Inverses, Kommutativgesetz

Distributivgesetz

AUFGABE

Überlegt euch kurz, welche Körper ihr schon kennt, ohne

möglicherweise davon gehört zu haben, dass es sich dabei

tatsächlich um solche handelt!

BEISPIELE

Körper der reellen, der rationalen und der komplexen Zahlen;

Was fällt euch bei diesen Beispielen auf?

Insbesondere im Hinblick auf die Anzahl der Elemente…

AUFGABE

Könnt ihr euch vorstellen, dass es auch Körper mit

endlich vielen Elementen geben kann?

Versucht einen solchen zu identifizieren oder zu

“konstruieren“!

ENDLICHE KÖRPER

WIE KOMMT MAN ZU DIESEN DOCH ETWAS UNGEWÖHNLICHEN

ERGEBNISSEN?

Auf einer normalen Uhr haben wir 12 Zahlen (Elemente).

Wenn wir so rechnen, wie wir es gerade gemacht haben, so erhalten wir

Folgendes:

4 + 10 = 14 “=“ 2

Ein weiteres Beispiel: 8 + 9 = 17 “=“ 5.

Bezüglich “∙“ analog;

AUFGABE

Wie kommt man dazu 14 mit 2 und 17 mit 5

gleichzusetzen?

Welche Rechnung beziehungsweise formale Überlegung

könnte dazu führen?

Wie man relativ leicht erkennt, erhält man die beiden

Gleichsetzungen ganz einfach dadurch, dass man das vorläufige

Ergebnis der Rechnung durch 12, das heißt durch die Anzahl

der „Elemente“ der Uhr, dividiert und den erhaltenen Rest

anschreibt.

AUFGABE

Ist es Zufall, dass es am Beispiel der Uhr bei diesen beiden

Rechnungen immer die Zahl 12 ist, durch die man dividiert, oder

könnte man dies sogar als allgemeine „Regel“ sehen?

Findet heraus, ob es sich mit dem Rechnen auf der Uhr immer

so verhält!

MODULORECHNUNG

Wir haben ja 14 mit 2 und 17 mit 5 gleichgesetzt - im Bezug auf die Uhr

und deren 12 Elemente.

MODULOSPRECH- UND -SCHREIBWEISE

14 und 2 sind kongruent modulo 12, symbolisch: 14 ≡ 2 (12)

17 und 5 sind kongruent modulo 12, symbolisch: 17 ≡ 5 (12)

Damit können wir dies ganz allgemein formulieren:

DEFINITION

Seinen a, b beliebige ganze Zahlen, m ϵ N, dann heißen a und b kongruent

modulo m, symbolisch a ≡ b (m), wenn m│a – b;

d. h. a – b = km bzw. a = b + km für eine natürliche Zahl k;

DEFINITION

Sind a, b ganze Zahlen, dann sagt man a teilt b, symbolisch a│b, wenn

b = ka für eine natürliche Zahl k, wenn nicht: a┼b.

BEISPIELE

•24 ≡ 6 (9), denn 9 │24 – 6 = 18

•14 ≡ -1 (5), denn 5 │14 – (-1) = 15

•6 ≡ 0 (3), denn 3│6 – 0 = 6

•29 ≡ 5 (12), denn 12│29 – 5 = 24

ZURÜCK ZU DEN ENDLICHEN KÖRPERN

Im Bezug auf das gerade Erlernte:

Handelt es sich bei den folgenden Mengen in Verbindung mit den beiden

Operationen “+“ und “∙“ um Körper?

{0, 2, 4, 6, 8}

{1, 3, 5, 7, 9, 11}

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

{0, 1, 2, 3, 4}

WICHTIGE ERKENNTNISSE

i.a ≡ b (m) und a ≡ b (n) sowie ggT(m, n) = 1 → a ≡ b (m ∙ n)

ii.Die lineare Kongruenz ax ≡ b (m) ist genau dann lösbar, wenn ggT(a, m)│b.

Ist dies der Fall, dann gibt es genau d = ggT(a, m) modulo m inkongruente

Lösungen.

iii.Gilt a│b und a│c → a│b ± c

iv. Unter der primen Restklassengruppe modulo m versteht man

Mengen (plus Operation), die aus allen zu m teilerfremden

(d. h. ggT = 1) natürlichen Zahlen (exklusive “0“) < m bestehen.

Die Anzahl ihrer Elemente bezeichnet man mit φ(m).

z. B.:

prime Restklassengruppe modulo 12 = {1, 5, 7, 11}

prime Restklassengruppe modulo 7 = {1, 2, 3, 4, 5, 6}

Insbesondere gilt: φ(p) = p – 1 (für p Primzahl)

v. Sind m ϵ N, a ϵ Z mit ggT(a, m) = 1, dann gilt: aφ(m) ≡ 1 (m)

…… Euler

PRAKTISCHE NUTZUNG IM BEREICH

DER KRYPTOGRAPHIE

DAS RSA-VERFAHREN

GRUNDPRINZIP

Eine sehr große natürliche Zahl kann sehr schwer (bis gar nicht)

in entsprechender Zeit in ein Produkt von Primzahlen zerlegt

werden, selbst wenn man weiß, dass es sich nur um 2 Faktoren

handelt.

METHODE

Eine Nachricht soll von A nach B übermittelt werden.

Dazu wählt B zwei große Primzahlen p und q (verschieden),

bildet n = p ∙ q und wählt eine natürliche Zahl e > 1 mit

ggT(e, φ(n)) = 1.

B gibt n und e bekannt.

A will eine Nachricht übermitteln und übersetzt sie dazu in Zahlenform,

etwa: a = 1, b = 2, …, z = 26 (jeweils getrennt durch 00).

Sei w ϵ N die so erhaltene Zahl (Nachricht).

VERSCHLÜSSELUNG DURCH A

Die verschlüsselte Nachricht ist definiert als die kleinste

natürliche Zahl c ϵ N mit we ≡ c (n).

A gibt nun c ϵ N bekannt.

ENTSCHLÜSSELUNG DURCH B

Es gilt: w ist die kleinste natürliche Zahl, für die gilt:

w ≡ cd (n), wobei d ϵ N die positive Lösung der linearen

Kongruenz ex ≡ 1 (φ(n)) ist.

BEWEIS

Da n = p ∙ q und ggT(p, q) = 1, genügt es zu zeigen, dass w ≡ cd modulo p und

modulo q. Daraus folgt nämlich nach i.:

w ≡ cd modulo (p ∙ q) also modulo (n)

Zeige: w ≡ wed modulo p und modulo q, da wegen we ≡ c (n):

wed ≡ cd (n), also cd ≡ wed modulo p und modulo q.

Ad „modulo p“ („modulo q“ analog):

Gilt p│w, dann auch p│wed, also gilt nach iii.: p│wed – w;

d. h.: wed ≡ w (p); fertig;

Gilt p ┼ w, dann gilt ggT(p, w) = 1. Somit gilt nach v. (Euler) wφ(p) ≡ 1 (p),

das heißt nach iv. w(p-1) ≡ 1 (p).

Da ggT(e, φ(n)) = 1 hat die lineare Kongruenz ex ≡ 1 (φ(n)) nach ii. genau eine

positive modulo φ(n) inkongruente (bzw. eindeutige) Lösung d ϵ N;

das heißt ed ≡ 1 (φ(n)) und ed = 1 + kφ(n) für ein k ϵ N (e, n, φ(n) positiv).

Somit: wed = w1 + kφ(n) = w1 ∙ wk(p-1)(q-1) = w ∙ (wp-1)k(q-1) ≡ w ∙ 1k(q-1) = w (p); fertig;

ZUSAMMENFASSENDER ÜBERBLICK ÜBER RSA

A B

erzeugt Nachricht w und gibt

bekannt:

c mit we ≡ c (n)

gibt bekannt:

n = p ∙ q (p, q … Primzahlen),

e mit ggT(e, φ(n)) = 1

berechnet w durch:

w ≡ cd (n), wobei d ϵ N die positive

Lösung der linearen Kongruenz

ex ≡ 1 (φ(n)) ist

BEMERKUNG

Damit ist die Nachricht w ϵ N berechenbar, wenn man

ex ≡ 1 (φ(n)) lösen kann.

Das heißt wenn man weiß, wie die Primfaktoren p und q von n

lauten.

Diese Zahlen p und q sind aber nur B bekannt, B hat sie ja

selbst gewählt.

BEISPIEL

B gibt bekannt: n = 69, e = 3

→ n = 3 ∙ 23 (= p ∙ q)

→ φ(69) = (3 - 1) ∙ (23 - 1) = 44

→ ggT(3, 44) = 1

A übermittelt an B: c = 12

Was war w ϵ N?

B löst: 3x ≡ 1 (44); d = 15 ist die einzige positive Lösung (inkongruent mod 44);

Weiters: cd ≡ w (n), also: w ≡ 1215 (69)

Es gilt: 122 = 144 ≡ 6 (69) → 124 ≡ 36 (69) → 125 = 36 ∙ 12 = 432 ≡ 18 (69)

→ 1210 ≡ 182 = 324 ≡ 48 (69)

→ 1215 ≡ 18 ∙ 48 = 864 ≡ 36 (69), also: w = 36