skip to content

Разделение ключей - Схема Шамира

Ни один из компонентов Si от 1-го до (K-1)-го не несет никакой информации о ключе, поскольку они созданы случайно, а последний компонент не значит ничего без остальных (К-1) значений. В итоге получить значение KEY стороны могут, только собравшись вместе и выполнив операцию "исключающего ИЛИ" над всеми А" компонентами ключа.

Дальнейшие исследования проблемы разделения секрета породили схемы, в которых воссоздать ключ могут любые Миз А" субъектов схемы. Например, сообщения могут прочесть любые 3 из 5 членов совета директоров (кворум). Подобные схемы получили название пороговых, или кворумных (англ. threshold schemes). Две самые простые и популярные схемы были практически независимо предложены A.Shamir и G.R. Blakley.

Схема Шамира основана на том, что для определения всех коэффициентов произвольного полинома степени М-1 требуется как минимум М точек, в которых известно его значение. Знание М-1 и меньшего количества точек не дает никакой информации о полиноме, в то время как для любого набора из М пар значений (хi, уi) существует эффективный алгоритм вычисления всех его коэффициентов. Для пороговой схемы с К субъектами и кворумом из М участников выбирается полином степени М-1, причем значениях его коэффициентов каким-либо способом закладывается с KEY. Затем каждому из К субъектов выдается значение полинома в определенной точке в качестве компоненты ключа. Вычисления можно производить в вещественных числах (закладывая информацию в двоичное представление числа), однако чаще применяются целочисленные поля и коэффициентов и для значений многочлена. В обоих случаях информационная емкость и сложность вычислений как коэффициентов, так и значений должна соответствовать разрядности разделяемого ключа.