Tutorial

Tutorial

-

Documents
21 pages
Lire
YouScribe est heureux de vous offrir cette publication

Description

I. Quantencomputer und ihre Bedeutung für die Kryptoanalyse Sebastian Lehnhoff 2 Quantencomputer und ihre Bedeutung für die Kryptoanalyse I. QUANTENCOMPUTER UND IHRE BEDEUTUNG FÜR DIE KRYPTOANALYSE ........ 1I.1 EINLEITUNG UND MOTIVATION...................................................................................... 3 I.2 NOTWENDIGE EINFÜHRUNG IN DIE QUANTENMECHANIK ................................... 4 I.2.1 DAS MACH-ZEHNDER-INTERFEROMETER ............................................................................... 4 I.3 DER QUANTENCOMPUTER ................................................................................................ 7 I.3.1 FUNKTIONSWEISE .................................................................................................................... 7 I.3.2 VOR- UND NACHTEILE............................................................................................................. 9 I.3.3 PROBLEME BEI DER KONSTRUKTION....................................................................................... 9 I.4 DIE BEDEUTENDSTEN ALGORITHMEN FÜR DIE KRYPTOANALYSE................. 10 I.4.1 ALGORITHMUS VON SHOR..................................................................................................... 10 I.4.2 AUS VON GROVER 11 I.5 ERFOLGVERSPRECHENDE QUANTENCOMPUTERMODELLE.............................. 13 I.5.1 DER IONENFALLEN-QUANTENCOMPUTER........................................................................ ...

Sujets

Informations

Publié par
Publié le 14 octobre 2014
Nombre de visites sur la page 33
Langue Deutsch
Signaler un problème

I. Quantencomputer und ihre Bedeutung
für die Kryptoanalyse
Sebastian Lehnhoff
2 Quantencomputer und ihre Bedeutung für die Kryptoanalyse

I. QUANTENCOMPUTER UND IHRE BEDEUTUNG FÜR DIE KRYPTOANALYSE ........ 1
I.1 EINLEITUNG UND MOTIVATION...................................................................................... 3
I.2 NOTWENDIGE EINFÜHRUNG IN DIE QUANTENMECHANIK ................................... 4
I.2.1 DAS MACH-ZEHNDER-INTERFEROMETER ............................................................................... 4
I.3 DER QUANTENCOMPUTER ................................................................................................ 7
I.3.1 FUNKTIONSWEISE .................................................................................................................... 7
I.3.2 VOR- UND NACHTEILE............................................................................................................. 9
I.3.3 PROBLEME BEI DER KONSTRUKTION....................................................................................... 9
I.4 DIE BEDEUTENDSTEN ALGORITHMEN FÜR DIE KRYPTOANALYSE................. 10
I.4.1 ALGORITHMUS VON SHOR..................................................................................................... 10
I.4.2 AUS VON GROVER 11
I.5 ERFOLGVERSPRECHENDE QUANTENCOMPUTERMODELLE.............................. 13
I.5.1 DER IONENFALLEN-QUANTENCOMPUTER............................................................................. 13
I.5.2 DER NMR-QUANTENCOMPUTER........................................................................................... 15
I.6 ZUSAMMENFASSUNG......................................................................................................... 19
I.7 LITERATURANGABEN ....................................................................................................... 19
I.7.1 PRINTMEDIEN ........................................................................................................................ 20
I.7.2 ELEKTRONISCHE DOKUMENTE.............................................................................................. 21
Kapitel I.2.1. Das Mach-Zehnder-Interferometer 3

I.1 Einleitung und Motivation
Die Geschichte der Computer Technologie beinhaltet hinsichtlich ihrer technischen Entwicklung und
Realisation eine Reihe von grundlegenden Veränderungen. Angefangen bei Schaltwerken, über
Röhren bis zur Entwicklung von Transistoren und integrierten Schaltkreisen ist es heutzutage möglich,
dank ausgefeilter lithografischer Methoden, logische Gatter und Verknüpfungen in der
Größenordnung einiger Nanometer auf die Oberfläche von Siliziumchips zu brennen.

Es ist abzusehen, dass man bei der Geschwindigkeit dieser Entwicklung in nicht all zu ferner Zukunft
einen Punkt erreicht haben wird, an dem diese logischen Strukturen nur noch die Größe einiger
weniger Atome haben werden. Beim Umgang mit diesen Größenordnungen verlassen wir jedoch den
Bereich der klassischen Physik. Auf atomarer Ebene herrschen die Gesetze der Quantenphysik, die
sich fundamental von denen unterscheiden, mit denen wir im Alltag zu tun haben und die das
Verhalten konventioneller logischer Gatter bestimmen.

