Системы с открытым ключом: алгоритм шифрования RSA
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
подходы, иногда дающие возможность взломать данное конкретное сообщение. Простейший из них - угадывание оригинала. Злоумышленник видит шифр, догадывается, что в сообщении написано Стреляй в Бориса, зашифровывает свою версию известным открытым ключом и сравнивает с шифровкой. Еще один подход основан на свойствах преобразования RSA. Если одно и то же сообщение посылается e разным получателям (где е не основание натурального логарифма, а открытая экспонента), то злоумышленник, перехвативший все е шифровок, сможет восстановить исходное сообщение.
Практическая реализация RSA
Практическая реализация RSA сопряжена с определенными проблемами. Первая и, пожалуй, главная из них - вычислительная сложность алгоритма. По сравнению с большинством симметричных криптосистем RSA работает в несколько сот раз медленнее. При обычной реализации генерация ключа длины k требует O(k4) операций; шифрование - O(k2), а расшифровывание- O(k3) операций. Наиболее быстрая из чисто программных реализаций (bSafe 3.0, RSA Data Security) осуществляет шифрование со скоростью 21.6 Kбит/сек для 512-битного ключа. Это очень быстро если представить себе операции с числами из 150 знаков, но само по себе это конечно же медленно. Поэтому обыкновенно системы с открытым ключом используют в сочетании с какой-нибудь симметричной системой - например, DES. Допустим, Александр хочет послать Борису сообщение. Для этого он генерирует случайный ключ DES и шифрует им текст сообщения. После этого он берет открытый ключ Бориса и шифрует им ключ DES. То, что получается в результате, носит название двоичного конверта(digital envelope) и сочетает в себе лучшее из обоих принципов - скорость симметричных систем и удобство использования систем с открытым ключом. Двоичный конверт можно безопасно передавать по линиям связи - используя свой закрытый ключ, Борис сначала восстановит ключ DES, а соответственно и текст исходного сообщения.
Обычной практикой является выбор не слишком большого e - это не отражается на криптостойкости алгоритма, но существенно ускоряет шифрование. Тем не менее, d почти всегда оказывается велико. Поэтому возводить при дешифровании cd обычно оказывается не самой лучшей идеей. К счастью, использование Китайской теоремы об остатках позволяет существенно понизить порядок возведения в степень, а также свести вычисления по модулю n к вычислениям по модулю p и q. Подробнее об этом см. у Е. Бубновой [2]. Результаты несложного теста, проведенного нами с помощью нашей (весьма медленной) реализации RSA приведены в таблице и позволяют наглядно увидеть, почему надо пользоваться Китайской теоремой об остатках и не надо ничего возводить в степень в лоб.
Размер файла (байты)Время шифрования (сек)Время дешифрования (сек)256 512 1024 204812 24 49 995 10 17 34
При шифровании мы использовали метод последовательного возведения в квадрат, а при дешифровании - теорему об остатках. В результате шифрование оказалось примерно в 2.5 раза медленнее дешифрования!! То есть, грубо говоря, возведение в степень 30-40 занимает втрое больше времени, чем в степень 1,000,000,000.
Еще одна сложная проблема, связанная с реализацией алгоритма - это генерация p и q. Самый примитивный вариант - решето Эратосфена - хорошо работает для чисел длиной знаков 10, не более. Для генерации пригодного к использованию ключа в 150 знаков этот метод не работает. Фирма RSA Data Security рекомендует использовать вероятностный подход - то есть, генерировать не на самом деле простые числа, а те, для которых вероятность того, что они составные, меньше наперед заданной малой величины. Существуют хорошие алгоритмы, позволяющие доказать это для заданного числа - или показать, что оно составное. Однако если тестируемое число на самом деле окажется составным, криптостойкость RSA падает. Поэтому альтернативой этому является использование намного более медленных тестов, позволяющих абсолютно точно сказать простое это число или составное. Классическая группа таких тестов основана на знании простых множителей для p-1 или p+1; если их можно найти, то появляется возможность доказать или опровергнуть простоту p. Вообще проблема доказательства простоты достаточно сложна, но совершенно не эквивалентна разложению чисел на множители, так что за приемлемое время всегда можно найти нужные p и q.
Обоснование алгоритма
Сначала выведем некоторые важные свойства остатков. Через a=resnx будем обозначать остаток от деления n на x; эквивалентная этому запись x=a mod n. Все числа считаются целыми и неотрицательными.
Свойства остатков
Пусть x = a mod n; y = b mod n; Тогда resnxy = resnab
x=un+a; y=vn+b;
Следовательно,
xy=(un+a)(vn+b)=uvn2+avn+bun+ab;
resnxy=resnab
Пусть x = a mod n; y = b mod n; Тогда resn(x+y) = resn(a+b)
Пусть x = a mod n; Тогда resn(xm) = resn(am)
= resn(x*x*тАж*x) = resn(a*a*тАж*a) = resn(am)
Пусть x<n. Тогда resnx=x (resn(x)) = resnx
Пусть n=pq; Тогда resp(resnx) = respx
Следующие два утверждения приводятся без доказательства.
Теорема Эйлера
Пусть p - простое, a<p. Тогда , где - к-во чисел < n и вз. простых с n; криптосистема открытый ключ
Лемма
Если n = pq, p и q простые, то
Функция называется функцией Эйлера. Следующая теорема использует эти результаты для доказательства возможности найти d; ее доказательство представляет практический способ его нахождения.
Теорема
Пусть e взаимно просто с . Тогда уравнение имеет единственное решение u <
Существование.
Так как НОД(e, )=1, то
Возможны два случая:>0, v0.
Рассмотрим
&