Engineering-Philosophie: Adi Shamir

Die wichtigsten Erkenntnisse

• Er ist das „S” in RSA, dem ersten praxistauglichen Public-Key-Kryptosystem. Gemeinsam mit Ron Rivest und Leonard Adleman erfand Adi Shamir 1977 am MIT RSA – noch im selben Jahr öffentlich beschrieben und im Februar 1978 in den Communications of the ACM veröffentlicht. Das Verfahren machte es möglich, jemandem verschlüsselte Nachrichten zu senden und seine Signaturen zu prüfen, ohne je vorab ein Geheimnis ausgetauscht zu haben; seine Sicherheit beruht auf der Schwierigkeit, große Zahlen zu faktorisieren. Für diese Arbeit erhielten die drei den ACM Turing Award 2002.¹²
• Er verwandelte ein Polynom in ein perfektes Geheimnis. 1979 veröffentlichte Shamir „How to Share a Secret”, ein Schwellenschema, das ein Geheimnis so unter n Personen aufteilt, dass beliebige k von ihnen es rekonstruieren können und beliebige k-1 überhaupt nichts erfahren – keinen Hinweis, keine Einengung. Das Ganze ist aus nichts weiter als Punkten auf einem Polynom aufgebaut.³
• Er ist ein Meister der Kryptoanalyse – er greift an, um zu verteidigen. Gemeinsam mit Eli Biham entdeckte Shamir Ende der 1980er-Jahre öffentlich die differentielle Kryptoanalyse, eine allgemeine Methode zum Brechen von Blockchiffren, und schon zuvor hatte er das Merkle-Hellman-Rucksack-Kryptosystem gebrochen. Derselbe Kopf, der RSA baute, verbrachte Jahrzehnte damit, das Brechen zu lernen – denn in der Kryptografie ist das die einzige ehrliche Art, zu wissen, dass ein System stark ist.⁴⁵
• Er verwandelt fortwährend saubere Mathematik in praktische Mechanik. Über RSA und Secret Sharing hinaus erfand Shamir die Fiat-Shamir-Heuristik mit – eine Methode, einen interaktiven Beweis mithilfe einer Hashfunktion in eine nicht-interaktive Signatur zu verwandeln – sowie identitätsbasierte und visuelle Kryptografie. Seit 1980 Professor am Weizmann-Institut, ist seine Laufbahn ein langer Beleg dafür, dass tiefe Zahlentheorie ein Werkzeugkasten ist und kein Museum.¹⁶

Das Prinzip

„Später stellte sich heraus, dass die differentielle Kryptoanalyse sowohl IBM als auch der National Security Agency bereits bekannt war – und geheim gehalten wurde.” – über die Technik, die Biham und Shamir öffentlich wiederentdeckten, sinngemäß nach der historischen Überlieferung⁴⁵

Der größte Teil der Ingenieurskunst arbeitet auf eine Demo hin. Man schreibt das Ding, lässt es laufen, es funktioniert, und das Funktionieren ist der Beweis. Die Kryptografie verweigert diesen Trost. Eine Chiffre, die korrekt ver- und entschlüsselt, hat damit nichts darüber gezeigt, ob sie sicher ist – eine gebrochene und eine unbrechbare Chiffre verhalten sich identisch, bis jemand sie angreift. Also musste das Fach einen anderen Wahrheitsmaßstab erfinden: Ein System ist nicht dann vertrauenswürdig, wenn es läuft, sondern wenn ernsthafte Leute hart versucht haben, es zu brechen, und gescheitert sind. Shamirs gesamte Laufbahn verkörpert genau diesen Maßstab. Man sichert ein System, indem man lernt, Systeme zu brechen – angreifen, um zu verteidigen.⁴