Wenn Computerstrukturen in Zukunft also immer weiter miniaturisiert werden, muss eine
Technologie, die auf eben diesen Gesetzen der Quantenmechanik aufbaut, unweigerlich unsere jetzige
"klassische“ Technologie ersetzen oder zumindest ergänzen.

Der springende Punkt ist jedoch, dass Quantentechnologie sehr viel mehr zu bieten hat, als schlicht
immer mehr Transistoren auf die Oberfläche eines Chips zu zwingen und die Taktfrequenz von
Prozessoren zu erhöhen. Quantentechnologie bietet eine vollkommen neue Art der Datenverarbeitung
und Bewältigung von Problemen mit qualitativ neuen Algorithmen, die sich die Prinzipien der
Quantenmechanik zu Nutze machen.

Um zu verstehen, was Quantencomputer so grundlegend von unseren jetzigen Systemen unterscheidet
betrachtet man, wie elementare Informationseinheiten in klassischen, digitalen Computern
repräsentiert werden, nämlich durch die Spannungszustände eines Kondensators. Hier entsprechen ein
geladener Kondensator der 1 und sein ungeladenes Gegenstück der 0. Ein Bit ließe sich aber ebenso
über zwei verschiedene Polarisationsebenen von Licht (Quanten) oder zwei elektronische
(energetische) Zustände eines Atoms repräsentieren.
4 Quantencomputer und ihre Bedeutung für die Kryptoanalyse

I.2 Notwendige Einführung in die Quantenmechanik
Verwendet man jedoch atomare Größen, wie Atomzustände oder Lichtquanten als Repräsentation, ist
eine Folge der Quantenmechanik, dass die Teilchen, abgesehen von ihren beiden diskreten Zuständen
auch noch einen dritten Zustand, nämlich eine kohärente Superposition beider Zustände einnehmen
können. Das bedeutet nichts weniger, als dass sich das Teilchen gleichzeitig in beiden Zuständen
befindet.
Um sich an diesen ungewöhnlichen Gedanken zu gewöhnen, betrachtet man folgendes Experiment,
dessen Aufbau allgemein als Mach-Zehnder-Interferometer bekannt ist [URL-8].

I.2.1 Das Mach-Zehnder-Interferometer
Es soll ein einzelnes Photon (Lichtteilchen) an einem halbdurchlässigen Spiegel reflektiert werden.
Ein halbdurchlässiger Spiegel reflektiert genau die Hälfte des auf ihn einfallenden Lichts und lässt die
andere Hälfte hindurch (Abbildung I.2-1: Mach-Zehnder-Interferometer - Aufbau 1). Es erscheint
einleuchtend, anzunehmen, dass sich das Photon entweder in dem reflektierten oder dem
durchgelassenen Strahl befindet und zwar mit der gleichen Wahrscheinlichkeit. Und in der Tat, wenn
wir das Experiment auf oben gezeigte Art und Weise mehrfach durchführen, erhalten wir ein
gleichverteiltes Ergebnis. Das Photon wird im Schnitt genauso oft an Detektor 1 gemessen, wie an
Detektor 2.

Abbildung I.2-1: Mach-Zehnder-Interferometer - Aufbau 1 Kapitel I.2.1. Das Mach-Zehnder-Interferometer 5

Tatsächlich jedoch nimmt das Photon "beide Wege gleichzeitig“. Um das zu demonstrieren,
kombiniert man beide Strahlen wieder miteinander. Dazu fügt man dem Versuchsaufbau noch einen
halbdurchlässigen Spiegel hinzu und bringt noch zwei vollständig reflektierende Spiegel in den
Strahlengang (Abbildung I.2-2: Mach-Zehnder-interferometer - Aufbau 2).

Wenn das Photon jetzt tatsächlich mit gleicher Wahrscheinlichkeit den durchgehenden und den
reflektierten Weg nehmen würde, würde man nach wie vor 50% der durch die Apparatur gegangenen
Photonen an Detektor 1 messen und die anderen 50% an Detektor 2. Dies passiert jedoch nicht.
Tatsächlich findet man das Photon bei diesem Aufbau mit 100% Wahrscheinlichkeit an Detektor 1
und niemals an Detektor 2.

Abbildung I.2-2: Mach-Zehnder-interferometer - Aufbau 2
Wie kommt die Auslöschung zustande? Man betrachte folgende schematische Darstellung unseres
Versuchs (Abbildung I.2-3: Mach-Zehnder-Interferometer - schematisch).

Abbildung I.2-3: Mach-Zehnder-Interferometer - schematisch 6 Quantencomputer und ihre Bedeutung für die Kryptoanalyse

