VIII Международная студенческая научная конференция Студенческий научный форум - 2016

Современные криптографические протоколы, охватывают многие сферы человеческой деятельности в сфере информационных технологий. Применение криптографических средств позволяет не только шифровать информацию, подписывать ее и передавать секретные ключи по открытому каналу, но и хранить секретную информацию распределенным образом так, чтобы ни один из держателей этой информации не мог ее восстановить самостоятельно. Данная статья посвящена разработке комплекса практических заданий, предназначенных для изучения протоколов разделения секрета, призванных решить проблему хранения информации так, чтобы те группы людей, которым позволено знать секрет, могли бы его восстановить, а те группы, которым секрет знать не позволено, восстановить его не смогли даже путем перебора. Цель первого практического задания - изучить теоретическую часть, касающуюся схем разделения секрета и научиться на практике применять протоколы разделения секрета.Основные задачи -смоделировать процесс разделения секретного значения между тремя, четырьмя или пятью пользователями с использованием схемы Блекли, схемы Шамира и Китайской теоремы об остатках.

Схема Блекли, основанная на том, что система k линейно независимых сравнений от k неизвестных по простому модулю имеет ровно одно решение. Пусть секрет m разделяется между n абонентами. Тогда раздающий случайным образом выбирает числа x₂^*, x₃^*, … , x_k^* , где k – минимальный размер разрешенной группы. Для i-го (i=1,…,n) участника, где n – число долей секрета, раздающий выбирает случайные коэффициенты a_1i, a_2i, a_3i, … , a_ki и посылает их iабоненту, после чего вычисляет b_i=a_1im + a_2ix₂^*+…+a_kix_k^* mod p, где p – большое простое число (p>m). При этом раздающий должен следить за тем, чтобы любые k сравнений были линейно независимы. Собравшись вместе, k абонентов могут составить из своих cравнений систему a₁₁x₁+ a₂₁x₂+…+a_k1x_k≡b₁(mod p) a₁₂x₁+ a₂₂x₂+…+a_k2x_k≡b₂(mod p) …………………………. a_1kx₁+ a_2kx₂+…+a_kkx_k≡b_k(mod p),

решив которую, они отыщут точку, первая координата которой как раз и будет секретом m.

Идея на которой основана схема Шамира заключается в том, что для интерполяции многочлена степени k—1 требуется k точек. Если известно меньшее количество точек, то интерполяция будет невозможной. Пусть секрет m разделяется между n абонентами. Тогда раздающий выбирает случайным образом коэффициенты s₁, s₂, … , s_k-1 , где k – минимальный размер разрешенной группы и составляет секретный полином S(x) = m+s₁x+s₂x²+ … +s_k-1x^k-1 mod p, где p – большое простое число (p>m). Каждому участнику посылается его доля секрета. Долей секрета i-го участника является пара чисел (i, S(i)). Собравшись вместе, участники могут восстановить коэффициенты многочлена, воспользовавшись интерполяционным многочленом Лагранжа:

S(x)=

и учтя, что m=S(0).

Схема разделения секрета на основе китайской теоремы об остатках выглядит следующим образом: пустьN – общий секрет. Выберем различные простые числа p₁,p₂,…,pn. Для чисел p₁, p₂,…, pn должно выполняться условие

Код для цитирования: Скопировать