(Das ist der Entwurf eines Artikels für die DMV-Mitteilungen.)

So etwas wie “des geht net” – das gibt’s hier in den USA nicht.

Anton Zeilinger laut https://www.zitate.eu/autor/univ-prof-dr-anton-zeilinger-zitate/280531

Wunderschöne Mathematik

profil: Wie also kamen Sie zur Quantenphysik?

Anton Zeilinger: Am Ende des Studiums wollten eine Kollegin, ein Kollege und ich mehr darüber wissen. Wir besorgten uns das Manuskript der Quantenvorlesung von Otto Hittmair von der TU Wien. Wir arbeiteten es von vorn bis hinten durch und waren total fasziniert.

profil: Was hat Sie dermaßen fasziniert?

Anton Zeilinger: Die wunderschöne Mathematik, die verwendet wurde. Das ist absolut einmalig. Der Nobelpreisträger Paul Dirac hat einen Formalismus der Quantenmechanik geschrieben, der einfach genial ist. Ebenfalls großartig für uns war das Buch des Nobelpreisträgers Claude Cohen-Tannoudji. Aber am Beginn der Bücher hieß es immer, dazu, was das alles bedeutet, kommen wir noch. Dann las man, aber das Versprochene kam nicht. Da habe ich gemerkt, das war ein Thema, das nicht berücksichtigt wurde.

profil: Ist es auch Teil der Faszination, mit der Sprache der Mathematik in eine Welt einzudringen, die sich der Erfahrbarkeit der Alltagswelt entzieht?

Anton Zeilinger: Die direkte Erfahrbarkeit kümmert einen als Physiker eigentlich nicht. Man sieht das sehr operativ. Es gibt mathematische Vorhersagen und experimentelle Möglichkeiten, diese zu testen.

So das österreichiche Nachrichtenmagazin profil am 8.10. im Interview mit dem vier Tage zuvor gekürten Nobelpreisträger Anton Zeilinger.

Recht und Gerechtigkeit als komplementäre Variablen

Quantenverschränkung wird – vor allem auch in Österreich, wo Zeilinger sehr populär ist – gerne mal als Metapher für versteckte Zusammenhänge in Politik und Gesellschaft verwendet.
Wissenschaftsjournalist Florian Aigner erklärte im ÖRF die mit dem Nobelpreis ausgezeichnete Entdeckung so:

Ich geb diese Mascherl in ein Geldkuvert. Dann werfe ich eines davon weg nach Liechtenstein. Schaue ich in das andere Kuvert rein, dann kenne ich die Vorwürfe, kann mich aber gleichzeitig auch nicht daran erinnern. […] Also zwei ÖVP-Mitglieder müssen nicht am selben Tisch sitzen, um korrupt zu sein, jeder agiert gleich – auch wenn der eine in Niederösterreich und der andere in Tirol sitzt.

Daneben gibt es aber auch anerkannte Universitätsprofessoren, die im Ernst versuchen, Quantenverschränkung zur Erklärung größerer Phänomene heranzuziehen. Zum Beispiel fand in Madrid im Juni 2009 eine Tagung “Entanglement and Mathematics” statt, in der es um die als “Schwache Quantentheorie” propagierte These ging, es gäbe Quantenverschränkung nicht nur in Quantensystemen, sondern auch anderswo. Den mathematischen Hintergrund dazu sollte die Nichtkommutativität liefern:

Weak Quantum Theory is an algebraic formalism and I’m not a mathematician so I can’t do with formulas but it is in fact modelled along the very same algebraic formalism that is used by Quantum Mechanics these days: it’s a C*-algebra for those of you that know the terminology. And what we have done or rather my physicists friends […] we have dropped all definitions, all precisions that are used in Quantum Mechanics to do the calculations and everything and have shrunk the whole formalism to its bare bones.

[…]

The very bare core means that the formalism handles what is called ‘Noncommutative Observables’ or noncommuting operators as it is done in quantum physics proper

[…]

