RAČU N A L NI STVO
Deljenje skrivnosti
-i' •i'
Damjan Strnad
V življenju se pogosto zgodi, da je potrebno zaupno informacijo, imenujmo jo skrivnost, deliti med vec oseb na tak nacin, da vsak posameznik poseduje le del skrivnosti. Pri tem zahtevamo, da posamezni del skrivnosti ne zadošča za določitev celotne skrivnosti, pač pa je potrebno za njeno rekonstrukcijo zbrati vsaj določeno število delov, ne pa nujno vseh.
Na slednji nacin lahko tudi zagotovimo, da skrivnost ne bo nedosegljiva ali celo izgubljena, ce bo pogrešan katerikoli posamezni del. Praktičen primer potrebe po deljenju skrivnosti je npr. delitev varnostne kode za uporabo jedrskega orožja med skupino pooblašcenih oseb, od katerih jih mora svoj del kode prispevati vsaj polovica, da se varnostna koda lahko sestavi in orožje uporabi. Podobna primera uporabe sta delitev kombinacije trezorja ali gesla za dešifriranje zaupnih dokumentov. V dolocenih prak-ticnih primerih skrivnosti ne pozna nihce (npr. šifrirni kljuc se nakljucno tvori med samim postopkom delitve), v drugih pa je lahko vsebina skrivnosti znana vsem pooblašcenim osebam in gre pri njenem deljenju samo za zašcito pred nepooblašceno osebo, ki mora pridobiti vsaj k delov skrivnosti za njeno rekonstrukcijo. Tretja možnost je uporaba zaupne osebe, imenovane delivec, ki izvede deljenje skrivnosti in posreduje dele pooblašcenim osebam.
V tem prispevku bomo opisali Shamirjev algoritem, ki je relativno preprosta, a ucinkovita in dokaj varna metoda deljenja skrivnosti. Predpostavili bomo, da je skrivnost S predstavljena kot pozitivno celo število. V primeru, da je izvorna skrivnost besedilo, ga je potrebno najprej pretvoriti v številsko obliko. Daljša besedila je pri tem potrebno razde-
liti na krajše odseke, ki jih zatem obravnavamo kot locene skrivnosti.
Naj bo n število delov, na katere želimo skrivnost S razdeliti, k pa minimalno število delov, ki jih potrebujemo za rekonstrukcijo S. Takšni obliki delitve skrivnosti bomo rekli shema (k,n). Vrednosti k in n sta javno znani in odvisni od prakticnih potreb. Ce želimo, da so vsi udeleženci enako pomembni, potem bomo vsaki od pooblašcenih oseb dodelili natanko en del. Lahko pa dolocenim pooblašcencem priredimo višjo prioriteto s tem, da jim dodelimo ve-cje število delov skrivnosti od ostalih. Kombinacijo bancnega trezorja bi lahko, recimo, delili po shemi (3,4), nato pa predsedniku banke dodelili dva dela skrivnosti, vsakemu od njegovih dveh pomocnikov pa po enega. Za odprtje trezorja bi potem zadostovala prisotnost predsednika in kateregakoli od po-mocnikov, medtem ko niti predsednik sam niti oba pomocnika skupaj ne bi imeli dostopa do trezorja.
V nadaljevanju bomo opisali poenostavljeno razli-cico originalne Shamirjeve metode, ki ima dolocene pomanjkljivosti, a uporablja samo obicajno aritmetiko in je zato enostavnejša za razumevanje. Metoda za razdelitev skrivnosti uporabi polinom stopnje k -1, ki ga lahko zapišemo kot p(x) = ak-1xk-1 + ... + a2x2 + a1 x + a0. Koeficienti a1,... ,ak-1 so skrita naravna števila, ki jih nakljucno izbere algoritem deljenja skrivnosti, medtem ko vrednost konstantnega clena a0 postavimo na S. Shamirjeva metoda temelji na matematicnem dejstvu, da za enolicno dolocitev polinoma stopnje k - 1 potrebujemo vsaj k njegovih tock - za dolocitev premice potrebujemo dve tocki, za dolocitev parabole tri tocke in tako naprej. Ce kot dele skrivnosti izberemo tocke di = (xt,p(xt)), kjer je xt = i za i G {1, 2,...,n}, potem bo potrebnih vsaj k ali vec delov za enolicno dolocitev neznanih koeficientov polinoma in s tem izracun skrivnosti.
Opisani postopek deljenja skrivnosti lahko strnemo v naslednjem algoritmu:
26
PRESEK 45 (2017/2018) 5
RAČUNALNIŠ TVO
function Deli_Skrivnost(n, k, S)
ao = S
for i = 1, 2,...,k - 1 do
ai = randint () end for
D = {}
for i = 1, 2,...,n do
pi = 0
for j = 0,1,...,k - 1 do
pt = pt + aj • ij end for
D = D [j{(i, pi)} end for return D end function
Klic funkcije randi nt v zgornji kodi vraca naključno celo število. V praksi največjo vrednost koeficienta polinoma omejimo, da ne pride do prekoraci-tve obsega predstavitve celih števil. Vhodni podatki algoritma so javno znani vrednosti n in k ter vrednost skrivnosti S, rezultat algoritma pa je množica D delov skrivnosti, od katerih je vsak zapisan kot par (x, p(x)).
Ostane še vprašanje rekonstrukcije skrivnosti, ce je znanih katerihkoli njenih k delov (xj,p(xj)) za j G {1, 2,..., k}. Vrednost prostega clena polinoma, ki predstavlja iskano skrivnost, lahko izracunamo neposredno po naslednji enacbi:
S = p(0) = X p( j=1
x
k
)
u=1 U*j
xu
xu x i
{1, 2, 3,4, 5}, dobimo naslednje dele skrivnosti:
■ d1 = (1,96332) d2 = (2, 290850) d3 = (3, 593226) d4 = (4,1003460) d5 = (5,1521552)
Poskusimo sedaj rekonstruirati skrivnost iz delov d1, d3 in d4:
24
S = 96332 ■ - ■ -+
S 96332 2 - 1 4 - 1 +
14 + 290850 ■ --- ■ --- +
+1003460
1 - 2 4 - 2 12
1-4 ^ — 4
770656 1163400 2006920
+--- = 9672
3
2
6
Na podoben nacin z rekonstrukcijo iz delov d2, d3 in d5 dobimo:
^ 290850
3
5
593226
3 - 2 5 - 2 25
^ — 3 5-3
1521552
^ — 5 3-5
Pri naivni implementaciji zgornje enacbe lahko pri racunanju ulomkov prihaja do zaokrožitvenih napak, kar lahko omilimo tako, da produkta števcev in imenovalcev izracunavamo loceno ter deljenje izvedemo šele na koncu.
Oglejmo si sedaj zgled deljenja in rekonstrukcije skrivnosti S = 9672 po shemi (3, 5). Ker je k = 3, tvorimo nakljucen polinom druge stopnje. Denimo, da sta nakljucno izbrana koeficienta a1 = 32731 in a2 = 53929. Skupaj z a0 = 9672 nam to da naslednjo enacbo polinoma:
■ p(x) = 53929x2 + 32731x + 9672.
Ce enacbo polinoma ovrednotimo pri x G
4362750 5932260 9129312
H---- = 9672
3
2
6
Bralec se lahko preprica, da tudi vsaka druga trojica delov omogoca rekonstrukcijo zacetne skrivnosti.
Kot smo na zacetku omenili, je opisan postopek v resnici poenostavitev originalne Shamirjeve metode, ki za izracun delov skrivnosti uporablja modularno aritmetiko. Pomanjkljivost opisane metode je v tem, da lahko z vsakim pridobljenim delom skrivnosti dodatno omejimo nabor možnih vrednosti koeficientov polinoma. Z zadostnim številom pridobljenih delov lahko zato nepridipravu uspe zalogo vrednosti koeficientov skrciti do te meje, da lahko skrivnost iz-racuna z grobo metodo, tj. s preizkušanjem vseh
->
2
3
PRESEK 45 (2017/2018) 5
27
RAČUNALNIŠ TVO

možnih kombinacij. Dobra novica je, da lahko varnost metode povečamo s preprosto razširitvijo, pri kateri izberemo veliko praštevilo m, za katerega velja m > S in m > n. Vrednost m mora biti javno znana. Naključne vrednosti koeficientov polinoma potem omejimo na ai < m in dele skrivnosti določimo kot di = (xi,p(xi) mod m), kjer mod predstavlja ostanek pri celoštevilskem deljenju. Zaradi tega se nekoliko zaplete tudi postopek rekonstrukcije skrivnosti, vendar sedaj nepooblašcena oseba s prilastitvijo dodatnih delov skrivnosti, vse dokler jih skupaj nima vsaj k, ne pridobi dodatne informacije za rekonstrukcijo celotne skrivnosti.
Literatura
[1] A. Shamir, How to Share a Secret, Communications of the ACM, 1979.
_ XXX
Križne vsote
Rešitev s strani 8
•i' Vp
Barvni sudoku
Vp As
V 8 x 8 kvadratkov moraš vpisati začetna naravna števila od 1 do 8 tako, da bo v vsaki vrstici, v vsakem stolpcu in v kvadratkih iste barve (pravokotnikih 2 x 4) nastopalo vseh 8 števil.
			4				6
1				8			
	1						
7		4	6				3
	2					5	
			5	6	7		
			2				
8				1	3		
	4	»					
>3	1	2				10	11
10	3	7	6		7 6	2	4
	10	8	2		9	8	7
		10	4	5	1		
			■	8	7		
	o
	v
	O
	□
	O
	m
	Ž
	>
	a
	<
	a
	>
	m
	H
	>im
->	m
	a
2	9	3	1	7	5	4	8
7	8	5	4	2	1	3	9
1	2	7	6	5	3	8	4
8	5	4	3	1	9	2	7
3	1	8	2	6	4	7	5
4	7	9	5	8	2	1	3 1
5	4	2	8	3	7	9	
6	3	1	7	4	8	5	2
XXX
XXX
28
PRESEK 45 (2017/2018) 5	28