Die Zukunft des Computers

[Cyrics]

Andere (elliptische Kurven, Gitterverfahren wie etwa das shortest vector problem) gelten nach bisherigen Forschungsstand als sicher. Es gibt zu diesem Thema leider keine allgemeinverständlichen Abhandlungen, bisher gibt es nur Fachartikel und wenige Bücher aus den Bereichen Mathematik und theoretischer Informatik. Die mathematischen Vorkenntnisse sind nahezu gleich hoch, so daß man das niemanden als Lektüre für nebenher empfehlen kann.

Also die elliptische Kurven-Kryptographie finde ich recht interessant, auch relativ leicht verständlich.
Soweit ich es verstanden habe, einigen sich beide Seiten auf eine gemeinsame ellptische Kurve bzw. Funktion dritten Grades und wählen einen zufälligen Punkt P auf dieser Kurve aus.
Nun ermitteln beide Seiten einen privaten Punkt (und hier hab ich nicht verstanden, ob dieser auf der Kurve oder nicht auf der Kurve liegt) aus. Mit der Multiplikation mit dem gemeinsamen Punkt P ergeben sich für beide Seiten die öffentlichen Schlüssel.

Wie würde das nun bei dem Gitterverfahren funktionieren? Basiert dies auch auf öffentlichen und privaten Schlüsseln? Ich finde dazu leider kaum etwas.
Kann man davon ausgehen, dass nur die Algorithmen betroffen sind, die auf großen Schlüssellängen basieren und dadurch eben geknackt werden können?

 

[KayHH]

Moin tjp,

Zur Zeit ist das für all die jenigen wichtig, die Dokumente verschlüsseln oder digital unterschreiben und diese Schutz noch in einigen Jahren notwendig ist. Man kann daher nur empfehlen schon jetzt die kryptographischen Verfahren umzustellen, denn mit einem Quantenrechner kann man nur bestimmte Verfahren (davon betroffen ist der sehr beliebte RSA-Algorithmus und alle diskreten Logarithmusverfahren Deffie-Hellman, ElGamal, SHA-*, MD*, d.h. so ziemlich jeder häufig genutzte Algorithmus ist damit obsolet) knacken. Andere (elliptische Kurven, Gitterverfahren wie etwa das shortest vector problem) gelten nach bisherigen Forschungsstand als sicher.

wobei das mit dem Forschungsstand natürlich so eine Sache ist. Da die NSA als weltweit größter Arbeitgeber von Mathematikern einen nicht unwesentlichen Teil der Gesamtmenge aller Mathematiker auf diesem Planeten beschäftigt würde ich in jedem Fall davon ausgehen, dass sie einen Vorsprung haben.

Ich befinde mich gerade in der Planung zukünftig alles nur noch verschlüsselt zu speichern. Derzeit favorisiere ich Blowfish mit voller Schlüssellänge. Kannst Du dazu eine Aussage in Bezug auf die Sicherheit machen? Mir ist nicht klar ober er in die gefährdete Kategorie fällt.


Gruss KayHH

 

[tjp]

Wie würde das nun bei dem Gitterverfahren funktionieren?

Eine Einführung in das Thema
Artikel Liste der Arbeitsgruppe
Ein Vorlesungsskript zum Thema Gitter
Eine Diplomarbeit zu dem Thema

Kann man davon ausgehen, dass nur die Algorithmen betroffen sind, die auf großen Schlüssellängen basieren und dadurch eben geknackt werden können?

Die Schlüssellänge ist eher sekundär. Es geht um prinzipielle Angriffsmöglichkeiten. Die "Sicherheitsbeweise" für RSA- oder DL-Kryptosysteme setzen voraus, daß gewisse Berechnungen schwer sind. Man nimmt an, daß das Faktorisieren für große Zahlen schwer sei, der beste Algorithmus auf einem normalen Computer ist das "Number-Sieve-Field". Auf einem Quantenrechner sinkt der Aufwand sehr stark ab. Das wird in diesem Paper beschrieben. Bei anderen Kryptosystemen nimmt man an, daß andere Probleme schwer seien. Das gilt immer solange bis jemand einen bessere Algorithmus findet. Quantenrechner eröffnen nun eine Vielzahl neuer Möglichkeiten. Bisher hat man so gut wie keine Algorithmen gefunden, die auf einem Quantenrechner laufen. Dazu ist das Themengebiet noch zu neu. Früher galt das als reine Zeitverschwendung, da niemand annahm, daß man so etwas überhaupt bauen kann. Jetzt hat man den qualitativen Nachweis, daß es geht.

@KayHH
Was Blowfish betrifft. Das wird meist nicht behandelt und auf die Schnelle habe ich keinen Sicherheitsbeweise gefunden. Sicherheitsbeweise sind keine 100% Beweise, da immer wieder jemand einen besseren Algorithmus finden kann, aber sie zeigen zumindest, daß sich Personen damit intensiv beschäftigt haben.

 

[tjp]

Da die NSA als weltweit größter Arbeitgeber von Mathematikern einen nicht unwesentlichen Teil der Gesamtmenge aller Mathematiker auf diesem Planeten beschäftigt würde ich in jedem Fall davon ausgehen, dass sie einen Vorsprung haben.

In Bruce Schneiers Buch wird darauf hingewiesen, daß die NSA damals DES gegen die Differentiale Cryptanalyse optimiert hat. Lange bevor irgend jemand außerhalb wußte, daß DES gegen diesen Angriff verwundbar ist. Ob sie allerdings immer noch so viel besser sind als die globale Forschergemeinschaft weiß keiner.

Die Quantenrechner werden jedenfalls von Physiker gebaut und Mathematiker sind da nur bedingt hilfreich. Die Theorie ist ja bekannt, die praktische Umsetzung ist das Problem.