We normally have in algebra that it’s commutative, so we say that 2 times 3 is the same as 3 times 2, it’s 6. It doesn’t matter whether you do this and this first. Now in real life it’s actually more complicated because we slaughter the cow first, then we pull the skin off and then we eat it. We don’t eat it, pull the skin off and then slaughter it. There is a definite sequence in all what we do in life and commutation, I feel, is one of the elements which are important here to take into account.
By quantum mechanics noncommutative elements are actually defined as complementary elements [..]

Nichts davon ist eigentlich falsch (außer dass es im letzten Satz natürlich “noncommuting” statt “noncommutative” heissen muss), aber es ist alles, nun ja, irgendwie trivial und man fragt sich zunächst, was aus solcherart Allgemeinplätzen eigentlich folgen soll.

Die Anwendbarkeit dieser Theorie nichtkommutierender Operatoren (komplementärer Observablen) auch außerhalb der Quantenphysik wurde dann so erklärt.

Individual and community is an example of a pair of complementary variables. […] You could also frame it as separation and connectedness, that’s the same way of putting it. I feel, structure and freedom, a pair that we know from from education, is a complementary pair, […] form and content, something that we know from literature and poetry for instance, maybe law and justice, I’m not quite sure about that, they are relevant in a legal context […] maybe they fulfill the generic properties of complementary pairs being mutually exclusive, maximally incompatible but necessary at the same time to describe the situation.

Im Feuilleton einer Tageszeitung fände man es ja ganz lustig, Recht und Gerechtigkeit mit Verweis auf die Quantenphysik als komplementäre Observablen zu bezeichnen. (Gut, soo originell auch wieder nicht.) Aber der Sprecher schien überzeugt, hier wirklich einen brauchbaren Zugang zur Erklärung von “Systemen” gefunden zu haben:

Suppose you have a system, this one here, and suppose in that system you have various elements. If these elements here, if the description of these elements here, that’s why I have squared them, is complementary to the description of the whole system, then entanglement ensues between all those elements, and not between the other ones, maybe.

