Введение. Применение в криптографии

Применение в криптографии

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

Всеобщий интерес к проблеме разложения на простые множители резко возрос в 1977 году, когда Р. Л. Райвест (R. L. Rivest), А. Шамир (A. Shamir) и Л. Адэлман (L. Adleman) разработали первую систему шифрования с открытым ключом, известную в настоящее время как RSA. В данной системе процедуры зашифрования и расшифрования выполняются на различных ключах. Знание только ключа зашифрования не позволяет расшифровать сообщение, поэтому он не является секретным элементом шифра и обычно публикуется, чтобы любой желающий мог отправить владельцу этого ключа шифрованное сообщение. Зная только открытый ключ, секретный ключ вычислить невозможно. Криптостойкость данной системы основана на трудности разложения больших целых чисел на простые множители. Так как до сих пор не найден эффективный алгоритм разложения чисел на простые множители, этот метод позволяет почти гарантированно защитить засекреченные данные и сообщения в компьютерной сети.

RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.

Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других.

Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

§ Если известно , то вычислить относительно просто

§ Если известно , то для вычисления нет простого (эффективного) пути.

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

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, т.е.:

сообщения , где — множество допустимых сообщений.

допустимых открытого и закрытого ключей и

соответствующие функции шифрования и расшифрования , такие что

Дата добавления: 2015-04-24