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 ${\displaystyle p}$.

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

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

Nun gilt für alle Nachrichten ${\displaystyle m<p}$:

${\displaystyle (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 ${\displaystyle m^{k\cdot (p-1)}\equiv 1{\bmod {p}}}$

Ablauf

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

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

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

A erzeugt ${\displaystyle {\big (}(m^{e_{A}})^{e_{B}}{\big )}^{d_{A}}{\bmod {p}}}$, was nach dem Kleinen Satz von Fermat ${\displaystyle 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 ${\displaystyle e_{A}}$ auf ${\displaystyle m}$ „wieder aufgehoben“. Die Nachricht ist jedoch noch immer durch die Exponentiation mit ${\displaystyle e_{B}}$ verschlüsselt.

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

Aus allen ausgetauschten Nachrichten kann ohne Wissen um die Schlüssel der Teilnehmer nicht auf ${\displaystyle 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 ${\displaystyle m}$ beinahe unmöglich, die von einem Teilnehmer T gewählten Schlüssel ${\displaystyle e_{T}}$ und ${\displaystyle d_{T}}$ mit Hilfe einer mitgeschnittenen Nachricht ${\displaystyle 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.