Материал: Раздел 3. Криптографические протоколы

3.6. Бросание жребия по телефону

Обычно в серьезных криптографических работах при описании новых идей приводится шутливая фабула. Так описание данной идеи начинается следующим образом. Предположим, Алиса и Боб недавно развелись и хотят с помощью жребия решить, кому достанется, например, их общая машина. Вопрос о принадлежности машины они хотят решить по телефону путем бросания жребия, при этом, естественно, они стремятся к тому, чтобы игра была честной.

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

Все целые числа делятся на два класса: четные и нечетные. Пусть нечетным числам соответствует решка, а четным орел. Так, числам 1,3,5,7,9 соответствует решка, а числам 2,4,6,8,10 соответствует орел. Алиса и Боб договариваются об использовании некоторой односторонней функции, например, модульном возведении в некоторую степень: x^k ≡ a mod P. Фактически они должны согласовать значения k и P. Затем Алиса выбирает некоторое целое число x, возводит его в степень k по модулю P и полученное a передает Бобу. Боб не знает, соответствует ли a четному или нечетному числу и наугад принимает решение, например, говорит, что Алиса взяла четное число y. Тогда Алиса передает Бобу число x, которое она использовала для вычисления а. Боб сравнивает x и y по модулю 2 и если остатки совпадают, то выиграл Боб и он забирает машину, а если не совпадают, то выиграла Алиса.

В этом эксперименте важно так подобрать параметры, чтобы из четных и нечетных значений x с примерно равной вероятностью получались четные и нечетные а.

Пример. Пусть взята функция: x³ ≡ a mod 53. Будем выбирать разные x и вычислять а. Результаты занесем в Таблицу.

Таблица. Эксперименты с бросанием жребия.

Из таблицы следует, что из 6 нечетных чисел четыре раза получены нечетные и 2 раза четные. Из 6 четных чисел 4 раза получены нечетные числа и 2 раза четные. Конечно, такой эксперимент не обеспечивает полную случайность, но при выборе больших значений P и k результаты могут оказаться более приемлемыми.

3.7. Обеспечение доступа к ресурсам

Для обеспечения доступа к различным ресурсам вычислительной сети (памяти, принтерам, программным средствам и т.п.) часто используется система паролей, примерно так же, как и при охране военных объектов. Запрос с которым обращается пользователь к системе может включать фамилию пользователя и его пароль. По совпадению этих данных система открывает доступ к конкретным ресурсам. Однако для некоторого увеличения секретности в базе данных могут храниться не сами пароли, а только их “слепки”. Слепки получают из паролей с помощью односторонних функций. Т.е. по слепкам пароль восстановить невозможно. В этом случае нарушитель, даже получив каким-то образом доступ к базе данных, не сможет получить список паролей. Однако пароль можно подслушать, подсмотреть или перехватить каким-то другим способом и в дальнейшем его можно использовать для получения доступа к ресурсам системы. Поэтому возможен следующий сценарий, устраняющий этот недостаток. Пользователь выбирает два ключа – шифрования e и расшифрования d. При обращении клиента на центральный пункт ему посылается случайный запрос x, зашифрованный открытым ключом e, клиент расшифровывает своим секретным ключом d и посылает x на центральный пункт, по которому судят, что обращается “свой”.

Пример.

Пусть клиент выбирает большое простое число P и находит два числа, такие, что ed ≡1 mod P-1. Например, P = 103, e = 19, d = 43, x = 28. Проверим, 19*43  1 mod 102. Центр посылает запрос 28¹⁹  26 mod 103. Клиент расшифровывает полученное сообщение: 26⁴³  28 mod 103 и посылает число 28 в центр. Центр понимает, что обратился “свой”.

Аналогичную процедуру можно обеспечить, используя булевы преобразования. Так, если на центре и у клиента имеется одна и та же булева функция F, то взяв случайную двоичную последовательность А₁ центр может зашифровать ее в виде В₁ = F(A₁), а отправить клиенту А₁. Клиент преобразует В₁ = F(A₁) и возвратит на центр В₁. Центр сравнит вычисленное значение В₁ и полученное от клиента. Если значения совпадут, то можно считать, что обратился свой. Чтобы обмануть центр перехватчик по А₁ и В₁ может попытаться найти F₁. Однако вряд ли попытка окажется успешной, так как нахождение F неоднозначно. F₁ вычисленное клиентом не совпадет с F, поэтому, если перехватчик на запрос центра А₂ возвратит ему F₁(A₂) = B₂, то значение В₂ не совпадет со значением В, вычисленным центром F (A₂) ≠ F₁ (A₂). Сложность алгоритма подбора имеет оценку О( ).

Пример.

Пусть центр выбрал набор запросов А₁ – А₇ и ответ B, который должен дать клиент:

A₁: 1010001100101110 – A32E

A₂: 0101110010110100 – 5CB4

