Blom procedure

The Blom method is a cryptographic protocol for exchanging symmetric keys with the help of a trustworthy party. The process is much faster than an asymmetrical process . Thus, it also runs on low-performance microchips. It is currently used in the HDCP protocol (the copy protection method of HDTV ).

The protocol

The key exchange requires a trustworthy party (trent) and users (new users can also be easily added later). The trustworthy party gives each of the participants a secret private key and a public identification number. With this data, every protocol participant can exchange a symmetrical key with every other participant with the help of simple calculations (only linear algebra). ${\displaystyle n}$ ${\displaystyle n}$

If or more compromised users should work together, they can break the procedure (i.e. they can calculate the master key of the above-mentioned trusted party). Fewer than users can (with optimal parameter selection) achieve nothing. This is a threshold scheme . ${\displaystyle k}$ ${\displaystyle k}$

Let Alice and Bob be two users in the following.

Protocol preparation

The trusted party Trent selects a master key a secret, random and symmetric matrix over , with a prime number must be. This matrix must be known to add a new user. ${\displaystyle k\times k}$ ${\displaystyle D}$ ${\displaystyle GF(p)}$ ${\displaystyle p}$

For example, let D ( ): ${\displaystyle p=17}$ ${\displaystyle {\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}\mod 17}$

Adding a new participant

A new user Alice wants to join the key exchange group. Trent chooses a public user ID for Alice (preferably based on her name). From a mathematical point of view, this is a vector with components . ${\displaystyle I_{A}}$ ${\displaystyle k}$ ${\displaystyle GF(p)}$

Trent then calculates Alice's private key: Alice can now use the private key to calculate a shared key with any other group member. ${\displaystyle g_{A}=(D*I)}$

${\displaystyle I_{A}={\begin{pmatrix}3\\10\\11\end{pmatrix}}}$, then ${\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}}}$, then ${\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}$

Calculation of a common key between Alice and Bob

Now Alice wants to communicate with Bob. Alice knows Bob's identification (namely the vector ) and her own private key . ${\displaystyle I_{B}}$ ${\displaystyle g_{A}}$

She now calculates the product of this: ( means transposed ) ${\displaystyle k_{AB}=g_{A}^{T}*I_{B}}$ ${\displaystyle T}$

Bob can do the same (but with his private key and Alice's identification vector, of course).

Examples:

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

Remarks

So that first or more corrupted users can crack the system, their user IDs ( i.e. the vectors ) must be linearly independent in groups. that is, any choice of vectors is linearly independent . This can be achieved in that the matrix spanned by all user vectors represents an MDS code (Maximum Distance Separable Error Correction Code ). The user IDs are the columns of this matrix. ${\displaystyle k}$ ${\displaystyle I_{Benutzer}}$ ${\displaystyle k}$ ${\displaystyle k}$

swell

• 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 page for publication