Blom-Verfahren

Das Verfahren v​on Blom i​st ein kryptographisches Protokoll z​um Austausch symmetrischer Schlüssel m​it Hilfe e​iner vertrauenswürdigen Partei. Das Verfahren i​st wesentlich schneller a​ls ein asymmetrisches Verfahren. Somit läuft e​s auch a​uf leistungsschwachen Mikrochips. Es w​ird derzeit i​m HDCP-Protokoll (dem Kopierschutzverfahren d​es HDTV) eingesetzt.

Das Protokoll

Der Schlüsselaustausch erfordert eine vertrauenswürdige Partei (Trent) und ${\displaystyle n}$ Benutzer (neue Benutzer können auch nachträglich bequem hinzugefügt werden). Die vertrauenswürdige Partei gibt dabei jedem der ${\displaystyle n}$ Teilnehmer einen geheimen privaten Schlüssel sowie eine öffentliche Identifikationsnummer. Mit diesen Daten kann jeder Protokollteilnehmer mit jedem anderen Teilnehmer mit Hilfe einfacher Berechnungen (nur lineare Algebra) einen symmetrischen Schlüssel austauschen.

Wenn ${\displaystyle k}$ oder mehr kompromittierte Benutzer zusammenarbeiten sollten, können sie das Verfahren knacken (d. h., sie können den Master-Schlüssel der o. g. vertrauenswürdigen Partei berechnen). Weniger als ${\displaystyle k}$ Benutzer können (bei optimaler Parameterwahl) nichts ausrichten. Es handelt sich dabei um ein Schwellwertverfahren (englisch threshold scheme).

Alice u​nd Bob s​eien im Folgenden z​wei Benutzer.

Protokoll-Vorbereitung

Die vertrauenswürdige Partei Trent wählt als Master-Schlüssel eine geheime, zufällige und symmetrische ${\displaystyle k\times k}$-Matrix ${\displaystyle D}$ über ${\displaystyle GF(p)}$, wobei ${\displaystyle p}$ eine Primzahl sein muss. Diese Matrix muss zum Hinzufügen eines neuen Benutzers bekannt sein.

D sei zum Beispiel (${\displaystyle p=17}$): ${\displaystyle {\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}\mod 17}$

Hinzufügen eines neuen Teilnehmers

Ein neuer Benutzer Alice möchte der Schlüsselaustausch-Gruppe beitreten. Trent wählt für Alice eine öffentliche Benutzerkennung (am besten abhängig von ihrem Namen). Dies ist hier mathematisch gesehen ein Vektor ${\displaystyle I_{A}}$ mit ${\displaystyle k}$ Komponenten aus ${\displaystyle GF(p)}$.

Anschließend berechnet Trent den privaten Schlüssel von Alice: ${\displaystyle g_{A}=(D*I)}$ Der private Schlüssel kann nun von Alice verwendet werden, um einen gemeinsamen Schlüssel mit einem beliebigen anderen Gruppenteilnehmer zu berechnen.

${\displaystyle I_{A}={\begin{pmatrix}3\\10\\11\end{pmatrix}}}$, dann ist ${\displaystyle g_{A}={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}*{\begin{pmatrix}3\\10\\11\end{pmatrix}}={\begin{pmatrix}0\\0\\6\end{pmatrix}}\mod 17}$

${\displaystyle I_{B}={\begin{pmatrix}1\\3\\15\end{pmatrix}}}$, dann ist ${\displaystyle g_{B}={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}*{\begin{pmatrix}1\\3\\15\end{pmatrix}}={\begin{pmatrix}15\\16\\5\end{pmatrix}}\mod 17}$

Berechnung eines gemeinsamen Schlüssels zwischen Alice und Bob

Nun möchte Alice mit Bob kommunizieren. Alice kennt hierzu Bobs Identifikation (nämlich den Vektor ${\displaystyle I_{B}}$) und den eigenen privaten Schlüssel ${\displaystyle g_{A}}$.

Sie berechnet nun das Produkt daraus: ${\displaystyle k_{AB}=g_{A}^{T}*I_{B}}$ (${\displaystyle T}$ bedeutet transponiert)

Bob k​ann dasselbe machen (aber natürlich m​it seinem privaten Schlüssel u​nd Alices Identifikationsvektor).

Beispiele:

${\displaystyle k_{AB}={\begin{pmatrix}0\\0\\6\end{pmatrix}}^{T}*{\begin{pmatrix}1\\3\\15\end{pmatrix}}=0*1+0*3+6*15=5\mod 17}$

${\displaystyle k_{BA}={\begin{pmatrix}15\\16\\5\end{pmatrix}}^{T}*{\begin{pmatrix}3\\10\\11\end{pmatrix}}=15*3+16*10+5*11=5\mod 17}$

Bemerkungen

Damit erst ${\displaystyle k}$ oder mehr korrumpierte Benutzer das System knacken können, müssen ihre Benutzerkennungen (also die Vektoren ${\displaystyle I_{Benutzer}}$) in ${\displaystyle k}$ Gruppen linear unabhängig sein, d. h., jede Auswahl von ${\displaystyle k}$ Vektoren ist linear unabhängig. Dies kann dadurch erreicht werden, dass die durch alle Benutzervektoren aufgespannte Matrix einen MDS-Code darstellt (Maximum-Distance-Separable-Fehlerkorrekturcode). Die Benutzerkennungen sind dabei die Spalten dieser Matrix.

Quellen

• A. Menezes, P. van Oorschot, S. Vanstone: Handbook of applied cryptography, CRC Press, 1996
• R. Blom, "An optimal class of symmetric key generation systems" (PDF; 158 kB)
• IACR-Seite zur Publikation