Применение NP-полных задач в ассиметрично-ключевой криптографии (стр. 5 из 6)
Перехваченный зашифрованный текст C
C1 = Ce mod n
C2 = C1e mod n
………………
Ck = Ck-1e mod n
, если Ck = C, останов: исходный текст - P = Ck-1Может ли это быть серьезной атакой на криптосистему RSA? Показано, что сложность алгоритма эквивалентна сложности разложения на множители n. Другими словами, нет никакого эффективного алгоритма, который может завершить эту атаку в полиномиальное время, если n является большим.
· Явная атака сообщения. Другая атака, которая базируется на отношениях перестановки между исходным текстом и зашифрованным текстом, – явная атака сообщения. Явное сообщение – сообщение, которое зашифровано само в себя (не может быть скрыто). Было доказано, что есть всегда некоторые сообщения, которые шифруются сами в себя. Поскольку ключ шифрования обычно нечетен, имеются некоторые исходные тексты, которые зашифрованы сами в себя, такие как P = 0 и P = 1. Но если ключ шифровки выбран тщательно, число их незначительно. Программа шифровки может всегда проверить, является ли вычисленный зашифрованный текст таким же, как исходный текст, и отклонить
исходный текст перед передачей зашифрованного текста. Главной атакой RSA является атака разложения на множители. Ее можно рассматривать как атаку малого модуля. Однако поскольку мы уже обсудили эту атаку, мы концентрируемся на другой атаке модуля: общей атаке модуля.
· Общая атака модуля. Она может быть начата, если сообщество
использует общий модуль, n. Например, люди в сообществе могли бы позволить третьей стороне, которой они доверяют, выбирать p и q, вычислять n и 
и создать пару образцов (ei, di) для каждого объекта. Теперь предположим, что Алиса должна передать сообщение Бобу. Зашифрованный текст Бобу – это 
Боб использует свой секретный ключ, dB, чтобы расшифровывать сообщение: 
. Проблема в том, что Ева может также расшифровать сообщение, если она – член сообщества и ей была назначена пара образцов (eE и dE), как мы узнали в разделе «атака малого значения ключа дешифрации». Используя свои собственные ключи (eE и dE), Ева может начать вероятностную атаку на сомножители n и найти dB Боба. Чтобы сорвать этот тип атаки, модуль не должен быть в совместном пользовании. Каждый объект должен вычислить свой собственный модуль.· Атаки реализации
Предыдущие атаки базировались на основной структуре RSА. Как показал Дэн Бонех (Dan Boneh), есть несколько атак реализации RSА. Мы приведем две из них: атака анализом времени и атака мощности.
· Атака анализом времени (Timing attack). Пауль Кочер (Paul Kocher) демонстрировал атаку только зашифрованного текста, называемую атака анализом времени. Атака основана на быстром алгоритме с показательным временем. Использует только возведение во вторую степень, если соответствующий бит в секретном показателе степени d есть 0; он используется и при возведении во вторую степень и умножении, если соответствующий бит – 1. Другими словами, синхронизация требует сделать каждую итерацию более длинной, если соответствующий бит – 1. Эта разность синхронизации позволяет Еве находить значение битов в d, один за другим.
Есть два метода сорвать атаку анализом времени:
1. добавить случайные задержки к возведению в степень, чтобы каждое возведение в степень занимало одно и то же время;
2. Ривест рекомендовал «ослепление». По этой идее зашифрованный текст умножается на случайное число перед дешифрованием. Процедура содержит следующие шаги:
a. Выбрать секретное случайное число r между 1 и (n – 1).
b. Вычислить
.c. Вычислить P1 = C1d mod n.
d. Вычислить
.· Атака анализом мощности подобна атаке анализом времени. Было показано, что если Ева может точно измерить мощность, использованную в течение дешифрования, она может начать атаку анализа мощности на основании принципов, рассмотренных для атаки анализом времени. Итеративное умножение и возведение в квадрат потребляют больше мощности, чем только итеративное возведение в квадрат. Та же самая группа методов, которая предотвращает атаки анализом времени, может сорвать атаки анализа мощности.
Следующие рекомендации основаны на теоретических и экспериментальных результатах.
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 (modp)
• Определение значения C2 из выражения: C2=e2rP(modp)
• Криптограмма С, состоящая из C1 и C2, отправляется получателю
• Получатель расшифровывает криптограмму с помощью выражения:
P = [C2(C1d)-1]modp
Боб выбирает 11 в качестве p. Затем он выбирает e1 = 2. Обратите внимание, что 2 – первообразный корень в Z11* (см. приложение J). Затем Боб выбирает d = 3 и вычисляет e2 = e1d = 8. Получены открытые ключи доступа – (2, 8, 11) и секретный ключ – 3. Алиса выбирает r = 4 и вычисляет C1 и C2 для исходного текста 7.
Исходный текст: 7
C1 = e1rmod 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', используя следующие шаги: