35.Задача разделения секрета.

Схема разделения секрета позволяет раздать информацию о сообщении S мн-ву участников таким образом, чтобы заранее заданные разрешённые подмн-ва участников могли однозначно восстановить сообщение S, а неразрешённые не имели такой возможности.

Защищаемое сообщение S – секрет, а мн-во S всех возможных секретов – мн-во секретов.

Сообщение, содержащее частичную информацию о секрете и созданное для индивидуального участника – доля этого участника.

Простейший случай: имеется n участников, любые t из них, собравшись вместе, могут открыть секрет , (t,n)-пороговая система доступа

Пусть t=n.

1) Кодируем секрет как большое натуральное число S. 2) Выбираем n-1 большое случайное число r₁,…,r_n-1 и выдаем r_i в качестве доли i-го участника. 3) В качестве доли n-го участника полагаем r_n = s-r₁-…-r_n-1.

Пусть t<n, тогда – схема Шамира.

Идея: для любых k точек (x₁,y₁),…,(x_k,y_k)ÎR² существует единственный полином q(x)

степени k-1 такой, что q(x_i) = y_i для всех i=1,…,k.1) Кодируем секрет как большое натуральное число S2) Пусть f(x)=a_k-1x^k-1+…+a₁x + a₀, где a₀ = s, a₁,…,a_k-1-случайные числа из интервала (0,p), где p – простое число, существенно большее, чем n и S.3) i-му участнику в качестве его доли выдается пара (x_i,y_i).