Схема Блекли, основанная на том, что система k линейно независимых сравнений от k неизвестных по простому модулю имеет ровно одно решение. Пусть секрет m разделяется между n абонентами. Тогда раздающий случайным образом выбирает числа x2*, x3*, … , xk* , где k – минимальный размер разрешенной группы. Для i-го (i=1,…,n) участника, где n – число долей секрета, раздающий выбирает случайные коэффициенты a1i, a2i, a3i, … , aki и посылает их iабоненту, после чего вычисляет bi=a1im + a2ix2*+…+akixk* mod p, где p – большое простое число (p>m). При этом раздающий должен следить за тем, чтобы любые k сравнений были линейно независимы. Собравшись вместе, k абонентов могут составить из своих cравнений систему a11x1+ a21x2+…+ak1xk≡b1(mod p) a12x1+ a22x2+…+ak2xk≡b2(mod p) …………………………. a1kx1+ a2kx2+…+akkxk≡bk(mod p),
решив которую, они отыщут точку, первая координата которой как раз и будет секретом m.
Идея на которой основана схема Шамира заключается в том, что для интерполяции многочлена степени k—1 требуется k точек. Если известно меньшее количество точек, то интерполяция будет невозможной. Пусть секрет m разделяется между n абонентами. Тогда раздающий выбирает случайным образом коэффициенты s1, s2, … , sk-1 , где k – минимальный размер разрешенной группы и составляет секретный полином S(x) = m+s1x+s2x2+ … +sk-1xk-1 mod p, где p – большое простое число (p>m). Каждому участнику посылается его доля секрета. Долей секрета i-го участника является пара чисел (i, S(i)). Собравшись вместе, участники могут восстановить коэффициенты многочлена, воспользовавшись интерполяционным многочленом Лагранжа:
S(x)=
и учтя, что m=S(0).
Схема разделения секрета на основе китайской теоремы об остатках выглядит следующим образом: пустьN – общий секрет. Выберем различные простые числа p1,p2,…,pn. Для чисел p1, p2,…, pn должно выполняться условие