Есть два метода сорвать атаку анализом времени:

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

2. Ривест рекомендовал «ослепление». По этой идее зашифрованный текст умножается на случайное число перед дешифрованием. Процедура содержит следующие шаги:

a. Выбрать секретное случайное число r между 1 и (n - 1).

b. Вычислить .

c. Вычислить P1 = C1d mod n.

d. Вычислить .

· Атака анализом мощности подобна атаке анализом времени. Было показано, что если Ева может точно измерить мощность, использованную в течение дешифрования, она может начать атаку анализа мощности на основании принципов, рассмотренных для атаки анализом времени. Итеративное умножение и возведение в квадрат потребляют больше мощности, чем только итеративное возведение в квадрат. Та же самая группа методов, которая предотвращает атаки анализом времени, может сорвать атаки анализа мощности.

8. Рекомендации для RSA

Следующие рекомендации основаны на теоретических и экспериментальных результатах.

1. Число битов для n должно быть, по крайней мере, 1024. Это означает, что n должно быть приблизительно 21024, или 309 десятичных цифр.

2. Два простых числа p и q должны каждый быть по крайней мере 512 битов. Это означает, что p и q должны быть приблизительно 2512 или 154 десятичными цифрами.

3. Значения p и q не должен быть очень близки друг к другу.

4. p - 1 и q - 1 должны иметь по крайней мере один большой простой сомножитель.

5. Отношение p/q не должно быть близко к рациональному числу с маленьким числителем или знаменателем.

6. Модуль n не должен использоваться совместно.

7. Значение e должно быть 216 + 1 или целым числом, близким к этому значению.

8. Если произошла утечка частного ключа d, Боб должен немедленно изменить n так же, как e и d. Было доказано, что знание n и одной пары (e, d) может привести к открытию других пар того же самого модуля.

9. Сообщения должны быть дополнены, используя OAEP, который рассматривается далее.

9. Криптографическая система Эль-Гамаля

Помимо RSA есть другая криптосистема с открытым ключом Эль-Гамаля (ElGamal), которая названа по имени ее изобретателя, Тахира Эль-Гамаля (Taher ElGamal).

Если p - очень большое простое число, e1 - первообразный корень в группе и r - целое число, тогда e2 = e1r mod p просто вычисляется с использованием быстрого показательного алгоритма (метод «возведения в квадрат и умножения»). Но по данным e2, e1 и p, невозможно вычислить r = loge1e2 mod p (проблема дискретного логарифма).

Рис. 8 показывает генерацию ключей, шифрование и дешифрование в криптосистеме Эль-Гамаля.

Рис. 8  Генерация ключей, шифрование, и дешифрование в криптосистеме Эль-Гамаля

Определение общедоступного и частного ключей

• Выбор двух взаимно простых чисел p и e1, e1<p

• Выбор значения секретного ключа d, d<p

• Определение значения открытого ключа e2 из выражения:

e2=e1d (mod p)

• Общедоступный ключ (e1,e2,p) может быть объявлен публично

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

Алгоритм шифрования сообщения P

• Выбор случайного числа r, удовлетворяющего условию:

0?r<p-1 и НОД(r,p-1)=1

• Определение значения C1 из выражения: C1=e1r (mod p)

• Определение значения C2 из выражения: C2=e2r P(mod p)

• Криптограмма С, состоящая из C1 и C2, отправляется получателю

• Получатель расшифровывает криптограмму с помощью выражения:

P = [C2(C1d)-1]mod p

Пример 6

Боб выбирает 11 в качестве p. Затем он выбирает e1 = 2. Обратите внимание, что 2 - первообразный корень в Z11* (см. приложение J). Затем Боб выбирает d = 3 и вычисляет e2 = e1d = 8. Получены открытые ключи доступа - (2, 8, 11) и секретный ключ - 3. Алиса выбирает r = 4 и вычисляет C1 и C2 для исходного текста 7.

Исходный текст: 7

C1 = e1r mod 11 = 16 mod 11= 5 mod 11

C2 = (P ? e2r) mod 11 = (7 ? 4096) mod 11 = 6 mod 111

Зашифрованный текст: (5, 6)

Боб получает зашифрованные тексты (5 и 6) и вычисляет исходный текст.

Зашифрованный текст: [C1 ? (C2d)-1] mod 11 = 6 ? (53)-1 mod 11 = 6 ? 3 mod 11 = 7 mod 11

Исходный текст: 7

10. Безопасность криптосистемы Эль-Гамаля

· Атаки малого модуля

Если значение модуля p не является достаточно большим, Ева может использовать некоторые эффективные алгоритмы, чтобы решить проблему дискретного логарифма и найти d или r. Если p мало, Ева может просто найти d = loge1e2 mod p и сохранить его, чтобы расшифровать любое сообщение, передаваемое Бобу. Это может быть сделано единожды и работать, пока Боб использует те же самые ключи. Ева может также использовать значение случайного числа r, применяемого Алисой в каждой передаче r = loge1C1 mod p. Оба этих случая подчеркивают, что безопасность криптосистемы Эль-Гамаля зависит от решения проблемы дискретного логарифма с очень большим модулем. Поэтому рекомендовано, что p должны быть по крайней мере 1024 бита (300 десятичных цифр).

