Quantum Computing RSA-Public-Key-Kryptograhie Shor `94

Quantum Computing

RSA-Public-Key-KryptograhieShor `94

Überblick

• Public-Key-Kryptographie; RSA-Verfahren• Grundlagen des Quantencomputers, „Schnelligkeit“• Quantenparallelismus und Quantenfouriertransformation• Die 5 Schritte des Shor-Algorithmus• Der 2. Schritt im Shor-Algorithmus• Der 2. Schritt im Shor-Algorithmus - Wahrscheinlichkeit• Ein Demonstrationsbeispiel mit kleinen Zahlen• Beantworten von Fragen, Diskussion, Beweise, Beispiel mit

größeren Zahlen, was auch immer,...

Ich werde heute behandeln:

Kryptographie-Grundlagen

Kryptographie-Prinzip

• Klartext: „Hallo!“• Sender,

verschlüsselt Text mit Schlüssel

• Geheimtext „101010“• Empfänger, entschlüsselt• Klartext: „Hallo!“

Grundbegriffe• Angreifer ...

will Geheimtext lesen, muss also Schlüssel finden

• „Kryptoanalyse“... das macht der Angreifer

• Schlüssel ... allg. Vorschrift wie ich Klartext verändere (Algorithmus)

Das bedeutet: • Empfänger und Sender

benötigen nicht die selbe Information.

• Empfänger gibt dem Sender einen öffentlich zugänglichen Schlüssel.

• Empfänger hält privaten Schlüssel geheim.

Prinzip:• ET ('public-key')

• DT (privater Schlüssel)• b ... Botschaft• c ... Geheimtext• Public-Key-Eigenschaft: DT kann aus

ET nicht berechnet werden!• Entschlüsselungseigenschaft:

DT(ET (b))=b

• Codieren: c = EB(b)

• Decodieren: DB(c)=DB(EB(b))=b

Public-Key-Kryptographie

quantum circuit model

• ... mathematisches Modell für Quantencomputer • Anstatt der BITS (1,0) haben wir nun QUBITS,

die in beliebigem 2-Zustandssystemen realisiert sind zB.: Stern-Gerlach, Polarisation, Metastabile Zustände

• qubits in z-Basis: ... False

... True

Quantencomputer-Grundlagen

1-qubit-gates

Quantencomputer-Grundlagen

Not... Spin-Flip, oder einfach Paulimatrix multiplizieren.

Hadamard ...

Phase-Shift-Gate ...

Mit Hadamard und Phase-Shift lassen sich allgemein 1-qubit-Transformationen erzeugen:

• „and“ „or“ sind nicht reversibel, d.h.: Reduktion des Hibertraumes, d.h.: Probleme bei Zeitentwicklung, denn wir benötigen UNITÄRE Operatoren.

• Lösung: Tensorprodukt zweier Zustände , Controlled-U-Gate Macht das gleiche wie das CNOT - Gate, nur für beliebige 1-qubit-Gates U. Also wendet es U auf 2. qubit an, falls das 1. qubit true ist. Controlled – NOT – Gate … CNOT ... Tauscht mit .

• Matrixdarstellung in z-Basis:

Quantencomputer-Grundlagen

2-qubit-gates

Universeller Satz • Mit diesen drei können wir

beliebige, unitäre Transformationen durchführen.

• Erstere beiden sind 1-qubit und drittes ist 2-qubit-Gate.

• Man baut also jedes Quantennetzwerk mit diesen dreien auf.

• Auch für n-qubits.

Verschränkte Zustände

• Kann nicht als Produktzustand geschrieben werden.

• Können nur durch Wechselwirkungen zwischen Teilchen entstehen (2-qubit-Gates, wie CNOT)

•

Quantencomputer-Grundlagen

„Schnellgkeit“ von Algorithmen

• effiziente Algorithmen = berechenbare Algorithmen, Komplexitätsklasse 'P' , polynomiale Probleme

• ineffiziente Algortihmen = unberechenbare Algorithmen, Komplexitätsklasse 'NP' oder 'N‚exponentielle Probleme

Gegenüberstellung Faktorisierung• Faktorisierung benötigen

wir später! • Shor =

Quantenalgorithmus!

Quantencomputer-Grundlagen

Dezimal-stellen

Klass. Algorithmus

(1GHz)

Shor ’94 (1MHz)

100 150 Tage 2.5 Stunden

300 6 Millionen Jahre

2.5 Tage

Überlagerung von Zuständen

