Geheimnisteilen

Eine algebraische Variante des Geheimnisteilens

Als nächstes betrachten wir eine auf der modularen Addition basierende Varianten des Geheimnisteilens. Dazu gehen wir jedoch von einem Beispiel aus, das auf der gewöhnlichen Addition basiert, damit später die Vorteile der Anwendung der modularen Addition gut in Abgrenzung zu diesem einführenden Beispiel herausgestellt werden können.

Einführendes Beispiel

Eine Zahl kleiner als 1000, die das Geheimnis G ist, wird in drei positive Summanden G1, G2 und G3 zerlegt. Hier ist wichtig anzumerken, dass jedem der später Beteiligten bekannt ist, dass das Geheimnis eine Zahl zwischen 0 bis 999 ist, es also in diesem Fall 1000 mögliche Geheimisse gibt. Beachte, dass die Wahl des Zahlenbereichs jedoch auch anders hätte ausfallen können.

Diese drei Summanden G1, G2 und G3 sind dann die Teilgeheimnisse und werden auf drei Geheimnisträger verteilt.

Konkret sei das Geheimnis Zahl G = 800 sowie die drei Teilgeheimnisse G1 = 330, G2 = 420 und G3 = 50. Wegen der Konstruktion erfüllen diese vier Zahlen die Gleichung.

G = G1+G2+G3 ⇔ 800 = 330+420+50

Werden die drei Teilgeheimnisse G1, G2 und G3 von einem Geheimnishüter auf drei Geheimnisträger verteilt, so können diese drei Geheimnisträger dann zusammen durch die Addition ihrer Teilgeheimnisse das Geheimnis G = 800 berechnen.

Tritt aber der Fall ein, dass einer der drei Geheimnisträger sein Teilgeheimnis nicht verrät, so kann die Berechnung nicht mehr stattfinden, jedoch sind die beiden verbleibenden Geheimnisträger in der Lage die Addition ihrer Teilgeheimnisse durchzuführen. Weil ihnen bekannt ist, dass das Geheimnis kleiner als 1000 ist, können sie somit den Zahlenbereich, in dem das Geheimnis G liegt, drastisch einschränken, und zwar von dem Zahlenbereich [0,...,999] auf den Zahlenbereich [750,...,999]. Damit haben die beiden zusammen bereits durch ihre beiden Teilgeheimnisse G1 und G2, auch ohne den dritten Geheimnisträger und dessen Teilgeheimnis G3, ein erheblich größeres Wissen über das Geheimnis G als einzeln.

Modulare Addition

Nun wird die Modulare Addition erläutert und anschließend wird diese in den Aufgaben auf das einführende Beispiel angewendet. Die Vorteile der Verwendung der modularen Addition beim Geheimnisteilen werden dir durch die Aufgaben schnell ersichtlich werden.

Sei eine natürliche Zahl m größer als oder gleich 1 fest gewählt. Diese Zahl wird der Modul der modularen Addition genannt. Sind zwei weitere natürliche Zahlen a und b gegeben, so ist die Addition a und b modulo m folgendermaßen definiert:

a ⊕ b := Rest der Division "a+b dividiert durch m"

Das Ergebnis der modoluaren Additin bezüglich des Moduls m liegt im Zahlenbereich [0,...,m-1].

Mit dieser modularen Addition verändert sich die obige Situation im Zahlenbereich [0,...999] grundlegend, wenn als Modul die Zahl 1000 gewählt wird.


Einige Beispiele zur modularen Addition:
X

Fehler melden

X

Suche