Ich hab mal gelesen, dass man große Zahlen schnell faktorisieren kann, wenn für einen Primfaktor (p) die Zahl p+1 oder p-1 aus sehr kleinen Faktoren besteht.
Wie kann man RSA dagegen schützen?
Wie prüft man Faktoren, ob sie die Bedingung erfüllen?
bzw.
Wie erstellt man Faktoren, die die Bedingung erfüllen?
RSA gegen p+1, p-1 schützen
-
test123
- XBOX360-Installer
- Beiträge: 68
- Registriert: 26.02.2008 21:45
Re: RSA gegen p+1, p-1 schützen
Richtig ist, dass es Faktorisierungsverfahren gibt, die i.W. damit arbeiten, wie für einen (zu findenden) Primfaktor p Werte in dessen Umgebung zusammen gesetzt sind, also z.B. p-1 und p+1. Sie funktionieren, wenn in der Primfaktorzerlegung von p-1 bzw. entsprechende Werte jeder Faktor kleiner ist als eine vorgegebene Schranke.
Verwendet man die Faktorisierungsmethode mithilfe Elliptischer Kurven (ECM) läuft der Hase i.W. genauso, wobei abhängig von der betrachteten Kurve es nicht um p-1 oder p+1 geht, sondern um p+-s, wobei s eine ganze Zahl < sqrt(p) ist, aber sich in dem Bereich halbwegs gleichverteilt bewegt.
Dagegen kann man sich nicht wehren. Das einzige, was hilft, sind größere Primzahlen p für RSA zu verwenden, denn je größer diese sind, desto unwahrscheinlicher ist es, dass die Zahlen in der Umgebung von p in lauter kleine Primzahlpotenzen faktorisieren...
Verwendet man die Faktorisierungsmethode mithilfe Elliptischer Kurven (ECM) läuft der Hase i.W. genauso, wobei abhängig von der betrachteten Kurve es nicht um p-1 oder p+1 geht, sondern um p+-s, wobei s eine ganze Zahl < sqrt(p) ist, aber sich in dem Bereich halbwegs gleichverteilt bewegt.
Dagegen kann man sich nicht wehren. Das einzige, was hilft, sind größere Primzahlen p für RSA zu verwenden, denn je größer diese sind, desto unwahrscheinlicher ist es, dass die Zahlen in der Umgebung von p in lauter kleine Primzahlpotenzen faktorisieren...