Vertrauen ist gut, Kontrolle ist besser. Das muss sich der Mathematiker Adi Shamir gedacht haben, als er das nach ihm benannte »Secret Sharing«-Verfahren entwickelte. Um zu verstehen, was dahintersteckt, hilft folgendes Rätsel: Angenommen, eine ältere Frau möchte den Inhalt ihres mit einem Zahlenschloss gesicherten Tresors an ihre fünf Söhne vererben. Sie misstraut aber jedem einzelnen von ihnen. Würde sie einem Sohn den Zahlencode verraten, so ihre Befürchtung, würde er sich mit dem Inhalt aus dem Staub machen. Deshalb möchte sie jedem Sohn einen Hinweis geben, damit die fünf den Safe nur gemeinsam öffnen können. Wie könnte die Frau vorgehen?

Für einige mag die Aufgabe einfach erscheinen. Wenn das Zahlenschloss beispielsweise einen fünfstelligen Code erfordert, könnte sie jedem Sohn eine Zahl mitteilen, so dass sie das Schloss gemeinsam öffnen können. Wenn sich jedoch drei Söhne zusammentun, können sie ihre Informationen zusammentragen und ihre beiden anderen Brüder übergehen. Da den drei Verbündeten nur zwei Zahlen zum gesamten Code fehlen, können sie die Zahlenkombinationen des Tresors schnell durchprobieren und so an den begehrten Inhalt gelangen.

Die Frau sucht daher nach einer Möglichkeit, Informationen an ihre Söhne zu verteilen, die sich nur dann verwerten lassen, wenn alle fünf beisammen sind. Wenn sich zwei, drei oder vier der fünf Jungs zusammentun, muss der gemeinsame Informationsgehalt praktisch nutzlos sein. So stellt sich die Aufgabe deutlich komplexer dar. Der Mathematiker Adi Shamir ließ sich davon im Jahr 1979 nicht entmutigen. Mit gutem Grund: Zwei Jahre zuvor hatte er zusammen mit Ron Rivest und Leonard Adleman den so genannten RSA-Algorithmus entwickelt, die erste asymmetrische Verschlüsselung, die teilweise noch heute benutzt wird.

Shamir’s Secret Sharing in Aktion

Um das Shamir-Secret-Sharing-Verfahren nachzuvollziehen, hilft es, ein konkretes Zahlenbeispiel zu betrachten. Angenommen, der geheime Code der Frau wäre 43953. Und der Einfachheit halber nehmen wir zunächst an, sie hätte nur zwei Söhne – wir arbeiten uns dann später zu der Situation mit fünf Söhnen vor. Würde die Frau einem Sohn die beiden Zahlen 439 und dem anderen 953 anvertrauen, dann hätte sie den zwei Jungs gleichviel Information vermittelt. Nun könnten die Söhne aber wie oben erklärt jeweils versuchen, die fehlenden zwei Ziffern zu erraten. Sie müssten jeweils bloß höchstens 100 Kombinationen ausprobieren und könnten den Tresor öffnen. Shamir hat sich deshalb eine andere Lösung überlegt.

Am besten wäre es, wenn beide Söhne jeweils eine Information bekämen, die auf den ersten Blick nichts mit der Lösung zu tun hat. Doch wenn man beide Informationen zusammenfügt, sollte sich daraus eindeutig die Zahlenkombination 43953 ableiten lassen. Und es gibt tatsächlich einen eleganten und einfachen Weg, dies zu tun – mit Hilfe einer Geradengleichung.

Jede Gerade wird durch zwei Punkte eindeutig festgelegt. Shamir erkannte, dass man die Geheimzahl in einer Gerade codieren kann: Etwa als Höhe, bei der sie die y-Achse schneidet. Wenn man den zwei Söhnen die Koordinaten von jeweils einem Punkt auf der Gerade mitteilt, können sie nur gemeinsam die Zahl 43953 ermitteln. Einer der Söhne kann mit einem einzelnen Punkt allein nichts anfangen: Es gibt unendlich viele Geraden, die durch einen einzelnen Punkt verlaufen.

Die Frau könnte zum Beispiel die Geradengleichung y = 5x + 43953 wählen und dem ältesten Sohn den Punkt P₁ mit den Koordinaten (33503, 211468) und dem anderen P₂ = (85395, 470928) mitteilen. Selbst wenn die beiden Söhne schlecht in Mathe sind, können sie einfach die zwei Punkte in der Ebene markieren, sie mit einem Lineal verbinden und dann ablesen, an welcher Stelle die Gerade die y-Achse schneidet.

