0Pricing
Cryptology Academy · Lektion

GGT, Eulersche Phi-Funktion und Einführung in die Zahlentheorie

Setzen Sie den GGT und die Eulersche Phi-Funktion auf reale Kryptografieprobleme an.

GGT, Eulersche Phi-Funktion und Einführung in die Zahlentheorie ist eine kostenlose Cryptology Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Cryptology Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Cryptology Academy-Kurs umfasst insgesamt 4 Lektionen.

Willkommen

Der GCD und die Eulersche Phi-Funktion sind wichtige Werkzeuge in RSA und vielen anderen Public-Key-Systemen. Lassen Sie uns beide anhand von Beispielen beherrschen.

Größter gemeinsamer Teiler (GCD)

GCD(a, b) ist die größte ganze Zahl, die sowohl a als auch b ohne Rest teilt. GCD(12, 8) = 4. Wenn GCD(a, m) = 1 gilt, sind a und m teilerfremd.

Euklidischer Algorithmus

GCD(a, b) = GCD(b, a mod b), mit dem Basisfall GCD(a, 0) = a. GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

Erweiterter euklidischer Algorithmus

Die erweiterte Variante findet ganze Zahlen x und y, sodass ax + by = GCD(a,b) gilt. Wenn GCD(a,m)=1, ist x das modulare Inverse von a modulo m. So berechnet RSA private Schlüssel.

Eulersche Phi-Funktion φ(n)

φ(n) zählt die Zahlen von 1 bis n, die zu n teilerfremd sind. φ(10) = 4, weil {1, 3, 7, 9} zu 10 teilerfremd sind. Für jede Primzahl p gilt φ(p) = p-1.

Phi-Funktion eines Produkts

Für RSA gilt: n = p×q (p,q prim). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Beispiel: p=5, q=11: φ(55) = 4×10 = 40. Deshalb bricht die Faktorisierung von n RSA – sie gibt φ(n) preis.

Satz von Euler

Wenn GCD(a,n)=1 gilt: a^φ(n) ≡ 1 (mod n). Dies ist die mathematische Grundlage der RSA-Entschlüsselung: M = C^d mod n, weil e×d ≡ 1 (mod φ(n)) gilt.

d in RSA berechnen

Wählen Sie e = 65537 (ein gängiger öffentlicher RSA-Exponent). Berechnen Sie d = e^(-1) mod φ(n) mithilfe des erweiterten euklidischen Algorithmus. Überprüfen Sie, dass e×d mod φ(n) == 1 gilt.

Phi-Funktion in Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Carmichaels Lambda

Modernes RSA verwendet statt φ(n) die Carmichael-Lambda-Funktion λ(n) = lcm(p-1, q-1). Sie liefert einen kleineren, gleichwertigen Modulus. PKCS#1 v2 und NIST empfehlen λ(n).

Zusammenfassung der praktischen Anwendung

GCD: Überprüfen Sie, ob e und φ(n) teilerfremd sind. Erweiterter euklidischer Algorithmus: Berechnen Sie den privaten Schlüssel d. Phi-Funktion: Bestimmen Sie die Exponentengruppe für die modulare Exponentiation. Alle drei werden bei jeder RSA-Schlüsselerzeugung verwendet.

Schnelltest

Welchen Wert hat φ(n) bei RSA mit p=7 und q=11?

Zusammenfassung

Ausgezeichnet! GCD, der euklidische Algorithmus und die Eulersche Phi-Funktion gehören nun zu Ihrem Werkzeugkasten. Als Nächstes untersuchen wir XOR und bitweise Operationen – die Bausteine symmetrischer Chiffren.

Häufig gestellte Fragen

Ist die Lektion „GGT, Eulersche Phi-Funktion und Einführung in die Zahlentheorie“ kostenlos?

Ja — der vollständige Text von „GGT, Eulersche Phi-Funktion und Einführung in die Zahlentheorie“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Cryptology Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Cryptology Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „GGT, Eulersche Phi-Funktion und Einführung in die Zahlentheorie“?

Setzen Sie den GGT und die Eulersche Phi-Funktion auf reale Kryptografieprobleme an. Du übst Cryptology Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Cryptology Academy zu starten?

Keine Vorkenntnisse erforderlich. Cryptology Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.

Wie lange dauert die Lektion „GGT, Eulersche Phi-Funktion und Einführung in die Zahlentheorie“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Cryptology Academy-Lektion Code schreiben und ausführen?

Ja. Jede Cryptology Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Grundlagen von Binär- und Hexadezimalsystem
  2. Grundlagen der modularen Arithmetik
  3. Primzahlen und Faktorisierung
  4. GGT, Eulersche Phi-Funktion und Einführung in die Zahlentheorie
← Zurück zu Cryptology Academy