Am deutlichsten zeigt sich das daran, dass er beide Hälften selbst übernimmt. Er baute RSA, den Grundstein der Public-Key-Kryptografie, und er baute Shamirs Secret Sharing, ein Schema mit beweisbarer informationstheoretischer Sicherheit.¹³ Doch er brach auch das Merkle-Hellman-Rucksack-Kryptosystem – ein konkurrierendes Public-Key-Verfahren, das sicher aussah und es nicht war – und er entdeckte die differentielle Kryptoanalyse mit, eine Methode, allgemein genug, um den Data Encryption Standard selbst zu bedrohen.⁴⁵ Das sind nicht zwei Laufbahnen. Es ist eine Disziplin. Die Aufbauarbeit sagt einem, was möglich ist; die Zerstörungsarbeit sagt einem, was real ist. Ein Kryptograf, der nur baut, rät – und der erschreckendste Beleg dafür kam später, als herauskam, dass IBM und die NSA seit Mitte der 1970er-Jahre von der differentiellen Kryptoanalyse gewusst und sie als geheim eingestuft hatten – was bedeutet, dass das öffentliche Fach Chiffren gebaut hatte, blind für einen Angriff, den seine Gegner längst beherrschten.⁴⁵

Das Prinzip hat eine zweite Hälfte, leiser und genauso tragend: die Kraft, eine saubere mathematische Idee in einen praktischen Mechanismus zu verwandeln. Secret Sharing ist nur Polynom-Interpolation – eine Tatsache, der jeder Schüler in der Algebra begegnet: dass zwei Punkte eine Gerade festlegen und drei eine Parabel. Shamir erkannte, dass dieselbe Tatsache, rückwärts gelesen, ein Sicherheitsprimitiv ist: Man verteilt Punkte, und die Kurve bleibt verborgen, bis genügend von ihnen zusammenkommen.³ RSA ist nur modulare Exponentiation und die Schwierigkeit der Faktorisierung.² Die Fiat-Shamir-Heuristik ist nur das Ersetzen des Münzwurfs eines Prüfers durch einen Hash.⁶ Finde die saubere mathematische Struktur und lies sie dann als Mechanismus. Das Geniale ist selten neue Mathematik – es ist das Erkennen, dass alte Mathematik, aus dem richtigen Winkel betrachtet, bereits genau das ist, was man bauen muss.

Kontext

Adi Shamir wurde am 6. Juli 1952 in Tel Aviv, Israel, geboren.¹ Er machte 1973 seinen BSc in Mathematik an der Universität Tel Aviv und wechselte dann für das Aufbaustudium an das Weizmann-Institut für Wissenschaften, wo er 1975 einen MSc in Informatik und 1977 den PhD erwarb.¹ Sein Timing war, wie das des ganzen Fachs, im Begriff zu kippen: 1977 war das Jahr, in dem die Public-Key-Kryptografie von einer verlockenden Idee zu einem funktionierenden System wurde.

Nach der Promotion verbrachte er ein Jahr als Postdoktorand an der University of Warwick in England und ging dann an das Massachusetts Institute of Technology, wo er von 1977 bis 1980 wissenschaftlicher Mitarbeiter war.¹ Am MIT geschah RSA. Ron Rivest, der Kryptograf, jagte schon länger einem Public-Key-Verfahren nach, inspiriert von der Diffie-Hellman-Idee, dass zwei Parteien Geheimhaltung herstellen können, ohne ein gemeinsames Geheimnis zu teilen; Shamir und Adleman waren seine Mitarbeiter und, entscheidend, seine Gegenspieler – Rivest schlug ein Verfahren vor, und Shamir und Adleman brachen es, wieder und wieder, bis eines überlebte. Das, was überlebte, war RSA, benannt nach den dreien, 1977 vorgestellt und 1978 in den Communications of the ACM veröffentlicht.² (Ohne ihr Wissen hatte der britische Mathematiker Clifford Cocks beim GCHQ ein gleichwertiges System bereits in einem als geheim eingestuften Dokument von 1973 beschrieben, das bis 1997 geheim blieb – ein weiterer Fall, in dem das Fach im Dunkeln baute, während Nachrichtendienste zusahen.)²

1980 kehrte Shamir an das Weizmann-Institut zurück, wo er seither Professor in der Abteilung für Informatik und angewandte Mathematik ist und später zusätzlich eine eingeladene Professur an der École Normale Supérieure in Paris innehatte.¹ Fast alles, was ihn auszeichnet – Secret Sharing, der Angriff auf die Rucksack-Chiffren, die differentielle Kryptoanalyse mit seinem Studenten Eli Biham, die Fiat-Shamir-Heuristik, die visuelle Kryptografie mit Moni Naor, die Cube-Attacken, die Faktorisierungsmaschinen TWIRL und TWINKLE – entstand am Weizmann. 2002 verlieh die Association for Computing Machinery Rivest, Shamir und Adleman den Turing Award, die höchste Auszeichnung der Informatik, für ihre Beiträge zur Public-Key-Kryptografie.¹²

