karteikarten_modular_arithmetic Flashcards
(14 cards)
Frage
Antwort
Was ist eine Primzahl und warum ist sie in der Kryptographie wichtig?
- Definition: Eine Primzahl ist eine positive ganze Zahl ( p > 1 ), die keine positiven Teiler außer 1 und ( p ) hat.
- Bedeutung in der Kryptographie: Primzahlen sind die Basis vieler kryptographischer Algorithmen, da sie schwer zu faktorisieren sind, was die Sicherheit von Verschlüsselungssystemen erhöht.
- Beispiel: 2, 3, 5, 7, 11, 13, 17, 19, 23
Was besagt der Fundamentalsatz der Arithmetik und warum ist er für die Kryptographie relevant?
- Fundamentalsatz der Arithmetik: Jede ganze Zahl ( n > 1 ) ist entweder eine Primzahl oder das Produkt von Primzahlen.
- Relevanz: Die eindeutige Primfaktorzerlegung ist wichtig für die Sicherheit vieler kryptographischer Verfahren, wie RSA.
- Beispiel: ( 11000 = 2^3 \cdot 5^3 \cdot 11 )
Was ist der größte gemeinsame Teiler (GCD) und wie wird er in der Kryptographie verwendet?
- Definition: Der größte gemeinsame Teiler (GCD) von zwei positiven ganzen Zahlen ( a ) und ( b ) ist die größte positive ganze Zahl ( d ), die sowohl ( a ) als auch ( b ) teilt.
- Bedeutung: Der GCD wird verwendet, um festzustellen, ob zwei Zahlen relativ prim sind, was in vielen kryptographischen Algorithmen notwendig ist.
- Beispiel: ( ext{gcd}(54, 24) = 6 )
Was ist die Eulersche Phi-Funktion und welche Rolle spielt sie in der Kryptographie?
- Definition: Die Eulersche Phi-Funktion ( \phi(n) ) ist die Anzahl der positiven ganzen Zahlen bis ( n ), die zu ( n ) relativ prim sind.
- Anwendung: Sie wird bei der Berechnung der Schlüsselpaare in RSA verwendet.
- Beispiel: ( \phi(10) = 4 )
Was ist der Modulo-Operator und wie wird er in der kryptographischen Berechnung eingesetzt?
- Definition: Der Modulo-Operator gibt den Rest ( r ) einer Division an, wobei ( a \mod n ) den Rest von ( a ) geteilt durch ( n ) darstellt.
- Bedeutung: Modulare Arithmetik ist die Grundlage für viele kryptographische Algorithmen wie RSA und Diffie-Hellman.
- Beispiel: ( 15 \mod 12 = 3 )
Was besagt Fermats kleiner Satz und warum ist er in der Kryptographie wichtig?
- Fermats kleiner Satz: Für eine Primzahl ( p ) und eine ganze Zahl ( a ), wobei ( a ) nicht durch ( p ) teilbar ist, gilt ( a^{p-1} \equiv 1 \mod p ).
- Anwendung: Er wird verwendet, um die Verschlüsselung und Entschlüsselung in RSA zu ermöglichen.
- Beispiel: ( 2^4 \equiv 1 \mod 5 )
Was besagt Eulers Satz und wie wird er in der Kryptographie verwendet?
- Eulers Satz: Wenn ( ext{gcd}(a, n) = 1 ), dann gilt ( a^{\phi(n)} \equiv 1 \mod n ).
- Anwendung: Eulers Satz ist eine Verallgemeinerung von Fermats kleinem Satz und wird in asymmetrischen Verschlüsselungsverfahren wie RSA verwendet.
- Beispiel: ( 2^4 \equiv 1 \mod 5 ) bei ( n = 5 ) und ( \phi(5) = 4 )
Was ist eine primitive Wurzel modulo n und warum ist sie wichtig?
- Definition: Eine primitive Wurzel modulo ( n ) ist eine Zahl ( g ), sodass jede Zahl, die zu ( n ) relativ prim ist, eine Potenz von ( g ) modulo ( n ) ist.
- Bedeutung: Primitive Wurzeln werden in Diffie-Hellman und anderen kryptographischen Protokollen verwendet, um sicherzustellen, dass alle möglichen Schlüssel generiert werden.
- Beispiel: 2 ist eine primitive Wurzel modulo 5.
Was ist ein Gruppen und welche Eigenschaften haben Gruppen?
- Definition: Eine Gruppe ( G = (G, \circ, ext{inv}, e) ) ist eine Menge mit einer binären Operation ( \circ ), einer inversen Operation ( ext{inv} ) und einem Identitätselement ( e ), die bestimmte Eigenschaften erfüllen.
- Eigenschaften: Assoziativität, Identitätselement, Inverses Element.
- Anwendung: Gruppen bilden die mathematische Grundlage vieler kryptographischer Algorithmen.
- Beispiel: Die Menge der ganzen Zahlen mit der Addition als Operation bildet eine Gruppe.
Was ist der Diffie-Hellman-Schlüsselaustausch und welche mathematischen Konzepte werden dabei verwendet?
- Definition: Ein Protokoll zur sicheren Generierung eines gemeinsamen Schlüssels über einen unsicheren Kanal.
- Verwendete Konzepte: Primitive Wurzeln, Modulare Arithmetik, Gruppen.
- Prozess:
- Beide Parteien wählen eine private Zahl.
- Sie berechnen und tauschen die entsprechenden Potenzen der primitiven Wurzel modulo ( n ).
- Beide berechnen den gemeinsamen Schlüssel.
- Bedeutung: Ermöglicht sicheren Schlüsselaustausch ohne vorherige gemeinsame Geheimnisse.
Lagranges Theorem
- Lagranges Theorem besagt, dass die Ordnung (die Anzahl der Elemente) einer Untergruppe die Ordnung der gesamten Gruppe teilt.
- In der Kryptographie wird dieses Theorem genutzt, um die Sicherheit von Algorithmen zu analysieren. Zum Beispiel kann die Tatsache, dass die Ordnung einer Untergruppe ein Teiler der Ordnung der gesamten Gruppe ist, verwendet werden, um die Anzahl der möglichen Schlüssel zu bestimmen oder die Schwierigkeit bestimmter Probleme wie des Diskreten Logarithmus zu bewerten.
Untergruppen (subgroups)
Eine Untergruppe ist eine Teilmenge einer Gruppe, die selbst wieder eine Gruppe ist.
- In der Kryptographie werden oft zyklische Gruppen verwendet, die Untergruppen enthalten. Ein Beispiel ist die Gruppe der Punkte auf einer elliptischen Kurve, die bei elliptischen Kurvenkryptosystemen verwendet wird.
Safe prime? Wieso wirds verwendet
Safe primes werden in der Kryptographie verwendet, um die Sicherheit von kryptografischen Systemen zu erhöhen. Ein safe prime ist eine Primzahl ( p ), für die gilt ( p = 2q + 1 ), wobei ( q ) ebenfalls eine Primzahl ist. Hier sind einige Gründe, warum safe primes wichtig sind:Erhöhte Sicherheit:Safe primes minimieren die Anzahl der möglichen Untergruppen in einer Gruppe, was bestimmte Angriffe, wie den Pohlig-Hellman-Algorithmus zur Lösung des Diskreten Logarithmusproblems, erschwert.Vermeidung kleiner Untergruppen:Kleine Untergruppen können oft gezielt angegriffen werden. Safe primes sorgen dafür, dass die Gruppe eine große Primzahlordnung hat und somit keine kleinen, leicht angreifbaren Untergruppen vorhanden sind.Verwendung in Protokollen:Viele kryptografische Protokolle, wie Diffie-Hellman-Schlüsselaustausch, nutzen safe primes, um sicherzustellen, dass die erzeugten Schlüssel ausreichend sicher sind
