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

Современные криптографические протоколы, охватывают многие сферы человеческой деятельности в сфере информационных технологий. Применение криптографических средств позволяет не только шифровать информацию, подписывать ее и передавать секретные ключи по открытому каналу, но и хранить секретную информацию распределенным образом так, чтобы ни один из держателей этой информации не мог ее восстановить самостоятельно, подписывать договор по каналу связи. Обеспечение безопасности электронных платежей и электронных сделок также является задачей криптографических протоколов. Данная статья посвящена разработке комплекса практических заданий, предназначенных для изучения задач электронной жеребьевки (подбрасывание монеты), привязки к биту, разделения секрета, покер по телефону, слепая подпись, электронная монета, управление ключами. Протокол подбрасывания монеты заключается в том, что два не доверяющих друг другу участника хотят бросить жребий с помощью монеты. Причем взаимодействие осуществляется посредством канала связи («по телефону»), поэтому участники не видят друг друга. Примером может служить бросание монеты с помощью однонаправленной функции. Если участник A и участник Б сумеют заранее договориться об использовании конкретной однонаправленной функции f(x), криптографический протокол бросания монеты будет выглядеть так: 1. А выбирает случайное число х и вычисляет значение y = f(x). 2. А посылает у Б. 3. Б пытается догадаться, является ли х четным или нечетным числом, и сообщает о своей догадке А. 4.A информирует Б о том, какое число х он выбрал. 5. Б проверяет, действительно ли f(x) = y, а также узнает, была ли верна его догадка. Здесь все зависит от свойств однонаправленной функции f. Если А вдруг сможет найти два числа х и х' такие, что х является четным, а х' — нечетным, и при этом y = f(x) = f(x'), то Б всегда будет в проигрыше.

Протоколы привязки к биту являются составной частью протоколов подбрасывания монеты. Такие протоколы используются тогда, когда одному из абонентов следует назначить секретный случайный бит, который до определенного момента не должен быть известен другим абонентам.

Подобно тому, как А и Б бросали монету, они могут сыграть в покер. Теперь А требуется сгенерировать, зашифровать и отослать Б 52 битовых последовательности — по числу карт в колоде. Среди них Б случайным образом выбирает 5 битовых последовательностей, шифрует их при помощи своего открытого ключа и посылает А. А расшифровывает полученные последовательности и шлет обратно Б, который тоже расшифровывает их. Затем Б выбирает еще 5 битовых последовательностей и посылает А, который опять их расшифровывает. В результате и у А, и у Б на руках окажется по 5 карт, которыми они и будут играть друг против друга. Если потребуется, дополнительные карты могут быть розданы обоим игрокам по той же схеме. По окончании игры А и Б открывают свои карты и обмениваются ключами, чтобы иметь возможность проверить, насколько честно они следовали правилам карточной игры [1]. Протоколы разделения секрета - требуется распределить информацию об этом секрете между абонентами так, чтобы t из них, собравшись вместе, могли восстановить секрет, а меньшее их количество – не могли. Применяется для безопасного распределенного хранения информации. Одна из схем из разделения секрета – схема Блэкли, основанная на том, что система k линейно независимых сравнений от k неизвестных по простому модулю имеет ровно одно решение. Параметрами схемы являются: p – большое простое число. p должно быть больше любого секрета, который предполагается разделять в этой схеме (p>m). n – число долей секрета. k – минимальный размер разрешенной группы.

Раздающий случайным образом выбирает числа x₂^*, x₃^*, … , x_k^*. Тем самым получена секретная точка Q = (m,x₂^*, x₃^*, … , x_k^*).

Для i-го (i=1,…,n) участника раздающий выбирает случайные равномерно распределенные на Zp коэффициенты a_1i, a_2i, a_3i, … , a_ki и вычисляет b_i=a_1im + a_2ix₂^*+…+a_kix_k^* mod p.

После чего раздающий D посылает абоненту P_i сравнение a_1ix₁+a_2ix₂+…+a_kix_k≡ b_i(mod p) (а, точнее, его коэффициенты) с неизвестными x₁, x₂, …, x_k. При этом раздающий должен следить за тем, чтобы любые 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)

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

Другой схемой является схема Шамира - идея, на которой основана данная схема, заключается в том, что для интерполяции многочлена степени k—1 требуется k точек. Если известно меньшее количество точек, то интерполяция будет невозможной.

p – большое простое число. p должно быть больше любого секрета, который предполагается разделять в этой схеме (p>m).

n – число долей секрета.

k – минимальный размер разрешенной группы.

Раздающий выбирает коэффициенты s₁, s₂, … , s_k-1 случайным образом и составляет секретный полином S(x) = m+s₁x+s₂x²+ … +s_k-1x^k-1 mod p

Каждому участнику посылается его доля секрета. Долей секрета i-го участника является пара чисел (i, S(i)).

Пусть свои доли секрета объединяют k участников с номерами i₁, i₂, … , i_k. Такая группа участников располагает долями (i₁,S(i₁)), (i₂,S(i₂)), …, (i_k,S(i_k)). Каждая такая доля является точкой многочлена S(x), который имеет степень k—1. Поэтому, обладая k точками этого многочлена, участники могут восстановить коэффициенты многочлена, либо решив систему линейных сравнений относительно неизвестных коэффициентов m, s₁, s₂, … , s_k-1, либо воспользовавшись интерполяционным многочленом Лагранжа:

S(x)=

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

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

Часть секрета, выдаваемая i-му участнику схемы, есть число x_i, вычисляемое как x_i≡N(mod p_i). Заметим, что числа p₁, p₂,…, pn должны быть такими, чтобы произведение любых k из них было больше, чем N. А это достигается, когда для всех i выполняется p_i>. Для того, чтобы k–1 участников не смогли восстановить секрет без k-го участника, необходимо, чтобы p_i

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