Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Prüfung auf Echtheit einer RSA-Zahl
Autor
Universität/Hochschule Prüfung auf Echtheit einer RSA-Zahl
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1701
  Themenstart: 2022-05-25

Unter hier hatte pzktupel ja einen interessanten LINK zum Generieren von "RSA-Zahlen" gepostet. Zunächst fand ich es interessant, aber bei genauer Analyse stellte ich fest, dass einfach nur große Primzahlen miteinander multipliziert wurden, OHNE die Bedingungen für Starke Primzahlen (für die Primfaktoren) einzuhalten! Beispiel 1: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_keineRSA.PNG Schon der WilliamsP1-Test lieferte nach 0.199 s das Ergebnis (echte RSA braucht über 15 min!!) Faktor1 = 36481010466005958793 Faktor2 = 8125482146890370023 Dann wurde bei den Primfaktoren-Untersuchungen festgestellt: - die Größe des Primzahl-Nachfolgers nicht erreicht (orange) - die Differenz der umgebenen Primzahlen liegt nicht über 60 (rot) https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_keineStarkePrimzahl.png Kennt jemand noch andere Kriterien, die eine RSA-Zahl erfüllen muss? (außer die Größe selbst, denn alles unter 60 Stellen schafft SIQS unter 4 s.) Natürlich kann ich weitere Beispiele nennen, aber dazu wären schnellere Testverfahren Hilfreich... Ein weiteres Beispiel wäre der Carmichael-Test (den ich auch in unter 1 s finde), aber da diese seltener vorkommen, hatte ich noch kein Beispiel... Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1701
  Beitrag No.1, vom Themenstarter, eingetragen 2022-05-28

Hier ein schöner Fall, wo ALLE Faktorisierer relativ schnell zum Ziel kamen (was bei echten RSA NIE der Fall ist), da beide Faktoren nicht "Starke Primzahlen" sind: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_MehrereFundstellenQuelle.png https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_MehrereFundstellen.png Ein Faktor hat sogar einen winzigen Max[FactorInteger[q1 - 1]]=157 und beide p - (pv + pn)/2 sind statt > 60 hier nur < 0. Und laut Wiki: "... starke Primzahl im kryptographischen Sinn eine ganze Zahl p, wenn sie folgende Eigenschaften erfüllt: p kann nicht mit der Pollard-p-1-Methode in einer angemessenen Zeit faktorisiert werden..." -> auch nicht erfüllt! Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1701
  Beitrag No.2, vom Themenstarter, eingetragen 2022-05-30

Hier noch eine interessante Eigenschaft von "echten RSA-Zahlen": Bei der Untersuchung bekannter https://en.wikipedia.org/wiki/RSA_numbers (von 59 ... 220stellig) habe ich (noch) keinen einzigen Primfaktor gefunden, der sich mit den https://mathworld.wolfram.com/Prime-GeneratingPolynomial.html darstellen lässt (50 Faktoren * 7 Umkehrfunktionen = 350 Fälle!). Da ich nicht an Zufälle glaube & 350 Fälle schon recht viel ist, glaube ich, dass die RSA-Zahl Ersteller tunlichst vermieden haben, dass ihre Faktoren durch Polynome dargestellt werden können, die häufig Primzahlen als Funktionsergebnis haben. Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1701
  Beitrag No.3, vom Themenstarter, eingetragen 2022-06-02

