Передача аутентичного информационного сообщения по каналу связи

Пегги и Виктор повторяют этот протокол t раз, пока Виктор не убедится, что Пегги знает s₁, s₂, … s_k.

Вероятность, что Пегги удастся обмануть Виктор t раз, равна 1/2^kt. Авторы рекомендуют использовать вероятность мошенничества 1/2²⁰ и предлагают значения к = 5 и t = 4. Если у вас склонность к мании преследования, увеличьте эти значения.

Пример

Взглянем на работу этого  протокола небольших числах. Если п = 35 (два простых числа - 5 и 7), то возможными квадратичными остатками являются:

1: х² ≡ 1 (mod 35) имеет решения: х = 1,6, 29, 34.

 4: х² ≡ 4 (mod 35) имеет решения: х = 2, 12, 23, 33.

9: х² = 9 (mod 35) имеет решения:    х = 3, 17, 18, 32.

11: х² = 11 (mod 35) имеет решения: х = 9, 16, 19, 26.

14: х² = 14 (mod 35) имеет решения: х = 1, 28.

15: х² = 15 (mod 35) имеет решения: х = 15, 20.

16: х² = 16 (mod 35) имеет решения: х = 4, 11, 24, 31.

21: х² = 21 (mod 35) имеет решения: х = 14, 21.

25: х² = 25 (mod 35) имеет решения: х = 5, 30.

29: х² = 29 (mod 35) имеет решения: х = 8, 13, 22, 27.

30: х² = 30 (mod 35) имеет решения: х = 10, 25.

Обратными значениями (mod 35) и их квадратными корнями являются:

v	v-1	s=sqrt( v-1)
1	1	1
4	9	3
9	4	2
11	16	4

 

 

 

 

 

16 11 9

29 29 8

Обратите внимание, что  у чисел 14, 15, 21, 25 и 30 нет обратных значений mod 35, так как они не взаимно просты с 35. Это имеет смысл, так как должно быть (5 - 1) * (7 - 1)/4 квадратичных остатков mod 35, взаимно простых с 35: НОД( х, 35) = 1.

Итак, Пегги  получает открытый ключ, состоящий  из k = 4 значений: {4,11,16,29}. Соответствующим закрытым ключом является {3,4,9,8}. Вот один этап протокола.

1. Пегги выбирает случайное r=16, вычисляет 16² mod 35 = 11 и посылает его Виктору.
2. Виктор посылает Пегги строку случайных битов: {1, 1,0, 1}
3. Пегги вычисляет 16*(3¹*4¹*9⁰*8¹) mod 35 = 31 и посылает его Виктору.
4. Виктор проверяет, что 31²*(4¹*11¹*16⁰*29¹) mod 35 =11.

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

Небольшие числа, подобные использованным в примере, не обеспечивают реальной безопасности . Но когда длина п равна 512 и более битам, Виктор не сможет узнать о закрытом ключе Пегги ничего кроме того факта, что Пегги действительно знает его.

Улучшения

В протокол можно  встроить идентификационные данные. Пусть I - это двоичная строка, представляющая идентификатор Пегги: имя, адрес, номер социального страхования, размер головного убора, любимый сорт прохладительного напитка и другая личная информация. Используем однонаправленную хэш-функцию H(х) для вычисления H(I,j), где j - небольшое число, добавленное к I. Найдем набор j, для которых H(I,j) - это квадратичный остаток по модулю п. Эти значения H(I,j) становятся v₁, v₂, …v_k (j не обязаны быть квадратичными остатками). Теперь открытым ключом Пегги служит I и перечень j. Пегги посылает I и перечень j Виктору перед шагом (1) протокола (или Виктор загружает эти значения с какой-то открытой доски объявлений), И Виктор генерирует v₁, v₂, …v_k из H(I,j).

Теперь, после  того, как Виктор успешно завершит протокол с Пегги, он будет убежден, что Трент, которому известно разложение модуля на множители, сертифицировал связь  между I и Пегги, выдав ей квадратные корни из v_i полученные из I. Фейге, Фиат и Шамир добавили следующие замечания:

 