Die Arbeit

Shamirs Secret Sharing: eine Parabel, die ein Geheimnis hütet

Beginnen Sie hier, denn dies ist das Prinzip in seiner reinsten, schönsten Form. Angenommen, Sie haben ein Geheimnis – einen Hauptschlüssel, den Startcode, das Passwort zu einer Schatzkammer – und wollen es so unter fünf Treuhändern aufteilen, dass beliebige drei von ihnen es gemeinsam wiederherstellen können, beliebige zwei aber nichts erfahren. Sie könnten versuchen, den Schlüssel physisch in Stücke zu zerschneiden, doch das leckt: Jedes Stück engt die Vermutung ein. Shamirs Einsicht von 1979 in „How to Share a Secret” lautete, dass Polynome genau dies bereits exakt lösen.³

Der Kniff liest eine Schulwahrheit rückwärts. Zwei Punkte bestimmen eine eindeutige Gerade; drei Punkte bestimmen eine eindeutige Parabel; allgemein bestimmen k Punkte ein eindeutiges Polynom vom Grad k-1. Um also ein Geheimnis unter n Personen mit einer Schwelle von k zu teilen, verbergen Sie das Geheimnis als konstantes Glied eines zufälligen Polynoms vom Grad (k-1) – den Wert der Kurve bei x = 0 – und geben jeder Person einen Punkt auf dieser Kurve.³ Beliebige k von ihnen können die eindeutige Kurve durch ihre Punkte interpolieren und ihren Wert bei null ablesen. Doch das Erstaunliche ist die Sicherheit: Mit nur k-1 Punkten ist die Kurve nicht bloß schwer zu finden – sie ist tatsächlich unbestimmt. Für jeden möglichen Geheimwert gibt es genau eine Kurve des richtigen Grades, die durch ihre Punkte verläuft und bei null diesen Wert trifft. Wie Shamirs Schema garantiert, „lässt die Kenntnis von beliebigen k-1 oder weniger Anteilen S völlig unbestimmt”.³ Weniger als die Schwelle verrät nichts; die Schwelle verrät alles. Diese saubere Alles-oder-nichts-Grenze macht es informationstheoretisch sicher – sicher nicht, weil das Brechen rechnerisch schwer ist, sondern weil die Information schlicht nicht vorhanden ist.³

Warum das als Ingenieurskunst zählt: Das Schema ist das kanonische Beispiel dafür, wie Shamir Mathematik als Mechanismus liest. Er erfand die Polynom-Interpolation nicht – sie ist Jahrhunderte alt. Er erkannte, dass ihr Versagensmodus – dass man eine Kurve aus zu wenigen Punkten nicht wiederherstellen kann – exakt eine Sicherheitseigenschaft ist, und dass ihr Erfolgsmodus – dass genügend Punkte sie eindeutig festlegen – exakt eine Wiederherstellungseigenschaft ist. Dieselbe Tatsache, in beide Richtungen genutzt, wird zu einem kryptografischen Primitiv, das heute in Hardware-Sicherheitsmodulen, der Verwahrung von Kryptowährungen und Zertifizierungsstellen läuft. Saubere Mathematik, als Werkzeug gelesen.³

RSA: einem Fremden verschlüsselt schreiben

RSA beantwortete eine Frage, die fast paradox erschienen war: Wie können zwei Menschen, die sich nie begegnet sind und nur über eine Leitung kommunizieren, an der ein Gegner lauscht, Geheimnisse austauschen? Die klassische Kryptografie verlangte einen vorab vereinbarten gemeinsamen Schlüssel – doch Sie können keinen Schlüssel über genau den Kanal teilen, den Sie zu schützen versuchen. Der Durchbruch, den Rivest, Shamir und Adleman 1977 zu einem funktionierenden System ausbauten, war die Trapdoor-Einwegfunktion: eine Operation, die vorwärts leicht zu berechnen und rückwärts undurchführbar ist – es sei denn, man besitzt eine geheime Information.²

