Endliche Körper

Dozent:

Prof. Dr. Michael Eichberg

Kontakt:

michael.eichberg@dhbw-mannheim.de

Basierend auf:

Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Version:

2024-05-09

Gruppen, Ringe und Körper

((((((
    endliche Körper
        in Körper)
            in Integritätsring)
                in kommutative Ringe)
                    in Ringe)
                        in Abel'schen Gruppen)
                            in Gruppen)

Gruppen

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:

(A1) Abgeschlossenheit:

Wenn \(a\) und \(b\) zu \(G\) gehören, dann ist \(a \cdot b\) auch in \(G\).

(A2) Assoziativität:

\(a \cdot ( b \cdot c ) = ( a \cdot b ) \cdot c\) für alle \(a, b, c \in G\).

(A3) Existenz eines neutralen Elements:

Es gibt ein Element \(e \in G\), so dass \(a \cdot e = e \cdot a = a\) für alle \(a \in G\)

(A4) Existenz eines inversen Elements:

Für jedes \(a \in G\) gibt es ein Element \(a'\) in G, so dass \(a \cdot a' = a' \cdot a = e\)

Abel'sche Gruppen

(A1 bis A4) und:

(A5) Kommutativität:

\(a \cdot b = b \cdot a\) für alle \(a, b \in G\)

Zyklische Gruppen

• 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, und \(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.

Ringe

• 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\).

Ringe

(M1) Abgeschlossenheit der Multiplikation:

Wenn \(a\) und \(b\) teil von \(R\) sind, dann ist \(ab\) auch in \(R\)

(M2) Assoziativität der Multiplikation:

\(a(bc) = (ab)c\) für alle \(a,b,c \in R\)

(M3) Distributivgesetz:

\(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.

Ringe

• Ein Ring wird als kommutativ bezeichnet, wenn er die folgende zusätzliche Bedingung erfüllt:

  (M4) Kommutativität der Multiplikation:

  \(ab = ba\) für alle \(a, b \in R\)

Integritätsring

Ein kommutativer Ring, der den folgenden Axiomen gehorcht:

(M5) Existenz eines neutralen Elements bzgl. der Multiplikation:

Es gibt ein Element \(1\) in \(R\), so dass \(a1 = 1a = a\) für alle \(a \in R\)

(M6) Keine Nullteiler:

Wenn \(a,b \in R\) und \(ab = 0\), dann ist entweder \(a = 0\) oder \(b = 0\)

Körper

• 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\) ist ein Integritätsbereich, d. h. \(F\) erfüllt die Axiome A1 bis A5 und M1 bis M6

(M7) Existenz der multiplikativen Inversen:

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\)

Körper

• 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})\)

Unterteilung von Körpern

Endliche Körper der Form \(GF(p)\)

• Endliche Körper bilden die Grundlage von Fehlererkennungs- / Fehlerkorrekturcodes und insbesondere von bedeutenden kryptografischen Algorithmen.

Addition Modulo 8

Multiplikation Modulo 8

Additive and Muliplikative Inverse Modulo 8

Addition Modulo 7

Multiplikation Modulo 7

Additive und Muliplikative Inverse Modulo 7

Der Körper GF(2)

Endliche Körper - Konstruktion

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:

1. \(GF(p)\) besteht aus \(p\) Elementen.

2. 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.

Die Behandlung von Polynomen

(indeterminate unbestimmte)

Beispiel für gewöhnliche Polynomarithmetik

Addition:

\begin{equation*} (x^3 + x^2 + 2) + (x^2 - x + 1) \end{equation*}

\begin{equation*} = x^3 + 2x^2 - x + 3 \end{equation*}

Subtraktion:

\begin{equation*} (x^3 + x^2 + 2) - (x^2 - x + 1) \end{equation*}

\begin{equation*} = x^3 + x + 1 \end{equation*}

Beispiel für gewöhnliche Polynomarithmetik

Multiplikation:

\begin{equation*} (x^3 + x^2 + 2) \times (x^2 - x + 1) = \end{equation*}

\begin{equation*} \begin{matrix} & & & & x^3 & + & x^2 & & & + & 2 \\ & - & x^4 & - & x^3 & & & - & 2x & & & \\ x^5 & + & x^4 & & & + & 2x^2 & & & & & = \\ x^{5} & & & + & 3x^2 & -& 2x & & & + & 2 & \end{matrix} \end{equation*}

Division:

\begin{equation*} (x^3 + x^2 + 2) : (x^2 - x + 1) = x + 2 + \left ( \frac{x}{x^2 - x + 1} \right ) \end{equation*}

Polynomarithmetik mit Koeffizienten in \(Z_p\)

• 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.

    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.

Polynomiale Division

• 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.

Beispiel für Polynomarithmetik über GF(2)

Bestimmung des GGTs zweier Polynome

• 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.

Arithmetik in \(GF(2^3)\): Addition

(Die Definition der Addition des endlichen Körpers GF(2^3) wird in Kürze behandelt.)

Arithmetik in \(GF(2^3)\): Multiplikation

Arithmetik in \(GF(2^3)\)

Polynomarithmetik über \(GF(2^3)\)

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)\).

Polynomial Arithmetic in \(GF(2^3)\) Modulo \((x^3 + x + 1)\)

Polynomarithmetik im \(GF(2^3)\) Modulo \((x^3 + x + 1)\)

Multiplikation in \(GF(2^n)\)

• Mit keiner einfachen Operation lässt sich die Multiplikation in \(GF(2^n)\) erreichen.

• Es gibt jedoch eine vernünftige, unkomplizierte Technik.

Überlegungen zur Berechnung

• 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)