· Атака знания исходного текста

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

1. .

2. .

Поэтому рекомендовано, чтобы Алиса брала при каждой передаче новое значение r, чтобы сорвать атаки.

Чтобы криптосистема Эль-Гамаля была безопасной, модуль p должен содержать по крайней мере 300 десятичных цифр, новых для каждой шифровки.

11. Алгоритм обмена ключами Диффи-Хеллмана

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

Алгоритм был впервые опубликован Уитфилдом Диффи и Мартином Хеллманом в 1976 году.

Пускай мы хотим переслать сообщение приятелю так, чтобы никто не подслушал. У нас есть достаточно стойкий способ шифрования: мы знаем, что если даже перехватят зашифрованное сообщение, то без ключа они ни о чем не догадаются. Но чтобы расшифровать сообщение, приятель тоже должен знать ключ - как его передать? Долго считалось, что задача передачи ключа не разрешима принципально, то есть нам придётся встретиться заранее в укромном месте и придумать общий ключ: по открытому каналу мы не договоримся. Что же придумали Диффи и Хеллман: это вообще был крупнейший переворот в истории шифрования.

Во-первых, допустим, у меня есть шкатулка. Я хочу её переслать посылкой, чтобы никто не мог открыть (в границах аналогии - без грубой силы), а приятель мог бы. Как переслать ключ от шкатулки? Я повешу на шкатулку висячий замок и отправлю её без ключа. Приятель, получив посылку, не сможет её открыть, но повесит туда свой собственный замок (от которого ключ только у него) и отправит обратно мне. Я сниму свой замок и снова отправлю приятелю. И теперь он получит шкатулку, которую сможет открыть он, и только он.

Вариант 2. Допустим, мы хотим с приятелем загадать какой-нибудь цвет так, чтобы мы оба его знали, а никто кроме - нет, но у нас нет надёжного канала. У меня есть банка жёлтой краски известного объёма, и у приятеля тоже. Я загадаю какой-нибудь цвет, налью какое-то количество такой краски в банку и хорошо перемешаю. Приятель тоже. Мы обменяемся банками, и каждый повторит с полученной банкой ту же операцию. В результате у каждого будет в банке одинаковый цвет, но никто, перехватив в пути банку, или даже обе, не сможет ничего поделать.

Предположим, что обоим абонентам известны некоторые два числа g и p (например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент - число a, второй абонент - число b. Затем первый абонент вычисляет значение A = gamod p и пересылает его второму, а второй вычисляет B = gbmod p и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение Bamod p = gabmod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение Abmod p = gabmod p. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K = gabmod p. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления gabmod p по перехваченным gamod p и gbmod p, если числа p,a,b выбраны достаточно большими.

Рис.9 Алгоритм Диффи-Хеллмана

Алгоритм Диффи - Хеллмана, где K - итоговый общий секретный ключ

При работе алгоритма, каждая сторона:

1. генерирует случайное натуральное число a - закрытый ключ

2. совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

· p является случайным простым числом

· g является первообразным корнем по модулю p

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

A = ga mod p

4. обменивается открытыми ключами с удалённой стороной

5. вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a

K = Ba mod p

К получается равным с обеих сторон, потому что:

Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p

В практических реализациях, для a и b используются числа порядка 10100 и p порядка 10300. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

Криптографическая стойкость алгоритма Диффи - Хеллмана (то есть сложность вычисления K=gab mod p по известным p, g, A=ga mod p и B=gb mod p), основана на предполагаемой сложности проблемы дискретного логарифмирования. Однако, хотя умение решать проблему дискретного логарифмирования позволит взломать алгоритм Диффи - Хеллмана, обратное утверждение до сих является открытым вопросом (другими словами, эквивалентность этих проблем не доказана).

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

Заключение

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

В 1976 г. У.Диффи и М.Хеллманом был предложен новый тип криптографической системы - система с открытым ключом. В схеме с открытым ключом имеется два ключа, открытый и секретный, выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений. Шифрующая процедура использует открытый ключ, дешифрующая - секретный. Дешифрование кода без знания секретного ключа практически неосуществимо; в частности, практически неразрешима задача вычисления секретного ключа по известному открытому ключу. Основное преимущество криптографии с открытым ключом - упрощенный механизм обмена ключами. При осуществлении коммуникации по каналу связи передается только открытый ключ, что делает возможным использование для этой цели обычного канала и устраняет потребность в специальном защищенном канале для передачи ключа.

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

Цифровая подпись используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Она аналогична обычной рукописной подписи и обладает ее основными свойствами: удостоверяет, что подписанный текст исходит именно от лица, поставившего подпись, и не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным текстом. Цифровая подпись представляет собой небольшое количество дополнительной информации, передаваемой вместе с подписываемым текстом. В отличие от шифрования, при формировании подписи используется секретный ключ, а при проверке - открытый.

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

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

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