Laden...

PKE geknackt...

Erstellt von Timur Zanagar vor 17 Jahren Letzter Beitrag vor 17 Jahren 10.945 Views
Timur Zanagar Themenstarter:in
1.457 Beiträge seit 2004
vor 17 Jahren
PKE geknackt...

Was nicht möglich schien, ist eingetreten: Die asymmetrische Verschlüsselung ist geknackt. Mit einem künstlichen Gehirn ist dieses Kunststücke schweizer Forschern in Rekordzeit gelungen.

Quelle: dotnetpro

Artikel als PDF Datei

Gelöschter Account
vor 17 Jahren

ha!

ich wußte das das geht.
ich wußte aber nicht das die idee schon vergriffen und dermaßen fortgeschritten sei.
RESPEKT.
jetzt hilft uns nur noch die quantenverschlüsselung.. für eine weile...

S
8.746 Beiträge seit 2005
vor 17 Jahren

Ja, und am 1. April kommt der Osterhase...

3.825 Beiträge seit 2006
vor 17 Jahren

😉

Lustig !

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

Gelöschter Account
vor 17 Jahren

Original von svenson
Ja, und am 1. April kommt der Osterhase...

naja bill gates hat ja auch mal geglaubt das man nie mehr wie 640kb für ein programm brauchen wird. (so hab ich das aufgeschnappt)

O
778 Beiträge seit 2007
vor 17 Jahren

...und ein damaliger IBM-Chef (hab den Namen vergessen) hat den weltweiten Markt für Computer auf "etwa 7" geschätzt, in der IT-Branche hat's schon ne Menge gewaltige Fehleinschätzungen gegeben...

2.921 Beiträge seit 2005
vor 17 Jahren

Vielleicht ist es ja einfach nur Quatsch?! Ich bin mir da auch nicht sicher, nicht einfach alles zu glauben ist ja ok. Ohne Skepsis läuft man auf jeden Fall öfter mal auf.

Aber:

  • seht euch mal an was Combots probiert...
  • augmented reality, hätte ich vor ein paar Jahren noch nicht für möglich gehalten
  • KI Chatbots
  • Blue Pill

Und das sind keine leeren Versprechungen, sondern diese Projekte existieren real, wenn man das auch teilweise vielleicht nicht glauben mag.

Es tut sich auf jeden Fall was. In allen Bereichen.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

S
8.746 Beiträge seit 2005
vor 17 Jahren

Ich finde es schöner, wenn man April-Scherze in Fachzeitschriften weniger leicht erkennt als in diesem Fall. Mal gucken was heise in diesem Jahr fabriziert....

Gelöschter Account
vor 17 Jahren

Original von svenson
Ich finde es schöner, wenn man April-Scherze in Fachzeitschriften weniger leicht erkennt als in diesem Fall. Mal gucken was heise in diesem Jahr fabriziert....

ähm.. april ist erst in fast 2 wochen...

T
512 Beiträge seit 2006
vor 17 Jahren

Original von dr4g0n76
Vielleicht ist es ja einfach nur Quatsch?! Ich bin mir da auch nicht sicher, nicht einfach alles zu glauben ist ja ok. Ohne Skepsis läuft man auf jeden Fall öfter mal auf.

Aber:

  • seht euch mal an was Combots probiert...
  • augmented reality, hätte ich vor ein paar Jahren noch nicht für möglich gehalten
  • KI Chatbots
  • Blue Pill

Und das sind keine leeren Versprechungen, sondern diese Projekte existieren real, wenn man das auch teilweise vielleicht nicht glauben mag.

Es tut sich auf jeden Fall was. In allen Bereichen.

Das ist das schöne an der Mathematik. Was bewiesen ist, bleibt auch so, da tut sich nichts.

Und es ist bewiesen, dass Public Key Knacken genauso schwer ist wie Primzahlfaktorisierung. Das heißt, dass der Aufwand exponentiell ist. Das heißt, wenn das tolle Programm nur 2,3 Sekunden zum Knacken braucht, hängt man eben noch 2 Bytes ran und es braucht wieder 1 Jahr.

Wie schnell man einen Public Key knacken kann, ist völlig uninteressant. Es ist leicht das wieder zu ändern. Gescheitert ist es erst dann, wenn Faktorisierung in polynomialzeit möglich ist.

Ansonsten sollte jedem hoffentlich klar sein, dass Public Key Verfahren nicht 100% sicher sind, nie waren, und garnicht sein können. Stichwort Man in the Middle, ihr könnt Public Key nur vertrauen, wenn ihr allen Routern zwischen eurem PC und dem Ziel PC auch vertraut.

e.f.q.

Aus Falschem folgt Beliebiges

Q
214 Beiträge seit 2006
vor 17 Jahren

Moin,

Das ist das schöne an der Mathematik. Was bewiesen ist, bleibt auch so, da tut sich nichts.

Wenn man schon über den Ansatz der Mathematik geht, dann sollte man es aber auch korrekt wiedergeben.

Und es ist bewiesen, dass Public Key Knacken genauso schwer ist wie Primzahlfaktorisierung.

Das stimmt soweit, aber ...

Das heißt, dass der Aufwand exponentiell ist.

Dies ist leider totaler quatsch.

RSA, Diffie-Hellman etc. basieren auf dem Problem, dass es zur Zeit schwierig ist, große Zahlen zu faktorisieren (Aufwand wächst exponentiell zur Key-Länge). Allerdings konnte noch nicht bewiesen werden, dass die Faktorisierung großer Zahlen wirklich ein schweres/großes Problem darstellt.
Bislang gibt es kein Verfahren, was große Zahlen sehr schnell zerlegt, darum geht man bisher davon aus, dass die Zerlegung ein schwieriges Problem darstellt. Mit neuen Algorithmen* (z.B. Quadratisches Sieb) konnte man den Aufwand aber bereits extrem senken, so dass z.B. ein 640 Bit Key (RSA-640) bereits faktorisiert wurde.

Noch vor rund 15 Jahren gab es Behauptungen, dass eher die Sonne untergeht bevor man einen 512 Bit Key knackt...

* Es gibt bereits Algorithmen für Quantencomputer, wo der Aufwand nur noch linear zur Schlüssellänge wächst, womit jedes bekannte, asymmetrische Verfahren obsolet wäre. Allerdings fehlen bisher solche Quantencomputer, allerdings gibt es Bericht, nachdem die Forscher kurz vor einem Durchbruch stehen.

Nachzulesen u.a. hier:
Sicherheit von RSA
Grundlagen Kryptographie; RWTH-Aachen; Seite 24
Sowie in jedem guten Kryptographie-Buch (z.B. Angewandte Kryptographie von Bruce Schneier)

T
512 Beiträge seit 2006
vor 17 Jahren

Sorry aber irgendwie bin ich immer recht angefressen, wenn jemand glaubt die Weisheit mit dem Löffel gefressen zu haben.

Ja ich weiß, dass es einen Faktorisierungsalgorithmus in Polynomialzeit für Quantencomputer gibt. Aber das kann mit diesem Threadtitel wohl kaum gemeint sein oder?

Ansonsten IST Faktorisierung exponentiell im Aufwand. Es gibt keinen Algorithmus der für beliebige Zahlen in der Eingabelänge polynomial ist. Weiß garnicht was du mir da vorwerfen musst. Der Aufwand für Faktorisierung, und damit für das Knacken von Public Key Verfahren, daran ist garnichts Quatsch.
Es ist nicht bewiesen, dass es so sein muss, das hab ich auch nicht behauptet. Aber im Moment ist es einfach so, weil keine besseren Verfahren bekannt sind.

Exponentiell heißt nicht, dass es keine guten Verfahren für bestimmte Eingaben gibt. Aber es gibt keine guten Verfahren für ALLE Eingaben. Es spielt nunmal keine Rolle, ob es einen Algorithmus gibt, der Zahlen mit 1000 Stellen knacken kann. Weil der Aufwand exponentiell ist, brauch ich nur 2000 Stellen draus machen, und der Algorithmus versagt wieder völlig.

Im Gegensatz zur Faktorisierung ist das Erstellen eines Schlüssels beliebiger größe relativ leicht. Man nimmt sich einfach zwei beliebig große Zahlen, die wahrscheinlich Primzahlen sind. Die Wahrscheinlichkeit lässt sich mit Leichtigkeit auf sehr kleine Werte bringen, und für die Verfahren ist es auch nicht wichtig, ob diese zwei Zahlen wirklich Primzahlen sind.

Und durch diesen Unterschied zwischen Erstellung von beliebigen Schlüsseln und knacken von beliebigen Schlüsseln leben die Public Key Verfahren. Das heißt solange Faktorisierung ein exponentielles Problem ist, so lange sind Public Key Verfahren sicher. Egal ob es jetzt einen guten Algorithmus gelingt eine Zahl mit x Stellen schnell zu faktorisieren. In diesem Wettrüsten sind die Schlüsselgeneratoren immer weit voraus, außer jemand findet einen polynomialen Algorithmus.

Komplexität von Faktorisierung

e.f.q.

Aus Falschem folgt Beliebiges

2.921 Beiträge seit 2005
vor 17 Jahren

@Traumzauberbaum:

außer jemand findet einen polynomialen Algorithmus

Wahrscheinlich kann man damit sein ganzes Leben verbringen. Denn bisher hat ja noch keiner einen gefunden.

