Eigenschaften von Gruppen, Ringen und Körpern
Zusammenfassung
Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings
((((((
endliche Körper
in Körper)
in Integritätsring)
in kommutative Ringe)
in Ringe)
in Abel'schen Gruppen)
in Gruppen)
Integral Domains
Fields
Identity element
Übersetzungen mathematischer Fachbegriffe ins Deutsche: https://www.henked.de/woerterbuch.htm
Eine Menge von Elementen mit einer binären Operation \(\cdot\), die jedem geordneten Paar \((a,b)\) von Elementen in \(G\) ein Element \((a \cdot b ) \in G\) zuordnet, so dass die folgenden Axiome befolgt werden:
Wenn \(a\) und \(b\) zu \(G\) gehören, dann ist \(a \cdot b\) auch in \(G\).
\(a \cdot ( b \cdot c ) = ( a \cdot b ) \cdot c\) für alle \(a, b, c \in G\).
Es gibt ein Element \(e \in G\), so dass \(a \cdot e = e \cdot a = a\) für alle \(a \in G\)
Für jedes \(a \in G\) gibt es ein Element \(a'\) in G, so dass \(a \cdot a' = a' \cdot a = e\)
(A1 bis A4) und:
\(a \cdot b = b \cdot a\) für alle \(a, b \in G\)
Die Potenzierung ist innerhalb einer Gruppe als eine wiederholte Anwendung des Gruppenoperators definiert, so dass \(a^3 = a \cdot a \cdot a\).
Wir definieren:
\(a^0 = e\) als das neutrale Element
\(a^{-n} = (a')^n\) , wobei \(a'\) das inverse Element von \(a\) innerhalb der Gruppe ist.
Eine Gruppe \(G\) ist zyklisch, wenn jedes Element von \(G\) eine Potenz \(a^k\) (\(k\) ist eine ganze Zahl) eines festen Elements \(a \in G\) ist.
Das Element \(a\) erzeugt somit die Gruppe \(G\). \(a\) ist somit der Generator von \(G\).
Eine zyklische Gruppe ist immer abelsch und kann endlich oder unendlich sein.
Ein Ring \(R\), manchmal auch als \(\lbrace R , + , \times \rbrace\) bezeichnet, ist eine Menge von Elementen mit zwei binären Operationen, genannt Addition und Multiplikation, so dass für alle \(a , b , c \in R\) die Axiome (A1-A5) erfüllt sind.
\(R\) ist eine abelsche Gruppe in Bezug auf die Addition; das heißt, \(R\) erfüllt die Axiome A1 bis A5. Für den Fall einer additiven Gruppe bezeichnen wir das neutrale Element als \(0\) und den Kehrwert von \(a\) als \(-a\).
Wenn \(a\) und \(b\) teil von \(R\) sind, dann ist \(ab\) auch in \(R\)
\(a(bc) = (ab)c\) für alle \(a,b,c \in R\)
\(a(b+c) = ab+ac\) für alle \(a,b,c \in R\)
\((a+b)c = ac+bc\) für alle \(a,b,c \in R\)
Im Wesentlichen ist ein Ring eine Menge, in der wir Addition, Subtraktion \([a - b = a + (-b )]\) und Multiplikation durchführen können, ohne die Menge zu verlassen.
Ein Ring wird als kommutativ bezeichnet, wenn er die folgende zusätzliche Bedingung erfüllt:
\(ab = ba\) für alle \(a, b \in R\)
Ein kommutativer Ring, der den folgenden Axiomen gehorcht:
Es gibt ein Element \(1\) in \(R\), so dass \(a1 = 1a = a\) für alle \(a \in R\)
Wenn \(a,b \in R\) und \(ab = 0\), dann ist entweder \(a = 0\) oder \(b = 0\)
Ein Körper \(F\), manchmal auch bezeichnet als \(\lbrace F, +, \times \rbrace\), ist eine Menge von Elementen mit zwei binären Operationen, genannt Addition und Multiplikation, so dass für alle \(a, b, c \in F\) die Axiome (A1-M6) gelten.
Für jedes \(a\) in \(F\), außer \(0\), gibt es ein Element \(a^{-1} \in F\), so dass \(aa^{-1} = (a^{-1})a = 1\)
Im Wesentlichen ist ein Körper eine Menge, in der wir Addition, Subtraktion, Multiplikation und Division durchführen können, ohne die Menge zu verlassen. Die Division ist mit der folgenden Regel definiert: \(a/b = a (b^{-1})\)
\(F\) ist ein Integritätsbereich, d. h. \(F\) erfüllt die Axiome A1 bis A5 und M1 bis M6
Körper ≘ Field
Zusammenfassung
Endliche Körper bilden die Grundlage von Fehlererkennungs- / Fehlerkorrekturcodes und insbesondere von bedeutenden kryptografischen Algorithmen.
Die Ordnung eines endlichen Körpers ist die Anzahl der Elemente des Körpers.
Es kann gezeigt werden, dass die Ordnung eines endlichen Körpers eine Potenz einer Primzahl \(p^n\) sein muss, wobei \(n\) eine positive ganze Zahl ist.
Der endliche Körper der Ordnung \(p^n\) wird allgemein als \(GF(p^n)\) bezeichnet.
GF steht für Galois Field (Galoiskörper), zu Ehren des Mathematikers, der als erster endliche Körper untersucht hat.
Addition Modulo 8
\(+\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
2 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
3 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
4 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
5 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
6 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
7 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
Multiplikation Modulo 8
\(\times\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
2 |
0 |
2 |
4 |
6 |
0 |
2 |
4 |
6 |
3 |
0 |
3 |
6 |
1 |
4 |
7 |
2 |
5 |
4 |
0 |
4 |
0 |
4 |
0 |
4 |
0 |
4 |
5 |
0 |
5 |
2 |
7 |
4 |
1 |
6 |
3 |
6 |
0 |
6 |
4 |
2 |
0 |
6 |
4 |
2 |
7 |
0 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
\(w\) |
\(-w\) |
\(w^{-1}\) |
0 |
0 |
\(-\) |
1 |
7 |
1 |
2 |
6 |
\(-\) |
3 |
5 |
3 |
4 |
4 |
\(-\) |
5 |
3 |
5 |
6 |
2 |
\(-\) |
7 |
1 |
7 |
Addition Modulo 7
\(+\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
0 |
2 |
2 |
3 |
4 |
5 |
6 |
0 |
1 |
3 |
3 |
4 |
5 |
6 |
0 |
1 |
2 |
4 |
4 |
5 |
6 |
0 |
1 |
2 |
3 |
5 |
5 |
6 |
0 |
1 |
2 |
3 |
4 |
6 |
6 |
0 |
1 |
2 |
3 |
4 |
5 |
Multiplikation Modulo 7
\(\times\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
2 |
0 |
2 |
4 |
6 |
1 |
3 |
5 |
3 |
0 |
3 |
6 |
2 |
5 |
1 |
4 |
4 |
0 |
4 |
1 |
5 |
2 |
6 |
3 |
5 |
0 |
5 |
3 |
1 |
6 |
4 |
2 |
6 |
0 |
6 |
5 |
4 |
3 |
2 |
1 |
\(w\) |
\(-w\) |
\(w^{-1}\) |
0 |
0 |
\(-\) |
1 |
6 |
1 |
2 |
5 |
4 |
3 |
4 |
5 |
4 |
3 |
2 |
5 |
2 |
3 |
6 |
1 |
6 |
Addition
\(+\) |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Multiplikation
\(\times\) |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
Inverse
\(w\) |
\(-w\) |
\(w^{-1}\) |
0 |
0 |
0 |
1 |
0 |
1 |
Die Addition ist die XOR-Operation und die Multiplikation ist die AND-Operation.
In diesem Abschnitt haben wir gezeigt, wie man endliche Körper der Ordnung \(p\) konstruiert, wobei \(p\) prim ist.
\(GF(p)\) ist mit den folgenden Eigenschaften definiert:
\(GF(p)\) besteht aus \(p\) Elementen.
Die binären Operationen \(+\) und \(\times\) sind über der Menge definiert. Die Operationen der Addition, Subtraktion, Multiplikation und Division können durchgeführt werden, ohne die Menge zu verlassen. Jedes Element der Menge, das nicht 0 ist, hat eine multiplikative Inverse.
Für eine effiziente Nutzung klassischer Computer benötigen wir einen endlichen Körper der Form \(GF(2^n)\).
.svg)
(indeterminate unbestimmte)
Wenn jedes eindeutige Polynom als Element der Menge betrachtet wird, dann ist diese Menge ein Ring.
Wenn die Polynomarithmetik auf Polynomen über einem Körper durchgeführt wird, dann ist die Division möglich.
Wenn wir versuchen, eine Polynomdivision über eine Koeffizientenmenge durchzuführen, die kein Körper ist, dann ist die Division nicht immer definiert.
Auch wenn die Koeffizientenmenge ein Körper ist, ist die Polynomdivision nicht unbedingt exakt; d. h. es gibt ggf. einen Rest.
Das bedeutet nicht, dass eine exakte Teilung möglich ist.
Unter der Voraussetzung, dass Reste erlaubt sind, dann ist die Polynomdivision möglich, wenn die Koeffizientenmenge ein Körper bildet.
Wir können jedes Polynom in der Form schreiben: \(f(x) = q(x) g(x) + r(x)\)
\(r(x)\) kann als Rest interpretiert werden
Es gilt \(r(x) = f(x)\; mod\; g(x)\)
Wenn es keinen Rest gibt, dann teilt \(g(x)\) das Polynom \(f(x)\)
Notation: \(g(x) | f(x)\)
Wir können sagen, dass \(g(x)\) ein Faktor von \(f(x)\) ist
Oder \(g(x)\) ist ein Teiler von \(f(x)\)
Ein Polynom \(f(x)\) über einem Körper \(F\) ist irreduzibel, genau dann wenn \(f(x)\) nicht als Produkt zweier Polynome ausgedrückt werden kann, die beide Element von \(F\) sind und beide einen niedrigeren Grad als \(f(x)\) haben.
Ein irreduzibles Polynom wird auch als Primpolynom bezeichnet.
Die Polynomdivision kann über die Multiplikation definiert werden. Sei \(a,b \in F\) dann ist \(a/b = a \times b^{-1}\), wobei \(b^{-1}\) das einzige Element des Körpers ist, für das \(bb^{-1} = 1\) gilt.
Addition
Subtraktion
Multiplikation
Division
Das Polynom \(c(x)\) ist der größte gemeinsame Teiler von \(a(x)\) und \(b(x)\), wenn die folgenden Bedingungen erfüllt sind:
\(c(x)\) teilt sowohl \(a(x)\) als auch \(b(x)\)
Jeder Teiler von \(a(x)\) und \(b(x)\) ist auch ein Teiler von \(c(x)\)
Eine äquivalente Definition ist:
\(ggt[a(x), b(x)]\) ist das Polynom maximalen Grades, das sowohl \(a(x)\) als auch \(b(x)\) teilt.
Der euklidische Algorithmus kann erweitert werden, um den größten gemeinsamen Teiler von zwei Polynomen zu finden, deren Koeffizienten Elemente eines Körpers sind.
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
||
\(+\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
000 |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
001 |
1 |
1 |
0 |
3 |
2 |
5 |
4 |
7 |
6 |
010 |
2 |
2 |
3 |
0 |
1 |
6 |
7 |
4 |
5 |
011 |
3 |
3 |
2 |
1 |
0 |
7 |
6 |
5 |
4 |
100 |
4 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
101 |
5 |
5 |
4 |
7 |
6 |
1 |
0 |
3 |
2 |
110 |
6 |
6 |
7 |
4 |
5 |
2 |
3 |
0 |
1 |
111 |
7 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
Die Definition der Addition des endlichen Körpers \(GF(2^3)\) wird in Kürze behandelt.
Wiederholung
Die Subtraktion zweier Elemente des Körpers kann über die Addition definiert werden. Seien \(a, b \in F\) dann ist \(a - b = a + (-b)\) , wobei \(-b\) das einzige Element in \(F\) ist, für das \(b + (-b) = 0\) gilt (\(-b\) wird als das Negativ von \(b\) bezeichnet).
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
||
\(\times\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
000 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
001 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
010 |
2 |
0 |
2 |
4 |
6 |
3 |
1 |
7 |
5 |
011 |
3 |
0 |
3 |
6 |
5 |
7 |
4 |
1 |
2 |
100 |
4 |
0 |
4 |
3 |
7 |
6 |
2 |
5 |
1 |
101 |
5 |
0 |
5 |
1 |
4 |
2 |
7 |
3 |
6 |
110 |
6 |
0 |
6 |
7 |
1 |
5 |
3 |
2 |
4 |
111 |
7 |
0 |
7 |
5 |
2 |
1 |
6 |
4 |
3 |
Die Definition der Multiplikation des endlichen Körpers \(GF(2^3)\) wird in Kürze behandelt.
Die Anzahl der Vorkommen der ganzen Zahlen ungleich Null ist bei der Multiplikation einheitlich (Vor allem im Vergleich zu \(Z_8\)); dies ist für kryptographische Zwecke förderlich.
\(w\) |
\(-w\) |
\(w^{-1}\) |
0 |
0 |
\(-\) |
1 |
1 |
1 |
2 |
2 |
5 |
3 |
3 |
6 |
4 |
4 |
7 |
5 |
5 |
2 |
6 |
6 |
3 |
7 |
7 |
4 |
(Die Werte wurden aus den vorherigen Tabellen abgelesen.)
Um den endlichen Körper \(GF(2^3)\) zu konstruieren, müssen wir ein irreduzibles Polynom vom Grad 3 wählen, d. h. entweder \((x^3+x^2+1)\) oder \((x^3+x+1)\).
Mit Multiplikationen modulo \(x^3 + x + 1\) haben wir nur die folgenden acht Polynome in der Menge der Polynome über \(GF(2)\):
Die 8 Polynome sind die möglichen "Reste" bei der Division von Polynomen über \(GF(2^3)\) mit \(x^3 + x + 1\).
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
||
\(+\) |
\(0\) |
\(1\) |
\(x\) |
\(x+1\) |
\(x^2\) |
\(x^2+1\) |
\(x^2+x\) |
\(x^2+x+1\) |
|
000 |
\(0\) |
0 |
\(1\) |
\(x\) |
\(x+1\) |
\(x^2\) |
\(x^2 + 1\) |
\(x^2 + x\) |
\(x^2 + x + 1\) |
001 |
\(1\) |
\(1\) |
0 |
\(x+1\) |
\(x\) |
\(x^2 + 1\) |
\(x^2\) |
\(x^2 + x + 1\) |
\(x^2 + x\) |
010 |
\(x\) |
\(x\) |
\(x+1\) |
0 |
\(1\) |
\(x^2 + x\) |
\(x^2 + x + 1\) |
\(x^2\) |
\(x^2 + 1\) |
011 |
\(x+1\) |
\(x+1\) |
\(x\) |
\(1\) |
0 |
\(x^2 + x + 1\) |
\(x^2 + x\) |
\(x^2 + 1\) |
\(x^2\) |
100 |
\(x^2\) |
\(x^2\) |
\(x^2 + 1\) |
\(x^2 + x\) |
\(x^2 + x + 1\) |
0 |
\(1\) |
\(x\) |
\(x+1\) |
101 |
\(x^2+1\) |
\(x^2 + 1\) |
\(x^2\) |
\(x^2 + x + 1\) |
\(x^2 + x\) |
1 |
0 |
\(x+1\) |
\(x\) |
110 |
\(x^2+x\) |
\(x^2 + x\) |
\(x^2 + x + 1\) |
\(x^2\) |
\(x^2 + 1\) |
x |
\(x+1\) |
0 |
\(1\) |
111 |
\(x^2+x+1\) |
\(x^2 + x + 1\) |
\(x^2 + x\) |
\(x^2 + 1\) |
\(x^2\) |
\(x+1\) |
\(x\) |
\(1\) |
0 |
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
||
\(\times\) |
0 |
1 |
\(x\) |
\(x+1\) |
\(x^2\) |
\(x^2+1\) |
\(x^2+x\) |
\(x^2+x+1\) |
|
000 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
001 |
1 |
0 |
1 |
\(x\) |
\(x+1\) |
\(x^2\) |
\(x^2 + 1\) |
\(x^2 + x\) |
\(x^2 + x + 1\) |
010 |
\(x\) |
0 |
\(x\) |
\(x^2\) |
\(x^2 + x\) |
\(x+1\) |
1 |
\(x^2 + x + 1\) |
\(x^2 + 1\) |
011 |
\(x+1\) |
0 |
\(x+1\) |
\(x^2 + x\) |
\(x^2 + 1\) |
\(x^2 + x + 1\) |
\(x^2\) |
1 |
\(x\) |
100 |
\(x^2\) |
0 |
\(x^2\) |
\(x+1\) |
\(x^2 + x + 1\) |
\(x^2 + x\) |
\(x\) |
\(x^2 + 1\) |
1 |
101 |
\(x^2+1\) |
0 |
\(x^2 + 1\) |
1 |
\(x^2\) |
\(x\) |
\(x^2 + x + 1\) |
\(x+1\) |
\(x^2 + x\) |
110 |
\(x^2+x\) |
0 |
\(x^2 + x\) |
\(x^2 + x + 1\) |
1 |
\(x^2 + 1\) |
\(x+1\) |
\(x\) |
\(x^2\) |
111 |
\(x^2+x+1\) |
0 |
\(x^2 + x + 1\) |
\(x^2 + 1\) |
\(x\) |
1 |
\(x^2 + x\) |
\(x^2\) |
\(x+1\) |
Beispiel
Mit keiner einfachen Operation lässt sich die Multiplikation in \(GF(2^n)\) erreichen.
Es gibt jedoch eine vernünftige, unkomplizierte Technik.
Das von AES verwendete Polynom ist:
Bzgl. der Beobachtung: Wenn wir zum Beispiel das Polynom \(x^7\) multiplizieren mit \(x\) gilt:
da
Beispiel:
Hilfsrechnung:
Beispiel:
Hilfsrechnung:
Die Multiplikation mit \(x^2\) kann durch die zweifache Multiplikation mit \(x\) unter Anwendung der obigen Gleichung erreicht werden kann. D. h. \(x^7 \times x^2 = (x^7 \times x) \times x\)
Da die Koeffizienten 0 oder 1 sind, kann ein solches Polynom als Bitfolge dargestellt werden
Addition ist ein XOR dieser Bitstrings
Multiplikation ist eine Linksverschiebung gefolgt von einem XOR
(vgl. klassische Multiplikation per Hand.)
Die Modulo-Reduktion erfolgt durch wiederholtes Ersetzen der höchsten Potenz durch den Rest des irreduziblen Polynoms (auch Shift und XOR)
Repräsentation von Polynomen
Füllen Sie die fehlenden Werte aus (\(GF(2^m)\))
Polynomial |
Binary |
Decimal |
|---|---|---|
\(x^7 +x^6 +x^4 +x+1\) |
||
11001001 |
||
133 |
||
\(x^4 +x^2 +x\) |
||
00011001 |
||
10 |
Polynomarithmetik im GF(2^5)
Gegeben sei \(GF(2^5)\) mit dem irreduziblen Polynom \(p(x) = x^5 + x^2 + 1\)
Berechne: \((x^3 + x^2 + x + 1) - (x+1)\)
Berechne: \((x^4 + x) \times (x^3 + x^2)\)
Berechne: \((x^3) \times (x^2 + x^1 + 1)\)
Berechne: \((x^4+x)/(x^3+x^2)\) geben \((x^3+x^2)^{-1} =(x^2+x+1)\)
Zur Erinnerung: Division kann als Multiplikation definiert werden. Seien \(a, b \in F\), dann ist \(a/b = a \times (b^{-1})\), wobei \(b^{-1}\) die Umkehrung von \(b\) ist.
Verifiziere: \((x^3+x^2)^{-1}=(x^2+x+1)\)
Einfache Polynomarithmetik im GF(2^8)
Nehmen wir an, dass 7 und 3 stellvertretend für die Bitmuster der Koeffizienten des Polynoms stehen.
Berechne: \(7d - 3d\)
Berechne: \(7d + 3d\)
Polynommultiplikation im GF(2^8)
Berechne: \((0x03\; \times\; 0x46) \qquad\)
(0x3 und 0x46 sind die Hexadezimaldarstellungen der Koeffizienten des Polynoms und diese repräsentieren (auch nur) die Bitmuster der Koeffizienten des Polynoms.)