Rechnernetze / Kommunikationssysteme

Aufgaben Netzsicherheit – Algebra

Modulare Arithmetik

  1. Was ist der Unterschied zwischen den Ausdrücken: a = b mod m und a ≡ b (mod m) ?
  2. Ermitteln Sie die Rechenregeln für Kongruenzen.
  3. Gelten folgende Aussagen? 6 ≡ 11 (mod 5), 6 ≡ −9 (mod 5)
  4. Berechnen Sie: $3^{28} \pmod {4}$, $3^{28} \pmod {5}$, $3^{28} \pmod {6}$ mittels modularer Exponentiation!
  5. Berechnen Sie: $3^{28}$ (mod 6) mittels Square-and-Multiply-Algorithmus!
  6. Was bedeutet die eulersche Phi-Funktion? Bestimmen Sie $φ(n)$ für folgende Werte: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 90.
  7. Bestimmen Sie mittels Satz von Euler den Ausdruck: $11^{182}$ (mod 19).

Restklassenkörper (Primkörper)

  1. Wiederholen Sie die Axiome für Körper
  2. Berechnen Sie im GF(7) folgende Aufgaben: 4 + 6, 3 · 4, 3 − 4, 3/4
  3. Bestimmen Sie die primitiven Elemente in GF(7)
  4. Bestimmen Sie den diskreten Logarithmus : $\log₃(4)$

Fakultativ

Erweiterungskörper

Gegeben sei ein Erweiterungskörper (erweitertes Galoisfeld) mit p = 2 und m = 2 → (GF $2^2$). Verwendet wird das primitive Polynom $p(x) = x^2 + x + 1$.

  1. Berechnen Sie die Ausdrücke: $(x + 1) + x$; $(x + 1) · x$; $x − 1$; $x · x$; $x/(x + 1)$
  2. Bestimmen Sie ein primitives Element!

Gegeben sei ein Erweiterungskörper mit p = 2 und m = 3 → (GF $2^3$). Verwendet wird das primitive Polynom $p(x) = x^3 + x + 1$.

  1. Geben Sie alle Elemente des GF an!
  2. Berechnen Sie die Ausdrücke: $(x^2 + 1) + (x + 1)$; $(x^2 + 1) · x$; $x · x$
  3. Bestimmen Sie ein primitives Element!
  4. Bestimmen Sie $x^3 · x^4$ !

Lösung

Modulare Arithmetik

  1. Der erste Ausdruck definiert eine Zahl a während der zweite Ausdruck ein Äquivalenzklasse definiert.
  2. https://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)
  3. ja, da $6 − 11 = −1 · 5, 6 − (−9) = 3 · 5$, siehe Folie Modulare Arithmetik
  4. \[\begin{align} 3^{28} &= 3^{(2·14)} ≡ 9^{14} &≡ 1 \pmod {4} \\ 3^{28} &= 3^{(2·14)} ≡ 4^{14} ≡ 4^{(2·2·2+3·2)} &≡ 1 \pmod {5} \\ 3^{28} &= 3^{(2·14)} ≡ 3^14 ≡ 3^{(2·2·2+3·2)} ≡ 3 · 3 &≡ 3 \pmod {6} \end{align}\]
  5. $3^{28} = 3^{(2·2·2·2·2+2·2·2·2·2)} ≡ 3 · 3 ≡ 3 \pmod {6}$
  6. $φ(90) = φ(9)·φ(10) = 24$, https://de.wikipedia.org/wiki/Eulersche_Phi-Funktion
  7. ggT(11,19) = 1 -> Satz von Euler -> $11^{18} ≡ 1$ (mod 19) -> $11^{(18·k)} ≡ 1$ (mod 19) -> $11^{2} · 11^{(18·10)} ≡ 7$ (mod 19)

Restklassenkörper

  1. Siehe Vorlesungsfolien - Algebraische Grundlagen.
  2. In GF(7) wird immer modulo 7 gerechnet: a + b ≡ c (mod 7) mit a,b,c ∈ N. Dies kann verkürzt geschrieben werden als: a + b = c mit a,b,c ∈ GF(7): 4 + 6 = 3, 3 · 4 = 5, 3 − 4 = 3 + (−4) = 3 + 3 = 6, $3/4 = 3 · 4^{−1} = 3 · 2 = 6$ Für die Subtraktion wird das inverse Element bezüglich der Addition benötigt und für die Division das inverse Element bezüglich der Multiplikation, siehe Vorlesungsfolien.
  3. Ein primitives Element kann in einem Galoisfeld alle Elemente außer der Null über Potenzierung darstellen. Ein primitives Element aus GF(7) ist z. B. die 3, da $3^0 = 1$, $3^1 = 3$, $3^2 = 2$, $3^3 = 5$, $3^4 = 4$, $3^5 = 5$, $3^6 = 1$, . . .
  4. Diskreter Logarithmus, gesucht ist $x$ für $3^x = 4$. Über Einsetzen verschiedener Werte für $x$ erhält man $\log₃(4) = 4$ (In der Praxis benutzt man i.d.R. vorgefertigte Tabellen für den disk. Logarithmus, da kein effizienter Algorithmus zur Lösung bekannt ist, siehe auch Einwegfunktion und Diffie-Hellman-Schlüsselvereinbarung)

Erweiterungskörper

  1. Die Elemente aus einem Erweiterungskörper GF$(p^m)$ werden als Polynome $(a_0 x^0 + a_1 x^1 + a_2 x^2 \dots)$ dargestellt. Die Koeffizienten $a$ sind dabei Elemente aus dem Primkörper GF(p). Da die Polynommultiplikation nicht abgeschlossen ist, muss modulo $p(x)$ bei der Multiplikation von Elementen aus dem Erweiterungskörper gerechnet werden.
    • $(x+1) +x = 1x^0 + (1+1)x^1 = 1$
    • $(x+1) x = x^2 + x \mod p(x) = 1$
    • $x-1 = x +(-1) = x+1$
    • $x\cdot x = x^2 \mod p(x) = x+1$
    • $x/(x+1) = x \cdot (x+1)^{-1} = x \cdot x = x+1$
      Beispiel für die modulo-Rechnung mittels Division:
      \(\begin{align} x^2 \qquad : x^2 +x +1 = 1\\ x^2+x+1\\ -----------\\ x+1 => Divisionsrest \end{align}\)
  2. Ein primitives Element ist $x$, da alle Elemente außer Null dargestellt werden können: $x^0=1$, $x^1=x$, $x^2=x+1$

GF($2^3$)

  1. $0, 1, x, x+1, x^2, x^2 +1, x^2+x, x^2 +x +1 $
    • $x^2+x$
    • $x^3 +x \mod x^3 + x +1 = 1$
    • $x^2$
  3. $x^0=1$, $x^1$, $x^2$, $x^3 \mod x^3+x+1= x+1$, $x^4 \mod x^3+x+1 = x^2+x$, $x^5 \mod x^3+x+1 = x^2$, $x^6 \mod x^3 + x+ 1 = x^2 +1$
  4. $x^3 \cdot x^4 = x^{(3 + 4) \mod 7} = 1$ (Gerechnet wird im Exponenten mod $p^m -1$)

Letzte Änderung: 30. May 2024 16:05