Was vielleicht auch nicht möglich ist, weil es keinen gibt. Wenn aber doch, wäre auch interessant, was das für die Mathematik und andere Bereiche bedeutet.

Ist auf jeden Fall ein sehr interessantes Thema.

Zumindest ist auch wahr - um sich wieder der Sache mit dem künstlichen Gehirn anzunähern - dass, Wissenschaftler mit genauerem Nachbilden von Neuronen n-fach bessere Ergebnisse erzielt haben als mit dem alten Modell. Zum Beispiel beim Erkennen von Sprache.

Also egal, ob der Artikel jetzt echt ist oder nicht, auf jeden Fall finde ich die Existenz "künstlicher" (oder vielleicht bezeichnen wir sie lieber zuerst mal als "virtuell") Gehirne
mit pro Jahr n-fach potenzierter Neuronenanzahl sehr interessant.

Und dass diese weitaus komplexere Möglichkeiten bieten mögen als bisher angenommen bleibt abzuwarten, ist aber wohl sehr wahrscheinlich.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

T
512 Beiträge seit 2006
vor 17 Jahren

Die Idee ist sehr interessant und ich halte es sogar für möglich, dass man mit dieser völlig anderen Architektur eines "Rechners" auch völlig neue Algorithmen findet, die in der Laufzeit viel besser sind, oder sogar die erwähnte Polynomialzeit haben.

Ich finde es nur unglaubwürdig, dass wenn man einen guten Algorithmus für Faktorisierung findet (den man ja wie gesagt haben muss für PKE), dass man sich dann an Public Key Verfahren aufhängt 😉
Wenn man publiziert, dass man einen solchen Algorithmus gefunden hat, und das dann verifiziert wird, geht man in die Analen der Mathematik ein und wird berühmt wie Einstein. Da sind die Public Key Verfahren doch eher ein Sandkorn in der Wüste.

e.f.q.

Aus Falschem folgt Beliebiges

3.825 Beiträge seit 2006
vor 17 Jahren

Traumzauberbaum : Ich finde es bedenklich wenn man sich vor AUgen hält, dass weltweit so gut wie alle Verschlüsselungen darauf beruhen, dass man eine große Zahl nicht schnell in Primfaktoren zerlegen kann. Obwohl bisher nicht bewiesen wurde dass es keine schnellere Verfahren als die heute bekannten gibt.

Wenn nun doch so ein Verfahren entdeckt wird wären alle Schlüssel auf einmal geknackt.

Wenn bestimmte Kriterien erfüllt sind (z.B. beide Zahlen des Private Key exakt gleich lang), dann ist die Zeit für die Primfaktorenzerlegung wesentlich kürzer. Es kann ja nun sein, dass man weitere Bedingungen findet, die eine schnellere Zerlegung in Primzahlen ermöglicht. Dann wären zumindestens einige Keys knackbar.

Man muss ja auch bedenken dass viele Verschlüsselungsverfahren lange Zeit benutzt werden. Man denke an die total überholten PIN's der EC-Karten, die werden seit über 30 Jahren benutzt.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

Q
214 Beiträge seit 2006
vor 17 Jahren

Hallo,

Weiß garnicht was du mir da vorwerfen musst.

Original von Traumzauberbaum
Ansonsten IST Faktorisierung exponentiell im Aufwand.

Genau dort ist mein Problem. Man glaubt, dass Faktorisierung (auf normalen PCs) exponentiell im Aufwand sind, dieses konnte aber bisher keiner beweisen. Es kann angehen, dass morgen früh ein geniales, 10 jähriges Kind eine total einfache Methode findet, um Zahlen in wenigen Schritten in seine Primfaktoren zu zerlegen (woran ich aber nicht glaube).

Und bitte nicht so böse nehmen. Du schriebst, dass Faktorisierung exponentiell im Aufwand ist, ich wollte nur anmerken, dass man glaubt/annimmt, dass der Aufwand exponentiell wächst. Dieser kleine Unterschied zwischen ist und dass man etwas annimmt kann manchmal ganz wichtig sein. Z.B. behauptete man, "dass die Titanic unsinkbar ist", und deswegen brauchte man ja auch keine Rettungsboote...

Naja evt. sind dass auch die Nachleiden meines peniblen Mathelehrers 🤔

Sonst gebe ich dir in allen Punkten recht, war auch nicht böse von mir gemeint.

Leider ist der Artikel so schlecht geschrieben, dass der Fake sofort auffällt. Aber ob solche Neuronalen Netzwerke uns in der Forschung wirklich weiter bringen, davon bin ich nicht so überzeugt. Ich glaube auch kaum, dass man mal eben so ein Gehirn einer Ratte nachbilden kann.
Ein weiteres Problem sehen ich darin, wie sich z.B. selbst neue Neuronen bilden u.ä.