• = Register...das sind n qubits.

• ... Dezimal• Tensorprodukt zweier

Register mit x... Input-Registery... Output-Register

• Fouriertransformation an x:

Auswerten von Funktionen• Wir können nun mittels einer

unitären Transf.

mit nur EINEM SCHRITT eine beliebige Funktion für die überlagerten Werte auswerten. Messen allerdings müssen wir sie einzeln (Zustände kollabieren).

Quantenparallelismus

Rechenzeiten

• , n = 100 bits.• Rechenschritte für klassisches System, Schritte/sek. • 1(!) Rechenschritt für Quantencomputer, Entwicklungsjahre +

Zeit für eine Rechenoperation.

Das ergibt im Vergleich etwa:

Jahre (klassisch) : Entwicklungsjahre

Ein nettes Beispiel

Quantenfouriertransformation

5 Schritte des Shor-Algorithmus

• Sinn? Man kann damit ein große Zahl N faktorisieren, d.h.: N = pq ... p,q sind Primzahlen. Wozu? Sehen wir später.

• Schritt 1: wir wählen ein zufälliges m < N, ggT(m,N) = 1. • Schritt 2: Finden einer Periode der Funktion

• Schritt 3: P muss gerade sein, sonst zurück zu Schritt 1• Schritt 4: Falls , zurück zu Schritt 1

Sonst weiter zu: • Schritt 5: Die Zahl ist dann entweder

q oder p. Fertig.

Für ein klassisches System ist dieser Schritt hier ein „N“ Problem!

• Schritt 2.0:

• Schritt 2.1:

... Fouriertransformation, Überlagerung • Schritt 2.2: ,

... Unitäre Transformation für:

Der 2. Schritt-Finden einer Periode P

• Schritt 2.3: Nochmalige Fouriertransformation

, wobei:

, .

Der 2. Schritt-Finden einer Periode P

• 2.4: Messen der Zustände und Wahrscheinlichkeitsverteilung

Der 2. Schritt-Finden einer Periode P

Ist Q/P ganzzahlig, gibts nur an diesen z konstrukive Interferenz:

Der 2. Schritt-Finden einer Periode P

Ist Q/P nicht ganzzahlig, so gibt es einen Streubereich, und wir können z messen, die bei unseren späteren Überlegungen zu einer falschen Periode führen. (keine Delta-Peaks mehr!)

Der 2. Schritt-Finden einer Periode P

• Schritt 2.5.: Bestimmen von P mittels KettenbruchBei dieser Methode gibt es für bestimmte z kein Ergenbis, oder ein falsches (bei Brüchen, die sich noch kürzen lassen). Ich wähle alternativ ein z aus dem Streubereich. Es lässt sich aber zeigen, dass, selbst wenn man öfters messen muss, wir immer noch im effizienten Bereich liegen. Wir liegen auch dann noch im berechenbaren Bereich, wenn wir die nachbarn probieren.

Der 2. Schritt-Finden einer Periode P

Der 2. Schritt-Finden einer Periode P

Demonstrationsbeispiel-RSA-Teil

Der Öffentlichkeit bekannt: N , f also weiß das auch Bob, Codewort cNur Bob bekannt: Message b = „TOPSECRET“Nur Alice bekannt: p, q, d und später nach Decodierung: d

Demonstrationsbeispiel-RSA-Teil

ET ('public-key') ... (f,N) = (5,35)DT (privater Schlüssel) ... (d) = (5)

Demonstrationsbeispiel-RSA-Teil

Demonstrationsbeispiel-Shor-Teil

Wichtig! Durch unseren Quantencomputer knacken wir jetzt ein Verfahren,

das durchaus oft Anwendung findet! Das RSA-Verfahren ist eines der meistvervendetsten der Public-Key-Kryptographie:

Banken, Internet,....

Demonstrationsbeispiel-Shor-Teil

Demonstrationsbeispiel-Shor-Teil

Demonstrationsbeispiel-Shor-Teil

Schritt 2.4 ... Wir messen Q/z. Bildet das eine Differenz mit P/d, laut CFE-Bedingung, so erhalten wir unsere richtige Periode P. Es sei denn ggT(d,P) ist nicht 1.

Demonstrationsbeispiel-Shor-Teil

Demonstrationsbeispiel-Shor-Teil

Demonstrationsbeispiel-Shor-Teil

Am Ziel angelangt

Ergänzungen zur Effizienz

Ende

Es bedankt sich für eure Aufmerksamkeit: Manuel Grill