Курсовая работа: Современная криптография

вычисляет 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ÎRZq и вычисляет открытый ключ y = gxmodp. Для генерации подписи для сообщения m нужно выбрать uÎRZ*q \{1} и вычислить r = gumodpmodq и s = u-1 (h(m) +xr) modq. Параметр u должен быть секретным и может быть уничтожен после вычисления r и s. Если r = 0 или s = 0, то выбираются новое значение u и процесс генерации подписи повторяется. В противном случае (r,s) – искомая подпись для сообщения m.

Для проверки подписи (r,s) для сообщения m необходимо сначала проверить условие 0 < r < q и 0 < s <q. Если хотя бы одно из них ложно, то подпись отвергается. В противном случае подпись принимается тогда и только тогда, когда

gvh(m)yvr mod p mod q = r, где v = s-1 mod q.

Схема стандарта электронной подписи ГОСТ.

Пусть p,q,g,h,x,y имеют тотже смысл, что и в схеме DSA. Для генерации подписи для сообщения m нужно выбрать uÎRZ*q \{1} и вычислить

r = gumodpmodq и s = u-1 (h(m) +xr) modq. Параметр u должен быть секретным и может быть уничтожен после вычисления r и s. Если r = 0 или s = 0, то выбираются новое значение u и процесс генерации подписи повторяется. В противном случае (r,s) – искомая подпись для сообщения m.

Для проверки подписи (r,s) для сообщения m необходимо сначала проверить условие 0 < r < q и 0 < s <q. Если хотя бы одно из них ложно, то подпись отвергается. В противном случае подпись принимается тогда и только тогда, когда

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)dmodn , где

d = e-1 modj(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 < п. Говоря неформально, универсальное семейство хэш-функций — это метод "перемешивания" с сокращением длины строк, при котором выходные значения распределены равномерно.