RSAs Falltür ist die Faktorisierung. Sie wählen zwei große Primzahlen und multiplizieren sie zu einem Modul n; n und ein öffentlicher Exponent werden Ihr öffentlicher Schlüssel, den Sie aller Welt bekannt machen können. Jeder kann ihn nutzen, um Ihnen über modulare Exponentiation eine Nachricht zu verschlüsseln. Das Entschlüsseln aber erfordert den privaten Schlüssel, der sich nur aus den beiden ursprünglichen Primzahlen ableiten lässt – und diese Primzahlen aus ihrem Produkt zurückzugewinnen, bedeutet, eine sehr große Zahl zu faktorisieren, ein Problem ohne bekannte effiziente Lösung.² Wie es in der Formulierung heißt, ist es zwar praktikabel, die Schlüssel zu erzeugen, doch „wenn nur e und n gegeben sind, ist es undurchführbar, e-te Wurzeln modulo n zu berechnen”.² Sie veröffentlichen das Schloss; nur Sie besitzen den Schlüssel; und die Kluft zwischen beiden ist die Schwierigkeit der Faktorisierung.

Shamirs spezifische Rolle ist es wert, klar benannt zu werden, denn sie ist wieder das Prinzip: Er war, neben Adleman, der Kryptoanalytiker des Trios. Die Geschichte der Erfindung von RSA ist eine Geschichte des Brechens – Rivest schlug Kandidatenverfahren vor, und Shamir und Adleman griffen sie an, bis nur eines dem Ansturm standhielt. Das überlebende Verfahren war gerade deshalb stark, weil es den Angriffen zweier Leute standgehalten hatte, die entschlossen waren, es zu brechen. RSA ist kein System, das sicher konstruiert und dann nur erhofft wurde; es ist ein System, das den Anspruch verdiente, indem es seine eigenen Autoren überlebte.²

Angreifen, um zu verteidigen: Rucksäcke brechen und differentielle Kryptoanalyse

Wenn RSA Shamir beim Bauen zeigt, dann zeigt ihn die nächste Arbeit bei dem, was das Fach noch dringender braucht: beim Brechen. Ende der 1970er-Jahre war das Merkle-Hellman-Rucksack-Kryptosystem ein führender Konkurrent von RSA, dessen Sicherheit auf dem „Teilsummenproblem” beruhte, das NP-vollständig ist und daher gewaltig schwer aussah. Shamir brach es. Er zeigte, dass die konkreten Rucksäcke, die Merkle-Hellman verwendete, nicht der schwere allgemeine Fall waren, sondern ein spezieller, strukturierter, der sich effizient lösen ließ – und riss damit ein Verfahren ein, dem viele vertraut hatten.¹ Die Lehre ist eine, die die Kryptografie immer wieder neu lernt: Dass ein Problem im Allgemeinen schwer ist, heißt nicht, dass die Instanzen, die Ihre Chiffre tatsächlich verwendet, schwer sind. Nur der Angriff zeigt den Unterschied.

Seine einflussreichste kryptoanalytische Arbeit entstand mit seinem Studenten Eli Biham Ende der 1980er-Jahre: die differentielle Kryptoanalyse, veröffentlicht um 1990.⁴⁵ Es ist eine allgemeine Technik, die untersucht, wie sich Unterschiede zwischen Eingabepaaren einer Chiffre auf Unterschiede in der Ausgabe fortpflanzen. Wenn bestimmte Eingabeunterschiede mit nicht-zufälliger Wahrscheinlichkeit zu bestimmten Ausgabeunterschieden führen, ist diese statistische Verzerrung ein Riss – ein Leck von Information über den Schlüssel – und Biham und Shamir verwandelten sie in Angriffe auf eine Reihe von Blockchiffren, darunter eine theoretische Schwäche im Data Encryption Standard, damals der wichtigsten Chiffre der Welt.⁴⁵