Man muss wissen, dass ein Lichtstrahl bei der Reflektion an einer Oberfläche eine
Phasenverschiebung um eine halbe Wellenlänge erfährt, wenn das Medium auf der anderen Seite der
reflektierenden Schicht einen höheren Brechungsindex besitzt, als das Medium, durch das der Strahl
die reflektierende Oberfläche getroffen hat.

Das bedeutet, dass unser Lichtstrahl O sowohl an S1, als auch an S3 um jeweils eine halbe
Wellenlänge verschoben wird, an S4 jedoch keine Phasenverschiebung erfährt. Summieren wir diese
Phasenverschiebungen beider Strahlengänge O und U auf, erhalten wir eine konstruktive
Überlagerung der Strahlen an Detektor 1 und eine destruktive Überlagerung an Detektor 2.

Um wirklich sicher zu sein, nimmt man noch eine letzte Änderung an dem Versuchsaufbau vor. Es
wird eine lichtundurchlässige Scheibe in den reflektierten Strahlengang eingebracht (Abbildung I.2-4:
Mach-Zehnder-Interferometer - Aufbau 3).

Abbildung I.2-4: Mach-Zehnder-Interferometer - Aufbau 3
Das Blockieren eines Strahlengangs hat zur folge, dass wieder beide Detektoren mit gleicher
Wahrscheinlichkeit erreicht werden. Dieses Ergebnis ist natürlich unabhängig davon, ob wir nun den
reflektierten oder durchgelassenen Strahlengang unterbrechen.

Betrachtet man den Versuchsverlauf und erinnert sich daran, dass das ganze Experiment mit immer
nur einem Photon durchgeführt wird, kommt man unausweichlich zu dem Schluss, dass das Photon
beide Wege genommen haben muss. Wenn man den weiter oben eingeführten Begriff verwenden will,
lässt sich sagen, dass sich das Photon in einer (kohärenten) Superposition beider Strahlengänge
befindet. Kapitel I.3.1. Funktionsweise 7

I.3 Der Quantencomputer
I.3.1 Funktionsweise
Auf ähnliche Art und Weise kann man ein Atom in eine Superposition zweier elektronischer oder
Spin-Zustände bringen. Ganz allgemein kann man ein Quantensystem mit zwei Zuständen (Quanten
Bit oder kurz: Qubit) in eine Superposition seiner beiden logischen Zustände 1 und 0 bringen. Dies
bedeutet, dass ein Qubit zu einem bestimmten Zeitpunkt gleichzeitig den Zustand 1 und 0 annehmen
kann.

An dieser Stelle führt man eine neue Schreibweise für die Qubits ein. Dabei bezeichnet man die
beiden Zustände, die denen in einem klassischen System entsprechen mit |1> und |0> und die
Superposition beider Zustände als Linearkombination | ψ> = α |0> + β |1>, wobei α und β komplexe
Zahlen sind, die aus historischen Gründen Amplituden genannt werden. Diese "Dirac“-Schreibweise
2 2für Qubits verlangt außerdem, dass gilt: | α| + | β| = 1. Diese Zusatzbedingung wird unmittelbar klar,
wenn man sich vor Augen führt, dass eine Messung eines Qubits in einer Superposition | ψ> = α |0> +
2 2β |1> mit der Wahrscheinlichkeit | α| den Wert 0 liefert und mit der Wahrscheinlichkeit | β| den Wert
1. [Niel03]

Jetzt denkt man sich den Gedanken an Superpositionen einen Schritt weiter und stellt sich ein Register
mit drei physikalischen Bits vor. Jedes vorstellbare klassische Register dieses Typs kann zu jedem
beliebigen Zeitpunkt lediglich einen von acht verschiedenen Werten speichern. Ein Quantenregister,
welches sich aus drei Qubits zusammensetzt ist hingegen in der Lage zu einem bestimmten Zeitpunkt
alle acht Werte in einer Superposition zu speichern.

Die Tatsache, dass alle acht Belegungen physikalisch in einem Register belegt werden ist sehr
bemerkenswert, jedoch nicht fantastischer, als ein Qubit, welches sich gleichzeitig im Zustand 1 und 0
befindet. Hat man ein Register in einer Superposition mehrerer Zustände vorliegen, kann man
Operationen auf allen Zuständen gleichzeitig ausführen. [URL-8] 8 Quantencomputer und ihre Bedeutung für die Kryptoanalyse


Abbildung I.3-1: Quantenregister
Betrachtet man beispielsweise ein Register, in dem die Qubits durch Atome in verschiedenen
Energiezuständen repräsentiert werden. Ein Laserimpuls passender Frequenz und Energie ist dann in
der Lage ein Register aus einer bestehenden Superposition in eine andere Superposition zu überführen.
Dies bedeutet, man führt einen massiven parallelen Rechenschritt in nur einem Bauteil aus.

