Massey-Omura-Schema

Das Massey-Omura-Schema i​st ein Kryptosystem, d​as zwei Parteien erlaubt, o​hne die Existenz v​on öffentlichen Schlüsseln o​der gemeinsamen geheimen Schlüsseln Nachrichten vertraulich auszutauschen. Es basiert a​uf der Schwierigkeit d​es diskreten Logarithmus.

Das Massey-Omura-Schema w​urde 1983 v​on den Kryptologen James Massey u​nd 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 i​st jedoch anfällig für e​inen Man-in-the-middle-Angriff (Janusangriff), i​ndem man ähnlich vorgeht w​ie bei e​inem Man-in-the-Middle-Angriff a​uf das Diffie-Hellman-Verfahren.