Информационные технологии становятся неотъемлемой частью жизни каждого из нас. Мы передаем информацию через интернет, храним ее на своих компьютерах, пользуемся электронной почтой, оплачиваем покупки с помощью электронных денег… Вследствие этого возникает проблема — как передать нужную информацию нужному адресату втайне от других?
На сегодняшний день защита информации с помощью криптографических методов считается одной из самых надежных, т. к. эти методы решают проблемы, возникающие не только при хранении, но и при передаче информации. Но их слабым местом всегда была проблема передачи ключей.
Решение этой проблемы было найдено в середине 70-х годов XX века. Тогда были предложены криптосистемы с открытым ключом. Концепция криптографии с открытым ключом была предложена в 1976 г. У. Диффи и М. Хеллманом в работе «Новые направления в криптографии». В криптосистеме с открытым ключом для шифрования и расшифрования используются различные ключи. Общая идея такой системы заключается в использовании при зашифровке сообщения такой функции от открытого ключа и сообщения, которую очень трудно обратить. Это обеспечивает более высокую криптостойкость системы.
Достоинства асимметричных криптосистем:
- секретный ключ известен только одной стороне;
- секретный ключ не нужно передавать;
- ключи можно долго не менять;
Недостатки асимметричных криптосистем:
- более высокие затраты времени и других ресурсов;
- более длинные ключи;
- сложнее внести изменения.
Появление асимметричной криптографии открыло сразу несколько новых прикладных направлений, в частности системы электронной цифровой подписи (ЭЦП) и электронных денег.
Итак, криптосистема с открытым ключом (или двухключевая криптосистема, асимметричная криптосистема) — система шифрования и/или электронной цифровой подписи, при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки электронной цифровой подписи и для шифрования сообщения. Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, которые обладают следующими свойствами:
- Если известно x, то f(x) вычислить относительно просто
- Если известно y=f(x), то для вычисления x нет простого (эффективного) пути.
В асимметричных криптосистемах для шифрования используется один ключ, а для расшифрования — другой. Первый ключ является открытым и может быть опубликован для использования всеми пользователями системы, которые зашифровывают данные. Расшифрование данных с помощью открытого ключа невозможно. Для расшифрования данных получатель зашифрованной информации использует второй ключ, который является секретным. Разумеется, ключ расшифрования не может быть определен из ключа шифрования. Раскрытие секретного ключа по известному открытому ключу должно быть вычислительно неразрешимой задачей.
RSA — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Аббревиатура RSA образована от первых букв фамилий предложивших его авторов: Ronald Rivest, Adi Shamir, Leonard Adleman. В общем случае, криптосистема RSA относится к шифрам простой замены.
Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования за разумное время (обратной операции) необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложения числа на простые множители.
В RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их.
Алгоритм создания ключей:
1. Выбираются два больших простых числа p и q (держатся в секрете).
2. Вычисляется модуль n=p∙q и функция Эйлера φ(n)=(p-1)(q-1).
3. Выбирается целое число e, взаимно простое со значением функции Эйлера от числа n из интервала (1; φ(n)).
4. Вычисляется d, учитывая, что e и d имеют мультипликативную обратную связь, т. е. e∙d=1(modφ(n)).
5. Пара чисел е и n публикуется как открытый ключ шифрования, а d сохраняется как закрытый (секретный) ключ.
6. Размер ключа связан с размером модуля n. Два числа p и q, произведением которых является модуль, должны иметь приблизительно одинаковую длину, поскольку в этом случае найти сомножители (факторы) сложнее, чем в случае, когда длина чисел значительно различается.
7. Если два числа чрезвычайно близки друг к другу или их разность близка к некоторому предопределенному значению, то возникает потенциальная угроза безопасности, однако такая вероятность — близость двух случайно выбранных чисел — незначительна.
Без ограничения общности положим p > q.
Возьмем Y = (p+q)/2 и X = (p-q)/2.
n = p*q = Y2 — X2.
Имеем Y = sqrt (n –X2).
Таким образом, значения p и q можно легко найти, если разность p — q достаточно мала.
Оптимальный размер модуля определяется требованиями безопасности: модуль большего размера обеспечивает большую безопасность, но и замедляет работу алгоритма RSA. Длина модуля выбирается в первую очередь на основе значимости защищаемых данных и необходимой стойкости защищенных данных и во вторую очередь — на основе оценки возможных угроз.
При шифровании сообщение разбивается на блоки длиной меньше разрядности n. Зашифрованное сообщение будет состоять из блоков той же длины.
Шифрование производится по следующей формуле:
C = E (e,n) (M) = Me (mod n), где E(e,n) — преобразование, а (e,n) — ключ зашифрования.
Для расшифрования используется то же преобразование, только с другим показателем степени:
M = D (d,n) (C) = Cd (mod n), где D(d,n) — преобразование, а (d,n) — ключ расшифрования.
Для вычисления числа d нужно использовать расширенный алгоритм Евклида, который работает только если числа e и φ(n) взаимно просты. Вычисление числа d сводится к решению уравнения φ(n)*x+e*d = 1 в натуральных числах. Число x не существенно.
Алгоритм RSA выполняет следующие задачи: обеспечения целостности и конфиденциальности информации, обеспечения аутентификации, обеспечения отказа от авторства или приписывания авторства.
Для проведения криптоанализа с помощью алгоритма RSA был зашифрован текст. Исходный текст имеет следующий вид:
Коротышки были неодинаковые: одни из них назывались малышами, а другие — малышками. Малыши всегда ходили либо в длинных брюках навыпуск, либо в коротеньких штанишках на помочах, а малышки любили носить платьица из пестренькой, яркой материи. Малыши не любили возиться со своими прическами, и поэтому волосы у них были короткие, а у малышек волосы были длинные, чуть не до пояса. Малышки очень любили делать разные красивые прически, волосы заплетали в длинные косы и в косы вплетали ленточки, а на голове носили бантики. Многие малыши очень гордились тем, что они малыши, и совсем почти не дружили с малышками. А малышки гордились тем, что они малышки, и тоже не хотели дружить с малышами. Если какая-нибудь малышка встречала на улице малыша, то, завидев его издали, сейчас же переходила на другую сторону улицы. И хорошо делала, потому что среди малышей часто попадались такие, которые не могли спокойно пройти мимо малышки, а обязательно скажут ей что-нибудь обидное, даже толкнут или, еще того хуже, за косу дернут. Конечно, не все малыши были такие, но ведь этого на лбу у них не написано, поэтому малышки считали, что лучше заранее перейти на другую сторону улицы и не попадаться навстречу. За это многие малыши называли малышек воображульками — придумают же такое слово! — а многие малышки называли малышей забияками и другими обидными прозвищами.
Длина текста 1428 знаков с пробелами. Текст состоит из букв русского алфавита верхнего и нижнего регистра и знаков препинания.
Гистограмма открытого текста представлена на Рисунке 1.
Рис. 1. Гистограмма открытого текста
Из гистограммы можно увидеть частоту встречаемости букв в данном литературном тексте.
Если разбить текст на биграммы, то их получится 570. На Рисунке 2 приведена диаграмма для полученных биграмм.
Рис. 2. Диаграмма биграмм открытого текста
Шифрование и расшифрование текста с помощью RSA производилось с использованием следующих ключей: {17053, 86041} — открытый ключ, {8977, 86041} — закрытый ключ. Длина зашифрованного текста составляет 3336 знаков с пробелами. Возьмем за шифробозначения блоки, разделенные пробелами. Всего 570 шифробозначений. Гистограмма зашифрованного текста представлена ниже на Рисунке 3.
Рис. 3. Гистограмма зашифрованного текста
Разобьем текст на биграммы (всего 285 биграмм) и построим диаграмму. Т. к. повторения биграмм попадаются очень редко, укажем на ней только те, которые встречаются больше одного раза (Рис. 4).
Рис. 4. Диаграмма биграмм зашифрованного текста
Криптоанализ шифртекста, полученного с помощью шифра RSA.
Существует несколько способов взлома шифра RSA:
1. Попытка найти закрытый ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом и подделывать подписи. Для выполнения такой задачи необходимо найти сомножители p и q, что является сложной задачей, если ключи выбраны в соответствии с требованиями.
2. Поиск метода вычисления корня степени e из mod n. Т. к. С = Me (mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная закрытый ключ. Но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом, если ключ имеет большой размер.
3. Атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст, например, «Дальнейшие инструкции завтра», затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов.
4. Если кто-то посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3, нападающий может перехватить эти сообщения и расшифровать сообщение M. Такую атаку можно предотвратить, вводя в сообщение перед каждым шифрованием несколько случайных бит.
5. Также существуют несколько атак по зашифрованному тексту (или атаки отдельных сообщений с целью подделки подписи), при которых нападающий создает некоторый зашифрованный текст и получает соответствующий открытый текст, например, заставляя обманным путем зарегистрированного пользователя расшифровать поддельное сообщение.
Кроме вышеперечисленного нужно соблюдать все необходимые требования безопасности, чтобы секретные ключи оставались в секрете, т. к. злоумышленник может попробовать завладеть ими, если система должным образом не защищена.
Поиск закрытого ключа, соответствующего необходимому открытому ключу. Закрытый ключ является произведением простых чисел p и q, поэтому нам необходимо найти эти сомножители. Для этого можно воспользоваться методом факторизации Ферма.
Метод основан на поиске таких целых чисел x и y, которые удовлетворяют соотношению x2-y2=n, что ведёт к разложению n=(x-y)(x+y). Рассмотрим алгоритм поиска простых сомножителей по методу факторизации Ферма:
x2-y2=n равносильно x2-n= y2
Найдем 
– наименьшее число, при котором разность x2-n неотрицательна. Для этого для каждого значения k∈N, начиная с k=1, будем вычислять 
до тех пор, пока значение этого выражения не будет являться точным квадратом. Таким образом, находим k, а затем вычисляем 
и 
. Полученные x и y являются искомыми простыми сомножителями.
Для обеспечения высокой надежности алгоритма RSA необходимо, чтобы используемые ключи соответствовали ряду требований:
- размеры ключей должны быть очень большими (рекомендовано 1024 бит, для особо важной информации — 2048 бит);
- числа p и q должны иметь приблизительно одинаковую длину, поскольку в этом случае найти сомножители (факторы) сложнее, чем в случае, когда длина чисел значительно различается;
- если разность p — q достаточно мала, то их очень легко найти, следовательно, их значения не должны быть близки друг к другу.
Так как компьютер, который был использован для шифрования, имеет невысокие возможности, были выбраны небольшие ключи, поэтому вскрыть текст возможно (число 17053 легко раскладывается на множители).
Итак, алгоритм RSA является достаточно криптостойким шифром. Трудоемкость криптоанализа обеспечивается сложностью нахождения простых сомножителей закрытого ключа. В зависимости от защищаемых данных определяется длина ключа для обеспечения необходимой криптостойкости.
В настоящее время криптографическая система RSA получила широкое распространение. Она была первой системой, пригодной и для шифрования, и для цифровой подписи. Сейчас она используется в большом числе криптографических приложений, также ее используют в сочетании с симметричными криптосистемами.
Наука не стоит на месте. Вычислительные машины становятся еще мощнее, с их помощью можно решать все более и более сложные задачи. Поэтому и криптография должна постоянно совершенствовать свои методы, чтобы суметь противодействовать злоумышленникам.
Литература:
1. Бутакова Н. Г., Семененко В. А., Федоров Н. В. Криптографическая защита информации: Учебное пособие. — М.:МГИУ, 2011. — 316 с.
2. Введение в криптографию / Под общей редакцией В. В. Ященко. — 3-е изд., доп. — М.: МЦНМО: «ЧеРо», 2000. — 288 с.
3. Коутинхо С.. Введение в теорию чисел. Алгоритм RSA. — М.: Постмаркет, 2001. — 328 с.
4. Словарь криптографических терминов / Под редакцией Б. А. Погорелова и В. Н. Сачкова.- М: МЦНМО, 2006.
5. Математическая криптография [Электронный ресурс].- Режим доступа: http://cryptography.ru/
