Модернизация электронной подписи Эль-Гамаля - (диплом)
p>yi = f(I, j), отбирает среди них квадратичные вычеты по модулю n (изменив обозначения, мы считаем, что yi для всех j = 1, …, l являются квадратичными вычетами по млдулю n), и вычисляет xi – наименьший квадратичный корень по модулю n из yi-1 mod n. Числа yi играют роль открытого ключа, а xi – секретного. Так как эти ключи вычисляются с использованием I, схема Фивта –Шамира относится к схемам, основанным на идентификационной информации (identity based). В другом варианте схемы Фиата– Шамира сразу выбираются (псевдослучайным образом) параметру yi. На практике идентификационная информация I и/или открытый ключ (y1, …, yl) каждого пользователя помещаются в некоторый справочник, доступный всем пользователям для чтения, но не доступный для записи. Для обеспечения аутентичности, данные в этом справочнике заверяются подписью центра обеспечения безопасности. Секретный ключ (x1, …, xl) и идентификационная информация I могут быть помещены на интеллектуальную карточку пользователя. Для генерации подписи для обеспечения m подписывающийвыбирает uiОR Zn (каждое ui – независимо друг от друга) и вычисляет ri = ui2 mod n для i = 1, …, t;
вычисляет h(m, r1, …, rt) и полагает биты eij(i = 1, …, t, j = 1, …, t) равными первым lt битам h(m, r1, …, rt);
вычисляет для i = 1, …, t.
Искомой подписью для сообщения m является набор (eij, vi | i = 1, …, t, j = 1, …, l) Для проверки подписи (eij, vi | i = 1, …, t, j = 1, …, l) для сообщения m подписывающий вычисляет vj = h(I, j) для j = 1, …, lили берет их из общедоступного справочника и сравнивает их с имеющимися в подписи (если обнаружено несовпадение– подпись отвергается);
вычисляет для i = 1, …, t.
Подпись принимается тогда и только тогда, когда первые lt битов h(m, z1, …, zt) равны eij. Несомненным достоинством схемы Фмата –Шамира является отсутствие дискретного экспонентрирования, что делает схему весьма эффективной. Но с другой стороны, в этой схеме длины ключей и подписи значительно больше, чем в схемах типа Эль Гамаля.
Схема стандарта электронной подписи ANSI США (DSA)
Эта схема аналогична схеме Эль Гамаля, но несколько эффективнее, так как в ней порядокg меньше, чем в схеме Эль Гамаля. Пусть в открытом доступе имеются некоторые простые числаp, q такие, что q | p-1, а также элемент g порядка q группы Z*q и хэш-функция h, действующая из пространства сообщений в Z*q . Параметры p, q, g и хэш-функция hмогут быть выбраны центром обеспечения безопасности. Подписывающий выбирает секрктный ключ xОR Zq и вычисляет открытый ключ y = gx mod p. Для генерации подписи для сообщения m нужно выбрать u ОR Z*q \{1} и вычислить r = gu mod p mod q и s = u-1 (h(m) +xr) mod q. Параметр u должен быть секретным и может быть уничтожен после вычисления r и s. Если r = 0 или s = 0, то выбираются новое значение u и процесс генерации подписи повторяется. В противном случае (r, s) – искомая подпись для сообщения m. Для проверки подписи (r, s) для сообщения m необходимо сначала проверить условие 0 < r < q и 0 < s
gvh(m)yvr mod p mod q = r, где v = s-1 mod q.
Схема стандарта электронной подписи ГОСТ.
Пусть p, q, g, h, x, y имеют тотже смысл, что и в схеме DSA. Для генерации подписи для сообщения m нужно выбрать u ОR Z*q \{1} и вычислить r = gu mod p mod q и s = u-1 (h(m) +xr) mod q. Параметр u должен быть секретным и может быть уничтожен после вычисления r и s. Если r = 0 или s = 0, то выбираются новое значение u и процесс генерации подписи повторяется. В противном случае (r, s) – искомая подпись для сообщения m. Для проверки подписи (r, s) для сообщения m необходимо сначала проверить условие 0 < r < q и 0 < s
gwsy-wr mod p mod q = r, где w = h(m)-1 mod q.
Схема RSA .
В схеме RSA подписывающий выбирает два различных больших простых числа p и q, которые играют роль секретного ключа, и публикует открытый ключ (n, e), где n = pq, а e – некоторое число, взаимно простое с j(n) = (p-1)(q-1) (j - функция Эйлера). Подписью для сообщения m является s(m) = h(m)d mod n , где d = e-1 mod j(n)(очевидно, что, зная p и q, можно эффективно вычислить d) и h – хэш-функция. Проверка подписи s для сообщения m состоит в проверке сравнения se є h(m) (mod n) .
Схема RSA достаточно эффективна и широко используется на практике. Вера в стойкость схемы основана на (гипотетической) трудности задачи факторизации целых чисел.
Глава 3. Хэш-функции.
Хэш-функции являются необходимым элементом ряда криптографических схем. Под этим термином понимаются функции, отображающие сообщения произвольной длинны (иногда длинна сообщения ограничена, но достаточно большим числом) в значения фиксированной длинны. Последние часто называютхэш-кодами. Таким образом, у всякой хэш-функции h имеется большое количество коллизий, т. е. пар значений x№y таких, что h(x) = h(y). Основное требование, предъявляемое к хеш-функциям, состоит в отсутствии эффективных алгоритмов поиска коллизий. В ряде криптографических приложений, особенно в схемах электронной цифровой подписи, необходимым элементом является криптографически стойкая хэш-функция.
Практические методы построения хэш-функций можно условно разделить на три группы: на основе какого-либо алгоритма шифрования, на основе какой-либо известной вычислительно трудной математической задачи и методы построения "с нуля".
Наиболее эффективной с точки зрения программной реализации, оказываются хэш-функции построенные "с нуля".
В данной дипломной работе в качестве алгоритма построения хэш-функции использовался алгоритм Ривеста MD5, который будет описан ниже.
Универсальные семейства хэш-функций.
Понятие универсального семейства хэш-функций было введено в 1979 г. Картером и Вегманом [CW].
Определение 1. Пусть А и В - два конечных множества и H - семейство функций из А в В. H называется универсальным семейством хэш-функций если для любых х1 № х2 О А и y1, y2 О В
Вероятность берется по случайному равновероятному выбору функции h из семейства Н.
Обычно предполагается, что мощность образа (множества В)меньше, чем мощность прообраза (А), и что хэш-функции "сжимают" входные слова. Как правило, рассматриваются семейства хэш-функций, которые переводят множество всех двоичных строк длинып в множество всех двоичных строк длины m, где m < п. Говоря неформально, универсальное семейство хэш-функций —это метод "перемешивания" с сокращением длины строк, при котором выходные значения распределены равномерно.
Семейство хэш-функций из определения 1 принято назвать 2-универсалъным семейством. Если в этом определении заменить пары значений x и y на наборы из k значений, то получим определение k-универсального семейства хэш-функций .
Лемма о композиции [DeSY]. Пусть H1 и Н2 - 2-универсальные семейства, хэш-функций, действующих из C1 в C2 и из С2 в С3 соответственно. Тогда
Н = h1 О H1, h2 О H2,
где o обозначает композицию, является 2-универсальным семейством хэш-функции, действующих из C1 в C3.
Нас эти семейства интересуют в основном как инструмент для определения и построения семейств односторонних хэш-функций.
С прикладной точки зрения универсальные семейства хэш-функций должны удовлетворять некоторым дополнительным требованиям. Во-первых, хэш-функции должны быть эффективно вычислимыми. Часто это требование включают в определение универсального семейства и формализуют следующим образом. У каждой хэш-функции h ОH имеется достаточно короткое описание h и существуют два эффективных алгоритма, первый из которых по запросу и выдает случайное hО H, а второй по h аргументу x вычисляет h{x). Во-вторых, во многих случаях требуются семейства хэш-функций, которые определяются не на строках только данной фиксированной длины, а на строках всех длин (или бесконечной последовательности длин). В этом случае множествоНп, которое действует согласно определению 1 на строках длины п, называют коллекцией хэш-функций, а универсальным семейством называют {Нп}. В-третьих, для криптографических приложений иногда требуется так называемое свойство доступности коллизий(collision accessibility). Оно требует существования эффективного алгоритма, который по даннымх1 и х2 выбирает h О H такую, что
h(х1) = h(х2), равновероятным образом среди всех функций из Н, удовлетворяющих этому свойству.
Пусть F = GF(2k) и chop: {0, 1}k ® {0, 1}k-1- функция, которая просто отбрасывает последний бит. Тогда семейство хэш-функций {chop(ax+b)} является 2-универсальным и удовлетворяет свойству доступности коллизий. Пусть А = {0, 1}n и В {0, 1}m. Для х О {0, 1}n и у О {0, 1}n+m-1 определим конволюцию у о х элементов у и х как вектор длины m, i-я координата которого определяется по формуле
Тогда семейство H = { (a о х) Е b | a О {0, 1}n+m-1 , b О {0, 1}m} представляет собой универсальное семейство хэш-функций. Семейства односторонних хэш-функций.
Пусть {n1i} и { n0i} - две возрастающие последовательности натуральных чисел такие) что для всех i n1i і n0i и существует такой полином q, что q(n0i, ) і n1. (такие последовательности полиномиально связаны).
Пусть Нk - коллекция функций такая, что для всех h О Hk
и пусть .
Предположим, что А - вероятностный алгоритм, работающий за поли-номиальное время, который на входе k выдает строку x О {0, 1}n1k, называемую исходным значением, и затем для данной случайной h О Hk пытается найти у О {0, 1}n1k такое, что h{x) = h{y), но х № у.
Определение 2. Семейство U называется универсальным семейством односторонних хэш-функций, если для всех полиномов р, для всех полиномиальных вероятностных алгоритмов А и всех достаточно больших k выполняются следующие условия:
x О {0, 1}n1k - исходное значение для А, то
Рг[А(h, x) = у, h{x) - h(y), у № х] < 1/p(n1k),