In dem Stil ging es dann noch eine Weile weiter. (Die Zitate stammen aus einem Vortragsvideo, dass man auf https://www.comillas.edu/sophiaiberia/Vid/Harald\_Walach.wmv ansehen kann.) Die Schlußfolgerung war letztlich, dass es eine nichtlokale Korrelation zwischen “mind” und “body” geben solle. Die uns bekannten kausalen Zusammenhänge seien die zweiten Ableitungen dieser Korrelation. Das klingt dann doch wieder richtig nach Mathematik und strenger Wissenschaft.

Emergenz

Joseph Honerkamp schreibt in der Einleitung seines vor zwei Jahren bei Springer Spektrum erschienenen Buches “Über die Merkwürdigkeiten der Quantenmechanik”, dass unsere evolutionär erworbenen Vorstellungen und Bilder für das Verständnis des Wirkens der Natur nicht unbedingt auf allen Längenskalen taugen müssen. Das gilt natürlich auch in umgekehrter Richtung.

Eine reale Anwendung der Quantenverschränkung ist Quantenkryptographie. Eine interessante Podiumsdiskussion dazu gab es im September auf dem Heidelberg Laureate Forum, anzuschauen auf https://youtu.be/y-xNxhBmnc8.

Grundlagen der Kryptographie

Zur Bedeutung der Kryptographie im Internet-Zeitalter braucht man
wohl nicht viele Worte zu verlieren. Verschlüsselte, abhörsichere Übertragung ist beim Bezahlen im Internet, bei der elektronischen Unterschrift, im Kreditkartenwesen, bei Zugangskontrolle und Copyright oder natürlich auch einfach bei der üblichen Kommunikation per Handy und e-Mail von eminenter Bedeutung.

Die Aufstellung ist stets: Es gibt einen Sender A, der eine Nachricht an den Empfänger B schickt, und einen Lauscher E, der die (verschlüsselte) Nachricht abfängt. In der Fachliteratur heißt die Senderin A immer Alice, der Empfänger B immer Bob, und die Lauscherin E immer Eva, was wohl für “evil” oder auch “eavesdrop” stehen soll. Konkret ist beispielsweise B eine Bank und A ihr Online-Kunde. E ist ein Hacker, der A’s verschlüsselte Daten abgefangen hat.

Zu einem kryptographischen Verfahren gehört eine Verschlüsselungsfunktion (kurz: Schlüssel) die einen Klartext in einen verschlüsselten Text umwandelt, und eine Entschlüsselungsfunktion, die die Umkehrfunktion der Verschlüsselungsfunktion sein muss. Klassisch ist die Cäsar-Chiffre f(A)=D,f(B)=E,…,f(W)=Z,f(X)=A,f(Y)=B,f(Z)=C oder mathematisch f(x)=x+3 modulo 29, deren Entschlüsselungsfunktion f(x)=x-3 modulo 29 ist. Solche Verschlüsselungsverfahren, bei denen man aus der Kenntnis des Schlüssels sofort auf die Entschlüsselungsfunktion schließen kann, heißen symmetrische Verschlüsselungsverfahren.

Bei symmetrischen Verfahren ist es offenbar wesentlich, daß der Schlüssel geheim gehalten wird. So waren durch das Knacken des ENIGMA-Schlüssels im 2. Weltkrieg den Allierten zum Beispiel bei der Invasion 1944 die deutschen Gefechtsaufstellungen in der Normandie bekannt. Deshalb gelten Verfahren als besonders sicher, deren Sicherheit nicht von der Geheimhaltung des Schlüssels abhängt: sogenannte asymmetrische (“public key”) Verfahren.

Die sind freilich mit erheblichem Rechneraufwand verbunden. In der Praxis entscheidet man sich deshalb oft für symmetrische Verfahren
und verwendet bei wirklich sensiblen Daten eine Mischung aus beiden Verfahren: Man verwendet das asymmetrische Verfahren nicht zur Übermittlung der Nachricht selbst, sondern nur zur verschlüsselten Übermittlung eines Schlüssels. Mit diesem gemeinsamen Schlüssel verwenden A und B dann ein symmetrisches Verfahren zur Übermittlung der eigentlichen Nachricht.

Für symmetrische Verfahren gibt es seit 2000 einen vom National Institute of Science and Technology NIST – dem US-amerikanischen Gegenstück zur Physikalisch-Technischen Bundesanstalt – festgelegten Standard, den seitdem unter der Bezeichnung AES (Advanced Encryption Standard) bekannten Rijndael-Algorithmus. Der Algorithmus ist frei verfügbar und darf ohne Lizenzgebühren eingesetzt sowie in Software bzw. Hardware implementiert werden.

AES ist ein Blockchiffre mit Blöcken aus 128 Bit. Jeder Block wird bestimmten Transformationen unterzogen, wobei die Blöcke nicht unabhängig verschlüsselt, sondern verschiedene Teile des Schlüssels nacheinander auf den Klartext-Block angewendet werden.

Nach Meinung der NIST-Jury von 2000 bietet AES ausreichend Sicherheit für die nächsten 100 Jahre. (Mit solchen Prognosen muß man natürlich vorsichtig sein. In einem ähnlichen Zusammenhang sagte Ronald Rivest – einer der Entwickker von RSA – 1977, die Faktorisierung einer 125-stelligen Zahl dauere 40 Billiarden Jahre. Tatsächlich gelang eine solche Faktorisierung dann bereits 1994, ab 2003 wurden immer größere Zahlen faktorisiert und 2009 gelang die Faktorisierung einer 232-stelligen Zahl nach 20-monatiger Arbeit eines Rechnerpools einer Gruppe unter Leitung der Bonner Mathematiker Jens Franke und Thorsten Kleinjung. 2020 wurde am INRIA in Nancy erstmals eine 250-stellige Zahl faktorisiert.)

Jedenfalls soll AES als Standard für symmetrische Verschlüsselungsverfahren auf absehbare Zeit nicht geändert werden. Die Forschung in der Kryptographie konzentriert sich deshalb darauf, immer bessere asymmetrische Verfahren zu entwickeln (bzw. aus Sicht der Hacker immer bessere Angriffe auf asymmetrische Verfahren zu finden).

Asymmetrische Verschlüsselung

Alice will Bob eine verschlossene Kiste (mit einer Nachricht) senden, ohne den Schlüssel zu schicken.

Sie macht folgendes: sie sichert die Kiste mit einem Vorhängeschloß (und behält den Schlüssel) und schickt Bob die verschlossene Kiste.

Bob kann die Kiste natürlich nicht öffnen, aber er sichert die Kiste mit einem zweiten Vorhängeschloß (und behält ebenfalls den Schlüssel) und schickt die doppelt gesicherte Kiste an Alice zurück.

Alice öffnet ihr Schloß mit ihrem Schlüssel und schickt die (immer noch mit Bobs Vorhängeschloß gesicherte) Kiste an Bob.

Bob kann die Kiste jetzt mit seinem eigenen Schlüssel öffnen.

Während des gesamten Vorgangs ist die Kiste nie unverschlossen unterwegs gewesen.

Im Prinzip könnte man so Daten sicher übertragen. Nur ist es viel zu umständlich, alles zweimal hin- und herzuschicken.

Quelle

Lange hatte man das Problem der Schlüsselübertragung für ein unvermeidbares Problem der Datenübertragung gehalten. Mitte der 70er Jahre wurden dann (eigentlich relativ einfache) asymmetrische Verschlüsselungsmethoden entwickelt, die dieses Problem umgehen. Im Nachhinein ist es natürlich paradox, dass diese Methoden gerade rechtzeitig entdeckt wurden, um dann ab den 80er Jahren die sichere Datenübertragung per Internet zu ermöglichen. Ohne die mathematischen Entdeckungen, die Diffie-Hellman 1976 und Rivest-Shamir-Adleman 1977 machten, würde der Datenaustausch im Internet heute wesentlich zeitaufwendiger und Online-Handel damit praktisch unmöglich sein.

We stand today on the brink of a revolution in cryptography.

So begann, wenig bescheiden, 1976 ein Artikel von Diffie und Hellman, einem 32-jährigen Dauerstudenten – der seine Promotion bis heute nicht abgeschlossen hat – und seinem 31-jährigen Professor. In der Sache behielten sie mit ihrer Ankündigung durchaus recht: auf dem Diffie-Hellman-Prinzip beruhen heute die meisten Public-Key-Verschlüsselungsverfahren. (Man weiß heute, dass dieses Verfahren bereits 1974 beim britischen Geheimdienst von Malcolm Williamson entwickelt wurde. Der Geheimhaltung wegen durfte Williamson seine Arbeit damals nicht veröffentlichen.)

Der Diffie-Hellman-Schlüsselaustausch funktioniert nach folgendem Prinzip: A denkt sich a, B denkt sich b, dann schickt A g^a an B, der daraus g^ab berechnet, und B schickt g^b an A, der daraus g^ba berechnet.
Dabei sind a und b ganze Zahlen, g ist Element irgendeiner Gruppe G. g^ab=g^ba ist dann der gemeinsame Schlüssel.

Das ist (für Mathematiker) eigentlich eine sehr banale Idee. Dass sie trotzdem sichere Verschlüsselungsverfahren liefert, liegt daran, dass es Gruppen G gibt, die viel komplizierter sind als die ganzen Zahlen, und für die das Problem des diskreten Logarithmus schwer zu lösen ist.

Problem des diskreten Logarithmus: In einer abelschen Gruppe G seien ein Element g und eine Potenz g^a gegeben. Berechne die ganze Zahl a.

Der Diffie-Hellman-Schlüsselaustausch lässt sich knacken, wenn in einer Gruppe G der diskrete Logarithmus leicht zu berechnen ist, wie etwa in den ganzen Zahlen. Schwer zu berechnen ist der diskrete Logarithmus zum Beispiel in – darauf beruht RSA – oder in abelschen Varietäten, zum Beispiel in elliptischen Kurven über , die anders als höherdimensionale abelsche Varietäten auch mit vertretbarem Aufwand zu speichern sind. Auf elliptischen Kurven beruht die Elgamal-Verschlüsselung, die heute meist verwendet wird.

Um das Prinzip an einem sehr einfachen Beispiel zu veranschaulichen, nehmen wir mal die Kurve über , die zufällig aus genau 28 Punkten besteht, welche man also den Symbolen des deutschen Alphabets – 26 Buchstaben sowie Leerzeichen und Punkt – zuordnen kann.
Der Buchstabe A entspreche dem Punkt (0,5), der Buchstabe B dem Punkt (0,18), der Buchstabe H dem Punkt (4,20), der Buchstabe Z dem Punkt (20,9), das Leerzeichen dem Punkt (20,14) und der Punkt dem Punkt im Unendlichen. Wenn wir dann etwa als Verschlüsselungsfunktion , also a=2 wählen, dann wird jeweils der P entsprechende Buchstabe mit dem 2P=P+P entsprechenden Buchstaben verschlüsselt. Zum Beispiel ist (0,5)+(0,5)=(4,20), also wird A durch H verschlüsselt.

In der Praxis werden natürlich nicht Buchstaben, sondern Blöcke von Bits verschlüsselt, außerdem braucht man elliptische Kurven mit wesentlich mehr Punkten. Bei nur 28 Punkten wäre die Entschlüsselung notfalls auch durch brachiales Probieren machbar, mit Computer-Hilfe eine Sache von Sekunden-Bruchteilen.

Real verwendet man elliptische Kurven mit mindestens 2²⁵⁶ Punkten. Nach der von Hasse bewiesenen Riemann-Vermutung für Funktionenkörper elliptischer Kurven ist die Anzahl der Punkte einer elliptischen Kurve näherungsweise p+1 – genauer , weshalb man also auch p in dieser Größenordnung wählen muss. Um dieselbe Sicherheit nicht mit elliptischen Kurven, sondern mit RSA zu erreichen, müßte man mit viel größeren Zahlen rechnen.

Entschlüsselung

In der Kryptographie gelten Verschlüsselungsverfahren als unsicher, wenn es Entschlüsselungs-Algorithmen in subexponentieller Zeit gibt.

Es gibt eine Reihe von Algorithmen zum Knacken elliptischer Kurven, die exponentielle Zeit benötigen. Bekannte Beispiele sind der Babystep-Giantstep-Algorithmus, der Pohlig-Hellman-Algorithmus, der Pollard ρ-Algorithmus und der Pollard λ-Algorithmus. Wegen ihres hohen Zeit- und Speicher-Aufwandes sind sie nicht praktikabel und stellen also keine Gefahr dar.

Darüber hinaus gibt es Algorithmen, die für sehr spezielle elliptische Kurven tatsächlich Entschlüsselung in subexponentieller Zeit erreichen. Diese speziellen elliptischen Kurven dürfen dann natürlich in der Verschlüsselung nicht verwendet werden.

Konkret dürfen sogenannte “supersinguläre” und “anomale” Kurven nicht verwendet werden.
Eine “supersinguläre” Kurve ist eine Kurve, für die die Anzahl der Punkte genau p+1 ist, also Gleichheit im Satz von Hasse gilt. (Jedenfalls, wenn man modulo einer Primzahl rechnet. Die allgemeine Definition ist, dass durch p teilbar sein soll.) Für supersinguläre Kurven gibt es den MOV-Algorithmus, der in subexponentieller Zeit entschlüsselt. Der MOV-Algorithmus benutzt die Weil-Paarung, um die Berechnung diskreter Logarithmen in auf die (etwas einfachere) Berechnung diskreter Logarithmen in der multiplikatven Gruppe zurückzuführen.
Eine “anomale” elliptische Kurve ist eine Kurve, für die die Anzahl der Punkte genau p ist. Für anomale Kurven gibt es den SSSA-Algorithmus, der in subexponentieller Zeit entschlüsselt.

In der Praxis verwendet man ohnehin nur eine relativ kleine Auswahl von elliptischen Kurven. Die NSA zum Beispiel hat eine überschaubare Liste von zu verwendenden elliptischen Kurven.

In choosing an elliptic curve as the foundation of a public key system there are a variety of different choices. The National Institute of Standards and Technology (NIST) has standardized on a list of 15 elliptic curves of varying sizes. Ten of these curves are for what are known as binary fields and 5 are for prime fields. Those curves listed provide cryptography equivalent to symmetric encryption algorithms (e.g. AES, DES or SKIPJACK) with keys of length 80, 112, 128, 192, and 256 bits and beyond.

For protecting both classified and unclassified National Security information, the National Security Agency has decided to move to elliptic curve based public key cryptography. Where appropriate, NSA plans to use the elliptic curves over finite fields with large prime moduli (256, 384, and 521 bits) published by NIST.

Eine Kuriosität am Rande: auf viele Eigenschaften von elliptischen Kurven gibt es Patente von Unternehmen oder Privatpersonen, die NSA mußte für einige der auf ihrer Liste vorgeschlagenen Kurven zunächst eine Lizenz erwerben.

Quantencomputer – die es freilich noch nicht gibt – könnten mit einem Algorithmus, für den Peter Shor 1998 den (inzwischen in IMU Abacus Medal umbenannten) Nevanlinna-Preis erhielt die Primfaktorzerlegung großer Zahlen effektiv berechnen. Mit einer Variante des Shor-Algorithmus könnten sie auch diskrete Logarithmen in beliebigen zyklischen Gruppen endlicher Ordnung ziehen und damit jede Variante der auf elliptischen Kurven beruhenden Elgamal-Verschlüsselung effektiv brechen.

Warum werden Bitcoins nicht geknackt?

Wer schon immer einmal wissen wollte, welches Verschlüsselungsverfahren Bitcoins verwenden: diese Frage wurde im November 2019 auf Mathoverflow diskutiert.

Verwendet wird die sehr einfach aussehende elliptische Kurve

über dem endlichen Körper F_p mit
.

Tatsächlich betrachtet man in dieser elliptischen Kurve nur eine zyklische Untergruppe der Ordnung 115792089237316195423570985008687907852837564279074904382605163141518161494337.

Die Antworten auf Mathoverflow kann man wohl so zusammenfassen, dass man an die Sicherheit des Bitcoin-Algorithmus glaubt, weil viele smarte Leute versucht haben ihn zu knacken und es noch niemandem gelungen ist.

Schutz vor Quantencomputern

Zurück zur Podiumsdiskussion Ende September auf dem Heidelberg Laureate Forum. Diese begann mit einem halbstündigen Referat von Whitfield Diffie über die Geschichte der Kryptographie, das er mit dem Hinweis beendete, dass schon 2015 das Committee on National Security Systems aufgefordert hatte, zu Algorithmen zu wechseln, die auch gegen Quantencomputer – insbesondere Shors Algorithmus – resistent sind. Nach dieser Aufforderung sei sieben Jahre lang nichts passiert, aber vor wenigen Tagen sei ein auf CRYSTALS basierender neuer Algorithmus herausgekommen.

CRYSTALS steht für „Cryptographic Suite for Algebraic Lattices“, es setzt sich zusammen aus Kyber, einem IND-CCA2-secure key-encapsulation mechanism, und Dilithium, einem strongly EUF-CMA-secure digital signature algorithm. Beide Algorithmen basieren auf schweren Problemen aus der Theorie von Gittern in Moduln. Ein paar Stichworte zum mathematischen Hintergrund gibt der Wikipedia-Artikel “Lattice-based cryptography”.

Die Frage, wann mit Quantencomputern zu rechnen sei, wurde von den Teilnehmern der anschließenden Podiumsdiskussion mit Zahlen zwischen 10 und 30 Jahren beantwortet. Man solle trotzdem jetzt mit den Umstellungen beginnen, weil solch ein Wechsel eine lange Zeit benötige: Standards müßten geändert, Menschen dafür ausgebildet und zahlreiche praktische Probleme gelöst werden. Außerdem könnten wichtige Geheimnisse heute gestohlen und 20 Jahre später entschlüsselt werden, weshalb man sie schon heute gegen Angriffe durch Quantencomputer schützen sollte.