1. Foren
  2. Kommentare
  3. Sonstiges
  4. Alle Kommentare zum Artikel
  5. › Universell programmierbarer…

An alle Verschlüsselung-Leute

Neue Foren im Freiraum! Raumfahrt und freie Software haben jetzt einen Platz, die Games tummeln sich jetzt alle in einem Forum.
  1. Thema

Neues Thema Ansicht wechseln


  1. An alle Verschlüsselung-Leute

    Autor: Verschl 19.11.09 - 10:37

    Verschlüsselungsverfahren die auf NP-vollständigen Problemen basieren (auch asymetrische) sind mit Quantencomputer ebenfalls nicht knackbar (nach aktuellen theoretischen Standpunkt), da die Klasse BQP höchstwahrscheinlich NP nicht umfasst.

    D.h. beispielsweise das "McElise" Verfahren ist weiterhin ideal zur Verschlüsselung. Zwar benötigt es O(n^2) große öffentliche Schlüssel, aber es gibt bereits O(n) Varianten des Algorithmus.

    Fazit: "Nur" Verschlüsselungen basierend auf Faktorisierung (RSA) und diskretem Logarithmus (ElGamal) sind damit knackbar, nicht Verschlüsselungen basierend auf NP-vollständigen Problemen!

  2. Re: An alle Verschlüsselung-Leute

    Autor: Siga4329428742 19.11.09 - 11:40

    Kannst Du die O-Klassen von Defaktorisierung nennen. Die weiss ich gerade nicht.
    Oder war das nur O(n^3) oder sowas in der Richtung.

    Ich habe von Quanten-Rechnern zwar auch etwas, wenn ich n^3 in n^2 verwandle weil ich n*... parallelisiere.
    Aber ich bleibe doch dann in P wenn ich vorher schon drin war.

    Aber ich dachte, der Effekt wäre, das man auch bei O(x^n) einfach alle x und/oder n in einem Schritt durchprobieren kann.
    Bin jetzt nicht mehr so ganz in dem Thema drin.

  3. Re: An alle Verschlüsselung-Leute

    Autor: Faktorisator 19.11.09 - 14:28

    Zahlenfaktorisieren liegt auf jeden Fall in P. Da gab's vor 3-4 Jahren einen Beweis dazu. Afair kein praxisrelevantes P, aber doch in P :)

  4. Re: An alle Verschlüsselung-Leute

    Autor: Verschl 19.11.09 - 16:48

    Kurze Antwort: NEIN

    "PRIMES is in P" lauetet der sensationelle Artikel, der besagt, das wir in polynomieller den Status bestimmen können, ob eine Zahl eine Primzahl ist oder nicht. Also nur JA / NEIN. Im Falle von NEIN liefert der Algorithmus NICHT die Primfaktoren, er beweist lediglich, dass ein Primfaktor existiert, nicht welcher.

  5. Re: An alle Verschlüsselung-Leute

    Autor: Verschl 19.11.09 - 16:52

    Der Status des Problems der Primfaktorzerlegung ist UNBEKANNT. Die besten Algorithmen haben Laufzeiten der Form O(a^f(n)) mit a > 1. D.h. sie sind exponentiell bzw. manche subexponentiell, jedoch WEIT ENTFERNT polynomiell zu sein.

    Der Quantencomputer dagegen faktorisiert in O(N^3), wobei N immer die Bitlänge der Zahl ist, nicht die Zahl selbst!

  6. Re: An alle Verschlüsselung-Leute

    Autor: Pergwe 19.11.09 - 16:59

    .....man sollte es aber nicht DEfaktorisierung nennen, sondern nur Faktorisierung, sonst wäre es doppelt negiert, was dem multiplizieren zweier Zahlen entspräche.

  7. Re: An alle Verschlüsselung-Leute

    Autor: Tyrox 19.11.09 - 18:31

    Verschl schrieb:
    --------------------------------------------------------------------------------
    > D.h. beispielsweise das "McElise" Verfahren ist weiterhin ideal zur
    > Verschlüsselung. Zwar benötigt es O(n^2) große öffentliche Schlüssel, aber
    > es gibt bereits O(n) Varianten des Algorithmus.

    Könntest du mich bitte aufklären, was das für ein Verfahren ist?
    Der einzige Google-Treffer zu "McElise Verschlüsselung" ist dein Beitrag hier.

  8. Re: An alle Verschlüsselung-Leute

    Autor: Siga49274947 19.11.09 - 18:39

    > Der Status des Problems der Primfaktorzerlegung ist UNBEKANNT.

    Ich brauche nur 2 Stück zu finden. Nicht die komplette Zerlegung.
    Weil ich dann ja testen kann, ob x1*x2=Y die x1 und x2 Primzahlen sind. Nämlich in P.
    Bei RSA muss man doch nur 2 Primzahlen finden die passen. Und es "müssen" welche passen. Damit ist das Problem u.u. nur eine sehr spezialisierte und vielleicht "knackbare"(in P liegende) TeilMenge/Nullmenge des viel allgemeineren aber hier nicht nötigen Problems der völligen Zerlegung in alle Primfaktoren.
    Vielleicht habe ich es auch falsch verstanden.

    D.h. man braucht nur Durchprobieren
    1*1 1*2 1*3 ... 1*Y (1 natürlich nicht, nur ein Beispiel)
    2*1 2*2 2*3 ... 2*Y/2
    3*1 .... 3*Y/3
    Ich brauche Y, Y/2 usw. aber nicht berechnen sondern ich multipliziere bis ich über Y drübergelaufen bin.
    Statt multiplizieren addiere ich immer denselben Wert.
    Also z=2,3,4,6,... until z>=Y.
    Dann z=3,6,9,... until z>=Y

    Anders gesagt: Ich male das kleine einmaleins auf. aber in viel größer. Und Beenden tue ich es überall dort, wo man über Y drüber kommt. D.h. so eine Art "45-Grad"/Diagonal-1x1-Tabelle.

    Eine Stufe schlauer:
    Wenn man jetzt clever ist, bleibt man in der Nähe und probiert 2,4,6,8,... gar nicht durch.

    wenn ichg 87 zerlegen will (und zwar nicht ganz sondern nur in zwei Teile), probiere ich also 9*10=90,8*10=80 80<87<90.
    Dann von 9 auf 8 runter: 8*10=80, 8*11=88. 80<87<88.
    Dann von 8 auf 7 runter: 7*11=77, 7*12=84, 7*13=91, 84<87<91
    Dann von 7 auf 6 runter: 6*13=78, +6=84, +6=90, also 84<87<90 und 6*15 sind 90.
    usw.
    D.h. ich muss evtl nur selten multiplizieren und dann reicht addieren.

    Wie bei Schiffe versenken, "messe"/probiere ich die Kombinationen y1*y2 in der Nähe der gesuchten Zahl durch.
    Andere Gebiete interessieren dabei nicht.

    Und man kann bei einer treffenden Kombination einen schnellen Primzahltest benutzen. Man WEISS ja, das es zwei Primzahlen sein müssen und hat dann die Keys in der Tasche und spart sich fette Beweise, ob das wirklich Primzahlen sind. Damit ist die Aufgabenstellung deutlich vereinfacht und ich muss gar nicht die völlige Faktorisierung betreiben.

    Sind nur so Ideen.

  9. Re: An alle Verschlüsselung-Leute

    Autor: Verschl 19.11.09 - 20:43

    sorry versuch's mit:

    McEliece ... ;-)

  10. Re: An alle Verschlüsselung-Leute

    Autor: Verschl 19.11.09 - 20:52

    Die Ideen erinnert an das "Sieb des Eratosthenes".

    Leider ist der Algorithmus weiterhin exponentiell. Um eine Zahl x zu faktorisieren benötigst Du mit der Methode grob abgeschätzt ca. Wurzel(x) Schritte mit diesem Verfahren. Du testest nämlich dabei alle Primzahlen bis zur Wurzel, denn ein Faktor MUSS kleiner sein als die Wurzel.

    Eine Zahl der Größe x hat aber ca. N=LOG(x) Bitlänge. Wenn Du einen polynomieller Algorithmus sucht, muss das einer sein der O(N^k) Zeit benötigt bzw. O(N^LOG(x)).

    Wenn du die beiden Zahlen
    1827612346129834621846129
    1283461284612894612984621
    addierst, dann benötigt du ja auch Zeit die proportionale zur Länge der Zahl ist und nicht proportional zum Wert der Zahl.

  11. Re: An alle Verschlüsselung-Leute

    Autor: Siga283942497 19.11.09 - 23:07

    Ok. Ich glaub ich habs verstanden.

    N ist die BitZahl der Keys.
    Bei 1024 Bit habe ich 2^1024 Zahlen zur Auswahl und darin dann bis zur Wurzel von "irgendeiner" Zahl ist natürlich immer noch "exponentiell".

    Ich hatte falscherweise N als Größe der zu faktorisierenden Zahl interpretiert und mich dann gewundert, wieso das Problem aus P herausspringen sollte.
    Aber jetzt ist es "klar". N ist _nicht_ die Größe der Zahlen, sondern die Größe ist 2^KeyLänge und die KeyLänge ist N.
    Und wenn man 1 Bit dazutut, wird das SiebFeld/Multiplikationstabelle 2*2 also vier Mal größer.

  12. Re: An alle Verschlüsselung-Leute

    Autor: Der Kaiser! 20.11.09 - 02:41

    >> Könntest du mich bitte aufklären, was das für ein Verfahren ist?
    >> Der einzige Google-Treffer zu "McElise Verschlüsselung" ist dein Beitrag hier.

    > sorry versuch's mit: McEliece* ... ;-)

    *[en.wikipedia.org]

    ___

    Die ganz grossen Wahrheiten sind EINFACH!

    Wirkung und Gegenwirkung.
    Variation und Selektion.
    Wie im grossen, so im kleinen.

  1. Thema

Neues Thema Ansicht wechseln


Um zu kommentieren, loggen Sie sich bitte ein oder registrieren Sie sich. Sie müssen ausserdem in Ihrem Account-Profil unter Forum einen Nutzernamen vergeben haben. Zum Login

Stellenmarkt
  1. SAP Logistik-Berater (m/w/x) mit Fokus auf SD - SAP Logistic
    über duerenhoff GmbH, Darmstadt
  2. SAP S/4 HANA Manufacturing Berater (m/w/x)
    über duerenhoff GmbH, Raum Düsseldorf
  3. IT Security Spezialist (m/w/d)
    BAHAG AG, Mannheim
  4. IT-Systemadministrator (m/w/d) für das Referat IT-Infrastruktur
    DAAD - Deutscher Akademischer Austauschdienst e.V., Bonn

Detailsuche


Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Spiele-Angebote
  1. (u. a. Age of Empires Definitive Collection für 17,99€, Age of Empires Definitive Collection...
  2. 25,99€
  3. 28,99€


Haben wir etwas übersehen?

E-Mail an news@golem.de


Neue iPhones und mehr: Apple macht ein Päuschen
Neue iPhones und mehr
Apple macht ein Päuschen

Apple hat neue Produkte vorgestellt - Bahnbrechendes war nicht dabei. Selbst die Apple-Manager machten einen lustlosen Eindruck.
Eine Analyse von Tobias Költzsch

  1. NSO-Trojaner Apple schließt Sicherheitslücke in iOS, MacOS und WatchOS
  2. Apple Event für iPad und Macs soll später folgen
  3. Arbeitsplatz Apple feuert Managerin, die sich gegen Missstände aussprach

Raumfahrt: Braucht es Kernkraft für den Flug zum Mars?
Raumfahrt
Braucht es Kernkraft für den Flug zum Mars?

In den USA werden wieder nukleare Raketentriebwerke für Mars-Reisen entwickelt. Aber wie funktionieren sie und wird Kernkraft dafür überhaupt benötigt?
Von Frank Wunderlich-Pfeiffer

  1. Astronomie Flüssiges Wasser auf dem Mars war wieder ein Irrtum
  2. Raumfahrt Rocketlab baut zwei Marssonden für die Nasa
  3. Raumfahrt Mars-Hubschrauber Ingenuity gerät ins Trudeln

IAA: Die Greenwashing-Party der deutschen Autoindustrie crashen
IAA
"Die Greenwashing-Party der deutschen Autoindustrie crashen"

IAA 2021 Auf der IAA präsentiert die Automobilindustrie neue Autos, als gebe es keinen Klimawandel. Aktivisten wollen die "Klimakillerparty" blockieren - und haben die Argumente auf ihrer Seite.
Ein IMHO von Moritz Tremmel und Sebastian Grüner

  1. IAA Mobility 2021 Verbrenner sind nichts mehr fürs Image, nur für den Umsatz
  2. Autobahn-Proteste Aktivisten müssen bis Ende der IAA in Haft
  3. Re:Move Polestar präsentiert elektrischen Lastenscooter