A₃: 1101111000000101 – DE05

A₄: 1011001100011101 – B31D

-----------------------------------------

A₅: 1001000111110101 – 91F5

A₆: 1100011000010011 – C613

A₇: 1111000100100111 – F127

B: 1011101000111100 (BA3C)

Центр находит булеву функцию F [14], которая по любому значению А_i (i = 1,2,3,4,5,6,7) выработает В, т.е В = F (A_i).

F = !2*1*0*-1*!-4+3*!0*!-2+1*0*!-1*!-3*!-4+3*!0*-1*!-5+!4*3*2*!0+1*!0*!-1*!-2*-4+!4*!3*!1*0*!-2*!-4+!2*!1*!-1*!-2*!-4+!4*!2*1*!0*!-1+2*!1*0*-2+3*1*!0*-1+!4*2*!-1*!-3+1*0*!-1*-2+1*0*-3*-4+!3*2*0*!-1+!0*!-1*!-2*!-3+2*-1*-3+1*!0*-1*-2*!-3+!1*0*-3*!-4+4*!2*0*!-1+4*0*-3.

Здесь обозначено:

!а – инверсия (а),

+ - дизъюнкция (),

* - конъюнкция ().

Перехватчик, наблюдая некоторое время за конкретным клиентом, пытается найти эту булеву функцию, но получив только первые 4 (А₁ – А₄) запроса по ним и ответу В находит булеву функцию:

F₁ =!4*!-1*!-2*!-3+1*0*!-1+3*2*!0*-1+3*!0*!-2+2*0*-2+3*1*-1+2*-1*-3+

1*!0*-2*!-3+0*-3*!-4+4*0*-2+2*!0*!-1*!-3+4*0*-3

Тогда, отвечая на запросы А₅-А₇ с помощью функции F₁, перехватчик вырабатывает совершенно неверные ответы:

F₁(A₅) = BFFC

F₁(A₆) = 840E

F₁(A₇) = 917C

Центр легко определяет, что обратился чужой.

Приведенный пример реализован с использованием теории, изложенной в Приложении 3, и специальной программы нахождения булевой функции F по набору значений векторов A_i и B_i.

3.8. Разделение секрета

Рассмотрим случай, когда руководитель банка или какой-либо другой организации не полностью доверяет своим сотрудникам и хочет подстраховаться при использовании секретного ключа или передачи секретного сообщения. Он может разделить секретный ключ или секретное сообщение на фрагменты и эти фрагменты раздать нескольким сотрудникам так, чтобы при общем числе сотрудников n ключ мог бы ими быть составлен (или полностью восстановлено секретное сообщение) если соберутся вместе не менее h сотрудников. Такая схема называется пороговой схемой разделения секрета (n,h).

Наиболее просто поставленная задача решается при h = n, т.е. когда фрагменты раздаются n сотрудникам и требуются все n фрагментов ключа, чтобы собрать полный ключ или полностью восстановить секретное сообщение.

Пусть S – секретное сообщение (ключ, секрет). Выберем некоторое простое число P > S. Для n – 1 участника случайным образом будем генерировать фрагменты s_i, I = 1,2,3,…,n-1 в виде элементов простого поля F(p), а для n-го участника вычислим его долю в виде: s_i ≡ S – s₁ – s₂ - … - s_n-1 mod P.

В этом случае при сложении всех фрагментов ключа по модулю P получим значение S. Если же соберется меньшее число участников, они не смогут получить S.

Более того, пока число участников меньше n, сколько бы их не было, им также трудно подобрать ключ, как и одному участнику (имеющему только один фрагмент ключа).

Пример. Пусть S = 89. n = 5. Выберем P = 103. Включим генератор случайных целых чисел и для первых 4-= участников получим случайные фрагменты, например, 37, 94, 66, 21. Для пятого участника вычислим его фрагмент:

s₅ = 89 - 37 – 94 – 66 -21 ≡ 77 mod 103.

Если теперь сложить все фрагменты, то получим S: 37+94+66+21+77 ≡ 89 mod 103.

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

Рассмотрим случаи, когда h < n, т.е. когда общее число участников больше порогового значения, при котором восстанавливается секрет. Предложено большое число различных схем порогового разделения секрета. Рассмотрим некоторые из них.

3.4.1.Пороговая схема разделения секрета на основе интерполяционных полиномов Лагранжа [ 4 ](Схема была предложена Ади Шамиром )

Возьмем большое простое число P. Если требуется построить пороговую

схему (n,h)., где n – общее число участников, h - порог, то нужно сгенерировать коэффициенты полинома степени n-1. Долями являются значения полинома по модулю P в n точках, которые раздаются n участникам, причем любые h из них могут найти коэффициенты полинома. Одним из коэффициентов полинома может быть секретное сообщение.

