Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings
https://delors.github.io/sec-endliche-koerper/kontrollaufgaben.de.rst.html
[HTML] https://delors.github.io/sec-endliche-koerper/folien.de.md.html
[PDF] https://delors.github.io/sec-endliche-koerper/folien.de.md.html.pdf
Bei der Erstellung der Unterlagen wurden KI Assistenten (insbesondere Claude aber ggf. auch ChatGPT, Ollama mit Gemma/LLama/Qwen oder OpenCode mit Kimi/Qwen/Deepseek...) unterstützend eingesetzt. Dies erfolgte insbesondere zur Unterstützung bei der Generierung von Grafiken (d. h. SVG Dateien), oder um sich Übersichtstabellen generieren zu lassen. Weiterhin wurde KI zur allgemeinen Qualitätssicherung eingesetzt. Inhalte, die ggf. von der KI vorgeschlagen wurden, wurden im Falle der Übernahme explizit validiert und angepasst.
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 , die jedem geordneten Paar von Elementen in ein Element zuordnet, so dass die folgenden Axiome befolgt werden:
Wenn und zu gehören, dann ist auch in .
für alle .
Es gibt ein Element , so dass für alle
Für jedes gibt es ein Element \in G, so dass
(A1 bis A4) und:
für alle
Die Potenzierung ist innerhalb einer Gruppe als eine wiederholte Anwendung des Gruppenoperators definiert, so dass .
Wir definieren:
als das neutrale Element
, wobei das inverse Element von innerhalb der Gruppe ist.
Eine Gruppe ist zyklisch, wenn jedes Element von eine Potenz ( ist eine ganze Zahl) eines festen Elements ist.
Das Element erzeugt somit die Gruppe . ist somit der Generator von .
Eine zyklische Gruppe ist immer abelsch und kann endlich oder unendlich sein.
Ein Ring , manchmal auch als bezeichnet, ist eine Menge von Elementen mit zwei binären Operationen, genannt Addition und Multiplikation, so dass für alle die Axiome (A1-A5) erfüllt sind.
ist eine abelsche Gruppe in Bezug auf die Addition; das heißt, erfüllt die Axiome A1 bis A5. Für den Fall einer additiven Gruppe bezeichnen wir das neutrale Element als und den Kehrwert von als .
Wenn und teil von sind, dann ist auch in
für alle
für alle
für alle
Ein Ring wird als kommutativ bezeichnet, wenn er die folgende zusätzliche Bedingung erfüllt:
für alle
Ein kommutativer Ring, der den folgenden Axiomen gehorcht:
Es gibt ein Element in , so dass für alle
Wenn und , dann ist entweder oder
Ein Körper , manchmal auch bezeichnet als , ist eine Menge von Elementen mit zwei binären Operationen, genannt Addition und Multiplikation, so dass für alle die Axiome (A1-M6) gelten.
Für jedes in , außer , gibt es ein Element , so dass
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:
ist ein Integritätsbereich, d. h. erfüllt die Axiome A1 bis A5 und M1 bis M6
Körper ≘ Field
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 |
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 |
0 | 0 | |
|---|---|---|
1 | 7 | 1 |
2 | 6 | |
3 | 5 | 3 |
4 | 4 | |
5 | 3 | 5 |
6 | 2 | |
7 | 1 | 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 |
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 |
Zu beachten ist hier, dass es zu jedem Element ein zweites Element gibt, so dass die Verrechnung (Addition oder Multiplikation) das jeweilige neutrale Element ergibt.
0 | 0 | |
|---|---|---|
1 | 6 | 1 |
2 | 5 | 4 |
3 | 4 | 5 |
4 | 3 | 2 |
5 | 2 | 3 |
6 | 1 | 6 |
0 | 1 | |
|---|---|---|
0 | 0 | 1 |
1 | 1 | 0 |
0 | 1 | |
|---|---|---|
0 | 0 | 0 |
1 | 0 | 1 |
0 | 0 | |
|---|---|---|
1 | 1 | 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 konstruiert, wobei prim ist.
ist mit den folgenden Eigenschaften definiert:
besteht aus Elementen.
Die binären Operationen und 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.
indeterminate ≘ unbestimmte
• Wir können jedes Polynom in der Form schreiben:
• kann als Rest interpretiert werden • Es gilt
• Wenn es keinen Rest gibt, dann teilt das Polynom
• Notation: • Wir können sagen, dass ein Faktor von ist oder • ist ein Teiler von
• Ein Polynom über einem Körper ist irreduzibel, genau dann wenn nicht als Produkt zweier Polynome ausgedrückt werden kann, die beide Element von sind und beide einen niedrigeren Grad als haben.
Ein irreduzibles Polynom wird auch als Primpolynom bezeichnet.
• Die Polynomdivision kann über die Multiplikation definiert werden. Seien , dann ist , wobei das einzige Element des Körpers ist, für das gilt.
Addition
Subtraktion
Multiplikation
Division
Das Polynom ist der größte gemeinsame Teiler von und , wenn die folgenden Bedingungen erfüllt sind:
teilt sowohl als auch
Jeder Teiler von und ist auch ein Teiler von
Eine äquivalente Definition ist:
ist das Polynom maximalen Grades, das sowohl als auch 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.
Mit keiner einfachen Operation lässt sich die Multiplikation in GF(2ⁿ) erreichen.
Es gibt jedoch eine vernünftige, unkomplizierte Technik.
Das von AES verwendete Polynom ist:
Bzgl. der Beobachtung: Wenn wir zum Beispiel das Polynom multiplizieren mit gilt:
da
Beispiel:
Hilfsrechnung:
Beispiel:
Hilfsrechnung:
Die Multiplikation mit kann durch die zweifache Multiplikation mit unter Anwendung der obigen Gleichung erreicht werden kann. D. h.
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 ()
Polynomial | Binary | Decimal |
|---|---|---|
x⁷ + x⁶ + x⁴ + x + 1 | ||
11001001 | ||
133 | ||
x⁴ + x² + x | ||
00011001 | ||
10 |
Polynomarithmetik im GF(2⁵)
Gegeben sei GF(2⁵) mit dem irreduziblen Polynom p(x) = x⁵ + x² + 1
Berechne: (x³ + x² + x + 1) - (x + 1)
Berechne: (x⁴ + x) × (x³ + x²)
Berechne: (x³) × (x² + x¹ + 1)
Berechne: (x⁴ + x)/(x³ + x²) geben (x³ + x²)⁻¹ = (x² + x + 1)
Zur Erinnerung: Division kann als Multiplikation definiert werden. Seien a, b ∈ F, dann ist a / b = a × (b⁻¹), wobei b⁻¹ die Umkehrung von b ist.
Verifiziere: (x³ + x²)⁻¹ = (x² + x + 1)
Einfache Polynomarithmetik im GF(2⁸)
Nehmen wir an, dass die Dezimalzahlen 7 und 3 stellvertretend für die Bitmuster der Koeffizienten des Polynoms stehen.
Berechne: 7₁₀ - 3₁₀
Berechne: 7₁₀ + 3₁₀
Polynommultiplikation im GF(2⁸)
Berechne: 0x03 × 0x46
(0x3 und 0x46 sind die Hexadezimaldarstellungen der Koeffizienten des Polynoms und diese repräsentieren (auch nur) die Bitmuster der Koeffizienten des Polynoms.)