Für zwei Söhne ist das Problem also gelöst. Wenn die Frau drei Söhne hat, kann man ähnlich vorgehen. In diesem Fall wählt man allerdings keine Gerade, sondern eine Parabel, um den Code zu verstecken. Die Frau kann also zum Beispiel die quadratische Funktion y = 5x² + 10x + 43953 wählen und jedem ihrer Söhne je einen Punkt, der auf der Parabel liegt, mitteilen. Wieder entspricht der Schnittpunkt mit der y-Achse der begehrten Lösung 43953. Auch wenn sich zwei der Söhne gegen den dritten verschwören, ist ihnen nicht wirklich geholfen: Durch zwei Punkte können immer noch unendlich viele Parabeln verlaufen, so dass sie auf den dritten Bruder angewiesen sind, um den Schnittpunkt mit der y-Achse und damit den Code zum Safe zu ermitteln.

Das Prinzip lässt sich für beliebig viele Parteien verallgemeinern: Eine Frau mit vier Söhnen kann eine Gleichung der Art y = a·x³ + b·x² + c·x + 43953 (wegen der drei als höchsten Exponenten spricht man von einer Polynomgleichung dritten Grades) verwenden, eine mit fünf Söhnen nutzt entsprechend eine Polynomialgleichung vierten Grades (etwa y = a·x⁴ + b·x³ + c·x² + d·x + 43953) und so weiter. Dem Prinzip liegt die so genannte Polynominterpolation zu Grunde: Man braucht im Allgemeinen n+1 Punkte, um ein Polynom n-ten Grades eindeutig zu bestimmen.

Diese Methode lässt sich auch nutzen, wenn die Frau ihren Söhnen paarweise einen Zugang ermöglichen möchte. In diesem Fall setzt sie darauf, dass sich die Söhne gegenseitig so kontrollieren, dass es genügt, wenn zwei von fünf Personen anwesend sind, um den Tresor zu öffnen. Dafür könnte die Frau wieder eine Gerade als Basis wählen und darauf fünf zufällig ausgewählte Punkte markieren. Indem sie jedem Sohn einen Punkt mitteilt, können je zwei von ihnen den Code ermitteln – unabhängig davon, welche zwei der Söhne sich treffen.

Aber ganz so einfach ist es dann leider doch nicht. Dafür kann man zum Szenario mit den fünf Söhnen zurückkehren. Wenn sich vier von ihnen gegen einen Bruder verschwören, können sie die vier Punkte nutzen, um die Gleichung vierten Grades so weit wie möglich zu lösen. Natürlich können sie daraus nicht direkt den Code ablesen. Am Ende bleibt eine Gleichung mit zwei Unbekannten übrig: ein Parameter a und der Code c (der in unserem Beispiel 43953 entspricht, aber das wissen die Söhne nicht). Allerdings wissen die vier Jungs, dass c eine ganze Zahl sein muss. Und wenn die Frau ihnen zum Beispiel stets ganzzahlige Koordinaten für die Punkte auf der Kurve übermittelt hat, dann könnten sie davon ausgehen, dass wahrscheinlich auch a einen ganzzahligen Wert hat. Das schränkt den Raum der Möglichkeiten erheblich ein. Die Brüder könnten ein Computerprogramm nutzen, um verschiedene Lösungen durchzuprobieren – und eventuell damit in nicht allzu langer Zeit den richtigen Code zu ermitteln.

Ausflug in einen anderen Zahlenraum

Um einen solchen Fall zu vermeiden, hatte Shamir einen weiteren Trick auf Lager: Statt mit den üblichen reellen Zahlen zu rechnen, beschränkte er sich auf einen kleineren Zahlenraum: einen endlichen Körper. Dabei handelt es sich um ein Zahlensystem, in dem sich die vier Grundrechenarten (Addition, Multiplikation, Subtraktion und Division) wie gewohnt anwenden lassen. Statt unendlich vieler Zahlen enthält dieser Zahlenraum aber nur endlich viele.

Auch wenn es ungewohnt klingt, benutzen wir diesen endlichen Zahlenraum täglich – nämlich immer dann, wenn wir auf die Uhr schauen. Betrachtet man nur die Stunden, umfasst der Zahlenraum 24 (oder 12) Zahlen. Das hält uns nicht davon ab, in diesem beschränkten Raum zu rechnen: Wenn es 23 Uhr ist und jemand sagt, dass die Bäckerei in sieben Stunden öffnet, dann ist klar, dass damit sechs Uhr gemeint ist.

Für Shamir’s Secret Sharing wird ebenfalls ein eingeschränkter Zahlenraum gewählt, allerdings nutzt man in der Regel als obere Grenze nicht eine kleine Zahl wie 24 oder 12, sondern eine große Primzahl. Wenn man den Zahlenraum so wählt, entspricht der Graph eines Polynoms nicht mehr einer stetigen Kurve, sondern wirr verteilten Punkten in der Ebene.

Indem die Frau die Berechnungen auf einen solchen Zahlenraum beschränkt, ist es praktisch unmöglich, dass sich die Brüder gegeneinander verschwören – zumindest bringt es ihnen nichts. Um den richtigen Zahlencode herauszufinden, müssen sie zwangsweise zusammenarbeiten.