Informatik Security
Topic 3 Number-Theoretic Algorithms and Hardness Assumptions
Topic 3 Number-Theoretic Algorithms and Hardness Assumptions
Logaritmus / nach X umstellen:
y = 2^x
2^4 = 16
2^10 = 1024
log2 x = y
log2 16 = 4
log2 1024 = 10
Logarithmus zur Basis 2
Logaritmus / nach X umstellen:
y = 5^x
5^4 = 625
5^10 = 9765625
log5 x = y
log5 625 = 4
log5 9765625= 10
Logarithmus zur Basis 5
Logaritmus / nach X umstellen:
y = e^ax
e^4 = 54.59....
e^10 = 22026.46....
log x = y
log 54.59... = 4
log 22026.46.... = 10
Logarithmus zur Basis e (natürlicher logarithmus oder auch ln genannt)
e = 2,718 (eulersche Zahl)
Wie sollte der Algorithmus aussehen um ein Element INT aus einer additiven Gruppe zu generieren?
siehe Bild:
Zuerst log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen
Wie sollte der Algorithmus aussehen um ein Element INT aus einer additiven Gruppe zu generieren, welche in eineren Menge nicht vorkommt?
siehe Bild:
Zuerst gewünschte additive Gruppe minus NICHT gewünschter Addtive Gruppe. Danach randint(n aufrufen)
log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen.
Aschliessend r noch addieren
Wie sollte der Algorithmus aussehen um ein Element INT aus einer multiplikativen Gruppe zu finden?
sie Bild:
Zuerst log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen
und zum Schluss noch überprüfen ob die Gruppenzahl und die zufällige Zahl teilerfremd sind bzw gcd=1
Wie sollte der Algorithmus aussehen um ein Element q aus der Gruppe p zu finden?
Siehe Bild
sie Bild:
Zuerst log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen
überprüfen ob die Gruppenzahl und die zufällige Zahl teilerfremd sind bzw gcd=1
wenn ja, quadrieren und mod p rechnen davon
Wie sollte der Algorithmus aussehen um ein Element der Gruppe mit der Ordnung q zu finden?
g=generator
q=ordnung
Zuerst log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen
Zum Schluss g mit der der neu generierte Zahl Fakorisieren
Wie sollte der Algorithmus aussehen um zu überprüfen ob ein Element g ein Generator der Gruppe der Ordnung q ist?
ke plan
Wie sollte der Algorithmus aussehen um zufällige Primzahlen der bitlänge k zu generieren?
wenn die bitlänge 2 ist, dann kann es nur noch 2 oder 3 sein.
Wenn bitlänge länger, dann random bits aufrufen mit k-2 um zu Vorderst eine eins und zu hinterst auch eine eins aufzurufen.
Damit soll erreichtwerden dass nur ungerade zahlen (prim= immer ungerade) generiert werden und die Länge garantiert ist
Es gibt diverse Anzähle um zu überprüfen ob eine Zahl eine Primzahl ist.
Wie sieht der Algorithmus mit dem einfachsten/primitivste Ansatz aus und was für eine Laufzeit hat dieser?
Der primitivste Weg eine Primzahl zu testen ist es, indem man für jede Zahl bis n überprüft ob der gcd=1 ist.
Etwas effektiver ist wenn man nur bis wurzel(n) geht. da wurzel(n) * wurzel(n) ergibt wieder n
Die Laufzeit dafür ist logischerweise O(wurzel(n)). Sie auch Bild
Es gibt diverse Anzähle um zu überprüfen ob eine Zahl eine Primzahl ist.
Wie sieht der probalistische Ansatz und was für eine Laufzeit hat dieser?
Der probalistische Ansatz basiert darauf, dass die Primzahl mit einer zufälligen Zahl verglichen wird und geprüft wird ob sie eine Komposition davon ist. Je mehr Zufallszahlen getestet werden, umso mehr steigt die Wahrscheinlichkeit, dass eine Zahl Prim oder nicht ist.
Die Laufzeit des Algorithmus ist O(log(n)^6) wobei in der Praxis viel schneller ist.
Algorithmus: (n=zu testende Zahl, t=Anzahl durchläufe)
Alle Zahlen (ausser zwei) die mod 2 ergeben, sind gerade und somit automatisch keine Primzahlen.
Für Anzahl Durchläufe eine Zufallszahl generieren und schauen ob sie eine Komposition davon ist.
Es gibt diverse Anzähle um zu überprüfen ob eine Zahl eine Primzahl ist.
Wie sieht der Fermat Algorithmus aus und wieso sollte dieser nicht so verwendet werden?
Fermat's Theorem besagt, dass p eine Primzahl ist wenn a^(p-1) = 1 mod p für alle a € {1....p-1}
Es gibt jedoch Zahlen welche diese Bedingung erfüllen, jedoch kein Primzahlen sind: Carmichael numbers
Deshalb wird der Fermat Satz mit dem AKS Algorithmus kombiniert damit mit einer Wahrscheinlichkeit bestummen werden kann ob eine Zahl prim ist oder nicht
Es gibt diverse Anzähle um zu überprüfen ob eine Zahl eine Primzahl ist.
Wie sieht der am häufstigen verwendete Algorithmus aus?
Der Miller-Rabin test ist der meist verwendete Algorithmus da ein Durchlauf des Algorithmus bereits nur noch eine Chance von 0.25 hat um falsch zu liegen.
Der Algorithmus basiert auf den Fermat Satz: a^(n-1) - n = 0 mod n
a=zufällige Zahl (random number a<n)
n=zu prüfende Zahl
r und u= zahlen welche folgende Gleichung erfüllen müssen n-1=u2^r , grösser null sind und r ist ungerade
false= könnte prim sein / true= keine Primzahl
Wie sollte der Algorithmus aussehen um den gcd von zwei Zahlen herauszufinden? Tipp: Euclid
Wie ist die Laufzeit?
Solange das Resultat nicht null ist, wurde kein gemeinsamer Teiler gefunden. (rekursiv)
Mit mod wird herausgefunden ob die Zahlen einen gemeinsamen Teiler haben. Wenn es einen Resten gibt, wird mit dem Rest gerechnet.
laufzeit: O(log(a+b))
Wie sollte der Algorithmus aussehen um den gcd von zwei Zahlen herauszufinden und zusätzlich noch das Vielfache von diesem gcd? Tipp: Euclid
Wie ist die Laufzeit?
Für was soll der erweiterte Algorithmus besser sein als der einfache Euklid?
Der erweiterte Euklidische Algorithus findet den gcd zweier Zahlen heraus. Zusätzlich findet er noch die beiden Zahlen X und Y wobei X das multiplikative Inverse ist falls a € von Z*b ist.
laufzeit: O(log(a+b))
Rechnen sie folgende Aufgabe mit dem erweiterten euklidischen Logarithmus nach.
Sie sollten für d=5 erhalten, X=-7 und Y-4
Mit welchem Algorithmus findet man das Mulitplikative Inverse von einem element a in Z*n?
Mit dem erweiterten Euklid. X ist das multiplikative Inverse von a
Rechnen sie folgende Aufgabe mit dem erweiterten euklidischen Logarithmus nach.
Hinweis: a ist ein Element von Z*b
Sie sollten für d=1 erhalten, X=7 und Y=2
Welche Zahl ist das mutiplikative Inverse von a?
X ist das multiplikative Inverse von a
Welche Mathematisch Operation ist wohl die teuerste in vielen cryptografischen Applikationen?
Modularer Exponent = x^y mod n
Wie sieht die effektive rekrusive Definition für die Modulare Exponentiation einer Rechnung x^y modulo n?
Mit dieser Funktion wird der Rechnaufwand auf log(y) reduziert da jedes Mal der Exponent um die Hälfe reduiert wird.
Wie sieht der effektive Algorithmus für die Modulare Exponentiation (auch Square and Multiply genannt)einer Rechnung x^y modulo n?
Laufzeit O(log(y))
Führen sie den Square and Multiply Algorithmus (Modularer Exponent) auf folgende Zahlen: x=2, y=27, n=11 schritt für Schritt aus:
x^y mod n
Was ist eine "one-way" function? erklären Sie das anhand von der Funktion f(x)
Für alle x ist die Rechnung f(x) "einfach" zu berechnen. Der Rückweg, also f^-1(y) ist wiederum "hart" zu berechnen.
Wann ist eine mathematisch gesehen eine funktion "easy" und wann ist sie "hard"?
polynomial=easy (zb: O(1), O(log n), O(n), O(n log n), O(n^2))
super-polynomial=hard (zb: O(2^n), O(n!), O(n^n))
Was sind die Factoring und RSA Annahmen und beschreiben sie diese
Siehe Bild
Sie haben eine zyklische Gruppe: siehe Bild
Erklären sie die folgenden Annahmen: DL, CDH, DDH
siehe Bild
Was ist der Sicherheitsparameter in einer Funktion?
Die Bitlänge von n welches in die Funktion reingegeben wird. Je grösser die Bitlänge umso schwieriger ist das Problem zu lösen.
DL, CDH, DDH sind nicht in allen Gruppen sicher. Wo zum Beispiel ist DL nicht sicher?
DL ist in der Gruppe Zn nicht sicher da dort der erweiterte Euklid Algorithmus angewendet werden kann.
DL, CDH, DDH sind nicht in allen Gruppen sicher. Wo zum Beispiel ist DDH nicht sicher?
DDH ist in der Gruppe Z*p nicht sicher.
polynomial time reduction ??????
?????
Welcher Algorithmus ist der beste um das Factoring Problem zu lösen und welche Laufzeit hat dieser?
- general number field sieve (GNFS)
Welcher Algorithmus ist der beste um das DL Problem in Z*p und deren Subgruppen zu lösen und welche Laufzeit hat dieser?
Algo: index calculus
Welcher Algorithmus ist der beste um das DL Problem in Gruppen der Ordnung q zu lösen und welche Laufzeit hat dieser?
Algo: baby-step-giant
Wie sieht der baby-step-giant Algorithmus aus?
Lösen Sie den baby-step-giant Algorithmus ahand folgender Aufgabe
Nennen sie die aktuell empfohlene Bitlänge für folgende Probleme: Factoring, DL in Z*p, DL in Gq von Z*p, DL in Ea,b(Fb)
s= security strength = 2^s mit Bruteforce
112 ist bis 2030 emfohlen
-
- 1 / 37
-
Flashcards
Logaritmus / nach X umstellen:
y = 2^x
2^4 = 16
2^10 = 1024
log2 x = y
log2 16 = 4
log2 1024 = 10
Logarithmus zur Basis 2
Logaritmus / nach X umstellen:
y = 5^x
5^4 = 625
5^10 = 9765625
log5 x = y
log5 625 = 4
log5 9765625= 10
Logarithmus zur Basis 5
Logaritmus / nach X umstellen:
y = e^ax
e^4 = 54.59....
e^10 = 22026.46....
log x = y
log 54.59... = 4
log 22026.46.... = 10
Logarithmus zur Basis e (natürlicher logarithmus oder auch ln genannt)
e = 2,718 (eulersche Zahl)
Wie sollte der Algorithmus aussehen um ein Element INT aus einer additiven Gruppe zu generieren?
siehe Bild:
Zuerst log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen
Wie sollte der Algorithmus aussehen um ein Element INT aus einer additiven Gruppe zu generieren, welche in eineren Menge nicht vorkommt?
siehe Bild:
Zuerst gewünschte additive Gruppe minus NICHT gewünschter Addtive Gruppe. Danach randint(n aufrufen)
log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen.
Aschliessend r noch addieren
Wie sollte der Algorithmus aussehen um ein Element INT aus einer multiplikativen Gruppe zu finden?
sie Bild:
Zuerst log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen
und zum Schluss noch überprüfen ob die Gruppenzahl und die zufällige Zahl teilerfremd sind bzw gcd=1
Wie sollte der Algorithmus aussehen um ein Element q aus der Gruppe p zu finden?
Siehe Bild
sie Bild:
Zuerst log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen
überprüfen ob die Gruppenzahl und die zufällige Zahl teilerfremd sind bzw gcd=1
wenn ja, quadrieren und mod p rechnen davon
Wie sollte der Algorithmus aussehen um ein Element der Gruppe mit der Ordnung q zu finden?
g=generator
q=ordnung
Zuerst log zur Basis 2 ausrechnen damit die Bitlänge k herausgefunden werden kann
Danach randBits Funktion mit der Bitlänge k aufrufen
Zum Schluss g mit der der neu generierte Zahl Fakorisieren
Wie sollte der Algorithmus aussehen um zu überprüfen ob ein Element g ein Generator der Gruppe der Ordnung q ist?
ke plan
Wie sollte der Algorithmus aussehen um zufällige Primzahlen der bitlänge k zu generieren?
wenn die bitlänge 2 ist, dann kann es nur noch 2 oder 3 sein.
Wenn bitlänge länger, dann random bits aufrufen mit k-2 um zu Vorderst eine eins und zu hinterst auch eine eins aufzurufen.
Damit soll erreichtwerden dass nur ungerade zahlen (prim= immer ungerade) generiert werden und die Länge garantiert ist
Es gibt diverse Anzähle um zu überprüfen ob eine Zahl eine Primzahl ist.
Wie sieht der Algorithmus mit dem einfachsten/primitivste Ansatz aus und was für eine Laufzeit hat dieser?
Der primitivste Weg eine Primzahl zu testen ist es, indem man für jede Zahl bis n überprüft ob der gcd=1 ist.
Etwas effektiver ist wenn man nur bis wurzel(n) geht. da wurzel(n) * wurzel(n) ergibt wieder n
Die Laufzeit dafür ist logischerweise O(wurzel(n)). Sie auch Bild
Es gibt diverse Anzähle um zu überprüfen ob eine Zahl eine Primzahl ist.
Wie sieht der probalistische Ansatz und was für eine Laufzeit hat dieser?
Der probalistische Ansatz basiert darauf, dass die Primzahl mit einer zufälligen Zahl verglichen wird und geprüft wird ob sie eine Komposition davon ist. Je mehr Zufallszahlen getestet werden, umso mehr steigt die Wahrscheinlichkeit, dass eine Zahl Prim oder nicht ist.
Die Laufzeit des Algorithmus ist O(log(n)^6) wobei in der Praxis viel schneller ist.
Algorithmus: (n=zu testende Zahl, t=Anzahl durchläufe)
Alle Zahlen (ausser zwei) die mod 2 ergeben, sind gerade und somit automatisch keine Primzahlen.
Für Anzahl Durchläufe eine Zufallszahl generieren und schauen ob sie eine Komposition davon ist.
Es gibt diverse Anzähle um zu überprüfen ob eine Zahl eine Primzahl ist.
Wie sieht der Fermat Algorithmus aus und wieso sollte dieser nicht so verwendet werden?
Fermat's Theorem besagt, dass p eine Primzahl ist wenn a^(p-1) = 1 mod p für alle a € {1....p-1}
Es gibt jedoch Zahlen welche diese Bedingung erfüllen, jedoch kein Primzahlen sind: Carmichael numbers
Deshalb wird der Fermat Satz mit dem AKS Algorithmus kombiniert damit mit einer Wahrscheinlichkeit bestummen werden kann ob eine Zahl prim ist oder nicht
Es gibt diverse Anzähle um zu überprüfen ob eine Zahl eine Primzahl ist.
Wie sieht der am häufstigen verwendete Algorithmus aus?
Der Miller-Rabin test ist der meist verwendete Algorithmus da ein Durchlauf des Algorithmus bereits nur noch eine Chance von 0.25 hat um falsch zu liegen.
Der Algorithmus basiert auf den Fermat Satz: a^(n-1) - n = 0 mod n
a=zufällige Zahl (random number a<n)
n=zu prüfende Zahl
r und u= zahlen welche folgende Gleichung erfüllen müssen n-1=u2^r , grösser null sind und r ist ungerade
false= könnte prim sein / true= keine Primzahl
Wie sollte der Algorithmus aussehen um den gcd von zwei Zahlen herauszufinden? Tipp: Euclid
Wie ist die Laufzeit?
Solange das Resultat nicht null ist, wurde kein gemeinsamer Teiler gefunden. (rekursiv)
Mit mod wird herausgefunden ob die Zahlen einen gemeinsamen Teiler haben. Wenn es einen Resten gibt, wird mit dem Rest gerechnet.
laufzeit: O(log(a+b))
Wie sollte der Algorithmus aussehen um den gcd von zwei Zahlen herauszufinden und zusätzlich noch das Vielfache von diesem gcd? Tipp: Euclid
Wie ist die Laufzeit?
Für was soll der erweiterte Algorithmus besser sein als der einfache Euklid?
Der erweiterte Euklidische Algorithus findet den gcd zweier Zahlen heraus. Zusätzlich findet er noch die beiden Zahlen X und Y wobei X das multiplikative Inverse ist falls a € von Z*b ist.
laufzeit: O(log(a+b))
Rechnen sie folgende Aufgabe mit dem erweiterten euklidischen Logarithmus nach.
Sie sollten für d=5 erhalten, X=-7 und Y-4
Mit welchem Algorithmus findet man das Mulitplikative Inverse von einem element a in Z*n?
Mit dem erweiterten Euklid. X ist das multiplikative Inverse von a
Rechnen sie folgende Aufgabe mit dem erweiterten euklidischen Logarithmus nach.
Hinweis: a ist ein Element von Z*b
Sie sollten für d=1 erhalten, X=7 und Y=2
Welche Zahl ist das mutiplikative Inverse von a?
X ist das multiplikative Inverse von a
Welche Mathematisch Operation ist wohl die teuerste in vielen cryptografischen Applikationen?
Modularer Exponent = x^y mod n
Wie sieht die effektive rekrusive Definition für die Modulare Exponentiation einer Rechnung x^y modulo n?
Mit dieser Funktion wird der Rechnaufwand auf log(y) reduziert da jedes Mal der Exponent um die Hälfe reduiert wird.
Wie sieht der effektive Algorithmus für die Modulare Exponentiation (auch Square and Multiply genannt)einer Rechnung x^y modulo n?
Laufzeit O(log(y))
Führen sie den Square and Multiply Algorithmus (Modularer Exponent) auf folgende Zahlen: x=2, y=27, n=11 schritt für Schritt aus:
x^y mod n
Was ist eine "one-way" function? erklären Sie das anhand von der Funktion f(x)
Für alle x ist die Rechnung f(x) "einfach" zu berechnen. Der Rückweg, also f^-1(y) ist wiederum "hart" zu berechnen.
Wann ist eine mathematisch gesehen eine funktion "easy" und wann ist sie "hard"?
polynomial=easy (zb: O(1), O(log n), O(n), O(n log n), O(n^2))
super-polynomial=hard (zb: O(2^n), O(n!), O(n^n))
Was sind die Factoring und RSA Annahmen und beschreiben sie diese
Siehe Bild
Sie haben eine zyklische Gruppe: siehe Bild
Erklären sie die folgenden Annahmen: DL, CDH, DDH
siehe Bild
Was ist der Sicherheitsparameter in einer Funktion?
Die Bitlänge von n welches in die Funktion reingegeben wird. Je grösser die Bitlänge umso schwieriger ist das Problem zu lösen.
DL, CDH, DDH sind nicht in allen Gruppen sicher. Wo zum Beispiel ist DL nicht sicher?
DL ist in der Gruppe Zn nicht sicher da dort der erweiterte Euklid Algorithmus angewendet werden kann.
DL, CDH, DDH sind nicht in allen Gruppen sicher. Wo zum Beispiel ist DDH nicht sicher?
DDH ist in der Gruppe Z*p nicht sicher.
polynomial time reduction ??????
?????
Welcher Algorithmus ist der beste um das Factoring Problem zu lösen und welche Laufzeit hat dieser?
- general number field sieve (GNFS)
Welcher Algorithmus ist der beste um das DL Problem in Z*p und deren Subgruppen zu lösen und welche Laufzeit hat dieser?
Algo: index calculus
Welcher Algorithmus ist der beste um das DL Problem in Gruppen der Ordnung q zu lösen und welche Laufzeit hat dieser?
Algo: baby-step-giant
Wie sieht der baby-step-giant Algorithmus aus?
Lösen Sie den baby-step-giant Algorithmus ahand folgender Aufgabe
Nennen sie die aktuell empfohlene Bitlänge für folgende Probleme: Factoring, DL in Z*p, DL in Gq von Z*p, DL in Ea,b(Fb)
s= security strength = 2^s mit Bruteforce
112 ist bis 2030 emfohlen