Dann lernte das Fach etwas Demütigendes. 1994 enthüllte Don Coppersmith, dass IBM – das DES in den 1970er-Jahren entworfen hatte – von der differentiellen Kryptoanalyse „schon 1974” gewusst hatte, dass die Verteidigung dagegen ein ausdrückliches Entwurfsziel von DES gewesen war und dass die NSA darauf gedrängt hatte, die Technik geheim zu halten, weil „die Offenlegung der Entwurfsüberlegungen die Technik der differentiellen Kryptoanalyse enthüllen würde, eine mächtige Technik, die gegen viele Chiffren eingesetzt werden könnte”.⁴⁵ DES’ rätselhafte interne Konstanten, lange im Verdacht, eine Hintertür zu verbergen, verbargen in Wahrheit eine Verteidigung gegen einen Angriff, von dessen Existenz die Öffentlichkeit nichts wusste. Die Episode ist das stärkstmögliche Argument für Shamirs Prinzip. Zwei Jahrzehnte lang hatte die offene Gemeinschaft Chiffren gebaut und ihnen vertraut, während sie blind blieb für einen grundlegenden Angriff, den die Gegner bereits beherrschten. Bihams und Shamirs öffentliche Wiederentdeckung schwächte die Kryptografie nicht – sie stärkte sie, indem sie den Angriff ans Licht zerrte, wo jeder dagegen entwerfen konnte. Angreifen, um zu verteidigen, im Maßstab eines ganzen Fachs.⁴⁵

Fiat-Shamir und die Breite des Werkzeugkastens

Derselbe Instinkt – finde die saubere Struktur, lies sie als Mechanismus – durchzieht Shamirs übrige Erfindungen. Die Fiat-Shamir-Heuristik, mit Amos Fiat Mitte der 1980er-Jahre, löste ein praktisches Problem interaktiver Wissensbeweise: Solche Beweise erfordern ein lebendiges Hin und Her, bei dem ein Prüfer eine zufällige Herausforderung sendet und ein Beweisführer antwortet. Fiat und Shamir erkannten, dass die einzige Aufgabe des Prüfers darin bestand, unvorhersehbare Zufälligkeit zu liefern, und dass eine auf die Nachricht des Beweisführers angewandte kryptografische Hashfunktion diese Zufälligkeit genauso gut liefern konnte – und verwandelten so ein Gespräch in einen einzigen, in sich geschlossenen, nicht-interaktiven Beweis, also in eine digitale Signatur.⁶ Diese eine Transformation liegt einem großen Teil moderner Signaturverfahren und Zero-Knowledge-Systeme zugrunde. Er schlug außerdem die identitätsbasierte Kryptografie vor (die Identität einer Person als ihr öffentlicher Schlüssel), erfand mit Moni Naor die visuelle Kryptografie mit (das Aufteilen eines Bildes in Folien, die ein Geheimnis erst beim Übereinanderlegen offenbaren – Secret Sharing, das man sehen kann) und entwickelte später die Cube-Attacken sowie die Faktorisierungsmaschinen TWIRL und TWINKLE.¹ Über all dem hält das Muster: ein bekanntes Stück Mathematik, richtig gedreht, wird zum Werkzeug.

Die Methode

Liest man quer durch RSA, Secret Sharing, die gebrochenen Rucksäcke, die differentielle Kryptoanalyse und Fiat-Shamir, kehren dieselben Verpflichtungen wieder. Shamirs Methode ist weniger ein Slogan als eine Menge fester Gewohnheiten.

Bauen und brechen mit denselben Händen. Der prägende Zug ist die Weigerung, die Arbeit zwischen jenen aufzuteilen, die Systeme bauen, und jenen, die sie angreifen. Shamir erfand RSA mit und brach den Merkle-Hellman-Rucksack; er bewies die Sicherheit von Secret Sharing und entdeckte die differentielle Kryptoanalyse mit. Die Lehre reicht weit über die Kryptografie hinaus: Sie verstehen nicht, was Sie gebaut haben, bis Sie ernsthaft versucht haben, es zu bezwingen. Es ist die Beweisschwelle, erhoben zu einer Lebensform – „es funktioniert” ist kein Beleg für Sicherheit; „ernsthafte Leute haben versucht, es zu brechen, und konnten es nicht” ist es.²⁴

