Massey-Omura-Schema

Das Massey-Omura-Schema ist ein Kryptosystem, das zwei Parteien erlaubt, ohne die Existenz von öffentlichen Schlüsseln oder gemeinsamen geheimen Schlüsseln Nachrichten vertraulich auszutauschen. Es basiert auf der Schwierigkeit des diskreten Logarithmus.

Das Massey-Omura-Schema wurde 1983 von den Kryptologen James Massey und Jim Omura entwickelt.

Voraussetzungen

Voraussetzung des Massey-Omura-Schemas ist das gemeinsame Wissen aller Teilnehmer um eine große Primzahl $p$.

Zusätzlich erzeugt jeder Teilnehmer $T$ für die Kommunikation einen Schlüssel $e_{T}$ mit $e_{T}<p-1$ welcher relativ prim zu $p-1$ ist, es gilt also: $\operatorname {ggT} (e_{T},p-1)=1$.

Zu diesem wird (z. B. mittels des erweiterten euklidischen Algorithmus) die Zahl $d_{T}$ bestimmt. Sie ist das multiplikative Inverse von $e_{T}$ modulo $p-1$. Es gilt also: $e_{T}\cdot d_{T}=1{\bmod {(}}p-1)$.

Nun gilt für alle Nachrichten $m<p$:

$(m^{e_{T}})^{d_{T}}=m^{e_{T}\cdot d_{T}}=m^{k\cdot (p-1)+1}=m^{k\cdot (p-1)}\cdot m=m{\bmod {p}}$ aufgrund des Kleinen Satzes von Fermat, da $m^{k\cdot (p-1)}\equiv 1{\bmod {p}}$

Ablauf

Als Beispiel soll ein Teilnehmer A die vertrauliche Nachricht $m$ an Teilnehmer B übermitteln. Sie verfügen beide über $p$, darüber hinaus kennt jeder nur seinen eigenen Schlüssel $e_{A}$ und $d_{A}$ bzw. $e_{B}$ und $d_{B}$.

A bildet nun $m^{e_{A}}{\bmod {p}}$ und sendet die entstehende Zahl an B.

B potenziert die erhaltene Nachricht mit $e_{B}$ und antwortet $(m^{e_{A}})^{e_{B}}{\bmod {p}}$.

A erzeugt ${\big (}(m^{e_{A}})^{e_{B}}{\big )}^{d_{A}}{\bmod {p}}$, was nach dem Kleinen Satz von Fermat $m^{e_{B}}{\bmod {p}}$ entspricht und sendet dies zurück an B. Somit hat A die Wirkung der Exponentiation mit dem nur ihm bekannten $e_{A}$ auf $m$ „wieder aufgehoben“. Die Nachricht ist jedoch noch immer durch die Exponentiation mit $e_{B}$ verschlüsselt.

B kann nun durch Exponentiation mit $d_{B}$ die Nachricht $m$ gewinnen: $(m^{e_{B}})^{d_{B}}=m{\bmod {p}}$.

Aus allen ausgetauschten Nachrichten kann ohne Wissen um die Schlüssel der Teilnehmer nicht auf $m$ geschlossen werden.

Sicherheitsbetrachtungen

Das Massey-Omura-Schema ist sicher gegen passives Mithören von Nachrichten, d. h. Dritte können aus den ausgetauschten Nachrichten nicht auf den Originaltext zurückschließen. Ferner ist es durch die angenommene Schwere der Berechnung diskreter Logarithmen auch bei vorhandenem Wissen um den Originaltext $m$ beinahe unmöglich, die von einem Teilnehmer T gewählten Schlüssel $e_{T}$ und $d_{T}$ mit Hilfe einer mitgeschnittenen Nachricht $m^{e_{T}}$ zu erschließen.

Das Verfahren ist jedoch anfällig für einen Man-in-the-middle-Angriff (Janusangriff), indem man ähnlich vorgeht wie bei einem Man-in-the-Middle-Angriff auf das Diffie-Hellman-Verfahren.