Схемы цифровой подписи с использованием дискретных логарифмов

Это шесть различных схем цифровых подписей. Добавление минуса увеличивает их количество до 24. При использовании всех возможных значения a, b и c число схем доходит 120.

EIGamal и DSA по существу основаны на уравнении (4). Другие схемы - на уравнении (2) Schnorr тесно связан с уравнением (5). А уравнение (1) можно изменить так, чтобы получить схему, предложенную в [1630]. Оставшиеся уравнения - новые.

Любую из этих схем можно сделать более DSA-подобной, определивrкак

r= (g^k mod p)mod q

Используйте то же уравнение подписи и сделайте уравнением проверки

u₁ = a^-1bmod q

u₂ = a^-1cmod q

v= (() mod p) mod q

(r mod q ) ^a= g^by^cmod p

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

Но и это еще не все. Дополнительные обобщения и изменения приводят более, чем к 13000 вариантам (не все из них достаточно эффективны).

Одной из приятных сторон использования RSA для цифровой подписи является свойство, называемое восстановлением сообщения. Когда вы проверяете подпись RSA, вы вычисляете m. Затем вычисленное mсравнивается с сообщением и проверяется, правильна ли подпись сообщения. В предыдущих схемах восстановить m при вычислении подписи невозможно, вам потребуется вероятное m, которое и используется в уравнении проверки. Но, оказывается, можно построить вариант с восстановлением сообщения для всех вышеприведенных схем. Для подписи сначала вычислим

r= mg^k mod p

и заменим mединицейв уравнении подписи. Затем можно восстановит уравнение проверки так, чтобы mмогло быть вычислено непосредственно. То же самое можно предпринять для DSA-подобных схем:

r= (mg^k mod p) mod q

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

Вопрос 27.1. Итерационные системы блочного шифрования. Особенности строения и ключевой системы шифров DES, GOST. Режимы шифрования. Аутентификация сообщений с использованием блочного шифра

На примере DES можно показать еще несколько принципов проектирования блочного шифра. Первым является идея итеративного блочного шифра. При этом предполагается, что простая функция этапа будет последовательно использована несколько раз. Двухэтапный DES не очень силен, чтобы все биты результата зависели от всех битов ключа и всех битов исходных данных, нужно 5 этапов. 16-этапный DES - это сильный алгоритм, 32-этапный DES еще сильнее.

Сети Фейстеля

Большинство блочных алгоритмов являются сетями Фейстеля. Возьмите блок длиной n и разделите его на две половины длиной n/2: L и R. Конечно, n должно быть четным. Можно определить итеративный блочный шифр, в котором результат j-го этапа определяется результатом предыдущего этапа:

L_i = R_i-1, R_i = L_i-1 Å f(R_i-1, K_i), где K_i - это подключ, используемый на j-ом этапе, а f - это произвольная функция этапа.

Эту концепцию можно увидеть в DES, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и других алгоритмах. Почему это так важно? Гарантируется, что эта функция является обращаемой. Так как для объединения левой половины с результатом функции этапа используется XOR, следующее выражение обязательно является истинным: L_i-1 Å f(R_i-1, K_i) Å f(R_i-1, K_i)= L_i-1

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

DES

DES представляет собой блочный шифр, он шифрует данные 64-битовыми блоками. С одного конца алгоритма вводится 64-битовый блок открытого текста, а с другого конца выходит 64-битовый блок шифротекста. DES является симметричным алгоритмом: для шифрования и дешифрирования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа).

Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени. Ряд чисел считаются слабыми ключами, но их можно легко избежать. Безопасность полностью определяется ключом.

На простейшем уровне алгоритм не представляет ничего большего, чем комбинация двух основных методов шифрования: смещения и диффузии. Фундаментальным строительным блоком DES является применение к тексту единичной комбинации этих методов (подстановка, а за ней - перестановка), зависящей от ключа. Такой блок называется этапом. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому тексту 16 раз.

Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-х. Изобилие повторений в алгоритме делает его идеальным для реализации в специализированной микросхеме.

Схема алгоритма

DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 этапов одинаковых действий, называемых функцией f, в которых данные объединяются с ключом. После шестнадцатого этапа правая и левая половины объединяются и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной).

На каждом этапе (см. Рис12-2) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f. Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов DES.

Если B_i - это результат i-ой итерации, L_i и R_i - левая и правая половины B_i, K_i - 48-битовый ключ для этапа i, а f - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:

L_i = R_i-1

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