Die Mathe-Redaktion - 20.08.2018 01:21 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt1 im Schwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 112 Gäste und 12 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » RSA-ähnliche und Carmichael-ähnliche Semiprime sauber unterscheiden?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule RSA-ähnliche und Carmichael-ähnliche Semiprime sauber unterscheiden?
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 507
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-03-25


Oft merke ich erst anhand der Rechenzeit (z.B. von
www.alpertron.com.ar/ECM.HTM
www.lamprechts.de/gerd/php/Carmichael-Zahl-Faktorisierer.php
), ob es sich bei einer Zahl, die ein Produkt 2er großer Primzahlen ist,
um eine RSA-ähnliche wie:
71641520761751435455133616475667090434063332228247871795429
(fast 1 min oder Stunden...)

oder um eine Carmichael-ähnliche
179103801904378588637834164217859841067625324523260639289603
(Rechenzeit unter 1 s)
Semiprime handelt.

a) Gibt es saubere unterscheidbare Benennungen dieser Semiprimes?
(RSA-ähnliche und Carmichael-ähnliche war jetzt meine Wortschöpfung)

b) Kann man sie schon vor Start der Berechnung unterscheiden z.B. per Phi- oder
de.wikipedia.org/wiki/Carmichael-Funktion
?

c) Wie wird bei Erstellung einer RSA-Zahl sichergestellt, dass sie sich durch gewisse Abkürzungen
(wie der "Carmichael-Entschlüsselungs-Algorithmus") nicht so leicht entschlüsseln lässt?
(ohne dabei den kompletten Elliptic Curve Method-Algorithmus anzuwenden)

d) Gibt es neben diesen beiden Semiprime noch weitere Zahlen,
die aus 2 großen (aber stark unterschiedlichen - also Differenz größer 10^29) Primzahlen zusammengesetzt sind und weder
RSA-ähnlich noch Carmichael-ähnlich sind? Beispiele?



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2794
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-03-25


Definiere mal, was du mit RSA-ähnlich meinst.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 507
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-03-26


2018-03-25 22:46 - cyrix in Beitrag No. 1 schreibt:
Definiere mal, was du mit RSA-ähnlich meinst.
Cyrix

Egal welche Internetseite ich über RSA-Zahlen fand (Beispiel
Wikis RSA )
steht überall nur was vom Mindestabstand 2er Primzahlen p und q, und wie man die Zufallsgeneratoren unabhängig voneinander macht.

Nirgend habe ich gefunden, dass diese beiden Zahlen nicht im Carmichael-Verhältnis (6m+1) und (12m+1)
oder (6m+1) zu (18m+1)
oder... stehen dürfen?!

Oder habe ich eine Sicherheitslücke entdeckt, die bisher nur Zufällig noch nicht beachtet wurde?

Aber alle Zahlen unter RSA_Factoring_Challenge
haben diese Carmichael-Verhältnisse nicht -> daher habe ich sie RSA-ähnliche genannt. Ich hätte sie auch "extrem schwer zu faktorisierende Semiprime" nennen können.

War das Zufall, oder könnte nicht doch ein RSA-Generator zufällig 2 solcher Zahlen generieren? Man ließt ja oft solche Dinge wie:
unsichere Krypto-Schlüssel

Da ich keine Fakten gefunden habe, nochmal eine Auflistung, wie ich diese beiden Semiprime n= p * q indirekt unterscheide:

a) {extrem schwer faktorisierbare; bisher nur bei RSA-Zahlen}
- Carmichael-Algorithmus liefert ab 20 Stellen kein Ergebnis
- ECM-Algorithmus braucht bei 59 Stellen etwa 1 min
(10^95-1293)/1134474340501050437624729 braucht 1 min 41 s
und ab 230 Stellen Jahre
- EulerPhi(n)/CarmichaelLambda(n) meist 2...42 {kann leider nicht überprüft werden, da beide eine Primezahlzerlegung benötigen, die es für die meisten RSA-Zahlen nicht gibt}

b) leicht zu faktorisierende meist Carmichael-ähnliche {keine echten Carmichael Zahlen aber bekannte a*m+b Verhältnisse}
- Carmichael-Algorithmus liefert selbst bei 1000stelligen Zahlen in wenigen Sekunden ein Ergebnis
- ECM-Algorithmus braucht bei vielen 100stelligen Zahlen oft nur Sekunden
- EulerPhi(n)/CarmichaelLambda(n) meist (p-1)

Unter factordb gibt es viele Semiprime, die noch nicht exakt zerlegt wurden. Die meisten gehören zum Typ a) aber ich habe auch schon einige (50...400stellige) mit dem Carmichael-Zahl-Faktorisierer zerlegen können und dann den gesuchten Faktor dort eingetragen/hochgeladen.
Dieser Algorithmus für b) ist dort also noch nicht bekannt.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 507
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2018-03-26


Interessant ist die 667stellige Zahl:
2629630079999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999756765608116686400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005624647535485806134401

schaffen factordb & ECM nicht in 26 min

ABER ein mit GMP-optimierter Carmichael-F.... in weniger als 0,5 s !!

Na da werde ich mir mal ein paar RSA-Codes vornehmen...



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 510
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-04-13


Was ist mit den Brilliant-Zahlen ?

100000000000000000000000000000000000000000000000000000000000002317

Die Faktoren sind bekannt, wie lauten diese mit Deinem Code ?



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 507
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2018-04-16


Leider gehören alle bisher von mir getesteten dieser "Brilliant-Zahlen"
zu den RSA-ähnlichen, die mein Algorithmus nicht so schnell findet.

Das bedeutet aber nicht, dass es für alle gilt.

Das Verhältnis ist leider sehr ungünstig für die Carmichael-ähnlichen,
was auch mit wachsender Größe noch ungünstiger wird.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 507
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-07-25 17:20


Habe endlich was gefunden zu unsicheren RSA-Zahlen:
ROCA_vulnerability

Das ist schon mal eine bekannte Lücke, mit der die beiden Faktoren schneller als "normal" gefunden werden können.

Damit gibt es schon mal eine 4er Unterscheidung, die auf keiner
mir bekannten Seite zur Bildung von RSA-Zahlen genannt wurde:
a) echte RSA-Zahl (300 Stellen in 100 Jahren)
b) ROCA-RSA (300 Stellen in wenigen Stunden)
c) Carmichael-Varianz (300...1000 Stellen in etwa 10 min)
d) Carmichael-ähnlich (300 Stellen in 2s ... 4 min)

Könnte durchaus sein, dass b) und c) Gemeinsamkeiten haben.
(und somit mein Carmichael-Varianz-Programm ROCA-RSA finden kann)



  Profil  Quote  Link auf diesen Beitrag Link
hyperG hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]