Bloms upplägg

Bloms schema är ett symmetriskt tröskelnyckelutbytesprotokoll i kryptografi . Upplägget föreslogs av den svenske kryptografen Rolf Blom i en serie artiklar i början av 1980-talet.

En betrodd part ger varje deltagare en hemlig nyckel och en offentlig identifierare, vilket gör det möjligt för två deltagare att oberoende skapa en delad nyckel för kommunikation. Men om en angripare kan äventyra nycklarna för minst k användare, kan de bryta schemat och rekonstruera varje delad nyckel. Bloms plan är en form av tröskelhemlighetsdelning .

Bloms schema används för närvarande av kopieringsskyddsschemat HDCP (endast version 1.x) för att generera delade nycklar för högupplösta innehållskällor och mottagare, såsom HD DVD- spelare och högupplösta TV-apparater .

Protokollet

Nyckelutbytesprotokollet involverar en betrodd part (Trent) och en grupp av $\scriptstyle n$ användare. Låt Alice och Bob vara två användare av gruppen.

Protokollinställning

Trent väljer en slumpmässig och hemlig symmetrisk matris $\scriptstyle D_{k,k}$ över det finita fältet $\scriptstyle GF(p)$ , där p är ett primtal . $\scriptstyle D$ krävs när en ny användare ska läggas till i nyckeldelningsgruppen.

Till exempel:

$\displaystyle {\begin{aligned}k&=3\\p&=17\\D&={\begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}}\ \mathrm {mod} \ 17\end{aligned}}}$

Infogar en ny deltagare

Nya användare Alice och Bob vill gå med i nyckelutbytargruppen. Trent väljer offentliga identifierare för var och en av dem; dvs k-elementvektorer:

$I_{\mathrm {Alice} },I_{\mathrm {Bob} }\in GF^{k}(p)$ .

Till exempel:

$I_{\mathrm {Alice} }={\begin{pmatrix}1\\2\\3\end {pmatrix}},I_{\mathrm {Bob} }={\begin{pmatrix}5\\3\\1\end{pmatrix}}$

Trent beräknar sedan sina privata nycklar:

${\begin{aligned}g_{\mathrm {Alice} }&=DI_{\mathrm {Alice} }\\g_{\mathrm {Bob} }&=DI_{\mathrm {Bob} }\end{aligned}}$

Använd $D$ enligt beskrivningen ovan:

${\begin{aligned}g_{\mathrm {Alice} }&={\begin{pmatrix }1&6&2\\6&3&8\\2&8&2\end{pmatrix}}{\begin{pmatrix}1\\2\\3\end{pmatrix}}={\begin{pmatrix}19\\36\\24\end{ pmatrix}}\ \mathrm {mod} \ 17={\begin{pmatrix}2\\2\\7\end{pmatrix}}\ \\g_{\mathrm {Bob} }&={\begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}}{\begin{pmatrix}5\\3\\1\end{pmatrix}}={\begin{pmatrix}25\\47\\36\end{pmatrix }}\ \mathrm {mod} \ 17={\begin{pmatrix}8\\13\\2\end{pmatrix}}\ \end{aligned}}$

Var och en kommer att använda sin privata nyckel för att beräkna delade nycklar med andra deltagare i gruppen.

Beräknar en delad nyckel mellan Alice och Bob

Nu vill Alice och Bob kommunicera med varandra. Alice har Bobs identifierare $\scriptstyle I_{\mathrm {Bob} }$ och hennes privata nyckel $\scriptstyle g_{\mathrm {Alice} }$ .

Hon beräknar den delade nyckeln $\scriptstyle k_{\mathrm {Alice/Bob} }=g_{\mathrm {Alice} }^{T}I_{\mathrm {Bob} }$ , där $\scriptstyle T$ betecknar matristransponering . Bob gör detsamma med sin privata nyckel och hennes identifierare, vilket ger samma resultat:

$k_{\mathrm {Alice/Bob} }=k_{\mathrm {Alice/Bob } }^{T}=(g_{\mathrm {Alice} }^{T}I_{\mathrm {Bob} })^{T}=(I_{\mathrm {Alice} }^{T}D^{ T}I_{\mathrm {Bob} })^{T}=I_{\mathrm {Bob} }^{T}DI_{\mathrm {Alice} }=k_{\mathrm {Bob/Alice} }$

De kommer var och en att generera sin delade nyckel enligt följande:

${\begin{aligned}k_{\mathrm {Alice/ Bob} }&={\begin{pmatrix}2\\2\\7\end{pmatrix}}^{T}{\begin{pmatrix}5\\3\\1\end{pmatrix}}=2\ gånger 5+2\ gånger 3+7\ gånger 1=23\ \mathrm {mod} \ 17=6\\k_{\mathrm {Bob/Alice} }&={\begin{pmatrix}8\\13\\ 2\end{pmatrix}}^{T}{\begin{pmatrix}1\\2\\3\end{pmatrix}}=8\ gånger 1+13\ gånger 2+2\ gånger 3=40\ \mathrm {mod} \ 17=6\end{aligned}}$

Attackmotstånd

För att säkerställa att minst k nycklar måste komprometteras innan varje delad nyckel kan beräknas av en angripare, måste identifierare vara k-linjärt oberoende: alla uppsättningar av k slumpmässigt valda användaridentifierare måste vara linjärt oberoende. Annars kan en grupp illvilliga användare beräkna nyckeln för alla andra medlemmar vars identifierare är linjärt beroende av deras. För att säkerställa denna egenskap ska identifierarna företrädesvis väljas från en MDS-kodmatris (maximal distans separerbar felkorrigeringskodmatris). Raderna i MDS-matrisen skulle vara användarnas identifierare. En MDS-kodmatris kan väljas i praktiken med hjälp av kodmatrisen för Reed–Solomon felkorrigeringskod (denna felkorrigeringskod kräver endast lättbegriplig matematik och kan beräknas extremt snabbt).