Рассмотрим работу асимметричного RSA . Он был предложен тремя математиками Рональдом Ривестом (R. Rivest ), Ади Шамиром (A. Shamir ) и Леонардом Адльманом (L. Adleman ) в 1978 году.

Под простым числом будем понимать такое число, которое делится только на 1 и на само себя. Эвклид в своих «Началах» показал, что для любого простого числа есть большее простое число, то есть количество простых чисел бесконечно.

Доказательство. Допустим, что существует наибольшее простое число p , определим произведение всех простых чисел P =2∙3∙5∙7∙…∙p .

Рассмотрим число P +1. Оно или само является простым числом большим p или произведением простых чисел, которые больше P . Мы пришли к противоречию, значит количество простых чисел бесконечно.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

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

Наконец, под результатом операции i mod j будем считать остаток от целочисленного деления i на j. Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги.

1. Выберем два очень больших простых числа р и q .

2. Определим n как результат умножения р на q (n=p·q).

3. Выберем большое случайное число, которое назовем d . Это число должно быть взаимно простым с результатом умножения (р – 1) · (q – 1).

4. Определим такое число е , для которого является истинным следующее соотношение (е·d) mod ((p – 1) · (q – 1)) = 1.

5. Назовем открытым ключом числа е и n , а секретным ключом – числа d и n .

Теперь, чтобы зашифровать данные по известному ключу {е, n }, необходимо сделать следующее:

– разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i) ;

– зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле С(i) = (M(i) e) mod n . Чтобы расшифровать эти данные, используя секретный ключ {d, n}, необходимо выполнить следующие вычисления: M(i)=(C(i) d) mod n . В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Алгоритм RSA основан на одной из доказанных теорем Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q , то для любого x имеет место равенство

x (p-1)(q-1) mod n = 1.

Для дешифрования RSA- сообщений воспользуемся этой формулой. Для этого возведем обе ее части в степень (-y ):

(x (- y)(p-1)(q-1)) mod n = 1 (- y) = 1.

Теперь умножим обе ее части на x:

(x (-y)(p-1)(q-1)+1) mod n = 1· x = x.

Вспомним теперь, как создавались открытый и закрытый ключи. Мы подбирали d такое, что

e·d+(p-1)(q-1) ·y = 1,

e·d = (-y)(p-1)(q-1)+1.

Следовательно, в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e·d). Получаем (x e · d) mod n = x . Для того чтобы прочесть сообщение c i = ((m i) e)mod n достаточно возвести его в степень d по модулю m :

((c i) d)mod n = ((m i) e · d) mod n = m i .

Приведем простой пример использования метода RSA для шифрования сообщения «CAB». Для простоты будем использовать очень маленькие числа (на практике используются большие числа).

1. Выберем р= 3и q= 11.

2. Определим n= 3· 11=33.

3. Найдем (р–1) (q–1)= 20. В качестве d выберем любое число, которое является взаимно простым с 20, например d= 3.

4. Выберем число е . В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е· 3) mod 20 = 1,
например 7.

5. Представим шифруемое сообщение как последовательность целых чисел в диапазоне 0...32. Пусть буква А изображается числом 1, буква В – числом 2, а буква С – числом 3. Тогда сообщение можно представить в виде последовательности чисел 312. Зашифруем сообщение, используя ключ {7, 33}:

С(1)=(З 7) mod 33 = 2187 mod 33 = 9,

С(2) = (1 7) mod 33 = 1 mod 33 = 1,

С(З) = (2 7) mod 33 = 128 mod 33 = 29.

6. Попытаемся расшифровать сообщение {9, 1, 29}, полученное в результате зашифровывания по известному ключу, на основе секретного ключа {3, 33}:

M(1) = (9 3) mod 33 = 729 mod 33 = 3,

М(2) = (1 3) mod 33 = 1 mod 33 = 1,

М(З) = (29 3) mod 33 = 24389 mod 33 = 2.

Таким образом, в результате расшифровывания сообщения получено исходное сообщение «CAB».

