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

(9.1.10).

Получив сообщение Боб заново вычисляет значение хеш-функции и проверяет подпись, используя равенство

(9.1.11)

/*Пример*/

Пусть общие параметры для некоторого сообщества пользователей . Алиса выбирает свой секретный ключ и вычисляет открытый ключ по формуле (9.1.5):

Пусть Алиса создала документ и хочет его подписать. Прежде всего Алиса вычисляет хеш-функцию, пусть её значение будет равно . Затем Алиса генерирует случайное число , например, .

9.2 Криптосистемы на эллиптических кривых

Использование эллиптических кривых в криптографических целях было Нило Коблицом и Виктором Миллером в 1985 году. С 1998 года использование эллиптических кривых для решения криптографических задач, таких, как цифровая подпись, было закреплено в стандартах США ANSI X9.62 и FIPS 186-2, а в 2001 году аналогичный стандарт, ГОСТ Р34.10-2001, был принят и в России.

Особое достоинство криптосистем на эллиптических кривых состоит в том, что по сравнению с “обычными” RSA системами, они обеспечивают существенно более высокую стойкость при равной трудоемкости или, наоборот, существенно меньшую трудоемкость при равной стойкости.

В результате тот уровень стойкости, который достигается в RSA при использовании 1024-битовых модулей, в системах на эллиптических кривых реализуется при размере модуля 160 бит, что обеспечивает более простую как программную, так и аппаратную реализацию.

Эллиптические кривые.

Кривая третьего порядка , задаваемая уравнением вида:

(1)

называется эллиптической кривой.

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

(2)

Дискриминант этого уравнения равен

(3)

Если уравнение (2) имеет три различных корня если то (2) имеет три действительных корня (два из которых равны); если уравнение имеет один действительный корень и два комплексно сопряженных.

Графический вид шифрования.

- изменение знака

Алгоритм шифрования.

Для пользователей некоторой сети выбираются общая эллиптическая кривая и некоторая точка , такая, что … - это различные точки, а (точка в бесконечности) для некоторого простого числа .

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

Допустим, пользователь хочет передать сообщение пользователю .

делает следующее:

1. Выбирает случайное число

2. Вычисляет ;

3. Шифрует

4. Посылает криптограмму

Пользователь после получения

1. Вычисляет

2. Дешифрует

{ - угловой коэффициент }

Цифровая подпись.

Для сообщества пользователей выбирается общая эллиптическая кривая и точка на ней, такая, что … суть различные точки, и для некоторого простого числа (длина числа равна 256 бит).

Каждый пользователь выбирает случайное число (секретный ключ), , и вычисляет точку на кривой (открытый ключ). Параметры кривой и список открытых ключей передаются всем пользователям.

Чтобы подписать сообщение, Алиса делает следующее:

1. Вычисляет значение хеш-функции сообщения ;

2. Выбирает случайно число , ;

3. Вычисляет ;

4. Вычисляет (при возвращается к шагу 2);

5. Вычисляет (при возвращается к шагу 2);

6. Подписывает сообщение парой чисел .

Для проверки подписанного сообщения любой пользователь, знающий открытый ключ , делает следующее:

1. Вычисляет ;

2. Убеждается, что ;

3. Вычисляет и ;

4. Вычисляет композицию точек на кривой и если , отвергает подпись;

5. Если , принимает подпись, в противном случае отвергает ее.

9.5 Общие принципы стохастической защиты информации

Метод стохастической защиты информации был разработан как помехоустойчивый код, содержащий признаки и операции введения избыточности при кодировании и принятия решения о наличии ошибок (и исправлении ошибок) при декодировании, объединенные с операциями прямого и обратного стохастического преобразования.

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

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

2) Сочетание преобразования на большой длине блока (блочное шифрование) с использованием последовательности гаммы.

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

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

5) Использование при генерации гаммы регистров с обратной связью при большой длине регистра и нелинейных операций в цепях обратной связи.

6) Принцип преобразования сообщения в квази случайную последовательность с распределением, не зависящим от статистики исходного сообщения.

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

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

имеет место:

при ,

при ,

для всех от 1 до

где и - канальный (исходный) и преобразованный векторы ошибки, т.е. сумма по модулю 2 между искажаемым и искаженным вектором.

Особенности стохастического шифрования.

1) Использование двупараметрической операции замены.

2) Развитие двух идей Шеннона:

- равновероятность обеспечивает нулевое количество в криптограмме о сообщении (проверяется с помощью тестов Кнута или NIST);

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

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

10. Криптоанализ

10.1 Существующие методики криптографических атак

Все предназначение криптографии заключается в сохранении открытого текста (или ключа, или того и другого) в тайне от оппонентов. Предполагается, что оппоненты располагают неограниченным доступом к линиям связи между отправителем и получателем.

Криптоанализом называют науку восстановления (дешифрования) открытого текста без доступа к ключу. Успешный криптоанализ позволяет восстановить открытый текст или ключ. Кроме того, криптоанализ позволяет обнаружить слабые места в криптоносителях, что в конце концов приведет к тем же результатам. Раскрытие ключа без привлечения методов криптологии называют компрометацией.

Попытка криптоанализа называется атакой. Фундаментальное допущение криптоанализа состоит в том. Что секретность сообщения всецело зависит от ключа.

Известны четыре основных типа криптоаналитических атак:

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

Дано:

Определить: либо либо алгоритм восстановления из .

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

Дано: .

Определить: либо , либо алгоритм восстановления из .

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

Дано: ,

где криптоаналитик может выбирать

Определить: либо , либо алгоритм восстановления из .

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

Кроме перечисленных типов известны так же, по крайней мере, еще три типа криптоаналитических атак.

1) Атака на основе подобранного шифротекста. Криптоаналитик может выбирать различные шифротексты для расшифрования. А так же имеет доступ к расшифрованным открытым текстам. Например, у криптоаналитика есть доступ к «черному ящику», выполняющему автоматическое расшифровывание. Его задача состоит в раскрытии ключа.

Дано: .

Получить: .

Такой тип вскрытия применим, главным образом, к алгоритмам с открытым ключом. Кроме того, вскрытие с использованием подобранного шифротекста в некоторых случаях эффективно против симметрических алгоритмов.

2) Атака на основе подобранного ключа. Такой тип вскрытия не означает, что криптоаналитик может выбирать ключ - просто он кое-что знает о связях между различными ключами.

3) Бандитский криптоанализ. До получения ключа «криптоаналитик» прибегает к угрозам, шантажу или пыткам. Возможно также взяточничество, которое иногда называют «вскрытием с покупкой ключа». Это очень мощные и, зачастую, самые эффективные методы взлома алгоритма.

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

10.2 Взлом шифров с открытым ключом на основе подобранного шифротекста

Страницы: 1, 2, 3, 4, 5