Das allgemeine Problem ist folgendes: Wir haben ein Geheimnis (hier G), welches in eine bestimmte Anzahl an Teilen zerteilt werden und an verschiedene Personen verteilt werden soll. Dabei achten wir auf folgendes:

• Nur wenn alle Personen zusammenkommen und ihre Teilgeheimnisse kombinieren, können sie das Geheimnis G vollständig wiederherstellen
• Wenn aber nur ein paar Personen zusammenkommen, sollen sie G nicht vollständig wiederherstellen können. Sie sollen so wenig Informationen wie möglich über G erhalten.

Ein weiteres Einsatzszenario, neben dem der Schatzkarte, ist z.B. ein brisantes Dokument, wessen Veröffentlichung nur mit der Einstimmung von n Personen geschehen darf. In diesem Fall könnte man das Dokument einfach in einen Safe schließen und diesen mit n Schlössern sichern, für jede Person eines. Um die Mehrkosten durch die vielen Schlösser zu vermeiden, kann man auch ein Zahlenschloss verwenden, dessen Kombination in n Teile aufgeteilt wird.

Eine einfache Methode zum Teilen von Geheimnissen

Nur wie teilt man das Geheimnis (in diesem Fall die Kombination für das Schloss)? In unserem Beispiel ist die Geheimzahl für das Schloss etwa

1

G = 19931 99231 12345 98465 35794 39645 36987 15348 76453 58736

Jetzt kommen wir dem ganzen schon etwas näher. Wir wählen 10 (Anzahl der Personen) zufällige Zahlen, die größer als Null sind und deren Summe G ergibt. Das will ich euch mal an einem kleinen Beispiel zeigen: Unser Geheminis G ist eine ganze Zahl, die Teilgeheimnisse sind auch ganze Zahlen zwischen 1 und 50, und wir haben dieses mal nur 4 Personen, unter denen das Geheimnis aufgeteilt wird. Das Geheimnis G ist also in diesem Beispiel maximal 200. Wir wählen hier die Zahl 123 als G. In diesem Fall sind die Teilgeheimnisse zum Beispiel 15, 45, 30 und 33, denn 15+45+30+33=123. Nur ist dieses Verfahren auch sicher? Wir werden schnell feststellen: Nein. Denn wenn sich die ersten 3 Personen zusammentun, wissen sie: G liegt zwischen 15+45+30=90 und 200. Sie haben also die Möglichkeiten für G fast halbiert. Mit einem kleinen Trick können wir aber das Verfahren sicher machen, indem wir Modulo (Division mit Rest) verwenden.

Jetzt sieht das Verfahren zum Teilen folgendermassen aus: Das Geheimnis G ist eine Zahl zwischen 0 und N. In unserem Beispiel ist N=10⁵⁰, also eine 1 mit 50 Nullen. Wir haben wieder n = 10 Personen (wobei die Anzahl der Personen hier relativ egal ist). Jetzt gehen wir in 2 Schritten vor:

• Als erstes wählen wir n-1 zufällige Zahlen zwischen 0 und N-1. Wir nennen diese Zahlen t₁, t₂, ......., t₉. Dies sind die Teilgeheimnisse der ersten 9 Personen.
• Um das 10te Teilgeheimnis t₁₀ zu bestimmen, bilden wir zunächst t₁ + ... + t₉ und dividieren diese Summe durch N. Von dieser Division nehmen wir den Rest R und bilden die Differenz G - R. Falls G - R positiv ist, ist dies unser gesuchtes t₁₀. Falls G - R negativ ist, ist t₁₀ gleich G - R + N. Dadurch gilt, dass t₁ + t₂ + ..... + t₁₀ bei Division durch N den Rest G ergibt.

Wir wollen uns das ganze mal anhand eines einfachen Beispieles angucken: Als Werte nehmen wir N=68 und m=4. Das Geheimnis ist G=36.

• Als erstes wählen wir die ersten 3 Teilgeheimnisse. In diesem Beispiel 19, 46 und 30.
• Um das letzte Teilgeheimnis zu bestimmen, berechnen wir als erstes die Summe der ersten 3 Teilergebnise, also 19 + 46 + 30 = 95. Jetzt addieren wir zu den 95 noch 9 hinzu und erhalten 104. Bei Division mit Rest von 104 durch 68 erhalten wir 36, das Geheimnis. Unser viertes Teilgeheimnis ist daher 9.

Umsetzung in Python

Eine Python-Implementierung könnte etwa wie folgt aussehen (mit unseren Beispielwerten unten im Beispiel):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#!/usr/bin/env python
import random

def get_partly_secrets(G, N, m):
	if G>N:
		raise ValueError, "G be smaller than N!"
	secrets = [random.randrange(0,N-1) for i in range(m)]
	total = sum(secrets)
	R = total%N
	diff = G-R
	if diff>0:
		secrets.append(diff)
	else:
		secrets.append(G-R+N)
	return secrets

def get_secret(secrets, N):
	secret = sum(secrets)%N
	return secret

if __name__ == '__main__':
	G = 36
	N = 68
	m = 4
	secrets = get_partly_secrets(G, N, m)
	print secrets
	print get_secret(secrets, N)