Криптостойкость алгоритма RSA основывается на предположении, что исключительно трудно определить секретный ключ по известному открытому, поскольку для этого необходимо решить задачу о существовании делителей целого числа. Данная задача не допускает в настоящее время эффективного (полиномиального) решения. В связи с этим для ключей, состоящих из 200 двоичных цифр (а именно такие числа рекомендуется использовать), традиционные методы поиска делителей требуют выполнения огромного числа операций (около 10 23).

Криптосистема RSA используется в самых различных платформах и во многих отраслях. Она встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении алгоритм RSA применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании фирмы Zaxus (Rasal). Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах.

Технологию шифрования RSA BSAFE используют более 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего ключа в мире, и это количество имеет явную тенденцию к увеличению по мере роста пользователей Internet.

Алгоритм шифрования с открытым ключом RSA был предложен одним из первых в конце 70-х годов ХХ века. Его название составлено из первых букв фамилий авторов: Р.Райвеста (R.Rivest), А.Шамира (A.Shamir) и Л.Адлемана (L.Adleman). Алгоритм RSA является, наверно, наиболее популярным и широко применяемым асимметричным алгоритмом в криптографических системах.

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

1. задача проверки числа на простоту является сравнительно легкой;
2. задача разложения чисел вида n = pq (р и q - простые числа); на множители является очень трудной, если мы знаем только n , а р и q - большие числа (это так называемая задача факторизации, подробнее о ней см. "Основные положения теории чисел, используемые в криптографии с открытым ключом").

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные должны быть представлены в виде целых чисел между 0 и n -1 для некоторого n .

Шифрование

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

Первым этапом является генерация открытого и закрытого ключей. Для этого вначале выбираются два больших простых числа Р и Q . Затем вычисляется произведение N :

После этого определяется вспомогательное число f :

f = (Р - l)(Q - 1).

Затем случайным образом выбирается число d < f и взаимно простое с f .

Числа d и N будут открытым ключом пользователя, а значение е – закрытым ключом.

Таким образом, на этом этапе у пользователя должна быть информация, указанная в следующей таблице:

Так как пользователь Б хочет получить зашифрованное сообщение от пользователя А, значит пользователь Б должен отправить свой открытый ключ (d, N) пользователю А. Числа Р и Q больше не нужны, однако их нельзя никому сообщать; лучше всего их вообще забыть.

На этом этап подготовки ключей закончен и можно использовать основной протокол RSA для шифрования данных.

Второй этап – шифрование данных . Если абонент А хочет передать некоторые данные абоненту Б, он должен представить свое сообщение в цифровом виде и разбить его на блоки m 1 , m 2 , m 3 , ... , где m i < N . Зашифрованное сообщение будет состоять из блоков с i .

Абонент А шифрует каждый блок своего сообщения по формуле

c i = m i d mod N

используя открытые параметры пользователя Б, и пересылает зашифрованное сообщение С=(с 1 , с 2 , с 3 , ...) по открытой линии.

Абонент Б, получивший зашифрованное сообщение, расшифровывает все блоки полученного сообщения по формуле

Все расшифрованные блоки будут точно такими же, как и исходящие от пользователя А.

Злоумышленник, перехватывающий все сообщения и знающий всю открытую информацию, не сможет найти исходное сообщение при больших значениях Р и Q .

Пример вычислений по алгоритму

Пусть пользователь А хочет передать пользователю Б сообщение. В этом случае вначале пользователь Б должен подготовить открытый и закрытый ключи. Пусть им выбраны, например, следующие параметры:

Р = 3, Q = 11, N = 3x11 = 33.

Тогда f = (Р - l)(Q - 1) = (3-1)(11-1) = 20 .

Затем пользователь Б выбирает любое число d , не имеющее общих делителей с f (это необходимо для того, чтобы зашифрованное сообщение можно было потом однозначно восстановить). Пусть d = 13 . Это число будет одним из компонентов открытого ключа.

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

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

Алгоритм RSA

Шифрование с использованием публичного ключа

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

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

Демо-программа на базе алгоритма RSA

Не все пользователи персональной компьютерной техники знают и понимают, что такое RSA-шифрование и при звучании этого термина удивляются. Но ничего сложного в этом понятии не таится. RSA-шифрование — это все лишь криптосистема, которая позволяет в безопасном ключе использовать все электронные данные, создаваемые на компьютерной технике. Это не дешифрование данных, когда файлы невозможно прочесть, не зная определенного кода. RSA-шифрование подразумевает открытость ключей.

RSA-шифрование работает по принципу факторинга. Как это? А это факторинговое
воспроизведение двух больших числовых данных.

Кто создал систему RSA-шифрования?

Алгоритм RSA-шифрования был создан еще в 1977 году, его создателями являются ученые Ривест, Шамир, Адлеман, аббревиатура из начальных букв фамилий составляет термин RSA. Более ранний алгоритм проработал Клиффорд Кокс, математик из Англии, который работал на спецслужбы страны. В 1973 году ему удалось создать эквивалентную систему, но нею пользовались исключительно засекреченные лица, и методика не распространялась на уровне обычных пользователей персональной компьютерной техники.

Как работает RSA-шифрование?

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

Сегодня RSA-шифрование характеризуют как не слишком надежный метод шифрования данных. Это медленный алгоритм, поэтому он не настолько распространен в среде рядовых пользователей компьютеров. Так для чего же тогда создана эта система, если ею практически не пользуются рядовые компьютерщики?

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

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

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

Цифровая подпись и связь с открытыми ключами

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

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

Электронная подпись тесно связана с рассматриваемым RSA-шифрованием. Эта система, как уже упоминалось выше, предполагает наличие открытого ключа. Сегодня используется на практике два ключа – открытый – известный всем и закрытый – зашифрованный с целью недопущения к информации посторонних лиц.

Таким образом, открытый ключ позволяет получить доступ к документу с электронной печатью, а закрытый – расшифровать подпись и проверить ее. Иными словами RSA-шифрование позволяет скрывать документы от посторонних глаз, засекретить их, но с возможностью получения к ним доступа в нужный момент.

Давайте разберемся, в чем суть придуманного алгоритма?

RSA-шифрование работает по принципу четырех этапов:
генерация ключей;
распределение ключей;
шифрование ключей;
дешифрование ключей.

Принцип RSA-шифрования объединяет создание открытых и закрытых ключей. Еще раз на этом остановимся. Открытый – известен всем, может использоваться для шифровки сообщений. Эти электронные данные можно расшифровать с помощью секретного ключа. При создании от крытых ключей выбираются случайные и одинаковые по величине числа, но разные по продолжительности записи, чтобы факторинг был сложнее.

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

Слабые стороны методики RSA-шифрования

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

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

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

Дополнительные составляющие, обеспечивающие безопасность использования RSA-шифрования

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

RSA-шифрование разлаживает математические числа на множители, но до совершенства механизм доведен так и не был. Поэтому на данный момент у злоумышленников остается возможность и множество лазеек для подбора методик взлома шифрования данных. И удается им это делать именно механизму восстановления простых множителей.

Мошенники вычисляют секретный показатель, содержащийся в открытом ключе, и расшифровывают документацию стандартным методом. Так что поле действий для тех, кто реально хочет навредить какой-то компании, существенно большое. Скажем так, проблема безопасности RSA-шифрования до сих пор остается актуальной и открытой, хотя все гласно о ней мало кто говорит.

Автоматизированный процесс шифрования электронных данных

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

Программное обеспечение Yafu позволяет выполнять шифрование электронных данных в автоматическом режиме. Эта программка позволяет быстро находить данные для создания ассиметричных ключей, соблюдая правила надежности факторинга. Она сочетается в работе с такими процессорами, как SIQS , ECM, SNFS. Запускается она через командную строку. Введение этой команды в строку позволяет сократить время поиска данных для создания ключей в разы.