Vertraue nur dem, was Angriffe überlebt. Eine Chiffre, die lediglich sorgfältig entworfen wurde, ist eine Hoffnung; eine Chiffre, die konzentrierter Kryptoanalyse standgehalten hat, ist eine Tatsache. Die Disziplin besteht darin, das eigene System als schuldig zu behandeln, bis es angegriffen wurde – anzunehmen, dass es einen Riss gibt, und ihn zu suchen, statt darauf zu warten, dass ein Gegner ihn für einen findet. Dies ist die kryptografische Form von Thompsons „Reflections on Trusting Trust”: die grundlegende Einsicht, dass man nicht vertrauen kann, was man nicht gegnerisch geprüft hat, denn die Bedrohung, die man nicht sieht, ist die, die einen erwischt – wie die geheime Geschichte der differentiellen Kryptoanalyse bewies.⁴⁵

Lies Mathematik als Mechanismus. Die mächtigsten Primitive sind selten neue Mathematik; sie sind alte Mathematik, aus einem neuen Winkel gesehen. Polynom-Interpolation wird zu Secret Sharing; die Schwierigkeit der Faktorisierung wird zu einer Falltür; eine Hashfunktion wird zum Stellvertreter eines interaktiven Prüfers. Die Gewohnheit ist, eine saubere Struktur zu betrachten und nicht zu fragen „was ist das?”, sondern „was könnte das tun?” – dieselbe Ökonomie der Mittel, die die stärksten Primitive zugleich zu den einfachsten macht, im Geiste des Minimum Worthy Product.³⁶

Bevorzuge beweisbare Sicherheit, wo sie zu haben ist, und verdiente Sicherheit überall sonst. Secret Sharing ist informationstheoretisch sicher – kein Computer, so mächtig er auch sei, kann das Geheimnis aus zu wenigen Anteilen herausziehen, weil die Information nicht vorhanden ist.³ RSA ist rechnerisch sicher – nur so lange sicher, wie die Faktorisierung schwer bleibt. Shamir arbeitet auf beiden Ebenen und ist präzise darin, welche er gerade hat. Die Disziplin besteht darin, genau zu wissen, worauf der eigene Sicherheitsanspruch beruht, und niemals „bisher hat es noch niemand gebrochen” mit „es kann nicht gebrochen werden” zu verwechseln. Es ist Qualität ist die einzige Variable, angewandt auf Vertrauen: Das Einzige, was zählt, ist, ob die Garantie real ist.²³

Misstraue dem Spezialfall, der sich im allgemeinen verbirgt. Das Brechen von Merkle-Hellman lehrte das Fach, dass ein Problem, das im Allgemeinen NP-vollständig ist, nichts über die konkreten Instanzen aussagt, die eine Chiffre tatsächlich verwendet.¹ Die feste Gewohnheit ist, zu vermuten, dass die bequeme, strukturierte Variante eines schweren Problems – die, die leicht genug ist, um ein System darum herum zu bauen – vielleicht genau die Variante ist, die leicht zu brechen ist. Dasselbe Misstrauen, das Leslie Lamport in verteilte Systeme einbrachte: Vertraue nicht der Eigenschaft, die du angenommen hast; finde die genaue Bedingung, unter der sie tatsächlich gilt.

Einfluss-Kette

Wer ihn prägte

Diffie, Hellman und die Public-Key-Idee. RSA war eine direkte Antwort auf Whitfield Diffies und Martin Hellmans Vorschlag von 1976, dass Geheimhaltung ohne einen vorab geteilten Schlüssel hergestellt werden könne. Diffie-Hellman stellte die Frage – ein Public-Key-Kryptosystem sollte existieren – und Rivest, Shamir und Adleman bauten die erste praktische Antwort.² (Direkter Einfluss)

Ron Rivest und Leonard Adleman. Die RSA-Zusammenarbeit war wahrhaftig dreihändig: Rivest der unermüdliche Vorschlagende, Shamir und Adleman die unermüdlichen Brecher. Die gegnerische Struktur dieser Partnerschaft – vorschlagen, angreifen, wiederholen – prägte Shamirs lebenslange Überzeugung, dass Konstruktion und Kryptoanalyse eine Disziplin sind.² (Prägender Einfluss)

Die zahlentheoretische Tradition. Shamirs charakteristischer Zug – klassische Mathematik als kryptografischen Mechanismus zu lesen – stammt aus der langen Tradition, die Zahlentheorie, die Schwierigkeit der Faktorisierung und die Algebra endlicher Körper mit der Berechnung verbindet. Sein Genie lag in der Anwendung, nicht der Erfindung dieser Mathematik. (Prägender Einfluss)

