Hallo Leute, ich habe mich eben ein bisschen mit RSA beschäftigt. Nun habe ich mir die Frage gestellt, wieviele 768-Bit Primzahlen es gibt und wieviele verschiedene Schlüsselpaare (n=p*q) damit generiert werden können p und q jeweils eine 768-Bit Primzahl sind.
Wäre schön wenn mir jemand da weiterhelfen kann, oder mir einen link geben kann wo ich das nachlesen kann.
Danke schonmal im Vorraus.
lg
Tach,
Hallo Leute, ich habe mich eben ein bisschen mit RSA
beschäftigt. Nun habe ich mir die Frage gestellt, wieviele
768-Bit Primzahlen es gibt und wieviele verschiedene
Schlüsselpaare (n=p*q) damit generiert werden können p und q
jeweils eine 768-Bit Primzahl sind.
Die Anzahl der Primzahlen, die kleiner sind, als eine feste Zahl x, laesst sich mit dem Primzahlsatz abschaetzen, siehe fuer den Anfang http://de.wikipedia.org/wiki/Primzahlsatz dazu. Die Anzahl der Paare ist dann einfache Kombinatorik.
Gruss
Paul
Also müsste ich theoretisch ausrechnen wieviele 767-Bit und wieviele 769-Bite Primzahlen es gibt und dann einfach subtrahieren?
Irgendwie verstehe leider den Primzahlsatz nicht wirklich.
(x/ln x)
Also müsste ich theoretisch ausrechnen wieviele 767-Bit und
wieviele 769-Bite Primzahlen es gibt und dann einfach
subtrahieren?
Noe, Du berechnest wieviele Primzahlen es gibt bis zur hoechsten 768-Bit Zahl und ziehst davon die Anzahl der Primzahlen bis zur hoechsten 767-Bit Zahl ab.
Was muss ich nun in diese Gleichung für das x einsetzen?
Die groesste Zahl, ueber die Du wissen willst, wieviele Primzahlen es gibt, die kleiner sind, als diese Zahl. Wenn man es genauer haben will, gibt es sicher Tafelwerke dazu.
Gruss
Gut, dankeschön bis hierher schonmal =)
Jetzt habe ich aber erneut ein Problem mit den großen Zahlen.
Ich habe jetzt in die Gleichung eingesetzt, kann aber nichts ausrechnen weil kein Taschenrechner von mir eine Rechnung mit 2^767 ausführen kann.
Ich bin jetzt soweit: ((2^767)*766)/408302,506
wie rechne ich das jetzt aus?
Tach,
Jetzt habe ich aber erneut ein Problem mit den großen Zahlen.
Ich habe jetzt in die Gleichung eingesetzt, kann aber nichts
ausrechnen weil kein Taschenrechner von mir eine Rechnung mit
2^767 ausführen kann.Ich bin jetzt soweit: ((2^767)*766)/408302,506
wie rechne ich das jetzt aus?
Na Moment nicht so schnell. Ueberlegen wir uns zunaechst Mal, was die groessten darstellbaren Zahlen ueberhaupt sind. Bei 1 Bit gibt es insgesamt 2^1 Zahlen, naemlich 0 und 1, die hoechste ist 1, bei 2 Bit sind es 2^2 Zahlen 0, 1, 2, 3, die hoechste ist 3 usw. Also liegt der Schluss nahe, die hoechste mit n Bit darstellbare Zahl ist 2^n-1 . D.h. fuer uns, dass die groesste darstellbare 768-Bit Zahl 2^{768}-1 ist, und die hoechste darstellbare 767-Bit Zahl eben 2^{767}-1.
Der Primzahlsatz sagt, dass fuer grosse x (und 2^{768}-1 ist schon IMHO recht gross) gilt:
\lim_{x \to \infty}\frac{\pi(x)}{\frac{x}{\ln(x)}} = 1
,
mit anderen Worten der Ausdruck \frac{x}{\ln (x)} gegen die Anzahl der Primzahlen strebt, die kleiner als x sind.
Mit anderen Worten muss man rechnen
\frac{2^{768}-1}{\ln (2^{768}-1)}-\frac{2^{767}-1}{\ln (2^{767}-1)}
was schon ne ziemlich grosse Zahl ist, was auch nicht verwundert, denn 2^{768}-1 ist ja auch ne ziemlich grosse Zahl.
Wie auch immer, gerundet kriegt man fuer die Anzahl der nur 768-bittigen Primzahlen 1.4563*10^228. Jetzt darfst Du Dir die Anzahl der Paare ueberlegen 
.
Gruss
Paul
ja…und genau daran scheitere ich gerade =)
danke dir auf jedenfall schonmal für die bisherigen antworten. haben mir echt sehr geholfen.
also wenn ich jz rausfinden will wieviele n=pq es gibt, dann müsste das doch eine aufgabenstellung der kombinatorik sein oder?
kann man das da nicht mit dem urnenmodell herausfinden?
oder gibt es da bessere und einfachere(effektivere) möglichkeiten?
Moin nochmal,
also wenn ich jz rausfinden will wieviele n=pq es gibt, dann
müsste das doch eine aufgabenstellung der kombinatorik sein
oder?
kann man das da nicht mit dem urnenmodell herausfinden?
oder gibt es da bessere und einfachere(effektivere)
möglichkeiten?
http://www.schulminator.com/mathematik/kombinatorik
Schau Dir das an, insbesondere das letzte Beispiel (allerdings kenne ich die RSA-Verschluesselung nicht, wenn p,q nicht das Gleiche ist wie q,p passt gerade dieses Beispiel nicht, man kann sich dann ueberlegen wie man es modifiziert).
alles klar, ich danke dir vielmals für deine hilfe =)
Hallo,
also wenn ich jz rausfinden will wieviele n=pq es gibt, dann
müsste das doch eine aufgabenstellung der kombinatorik sein oder?
es gibt einfach
(1.4563 · 10228)2 ≈ 2.12 · 10456
mal soviele Zweierkombinationen, wobei je zwei Paare davon wegen des Kommutativgesetzes der Multiplikation dasselbe Produkt ergeben (p1 · p2 = p2 · p1. Ansonsten sind aber sämtliche Produkte natürlich voneinander verschieden!).
Die Größe der Zahl 10456 liegt jenseits jeder Vorstellungskraft. Falls Du Dich fragst, ob Du irgendeine Chance hättest, alle Kombinationen systematisch durchzutesten: Die Antwort lautet ‚nein‘. Selbst wenn Dir alle Computer der Welt alleine zur Verfügung stünden: Eine Milliarde Rechner, von denen jeder eine Milliarde Kombinationen pro Sekunde testen kann, würden in drei Jahren gerade mal lächerliche 1026 Kombinationen schaffen (109 · 109 · 60 · 60 · 24 · 365 · 3 ≈ 1026), also nur den etwa 10430-ten Bruchteil der Aufgabe.
Gruß
Martin
Falls Du Dich fragst, ob Du irgendeine
Chance hättest, alle Kombinationen systematisch durchzutesten:
Die Antwort lautet ‚nein‘.
Mit Quantencomputern würde sich das ändern. Die könnten nämlich alle Kombinationen gleichzeitig testen. Aber beim derzeitigen Tempo der technischen Entwicklung wird das wohl noch ein paar Jahrzehnte graue Theorie bleiben.
768-Bit Primzahlen es gibt und wieviele verschiedene
Schlüsselpaare (n=p*q) damit generiert werden können p und q
jeweils eine 768-Bit Primzahl sind.
Hallo,
nachdem es ja schon jede Menge Antworten zur Anzahl von Primzahlen gibt, möchte ich noch in die Waagschale werfen: Es ist nicht sehr geschickt, die Primzahlen p und q mit derselben Zahl von Bits zu wählen, weil es Zerlegungsalgorithmen gibt, die von oben her operieren. Daher wird meist empfohlen, ein paar Bits Abstand zu lassen, also statt 768 und 768 lieber 764 und 772 Bit zu wählen, was einfach den Suchraum bei einer brute-force Methode unangenehm vergrößert.
Grüße, guidot