MTI

Wir stellen hier nun einige Erweiterungen von 5.1 vor, in denen statische und flüchtige Schlüsselpaare zum Einsatz kommen. Wir stellen zunächst zwei Vertreter aus den MTI-Familien vor (benannt nach T. Matsumoto, Y. Takashima, H. Imai):

Algorithmus 5.2 (MTI/A0)  

1. Erzeugung des statischen Schlüsselpaares

   A wählt eine Zufallszahl $s_{A},\, 1<s_{A}<r$ und berechnet $\sigma _{A}\leftarrow s_{A}\cdot h$;

   B wählt eine Zufallszahl $s_{B},\, 1<s_{B}<r$ und berechnet $\sigma _{B}\leftarrow s_{B}\cdot h$.

2. Erzeugung des flüchtigen Schlüsselpaares

   A wählt eine Zufallszahl $t_{A},\, 1<t_{A}<r$ und berechnet $\tau _{A}\leftarrow t_{A}\cdot h$;

   B wählt eine Zufallszahl $t_{B},\, 1<t_{B}<r$ und berechnet $\tau _{B}\leftarrow t_{B}\cdot h$;

3. Austausch

   A sendet $\tau _{A}$ an B;

   B sendet $\tau _{B}$ an A.

4. Berechnen des gemeinsamen Wertes

   A besorgt Bs authentischen öffentlichen Schlüssel $\sigma _{B}$;

   B besorgt As authentischen öffentlichen Schlüssel $\sigma _{A}$;

   A berechnet $\kappa \leftarrow s_{A}\cdot \tau _{B}+t_{A}\cdot \sigma _{B}=\left( s_{A}t_{B}+s_{B}t_{A}\right) \cdot h$;

   B berechnet $\kappa \leftarrow s_{B}\cdot \tau _{A}+t_{B}\cdot \sigma _{A}=\left( s_{A}t_{B}+s_{B}t_{A}\right) \cdot h$.

 

Algorithmus 5.3 (MTI/C0)  

1. Erzeugung des statischen Schlüsselpaares

   A wählt eine Zufallszahl $s_{A},\, 1<s_{A}<r$ und berechnet $\sigma _{A}\leftarrow s_{A}\cdot h$;

   B wählt eine Zufallszahl $s_{B},\, 1<s_{B}<r$ und berechnet $\sigma _{B}\leftarrow s_{B}\cdot h$.

2. Erzeugung des flüchtigen Schlüsselpaares

   A besorgt Bs authentischen öffentlichen Schlüssel $\sigma _{B}$;

   B besorgt As authentischen öffentlichen Schlüssel $\sigma _{A}$;

   A wählt eine Zufallszahl $t_{A},\, 1<t_{A}<r$ und berechnet $\tau _{A}\leftarrow t_{A}\cdot \sigma _{B}$;

   B wählt eine Zufallszahl $t_{B},\, 1<t_{B}<r$ und berechnet $\tau _{B}\leftarrow t_{B}\cdot \sigma _{A}$;

3. Austausch

   A sendet $\tau _{A}$ an B;

   B sendet $\tau _{B}$ an A.

4. Berechnen des gemeinsamen Wertes

   A berechnet $\kappa \leftarrow s_{A}^{-1}t_{A}\cdot \tau _{B}=\left( t_{A}t_{B}\right) \cdot h$;

   B berechnet $\kappa \leftarrow s_{B}^{-1}t_{B}\cdot \tau _{A}=\left( t_{A}t_{B}\right) \cdot h$.

Man kann sich leicht davon überzeugen daß die Protokolle 5.2 und 5.3 vom DLP in $H$ abhängt. Die Protokolle der MTI-Familie weisen eine Reihe von Schwächen auf; zur Illustration demonstrieren wir einen Angriff auf MTI/C0, wenn $r$ keine Primzahl ist.

Angenommen, es sei $r=pu,\, p$ eine Primzahl und $u>1$ ein Teiler von $r$.

1. E fängt As Nachricht $\tau _{A}$ ab und ersetzt sie durch $p\cdot \tau _{A}$;
2. E fängt Bs Nachricht $\tau _{B}$ ab und ersetzt sie durch $p\cdot \tau _{B}$;
3. A berechnet $\kappa \leftarrow s_{A}^{-1}t_{A}\cdot \left( p\cdot \tau _{B}\right)$;
4. B berechnet $\kappa \leftarrow s_{B}^{-1}t_{B}\cdot \left( p\cdot \tau _{A}\right)$.

$\kappa$ ist nun in der Untergruppe mit $u$ Elementen enthalten, die von $p\cdot h$ erzeugt wird; wenn $u$ klein genug ist, dann kann $\kappa$ effizient z.B. durch erschöpfende Suche gefunden werden. Dieser Angriff wird als ,,Angriff mit kleinen Untergruppen'' (small subgroup attack) bezeichnet. Es gibt jedoch auch Angriffe gegen MTI-Protokolle, die nicht einfach nur durch gute Wahl von $h$ verhindert werden können.