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. Атака на основе подобранного открытого текста. У криптоаналитика есть доступ не только к шифротекстам и открытым текстам нескольких сообщений, но и возможность выбирать открытый текст для шифрования. Это предоставляет больше возможностей, чем вскрытие с использованием открытого текста, так как криптоаналитик может выбирать для шифрования блоки открытого текста, что может предоставить дополнительную информацию о ключе. Его задача состоит в раскрытии ключа (или ключей), применительно для шифрования сообщений, или алгоритма, позволяющего дешифровать все новые сообщения, зашифрованные тем же ключом (или ключами).
Страницы: 1, 2, 3, 4, 5, 6
