[Из песочницы] Выбор параметров шифра RSA и возможные последствия
Под катом описаны примеры выбора «плохих» парметров шифра RSA.Процитируем авторов учебного пособия «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001 г., на странице 316:
«Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля RSA (числа n) для каждого из корреспондентов сети. В связи с этим можно сказать следующее. Читатель может самостоятельно убедиться в том, что зная одну из трех величин p, q или φ (n), можно легко найти секретный ключ RSA…».
Дополним этот текст. При неудачном выборе модуля шифра RSA, как это сделано в примере пособия, приводимом ниже, можно дешифровать текст и без наличия секретного ключа, т.е. не зная ни одной из трех названных величин.
Для этого достаточно располагать зашифрованным текстом, заданным модулем шифра n, открытым ключом е шифра и выполнить всего три шага атаки «бесключевого чтения». После четвертого атакующего шага устанавливается, что на предыдущем шаге был получен исходный текст, он может быть прочитан. Покажем, насколько просто это делается.
Вначале приведем сам пример со стр. 313–315 из названного пособия.
ПримерШифрование короткого исходного текстового сообщения: RSA.Получатель устанавливает шифр с характеристиками n=pq=527, где р=17, q=31 и φ (n)=(р –1)(q — 1)=480. В качестве открытого ключа е выбрано число, взаимно простое с φ (n), е=7. Для этого числа с помощью расширенного алгоритма Евклида найдены целые числа u и v, удовлетворяющие соотношению е∙u+φ (n)∙v=1:480=7∙68+4,7=4∙1+3,4=3∙1+1,1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137, v=2, u=–137.
Поскольку –137≡343(mod480), то d=343.
Проверка: 7∙343=2401≡1(mod480).
Текстовое сообщение представляется в виде последовательности чисел, содержащихся в интервале [0, 526]. Для этого буквы R, S и A кодируются пятиразрядными двоичными числами. Используются порядковые номера этих букв в английском алфавите при их двоичном представлении:
R=1810=(10010)2, S=1910=(10011)2, A=110=(00001)2.
Тогда RSA=(100101001100001)2. Разбиение текста на блоки ограниченной длины дает представление из двух блоков: RSA=(100101001), (100001)=(М1=297, М2=33).
Последовательно шифруются блоки исходного текста М1=297, М2=33: y1=Еk (М1)=М1e≡2977(mod527)=474.
Здесь воспользовались тем, что:
2977=((2972)3)297≡(mod527)=(2003(mod527)297)(mod527)=474, y2=Еk (М2)=M2e≡337(mod527)=407.
Шифрованный текст, как и исходный, получаем в виде двух блоков: у1=474; у2=407.
Расшифрование представляется последовательностью действий Dk (yi)=(yi)d=(yi)343(mod 527), i=1,2.
Вычисления возведения в степень d более удобно проводить, предварительно представляя показатель степени суммой степеней числа 2, а именно: 343=256+64+16+4+2+1.
Используя это представление показателя степени d=343, получаем:
4742≡174(mod527),4744≡237(mod527),4748≡307(mod527),47416≡443(mod527),47432≡205(mod527),47464≡392(mod527),474128≡307(mod527),474256≡443(mod527), и окончательно 474343(mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.
Аналогично вычисляется значение 407343(mod527)=33.
Переход к буквенному представлению расшифрованного сообщения дает: RSA.
После рассмотрения примера в пособии приводятся рассуждения о стойкости системы RSA. Подчеркивается необходимость соблюдения осторожности в выборе модуля шифра RSA (числа n) для каждого из корреспондентов сети. Указывается на недопустимость игнорирования требований к выбираемым характеристикам системы шифрования. Среди таких требований, к сожалению, не указано то, нарушение которого иллюстрирует приведенный пример.
Атака на шифр RSA Рассмотрим пример атаки на шифр RSA. Воспользуемся данными примера, приведенного на странице 313–315 в учебном пособии «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001.Неудачность (недопустимость) выбранных параметров системы в этом примере легко показывается вычислениями, реализующими атаку бесключевого чтения исходного текста. Сущность такой атаки состоит в следующем. Заданы открытый ключ шифра RSA (е=7, n=527) и шифрованный текст. В примере шифрованный текст представлен двумя блоками у=(у1=474, у2=407).
Каждый шифрованный блок атакуется индивидуально, вначале атакуем у1=474, после его дешифрования, атакуем другой блок у2=407.
Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений уi, у1=у имеющийся шифрованный текст.
В алгоритме атаки на шифрованный текст определяется такой номер шага j, для которого yiej (mod n)=(yiej–1(mod n))e (mod n)=yi, i>1. Из последнего соотношения видим, что при возведении в степень е значения (yiej–1(mod n)) получается начальный шифoртекст yi = у1.
Но это и означает, что на этом шаге шифровался открытый текст. Непосредственными вычислениями (их оказывается совсем немного) с использованием экранного калькулятора находим то значение j, при котором цикл шифрования завершается значением y1, с которого цикл и был начат.
Атака на первый блок у1=474 шифртекста.Шаг 1: 4747(mod527)=382; Шаг 2: 3827(mod527)=423; Шаг 3: 4237(mod527)=297; Шаг 4: на этом шаге шифруется уже найденный исходный текст, но его необходимо выполнить, так как атакующий исходного текста не знает. Признаком завершения атаки является совпадение начального значения шифртекста (474) и результата 4-го шага зашифрования. Именно такое совпадение и имеет место.
2977(mod527)=474 получили начальный (первый) блок шифртекста. Атака на первый блок завершена успешно у1=474. Предшествующий результат шага 3 равен открытому тексту М1=297.
По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=297 по модулю n=527. Это записывается так yi=у1=297. Формируем степенные вычеты (((2977(mod527))7(mod527))7(mod527))7=297.
Атака на второй блок у2=407 шифртекста.Шаг 1: 4077(mod527)=16; Шаг 2: 167(mod527)=101; Шаг 3: 1017(mod527)=33; Шаг 4: 337(mod527)=407.
Вновь на третьем шаге получен блок исходного текста (М2=33), но атакующему это неизвестно, и он выполняет следующий (четвертый шаг), результат которого (407) совпадает с начальным шифртекстом у2=407.
По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=33 по модулю n=527. Это записывается так yi=у2=33. Формируем степенные вычеты ((337(mod527))7(mod527))7(mod527)=33.
Результат атаки (исходный текст М1=297, М2=33) получен трехкратным шифрованием заданного шифртекста. Больший успех для атакующего шифртекст трудно представить.
Продолжая обсуждение вопроса о выборе модуля и других параметров шифра, можно добавить, что модуль шифра (n=527) некоторые исходные тексты вообще не позволяет шифровать. При этом выбор значения открытого ключа е большой роли не играет. Существуют значения исходных текстов, которые вообще невозможно зашифровать выбранным шифром с модулем n=527.
Ни на одном из заданных е не удается зашифровать исходные тексты, представляемые числами 187, 341, 154 и 373.
Пример (невозможность шифрования значений некоторых исходных текстов) Пусть исходные тексты представлены четырьмя блоками y=(y1=154, y2=187, y3=341, y4=373). Экспонента е открытого ключа шифра может быть любым взаимно простым числом с функцией Эйлера φ (n)=φ (527)=480. Впрочем, для рассматриваемого случая открытый ключ е может быть задан произвольно. Действительно, пусть е=2, 4, 7, 9, 17, 111 тогда:1542(mod527)=1;1544(mod527)=1;1547(mod527)=154;1549(mod527)=154;15417(mod527)=154;154111(mod527)=154;1872(mod527)=187;1874(mod527)=187;1877(mod527)=187;1879(mod527)=187;18717(mod527)=187;187111(mod527)=187;3412(mod527)=341;3414(mod527)=1;3417(mod527)=341;3419(mod527)=341;34117(mod527)=341;341111(mod527)=341;3732(mod527)=1;3734(mod527)=373;3737(mod527)=373;3739(mod527)=373;37317(mod527)=373;373111(mod527)=373.
Из рассмотренного примера следует простой вывод. Действительно, к выбору параметров процесса шифрования надо подходить очень внимательно и проводить тщательный предварительный анализ таких параметров. Как это делать — отдельный вопрос, и в рамках этой работы он не рассматривается.