Пример. Пусть требуется построить пороговую схему (7,4). Пусть P = 53 – выбранное простое число. Секретное сообщение пусть равно M = 48. Случайным образом получим коэффициенты полинома степени 3: F (X) =

a* X³ + b* X² + c* X + M. Например

F (X) = 2 X³ + 11 X² + 3 X + 48.

Найдем значения полинома в 7 произвольных точках по модулю P = 53:

1. F(1) = 2 + 11 + 3 + 48 ≡ 11 mod 53.

2. F(2) = 16 + 44 + 6 + 48 ≡ 8 mod 53.

3. F(3) = 54 + 99 + 9 + 48 ≡ 51 mod 53.

4. F(4) = 128 + 176 + 12 + 48 ≡ 46 mod 53

5. F(5) = 250 + 275 + 15 + 48 ≡ 5 mod 53

6. f(6) = 432 + 396 + 18 + 48 ≡ 46 mod 53

7. F(7) = 686 + 539 + 21 + 48 ≡ 22 mod 53.

Раздадим четырем участникам значения F (X_i) mod 53: Например,

F(2) = 8 mod 53 - получил второй участник,

F(4) = 46 mod 53 - получил четвертый участник,

F(6) = 46 mod 53 - получил шестой участник,

F(7) = 22 mod 53 - получил седьмой участник.

Вчетвером они решают систему уравнений третьей степени с четырьмя неизвестными:

F(2) = A*2³ + B*2²+C*2 +M ≡ 8 mod 53

F(4) = A*4³ + B*4²+C*4 +M ≡ 46 mod 53

F(6) = A*6³ + B*6²+C*6 +M ≡ 46 mod 53

F(7) = A*7³ + B*7²+C*7 +M ≡ 22 mod 53

После упрощения ( замены чисел на остатки по модулю), получаем:

A*8 + B*4 +C*2 +M ≡ 8 mod 53

A*11 + B*16 +C*4 +M ≡ 46 mod 53

A*4 + B*36+C*6 +M ≡ 46 mod 53

A*25 + B*49+C*7 +M ≡ 22 mod 53

Откуда находим a = 3, b = 11, c = 3, M = 48.

3.4.2.Пороговая схема разделения секрета на основе китайской теоремы об остатках [ 10 ] (Схема предложена Арто Саломаа).

Обозначим участников A₁,A₂,A₃,…,A_n. Каждому участнику сопоставим некоторое целое положительное число, так, чтобы все числа были взаимно простыми, т.е. участник A_i получает номер m_i, причем (m_i, m_j) = 1 при i ≠ j.Обозначим M – произведение всех чисел m_i, где i = 1,2,3,…,n, т.е. M = m₁*m₂*…*m_n. Обозначим M_i = M/m_i, т.е. M_i равно произведению всех чисел кроме m_i. Вычислим значения N_i из сравнения:

N_i* M_i ≡ 1 mod m_i.

Поскольку (M_i, m_i.) = 1, то решение всегда существует.

В соответствии с китайской теоремой об остатках: Если имеется n сравнений вида x ≡ a_i mod m_i, i = 1,2,3,…n; a_i – целые, то общее решение этих сравнений имеет вид:

Кроме того, это решение единственное, т.е. любое другое решение y удовлетворяет сравнению y ≡ x mod M.

Например, пусть m₁ = 11, m₂ = 12, m₃ = 13. Тогда M = 1716. M₁ = 156, M₂ = 143. M₃ = 132; Решая сравнения N_i* M_i ≡ 1 mod m_i., найдем N₁ = 6, N₂ = 11, N₃ = 7. Тогда общее решение x = 11*156*6 + 12*143*11 + 13*132*7 = 41184.

Легко проверяется, что

41184 ≡ 0 mod 11,

41184 ≡ 0 mod 12.

41184 ≡ 0 mod 13.

Пусть h – фиксированный порог, 1 ≤ h ≤ n. Обозначим через min (h) наименьшее из h произведений mi, а max (h -1) – наибольшее из h-1 произведений mi, Если выполнены условия:

min (h) – max (h-1) ≥ 3 max (h-1) (*)

и max (h-1) < c < min (h) (**),

то множество остатков {a₁,a₂,…a_h}, где a_i ≡ C mod m_i образует (n,h) пороговую схему для C [ 10 ]. Это означает, что если C – неизвестный секретный ключ, а a_i - фрагменты ключа, розданные n участникам, то любые h из участников могут восстановить значение c по его фрагментам, а любые h-1 участников сделать это не смогут (без полного перебора вариантов). При этом, чем больше разность в (*), тем труднее h-1 участникам подобрать секретный ключ по своим фрагментам.

Пример.

Пусть n = 5 и m₁ = 97, m₂ = 98, m₃ = 99, m₄ = 101, m₅ = 103.

Возьмем h = 3 и вычислим min (3) = (97*98*99) = 941094; max(2) = (101*103) = 10403/ Неравенство (*) примет вид: