kleine Anmerkung: wenn bei `a = random.randrange(2, p)` die Zahl p-1 gewählt wird und p ungerade ist, gibt die Funktion garantiert True zurück (p-1 ist ja kongruent zu -1 modulo p). Außerdem ist es natürlich ineffizient, erst die Potenz `a ** (p - 1)` zu berechnen und dann erst modulo p zu reduzieren. 1024-bit große Zahlen lassen sich damit jedenfalls nicht testen. Eine leicht optimierte Variante der Funktion könnte so aussehen: def fermat(p, k): for runs in range(k): a = random.randrange(2, p-1) if pow(a, p-1, p) != 1: return False return True die builtin pow Funktion berechnet `base ** exp % mod` deutlich effizienter, da durch häufigere modulo-Reduktionen die Zwischenergebnisse klein gehalten werden. Eine Implementierung könnte folgendermaßen aussehen: def mod_pow(base, exp, mod): r = 1 while exp: if exp % 2 == 1: r = r * base % p base = base * base % p exp //= 2 return r Allerdings muss ich hier auch anmerken, dass diese Implementierung nicht für RSA-Berechnungen mit dem geheimen Schlüssel geeignet ist, da der if-Block im while-loop die Funktion anfällig für Seitenkanalangriffe macht.
1:41 Eine Primzahl ist eine natürliche Zahl, die genau zwei Teiler hat und nicht eine Zahl die nur durch 1 und sich sich selber teilbar ist. *Klugscheißermodus aus* :) Dann muss man auch die Zahl 2 nicht abfangen.
4:41 du sagst zwar kongruent, schreibst aber = Fehlt hier nicht das Kongurenzzeichen? Die Schreibweise mit = finde ich uneindeutig, man kann es auch falsch interpretieren.
Bei einer Million sollte es doch noch gehen, alle interessanten zu prüfen (Wurzel ist 1000, für 100 000 000, 10 000, und das sollte man durchgehen können, vorallem weil man nur ungerade zahlen prüfen muss, was es nochmal halbiert)
Wie schlimm ist es eigentlich, wenn man für den RSA algorithmus ausversehen zwei dreihundert stellige nicht Primzahlen erwischt, weil der Miller rabin Algorithmus ja probabilistisch ist?
@@Florian.Dalwigk kann nur sagen dass diese art von videos die sind, bei denen du von mir garantiert 100% watchtime bekommst... aber klar, die zielgruppe für sowas ist ziemlich klein
Wenn "p" aber groß wird, wird auch dieses Verfahren an seine Grenzen kommen, was mache ich dann? Wir suchen ja Primzahlen, die bis zu 2048 Bit (= 256 Byte) groß sind. In Rust gibt es einen Datentyp "u128"....
Der Algorithmus arbeitet nur mit integern, und für diese gibt es libs (je nach Programmiersprache heißen die unterschiedlich, z.B. BigInt, oder BigInteger, oder BigNum, etc.). Die Komplexität der Standardoperationen auf Integern ist relativ gut, sodass man damit auch hundert- oder tausendstellige Zahlen halbwegs flott abarbeiten kann. Potenzieren klingt hier jetzt erstmal wie ein Problem, ist es aber nicht. Angenommen du potenzierst 256 Byte mit 256 Byte, dann kann das Resultat maximal 256*256 = 65536 Stellen lang sein (bei heutigen Computern ist 65k RAM kein Problem, wie die Rechenzeit aussieht weiß ich nicht, wenn die Operation in der lib ist wird sie vermutlich optimiert sein und funktionieren). Natürlich wird es unangenehm, wenn du "Megabytegroße" Zahlen potenzieren willst, aber alles darunter sollte gehen. Für "Potenzieren mit Modulo" gibt es noch ein paar Tricks, aber da kenne ich mich nicht aus, das muss man selbst googeln.
@@MarsCorporations Mir geht es darum, die Potenz möglichst genau errechnen zu können. Ja, es geht um Integer, aber 2^1024 sind schon 1,7977E308 (308 Nullen), was ist dann 2^2048? Vielleicht kann mal wer kurz sagen, wieviele Stellen denn eine solche Primzahl haben sollte (nicht in bit, 10er System bitte). Diese Zahlen kann ich mir gerade nicht mehr selber vorstellen.
kleine Anmerkung:
wenn bei `a = random.randrange(2, p)` die Zahl p-1 gewählt wird und p ungerade ist, gibt die Funktion garantiert True zurück (p-1 ist ja kongruent zu -1 modulo p).
Außerdem ist es natürlich ineffizient, erst die Potenz `a ** (p - 1)` zu berechnen und dann erst modulo p zu reduzieren. 1024-bit große Zahlen lassen sich damit jedenfalls nicht testen.
Eine leicht optimierte Variante der Funktion könnte so aussehen:
def fermat(p, k):
for runs in range(k):
a = random.randrange(2, p-1)
if pow(a, p-1, p) != 1:
return False
return True
die builtin pow Funktion berechnet `base ** exp % mod` deutlich effizienter, da durch häufigere modulo-Reduktionen die Zwischenergebnisse klein gehalten werden. Eine Implementierung könnte folgendermaßen aussehen:
def mod_pow(base, exp, mod):
r = 1
while exp:
if exp % 2 == 1:
r = r * base % p
base = base * base % p
exp //= 2
return r
Allerdings muss ich hier auch anmerken, dass diese Implementierung nicht für RSA-Berechnungen mit dem geheimen Schlüssel geeignet ist, da der if-Block im while-loop die Funktion anfällig für Seitenkanalangriffe macht.
Vielen Dank für das tolle und gut verständliche Video!
Sehr gerne 😊
Bitte mehr solcher Videos :) Kannst du auch Videos über Endliche Körper und Elliptische Kurven machen?
Leider werden diese Videos im Vergleich zu anderen Videos nur sehr selten angeschaut :( Elliptische Kurven stehen aber noch auf dem Plan :)
Sehr nice Erklärung!
Danke fürs Feedback!
1:41 Eine Primzahl ist eine natürliche Zahl, die genau zwei Teiler hat und nicht eine Zahl die nur durch 1 und sich sich selber teilbar ist. *Klugscheißermodus aus* :) Dann muss man auch die Zahl 2 nicht abfangen.
;)
Mich würde interessieren wie Florian seine Videos macht. In einem Q&A wurde ja mal angekündigt, dass dazu ein Video kommt. Jemand nen Link?
Das bleibt erstmal ein Betriebsgeheimnis 🤫
Hilft sehr für das Verständnis von Cryptography Challenges in CTFs von Hack the Box :)
Das ist super :)
Ja, gerade bei Crypto Challenges sollte man sich nicht vor Mathe fürchten
interessant, kannte den algorithmus nicht allerdings denke ich kann ich den gut für eigene projekte verwenden! danke
Auf jeden Fall!
4:41 du sagst zwar kongruent, schreibst aber =
Fehlt hier nicht das Kongurenzzeichen? Die Schreibweise mit = finde ich uneindeutig, man kann es auch falsch interpretieren.
Man kann beides nutzen
hallo ich würde mir wohl gerne ein video wünschen über cloudflare warp wie es genau funktioniert und was es macht ist bestimmt interessant
Ist aktuell nicht geplant
Wäre es nicht nützlich sicherzustellen, dass bei "a = random. randrange (2, p)" a sich nicht wiederholt?
Kann man machen, kommt aber selten vor und kann deshalb vernachlässigt werden
Bei einer Million sollte es doch noch gehen, alle interessanten zu prüfen (Wurzel ist 1000, für 100 000 000, 10 000, und das sollte man durchgehen können, vorallem weil man nur ungerade zahlen prüfen muss, was es nochmal halbiert)
Ich meinte hier ja im Kopf ;)
@@Florian.Dalwigk achso, okay
Gibt es eine Möglichkeit, die Chance der Richtigkeit abzuschätzen?
Das ist die Challenge am Schluss
Wie schlimm ist es eigentlich, wenn man für den RSA algorithmus ausversehen zwei dreihundert stellige nicht Primzahlen erwischt, weil der Miller rabin Algorithmus ja probabilistisch ist?
Dann funktioniert der RSA nicht.
Aber wieso verwendet man dann probabilistische Algorithmen dafür? Ich meine, sind die bei 300 stelligen Primzahlen überhaupt sicher
Wird im Video erklärt.
Gerade bei 300-stelligen Primzahlen ist die Wahrscheinlichkeit, dass der Test fehlschlägt, extrem gering.
wird ja ne ganze " RSA verstehen " videoreihe xD
Kryptographie verstehen ;)
@@Florian.Dalwigk kann nur sagen dass diese art von videos die sind, bei denen du von mir garantiert 100% watchtime bekommst... aber klar, die zielgruppe für sowas ist ziemlich klein
@@Florian.Dalwigk ich schau mir solche Videos an :D Die meisten aus Interesse, aber zugegebenermaßen manche auch zur Prüfungsvorbereitung XD
Das freut mich sehr, danke dir :)
Genau dafür mache ich sie ja eigentlich ;)
Sollte für die Kongruenz nicht ≡ benutzt werden anstatt = (4:34)
Man kann beides nehmen
Wenn "p" aber groß wird, wird auch dieses Verfahren an seine Grenzen kommen, was mache ich dann? Wir suchen ja Primzahlen, die bis zu 2048 Bit (= 256 Byte) groß sind. In Rust gibt es einen Datentyp "u128"....
Wieso? Modulo-Rechnung ist sehr günstig von der Laufzeit
@@Florian.Dalwigk Ich vermute, er meint, um auch bei großen Zahlen eine hohe Genauigkeit zu bekommen, muss mann dann auch mehr Durchgänge machen.
Gar nicht Mal unbedingt, wenn es nicht gleich eine Carmichael Zahl ist.
Der Algorithmus arbeitet nur mit integern, und für diese gibt es libs (je nach Programmiersprache heißen die unterschiedlich, z.B. BigInt, oder BigInteger, oder BigNum, etc.). Die Komplexität der Standardoperationen auf Integern ist relativ gut, sodass man damit auch hundert- oder tausendstellige Zahlen halbwegs flott abarbeiten kann. Potenzieren klingt hier jetzt erstmal wie ein Problem, ist es aber nicht. Angenommen du potenzierst 256 Byte mit 256 Byte, dann kann das Resultat maximal 256*256 = 65536 Stellen lang sein (bei heutigen Computern ist 65k RAM kein Problem, wie die Rechenzeit aussieht weiß ich nicht, wenn die Operation in der lib ist wird sie vermutlich optimiert sein und funktionieren). Natürlich wird es unangenehm, wenn du "Megabytegroße" Zahlen potenzieren willst, aber alles darunter sollte gehen. Für "Potenzieren mit Modulo" gibt es noch ein paar Tricks, aber da kenne ich mich nicht aus, das muss man selbst googeln.
@@MarsCorporations Mir geht es darum, die Potenz möglichst genau errechnen zu können. Ja, es geht um Integer, aber 2^1024 sind schon 1,7977E308 (308 Nullen), was ist dann 2^2048? Vielleicht kann mal wer kurz sagen, wieviele Stellen denn eine solche Primzahl haben sollte (nicht in bit, 10er System bitte). Diese Zahlen kann ich mir gerade nicht mehr selber vorstellen.