Massey-Omura-Schema

Das Massey-Omura-Schema ist ein Kryptosystem, welches 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: 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 * d_T = 1 \mod (p-1)$.

Nun gilt für alle Nachrichten m < p:

$(m^{e_T})^{d_T} = m^{e_T * d_T} = m^{k*(p-1) + 1} = m \mod p$ aufgrund des Kleinen Satzes von Fermat.

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}\mod p$ und sendet die entstehende Zahl an B.

B exponenziert die erhaltene Nachricht mit e_B und antwortet $(m^{e_A})^{e_B}\mod p$.

A erzeugt $((m^{e_A})^{e_B})^{d_A}\mod p$, was nach dem Kleinen Satz von Fermat $m^{e_B}\mod 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 "geschützt" bzw. verschlüsselt.

B kann nun durch Exponentiation mit d_B die Nachricht m gewinnen: $(m^{e_B})^{d_B} = m\mod p$.

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

Sicherheitsbetrachtungen

Das Massay-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. Es ist jedoch anfällig für einen Man-in-the-middle-Angriff (Janusangriff). Durch die angenommene Schwere der Berechnung diskreter Logarithmen ist es 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.