Wen er prägte

Eli Biham und die moderne Kryptoanalyse. Die mit seinem Studenten Biham entwickelte differentielle Kryptoanalyse wurde zu einem Standardwerkzeug, gegen das sich heute jeder ernsthafte Entwerfer von Blockchiffren verteidigen muss – sie veränderte, wie Chiffren gebaut werden, einschließlich der Entwurfskriterien für den Advanced Encryption Standard.⁴⁵

Das gesamte Public-Key-Ökosystem. RSA trug jahrzehntelange sichere Kommunikation, digitale Signaturen und Schlüsselaustausch. Jedes Mal, wenn ein Browser eine sichere Verbindung aufbaut oder ein Zertifikat prüft, steht er auf dem Public-Key-Fundament, das Shamir mitlegte.²

Zero-Knowledge- und Signaturverfahren. Die Fiat-Shamir-Heuristik ist ein Arbeitstier unter einer großen Bandbreite moderner digitaler Signaturen und Zero-Knowledge-Beweissysteme, darunter auch jene, die heute zentral für datenschutzwahrende und Blockchain-Kryptografie sind.⁶

Der rote Faden

Shamir ist der Sicherheits-Schlussstein dieser Serie – die Figur, die den Rest des Stapels vertrauenswürdig macht. Tim Berners-Lee baute ein Web, das für alle gedacht war, doch ein Web, auf dem man einkaufen, Bankgeschäfte erledigen und frei sprechen kann, hängt restlos von der Public-Key-Kryptografie ab – für seine TLS-Verbindungen und signierten Zertifikate – das heißt, es hängt von RSA und dem Fach ab, das Shamir mitbegründete. Thompson und Ritchie gaben uns die Systeme, auf denen wir laufen, und, in „Reflections on Trusting Trust”, die grundlegende Warnung, dass man nicht vertrauen kann, was man nicht gegnerisch geprüft hat – genau der Instinkt, auf dem Shamir eine Laufbahn aufbaute. Und Leslie Lamport gab verteilten Systemen die Disziplin, Korrektheit präzise zu definieren und sie zu beweisen, gegen byzantinische Gegner, die sich beliebig verhalten; Shamirs Secret Sharing ist genau dieser Impuls in kryptografischer Form, ein Primitiv mit einem Beweis statt einer Hoffnung. Wo Berners-Lee sagt das ist für alle und Thompson sagt vertraue nichts, das du nicht selbst gebaut hast, sagt Shamir: Ich baue dir etwas Sicheres, und dann verbringe ich mein Leben damit, es zu brechen – denn das ist der einzige Weg, auf dem wir beide wissen werden, dass es real ist. (Serienbrücke)

Was ich daraus mitnehme

Die Lehre, die ich von Shamir behalte, lautet vertraue nur dem, was Angriffe überlebt. Mein Instinkt ist, wie der der meisten Erbauer, funktionierenden Code als Beweis zu behandeln – die Tests bestehen, die Demo läuft, ausliefern. Die Kryptografie verbietet diesen Trost, denn ein gebrochenes und ein solides System sehen identisch aus, bis jemand sie angreift, und Shamirs Antwort ist, dieser Jemand zuerst zu sein. Er brach die Rucksack-Chiffren; er und Adleman brachen Rivests Kandidatenverfahren, bis RSA überlebte; er und Biham brachen DES schlimm genug, um aufzudecken, was Nachrichtendienste zwanzig Jahre lang verborgen hatten. Wenn ich heute etwas baue – einen Auth-Ablauf, eine Berechtigungsgrenze, eine Datenpipeline – versuche ich daher, den Hut des Angreifers aufzusetzen, bevor ein Angreifer es tut, anzunehmen, dass es einen Riss gibt, und auf die Jagd zu gehen, statt darauf zu warten, darauf hingewiesen zu werden. Das Vertrauen, das zählt, ist nicht „ich sehe nicht, wie das bricht”; es ist „ich habe hart versucht, es zu brechen, und konnte es nicht”.