Dieser heise.de Artikel kommt gerade recht, denn diese "alte Faktorisierungsmethode von Fermat" hatte ich bisher vergessen. Auch Mathematica und SIQS sind nach mehreren Minuten nicht fertig (schwach!)! Dieser recht einfache Algorithmus beginnt im Gegensatz zu vielen anderen "von HINTEN": \sourceon einfaches Beispiel -----BEGIN RSA PUBLIC KEY----- MIIBCgKCAQEAkGbTtoSrOJmrwu9FV3A3xDfxNn3EnSO94M9+QIL3qJjjIMh30xrA dra5ZsXjhJrRApI0X+qArvTQVv6/n9YqEoAPmF7n46yJ1TtYETFzGCjqk1sDZ8rV Enq4bxPHk0EQcFiQIn6iwTPOjeidD2WKUNIVeJWI/2X8Ms3ITdt+P4jV0DVeA6rd R31ClG+HGos1OdTA+8nMwDId0jA/Kv8MOPFBLf24p9OB8fzXP2Uno0CSSrZLktJC ouOcPzGgBB5sZZFHxpsrf76uJNULBrjC9Pbxx3ogpGVy1L5CC9v8qk3L44qQpi4g /PC9wWNsK+NPr/tiq4+S3uB369Ye1n+0ywIDAQAB -----END RSA PUBLIC KEY----- -> to Number: 617 digits 18229021800499389179810999984147294316694481152259999178780074391429829111773881276038281122549654793695493293264207027376776682362226410733793123117211189262610875849497690435072434819643299230953875973012904516275649075242502330535166202977871076698326460570645695302887174347984232777274357996755103073370058925661345782916623908813122753869187282565276059526610380429671250747371523249129041042163813118053400537221212684975928016171244322844087003229657728793172722938168054943184764356498974298899669556165909647342688587153673679901583046195388386919521461435059782679160323429508745816818692733354205358568651 Start Fermat-Faktorisierung: n =1 p1=135014894735726802994479525124352606532682846869442467562232794161640007287732786286283457311587668258176672980526094032686312091076836119124819656545483473480249909911612176917264687950236058109468569144842605356817468423547274115168118770595461844004588922031840797062251736926993769808445959955789590683383 p2=135014894735726802994479525124352606532682846869442467562232794161640007287732786286283457311587668258176672980526094032686312091076836119124819656545483473480249909911612176917264687950236058109468569144842605356817468423547274115168118770595461844004588922031840797062251736926993769808445959955789590683597 in 0,002 s \sourceoff Wow. Natürlich ist dieses Beispiel hoch primitiv, aber ein ganz wichtiger Punkt beim Erstellen "ECHTER RSA Zahlen"! Der Test hat auch eine gute Eigenschaft: lässt sich gut parallelisieren! Gut für Rechner mit vielen Kernen! Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1701
  Beitrag No.4, vom Themenstarter, eingetragen 2022-06-05

Hier eine schöne "pseudo-RSA-Zahl", wo zwar die Primfaktoren "stark" sind, aber bezüglich des Fermat-Tests zu eng beieinander liegen. Die Größe wurde extra für SIQS optimiert (69...99 Stellen liegt der gut vergleichbare Bereich): \sourceon nameDerSprache 3761844347944019380812448477142805854310131054241322463562897739716154279181742220781 Faktorisierer | Berechnungszeit ---------------------+-------------------------- Pollard.., Williams, > 1 h (nicht abgewartet!) Carmich..., > 1 h (nicht abgewartet!) Mathematica > 1 h (nicht abgewartet!) alpertron.com 18 min 48 s yafu\siqs 8 Threads 55.7 s Fermat c# 1 Thread 17.35s Fermat GMP 1 Thread 1.01s \sourceoff Erstaunlicherweise tut sich alpertron sehr schwer mit dieser Zahl: kurz nach Start kleiner Absturz https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Keine_RSA_zuDichtFermat_Alpertron.png der sich aber mit F5 überspringen lässt. Interessant: diese Internetseite startet per (Google-) Browser mindestens 2 software_reporter_tool.exe und rechnet so mit mindestens 3 Threads parallel! (da wird bestimmt bald eine Sicherheitslücke wie damals bei JAVA gefunden...) Auch Mathematica kommt mit dieser Zahl nicht zurecht. c# war bei vielen Tests über 50 mal langsamer als c++ mit GMP. Je größer solche Zahlen werden, die zwischen "leicht mit Fermat... lösbar" und "echte RSA" liegen (der Übergangsbereich ist bei großen Zahlen ja riesig), um so größer wird auch der Abstand der Berechnungszeiten vom "Fermat GMP" zu SIQS. Mit mehreren Threads sind solche scheinbaren RSA-Zahlen in Millisekunden faktorisierbar! Ich habe absichtlich das Ergebnis der Faktoren nicht mit angegeben, damit jeder mal die Besonderheit dieser "pseudo-RSA-Zahl" selbst probieren kann. Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1701
  Beitrag No.5, vom Themenstarter, eingetragen 2022-06-08 23:05

Noch eine schöne "pseudo-RSA-Zahl", die eine ROCA-Verwundbarkeit hat und daher NICHT zur RSA-Verschlüsselung verwendet werden darf: \sourceon nameDerSprache 622971998446174998172136977037451396466894127370024805494879139320167898406063955838066322719921651671196240961 Faktorisierer | Berechnungszeit ---------------------+-------------------------- SIQS 8 Threads | 1,53 Stunden! GMP_ROCA_Faktorisier | 1,8 s \sourceoff Und es gibt noch mehr...


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]