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 G₁, G₂ und G₃ zerlegt. Hier ist wichtig anzumerken, dass jede der später Beteiligten bekannt ist, dass das Geheimnis eine Zahl zwischen 0 bis 999 ist, es also in diesem Fall 1000 mögliche Geheimnisse gibt. Beachte, dass die Wahl des Zahlenbereichs jedoch auch anders hätte ausfallen können.

Diese drei Summanden G₁, G₂ und G₃ sind dann die Teilgeheimnisse und werden auf drei Geheimnisträger verteilt.

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

G = G₁+G₂+G₃ ⇔ 800 = 330+420+50

Werden die drei Teilgeheimnisse G₁, G₂ und G₃ von einer Geheimnishüter:in auf drei Geheimnisträger:innen verteilt, so können diese drei Geheimnisträger:innen dann zusammen durch die Addition ihrer Teilgeheimnisse das Geheimnis G = 800 berechnen.

Tritt aber der Fall ein, dass eine der drei Geheimnisträger:innen ihr Teilgeheimnis nicht verrät, so kann die Berechnung nicht mehr stattfinden, jedoch sind die beiden verbleibenden Geheimnisträger:innen 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 G₁ und G₂, auch ohne den dritten Geheimnisträger und dessen Teilgeheimnis G₃, 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.

Das Ergebnis der modularen Addition 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:

• Sei als Modul die Zahl 27 gewählt, dann wird modular wie folgt gerechnet:
  34 + 12 = 46
  46 : 27 = 1 mit dem Rest 19
  Also gilt: a ⊕ b = 19
  Oder:
  67 + 31 = 98
  98 : 27 = 3 mit dem Rest 17
  Also gilt: a ⊕ b = 17
• Nun sei als Modul die Zahl 16 gewählt, dann wird modular wie folgt gerechnet:
  34 + 12 = 46
  46 : 16 = 2 mit dem Rest 14
  Also gilt: a ⊕ b = 14
  Oder:
  67 + 31 = 98
  98 : 16 = 6 mit dem Rest 2
  Also gilt: a ⊕ b = 2