Die zweite Lehre ist, dass die mächtigsten Mechanismen saubere, richtig gelesene Mathematik sind. Secret Sharing hat mich ein wenig umgehauen, als ich es zum ersten Mal verstand – es ist nur die Schulbuchtatsache, dass Punkte ein Polynom bestimmen, und doch ergibt es ein Geheimnis, das beweisbar, informationstheoretisch sicher ist. Shamir erfand keine schwerere Mathematik; er erkannte, dass Mathematik, die er bereits hatte, aus einem Winkel betrachtet genau ein Sicherheitsprimitiv war. Das veränderte, wie ich auf die Strukturen blicke, die bereits vor mir liegen. Der Hash, den ich für Lookups verwende, kann ein Commitment sein; die Redundanz, die ich für Zuverlässigkeit hinzufügte, kann ein Schwellenschema sein; die Einschränkung, die ich als Ärgernis behandelte, kann das Schloss sein. Die Kunst besteht nicht immer darin, etwas Neues zu erfinden – sie besteht darin, zu erkennen, dass das saubere Ding, das man bereits versteht, richtig gedreht der Mechanismus ist, den man brauchte.

FAQ

Wofür ist Adi Shamir bekannt?

Adi Shamir ist ein israelischer Kryptograf und Professor am Weizmann-Institut für Wissenschaften, am bekanntesten als das „S” in RSA – dem ersten praxistauglichen Public-Key-Kryptosystem, das er 1977 mit Ron Rivest und Leonard Adleman am MIT miterfand. Die drei teilten sich für diese Arbeit den ACM Turing Award 2002. Er erfand außerdem Shamirs Secret Sharing (1979), entdeckte mit Eli Biham die differentielle Kryptoanalyse mit und schuf neben vielen weiteren Beiträgen zur Kryptografie die Fiat-Shamir-Heuristik mit.¹²

Was ist Shamirs Secret Sharing?

Es ist eine 1979 von Shamir in „How to Share a Secret” veröffentlichte Methode, ein Geheimnis so unter n Personen aufzuteilen, dass beliebige k von ihnen es rekonstruieren können, beliebige k-1 aber nichts erfahren. Das Geheimnis ist als konstantes Glied eines zufälligen Polynoms vom Grad k-1 verborgen, und jede Person erhält einen Punkt auf dieser Kurve. Da k Punkte ein Polynom vom Grad (k-1) eindeutig bestimmen, stellen beliebige k Anteile das Geheimnis wieder her – während weniger als k es „völlig unbestimmt” lassen, was dem Schema informationstheoretische Sicherheit verleiht.³

Was ist das „S” in RSA, und wie funktioniert RSA?

Das „S” ist Shamir; RSA steht für Rivest, Shamir und Adleman. RSA ist ein Public-Key-Kryptosystem: Jeder Benutzer hat einen öffentlichen Schlüssel, mit dem jeder ihm Nachrichten verschlüsseln oder seine Signaturen prüfen kann, und einen privaten Schlüssel, den nur er besitzt. Seine Sicherheit beruht auf einer Falltür – der öffentliche Schlüssel ist aus dem Produkt zweier großer Primzahlen gebaut, und die Wiedergewinnung des privaten Schlüssels erfordert, dieses Produkt zurück in seine Primzahlen zu faktorisieren, was für hinreichend große Zahlen rechnerisch undurchführbar ist. RSA wurde 1978 in den Communications of the ACM veröffentlicht.²

Was ist die differentielle Kryptoanalyse?

Die differentielle Kryptoanalyse ist eine allgemeine Technik, die Ende der 1980er-Jahre von Eli Biham und Adi Shamir öffentlich entdeckt wurde, um Blockchiffren anzugreifen, indem man untersucht, wie sich Unterschiede zwischen Eingabepaaren auf Unterschiede in der Ausgabe fortpflanzen. Statistische Verzerrungen in dieser Fortpflanzung können Information über den geheimen Schlüssel preisgeben; Biham und Shamir nutzten sie, um eine theoretische Schwäche in DES zu finden. Später stellte sich heraus, dass IBM und die NSA die Technik seit Mitte der 1970er-Jahre gekannt und als geheim eingestuft hatten und DES insgeheim so entworfen hatten, dass es ihr widerstand.⁴⁵

Quellen