Для неидеальных  хэш-функций можно посоветовать рандомизировать I, добавляя к нему длинную случайную строку R. Эта строка выбирается арбитром и открывается Виктору вместе с I.

В типичных реализациях k должно быть от 1 до 18. Большие значения k могут уменьшить время и трудности связи, уменьшая количество этапов.

Длина и должна быть не меньше 512 битов. (Конечно, с  тех пор разложение на множители  заметно продвинулось.)

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

 

Другие улучшения

На основе алгоритма Fiat-Shamir существует и N-сторонняя схема идентификации. Так же существует ещё 3 варианта улучшения.

Патенты

Fiat-Shamir запатентован. При желании получить лицензию на алгоритм свяжитесь с Yeda Research and Development, The Weizmann Institute of Science, Rehovot 76100, Israel.

 

2. Электронная цифровая  подпись

 

2.1.Общая схема цифровой подписи

 

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

     Вероятностный алгоритм или система генерирования ключей. Каждый абонент получает пару ключей ( , ), где — открытый ключ, а — тайный.

     Алгоритм подписывания , который, используя сообщение и тайный ключ , выдает некоторое слово . Слово называется подписью абонента на сообщении . В случае, если абонент хочет послать сообщение с заверением того, что оно послано именно им, то он отсылает пару ( , ).

     Алгоритм проверки подписи , которым может воспользоваться любой желающий проверить факт, что подпись на сообщении принадлежит именно абоненту — владельцу открытого ключа . Если , то проверка подписи считается успешной.

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

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

     Предложенная схема цифровой подписи была развита американскими математиками Диффи и Хеллманом. При этом они утверждают, что любую криптосистему с открытым ключом можно превратить в систему цифровой подписи следующим образом. Пускай и — алгоритмы шифрования и дешифрования соответственно, и — открытый и тайный ключи. Тогда цифровая подпись ставится по такому правилу: , а проверку подписи нужно проводить следующим образом: если , то , во всех других случаях .

     Итак, рассмотрев общую схему построения цифровой подписи, приступим к описанию конкретных систем цифровой подписи.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2. Алгоритм цифровой подписи ГОСТ

 

     Это русский стандарт цифровой подписи, официально называемый ГОСТ Р 34.10-94. Алгоритм очень похож на DSA, и использует следующие параметры

р = простое  число, длина которого либо между 509 и 512 битами, либо между 1020 и 1024 битами.

q = простое число - множитель р-1, длиной от 254 до 256 битов.

а = любое число, меньшее р-1, для которого a^q mod p = 1.

y = a^x mod p.

Этот алгоритм также использует однонаправленную хэш-функцию : H(x). Стандарт определяет использование хэш-функции ГОСТ Р 34.1 1-94 (см. раздел 18.1 [1]), основанной на симметричном алгоритме ГОСТ (см. раздел 14.1 [1]).

Первые три  параметра: p, q и a, открыты и могут использоваться совместно пользователями сети. Закрытым ключом служит х, а открытым - у. Чтобы подписать сообщение m

(1) Алиса генерирует случайное число к, меньшее q

(2) Алиса генерирует I = (a^k mod p) mod q s = (ct+ k(H(m))) mod q

r = (a^k mod p) mod q

s = (xr + k(H(m))) mod q

 

Если H(m) mod q =0, то значение хэш-функции устанавливается равным 1. Если r =0, то выберите другое значение k и начните снова. Подписью служат два числа: r mod 2²⁵⁶ и s mod 2²⁵⁶, Алиса посылает их Бобу.

 

   (3) Боб проверяет  подпись, вычисляя 

v = H(m)^q-2 mod q

z₁ = (sv) mod q

  z₂ = ((q-r)*v) mod q