С этим программным обеспечением не справится рядовой пользователь персональной компьютерной техники. Для его установки и настройки требуются определенные знания и этим занимаются зачастую ИТ-программисты, специалисты.

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

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

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

Конечно же, для взлома RSA-шифрования требуется время. Многие хакеры тратят годы для достижения положительного результата. Зачастую это высокооплачиваемые перспективы, которые подогревают интерес к продолжению поиска нужного ключа. В большинстве то случаев от взлома длинных ключей отказываются в поисках более простых перспектив. Но, это не означает, что никто не пытается создать более упрощенный механизм взлома ключей.

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

Заключение

Исходя из выше сказанного RSA-шифрование – это безопасный метод сохранения конфиденциальности электронных данных при условии создания длинных и информационно объемных ключей.

Вручную их сложно подбирать, поэтому используется автоматизированный программный продукт Yafu. Его установкой и настройкой занимаются ИТ-специалисты. Самостоятельная работа может привести к поломке операционной системы компьютера.
Это программное обеспечение рассчитано на работу в тандеме с многоядерными компьютерными процессорами современного поколения.

Основными объектами мошеннических атак являются крупные промышленные и финансовые компании, поэтому без RSA-шифрования их электронный документооборот не работает. Электронная подпись документов также подлежит шифрованию, и к ней применимы такие же стандарты безопасности, как и для иных информационных данных. Принцип – чем больше ключ, тем сложнее взломать документ — должен быть применим абсолютно ко всем данным, которые не предназначены для общего пользования.

В зависимости от структуры используемых ключей методы шифрования подразделяются на:

• симметричное : посторонним лицам может быть известен алгоритм шифрования, но неизвестна небольшая порция секретной информации - ключа, одинакового для отправителя и получателя сообщения; Примеры: DES, 3DES, AES, Blowfish, Twofish, ГОСТ 28147-89
• асимметричное шифрование: посторонним лицам может быть известен алгоритм шифрования, и, возможно открытый ключ, но неизвестен закрытый ключ, известный только получателю. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), а так же SSH, PGP, S/MIME и т. д. Российский стандарт, использующий асимметричное шифрование - .

На данный момент асимметричное шифрование на основе открытого ключа RSA (расшифровывается, как Rivest, Shamir and Aldeman - создатели алгоритма) использует большинство продуктов на рынке информационной безопасности.

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

Рассмотрим алгоритм RSA с практической точки зрения.

Для начала необходимо сгенерировать открытый и секретные ключи:

• Возьмем два больших простых числа p and q.
• Определим n, как результат умножения p on q (n= p*q).
• Выберем случайное число, которое назовем d. Это число должно быть взаимно простым (не иметь ни одного общего делителя, кроме 1) с результатом умножения (p-1)*(q-1).
• Определим такое число е, для которого является истинным следующее соотношение (e*d) mod ((p-1)*(q-1))=1.
• Hазовем открытым ключем числа e и n, а секретным - d и n.

Для того, чтобы зашифровать данные по открытому ключу {e,n}, необходимо следующее:

• разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0,1,2..., n-1(т.е. только до n-1).
• зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле C(i)=(M(I)^e)mod n.

Чтобы расшифровать эти данные, используя секретный ключ {d,n}, необходимо выполнить следующие вычисления: M(i) = (C(i)^d) mod n. В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Следующий пример наглядно демонстрирует алгоритм шифрования RSA:

Зашифруем и расшифруем сообщение "САВ" по алгоритму RSA. Для простоты возьмем небольшие числа - это сократит наши расчеты.

• Выберем p=3 and q=11.
• Определим n= 3*11=33.
• Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
• Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно, например, 7: (e=7).
• Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (незабывайте, что кончается на n-1). Буква А =1, В=2, С=3.

Теперь зашифруем сообщение, используя открытый ключ {7,33}

C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;

Теперь расшифруем данные, используя закрытый ключ {3,33}.

M1=(9^3) mod 33 =729 mod 33 = 3(С);
M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);

Данные расшифрованы!