Damit ist ein Quantencomputer in der Lage in nur einem Schritt die gleiche mathematische Operation
L auf 2 verschiedenen Eingaben von L Qubits in Superposition durchzuführen. Auf einem klassischen
LComputer (mit nur einem Prozessor) wären für dieselbe Aufgabe 2 Schritte notwendig.

Man kann zeigen, dass sich jede Rechenoperation in eine Folge (d.h. ein logisches Netzwerk) von
Operationen eines CNOT-Gatters zusammen mit allgemeinen unitären Rotationen eines einzelnen
Qubits zerlegen lässt. Will man also mit einem Quantencomputer rechnen müssen diese beiden
Operationen realisierbar sein. [Vinc95]

Abbildung I.3-2: CNOT-Gatter Kapitel I.3.2. Vor- und Nachteile 9

I.3.2
So fantastisch dieses Prinzip auch klingt muss man an dieser Stelle auf ein unmittelbares Problem
aufmerksam machen. Wollen wir nun unser Ergebnisregister auswerten, bricht die kohärente
2Superposition unseres Registers zusammen und man erhält mit der Wahrscheinlichkeit |b | das 1
2Ergebnis 000, mit der Wahrscheinlichkeit |b | das Ergebnis 001, und so weiter. Das bedeutet auf der 2
Leinen Seite, dass man nur eines der 2 Ergebnisse erhält, auf der anderen Seite hängt das Endergebnis
Laber von allen 2 Ergebnissen ab.

I.3.3 Probleme bei der Konstruktion
Weiterhin brechen kohärente Superpositionen nicht nur durch Messvorgänge auf singuläre Zustände
zusammen, sondern ganz allgemein durch Interaktionen mit ihrer Umgebung. Da jedoch ein System
nicht vollständig vor äußeren Einflüssen isolierbar ist und auch die erforderlichen Arbeiten auf
atomarer Ebene derzeit noch nicht zu realisieren sind stellt sich hier noch ein generelles Problem bei
der Konstruktion von Quantencomputern.

Dem Problem des Zusammenbrechens kohärenter Superpositionen bei Messvorgängen wird begegnet,
indem man durch konstruktive Interferenz einzelner Qubits miteinander die Wahrscheinlichkeit
erhöht, bestimmte Ergebnisse zu messen. Tatsächlich arbeiten effiziente Quantenalgorithmen auf
diesen Wahrscheinlichkeitsamplituden und ermöglichen so, mit hoher Wahrscheinlichkeit das
gewünschte Ergebnis zu messen. Dieses Postprocessing, also das messbar machen relevanter
Ergebnisse in Quantencomputern, lässt jedoch den Geschwindigkeitsgewinn für viele Probleme, die
sich potentiell auf Quantencomputern behandeln lassen dahinschwinden. [URL-3][URL-7] 10 Quantencomputer und ihre Bedeutung für die Kryptoanalyse

I.4 Die bedeutendsten Algorithmen für die Kryptoanalyse
I.4.1 Algorithmus von Shor
1994 hat Peter Shor an den Bell Labs gezeigt, dass die Primzahlfaktorisierung auf dem
2Quantencomputer nicht nur möglich, sondern auch in Polynomialzeit On((log ) ∗log logn) zu
realisieren ist. Der schnellste bislang bekannte klassische Algorithmus zur Faktorisierung großer
1/3 2/3cn(log ) ∗(log logn)Zahlen besitzt eine Exponentielle Laufzeit von [Shor97]. Die Veröffentlichen von O()e
Shor’s Algorithmus vergrößerte den bis dahin recht kleinen Kreis von Forschungsanstalten, die sich
mit Quantencomputern beschäftigten, beträchtlich.

Abbildung I.4-1: Peter Shor - 1994
Wie geht Shor’s Algorithmus nun vor?

a„F(a) = x mod n“ ist eine periodische Funktion, wobei n die zu faktorisierende Zahl sei und x eine
0Zahl, die teilerfremd zu n ist. Da F eine periodische Funktion ist, lässt sich ein r finden, so dass x mod
r 2rn = 1‚ x mod n = 1‚ x mod n = 1, u.s.w.

Im folgenden benutzen wir als Beispiel n = 35, x = 6 und wie man durch Einsetzen leicht sieht, ist die
Periode r = 2.
0 1 2 3 4 5 66 6 6 6 6 6 6 …
1 6 1 6 1 6 1 …
Tabelle I.4-1: Beispiel für n=35, x=6