u = ((a^z1 * y^z2 mod p) mod q

Если u = r, то подпись правильна.

 

Различие между этой схемой и DSA в том, что в DSA s = (k^-1 (H(m) + xr)) mod q, что дает другое уравнение проверки. Любопытно, однако, что длина q равна 256 битам. Большинству западных криптографов кажется достаточным q примерно 160 битов длиной. Может быть это просто следствие русской привычки играть в сверхбезопасность.

 

Стандарт используется с начала 1995 года и не закрыт грифом «Для служебного пользования», что  бы это не значило.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Контроль  целостности передаваемых сообщений ГОСТ

 

3.1. Общая концепция алгоритма

ГОСТ

ГОСТ - это блочный  алгоритм, разработанный в бывшем Советском Союзе. Название "ГОСТ" является сокращением от "Государственный  стандарт", нечто похожее на FIPS за исключением того, что это название могут носить стандарты практически любого типа. (Полным названием является "Государственный стандарт Союза ССР", или "Государственный стандарт Союза Советских Социалистических Республик".) Номер данного стандарта - 28147-89. Все эти стандарты утверждаются Государственным комитетом по стандартам Союза ССР.

Не известно, использовался ли ГОСТ 28147-89 для засекреченного трафика или только для гражданского шифрования. Замечание в начале стандарта гласит, что алгоритм "удовлетворяет всем криптографическим требованиям, а степень защищаемой информации не ограничивается". Есть утверждения, что этот алгоритм первоначально использовался только для очень важных линий связи, включая секретные военные коммуникации.

Описание  ГОСТ

ГОСТ является 64-битовым  алгоритмом с 256-битовым ключом. ГОСТ также использует дополнительный ключ, который рассматривается ниже. В  процессе работы алгоритма на 32 этапах последовательно выполняется простой  алгоритм шифрования.

Для шифрования текст сначала разбивается на левую половину L и правую половину R. На этапе i используется подключ K_i. На этапе i алгоритма ГОСТ выполняется следующее:

L_i = R_i-1

R_i = L_i-1 f(R_i-1 ,K_i)

Этап ГОСТ показан  на Рис. 3.1. Функция f проста. Сначала правая половина и i-ый подключ складываются по модулю 2³². Результат разбивается на восемь 4-битовых кусочков, каждый из которых поступает на вход своего S-блока. ГОСТ использует восемь различных S-блоков, первые 4 бита попадают в первый S-блок, вторые 4 бита - во второй S-блок, и т.д. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Например, S-блок может выглядеть как:

7, 10, 2, 4, 15, 9, 0, 3, 6, 12, 5, 13, 1, 8, 11

Рис. 3.1. Этап ГОСТ.

В этом случае, если на входе S-блока 0, то на выходе 7. Если на входе 1, на выходе 10, и т.д. Все восемь S-блоков различны, они фактически являются дополнительным ключевым материалом. S-блоки должны хра-ниться в секрете.

Выходы всех восьми S-блоков объединяются в 32-битовое слово, затем все слово циклически сдвигается влево на 11 битов. Наконец результат объединяется с помощью XOR с левой половиной, и получается новая правая половина, а правая половина становится новой левой половиной. Выполните это 32 раза, и все в порядке.

Генерация подключей проста. 256-битовый ключ разбивается на восемь 32-битовых блоков: k1, k2, . . .k8. На каждом этапе используется свой подключ, как показано в Табл. 3.1. Дешифрирование выполняется также, как и шифрование, но инвертируется порядок подключей ki.

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

                            

Табл. 3.1.Использование подключей на различных этапах ГОСТ

 

Этап:          1       2       3       4       5       6      7       8       9     10     11     12     13     14     15   1б

Подключ:   1       2       3       4       5       6      7       8       1      2       3        4      5       6       7      8

Этап:         17     18     19     20     21     22     23     24     25     26     27     28     29     30    31  32

Подключ:   1       2       3       4       5       6       7       8       8       7       6       5       4       3      2     1

Совсем  недавно стал известным набор S-блоков, используемых в приложениях Центрального Банка РФ. Эти S-блоки также используются в однонаправленной хэш-функции ГОСТ . Они перечислены в Табл. 3.2.