O
778 Beiträge seit 2007
vor 17 Jahren

Naja, man kann ab und zu mal was vermuten und die Lösung erraten, was dann kein exponentieller Aufwand wäre

Allgemein kann man das nicht berechnen, weil die Zahlen mit denen man es bei der Entschlüsselung zu tun hat nicht normalverteilt sind (Bei normalverteilten Zahlen ist jede zweite Zahl durch 2 teilbar, bei der Faktorisierung von Zahlen, die bei einer Verschlüsselung verwendet werden wird das nicht so sein.), allein deshalb ist es ausgeschlossen, darüber Betrachtungen anstellen zu können

S
8.746 Beiträge seit 2005
vor 17 Jahren

Original von Qwald
Aber ob solche Neuronalen Netzwerke uns in der Forschung wirklich weiter bringen, davon bin ich nicht so überzeugt.

Zumindest nicht in diesem Bereich, denn in keinem - auch nur denkbaren - Fall ändern neuronale Netze irgendwas an den Aufwandsklassen von Problemen, zumindest solange sie auf Von-Neumann-Rechnern ausgeführt werden. Nur Quantenrechner haben zur Zeit dieses Potential. Auch biologische Rechner würden nicht weiterhelfen, es sei denn, sie hätten unendliche Masse.

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo Traumzauberbaum,

gerade im Zusammenhang mit dem möglichen Knacken von Keys macht es einen entscheidenden Unterschied, ob das Faktorisieren exponentiell IST oder ob man man bisher nur keinen nicht exponentiellen Algorithmus gefunden hat. Denn wenn die 2,3 Sekunden dadurch entstanden wären, dass man einen polynomiellen Algorithmus gefunden hätte, würde deine Argumentation mit dem Verlängern ins Leere laufen. Deshalb ist Qwald Einwand vollkommen berechtigt. Ich denke auch nicht, dass er dir damit die Kompetenz absprechen wollten. Zumindest mir ist aufgrund deiner vielen guten Beiträge bekannt, dass du dich mit Themen der theoretischen Informatik an sich sehr gut auskennst. Deshalb sollte es dir auch leicht gelingen einzugestehen, wenn du mal etwas daneben lagst.

herbivore

X
2.051 Beiträge seit 2004
vor 17 Jahren

Original von dotnetpro

...Wie es mit dieser Entwicklung weitergeht,
muss sich noch zeigen. Auf jeden Fall ist erst
einmal für den 1. April 2007 eine Anhörung
vor dem Landamann des Kantons Uri geplant.
Hier soll entschieden werden, wie weiter vorgegangen
werden soll. dotnetpro wird weiter
über diese Sache berichten.

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo Xqgene,

was willst du sagen? Dass es ein April-Scherz ist? Das wurde doch schon weiter oben festgestellt. Das ändert ja aber nichts daran, dass man Überlegungen zur (prinzipiellen) Knackbarkeit anstellen kann. 🙂

herbivore

T
512 Beiträge seit 2006
vor 17 Jahren

Ich weiß nicht warum ihr in ein IST mehr legt, als es bedeutet. IST bedeutet nicht ist optimal. Ich wollte damit doch nur die aktuelle Lage beschreiben, den IST-Zustand, und keine Prognose für die Zukunft abgeben.

Um Faktorisierung zu lösen ist der Aufwand im Allgemeinen (also ohne weitere Eigenschaften der Zahl voraussetzen zu können) exponentiell. Das ist doch einfach so, auch wenn es in Zukunft anders werden könnte.

Ich hab doch sogar geschrieben, dass PKE erst genau dann nicht mehr sicher ist, wenn ein polynomieller Algorithmus gefunden wird. Und dort steht nicht in einem Anhängsel "aber das wird nicht passieren" oder sowas.

Aber wenn man sich die ersten zwei Zeilen rauspickt...

Vieleicht ist das unglücklich formuliert, aber das deswegen als Quatsch zu bezeichnen und noch so nen Prolog dazu zu schreiben... ich glaube da darf ich mich angegriffen fühlen.

e.f.q.

Aus Falschem folgt Beliebiges

S
8.746 Beiträge seit 2005
vor 17 Jahren

Für diejenigen, die nicht so bewandert in theoretischer Informatik sind, hier ein schöner Artikel zum Thema und wie man eine Million gewinnt:

http://www.mathematik.de/mde/information/ueberallmathe/einemilliondollar/einemilliondollar.html

D
386 Beiträge seit 2007
vor 17 Jahren

Ich hab herzlich gelacht.. 😉

Pound for pound, plutonium is about as toxic as caffeine when eaten.