RSA

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

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

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

Степени, в которые возводятся числа, называются экспонентами (открытой и закрытой). Открытый ключ представляет собой пару чисел - открытая экспонента и модуль, а закрытый ключ состоит из закрытой экспоненты и того же модуля. Модуль является произведением двух больших простых чисел. Проблема взлома алгоритма RSA заключается в разложении модуля на эти сомножители. Чем больше по величине эти простые числа, тем сложнее взломать RSA. Качество ключа RSA измеряется в битах. Используются ключи длиной 512, 1024, 2048 бит и т.д. С удлинением ключа, однако, падает скорость работы алгоритма, поскольку для каждой операции требуется больше тактов процессора.

Как правило, открытая экспонента выбирается произвольно, а закрытая вычисляется на основании открытой экспоненты и модуля по расширенному алгоритму Евклида.