Мбоу «сош №143» г. Красноярска Метапредметный проект «Криптография: алгоритм rsa»
 Скачать 422.14 Kb.
|
3.4. Криптоанализ RSAПроблема различения простых и составных чисел и разложения последних в их главные факторы, как известно, является одной из самых важных и полезных в арифметике. Далее, достоинство самой науки требует, чтобы все возможные средства были исследованы для решения этой проблемы, столь изящной и настолько знаменитой. Карл Фридрих Гаусс «Арифметические исследования» (1801) Почему же тогда систему RSA трудно взломать? Ведь для нахождения р и q всего-то и надо, что разложить на множители число m. Однако, если каждое из простых чисел содержит больше 100 цифр, то время и ресурсы, необходимые для разложения числа m на множители, таковы, что взламывание кода становится очень трудным. Таким образом, ловушка в системе RSA заключается в том, что умножение чисел р и q для получения числа m — простая операция, тогда как обратная задача — разложение числа m на множители для получения р и q — практически неразрешима. Другими словами, мы очень хорошо понимаем, как взломать RSA, однако на практике взлом не реализуем. Не следует забывать, однако, что препятствие носит чисто технологический характер: можно представить себе, что в один прекрасный день развитие компьютеров или изобретение лучших способов разложения на множители сделают систему RSA устаревшей. Подтверждение этому был получено при взломе системы RSA-129. В 1977 году в том же номере Scientific American, где был опубликован алгоритм RSA, известный математик и учёный Мартин Гарднер по согласию авторов алгоритма, опубликовал математическую задачу, получившую название RSA-129. В ней он написал пару чисел (e, m) — открытый ключ, где длина числа m составляла 129 десятичных знаков: m=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541, а е=9007, и само зашифрованное сообщение: 96861375462206147714092225435588290575999112457431987469512093081629822514 5708356931476622883989628013391990551829945157815154. Дешифровавшему сообщение он обещал вознаграждение в $100, которые он положил в банк под 2% годовых. По подсчётам аналитиков, для разложения такого огромного числа на множители при существовавших алгоритмах факторизации и мощности тех компьютеров, потребуется 20.000 лет непрерывной работы (Рон Ривест предполагал 40 квадрильён лет для числа в 125 знаков). В 1994 году молодой криптограф американской армии Арьен Ленстра разработал алгоритм, позволяющий за разумное время найти разложение на простые множители числа до 130 цифр. Сам Ленстра не обладал необходимыми вычислительными мощностями, и тогда он предложил через Интернет добровольцам выделить часть своего процессорного времени на благо математики. Это был один из первых в истории больших проектов, использующих распределённые вычисления. К решению задачи присоединилось 600 человек, предоставив 1600 компьютеров: кроме самых обычных компьютеров участие приняли 3 суперкомпьютера. Далее, в дело вступил метеорологический суперкомпьютер, выделенный самому Ленстре, который за 220 дней непрерывной работы разложил на множители 129-значное число m. Ответ оказался таким: p=3490529510847650949147849619903898133417764638493387843990820577 q=32769132993266709549961988190834461413177642967992942539798288533 Длины чисел p и q оказались 64 и 65 знаков соответственно. Фраза, зашифрованная Мартином Гарднером, была такая: "The Magic Words are Squeamish Ossifrage", что переводится «Магические слова – брезгливый стервятник». Из $100 по процентам за 17 лет получилось примерно $140, которые и были переданы в фонд свободного программного обеспечения. Алгоритм RSA тесно связан с задачами теории чисел, которые просто формулируются, но сложно решаются.
ЗАКЛЮЧЕНИЕКриптография сегодня – это наука об обеспечении безопасности данных или, как говорят, информационной безопасности. Шифрование – это основное действие в криптографии, шифрование – это преобразование данных в такую форму или представление, что понять смысл передаваемых или хранимых данных, не обладая специальной дополнительной информацией (криптографическими ключами), невозможно. По определению ISO – международной организации, разрабатывающей стандарты для открытых систем, задачами обеспечения защиты информации являются:
Все эти задачи решаются с помощью применения методов и средств криптографической защиты информации. Криптография существует уже несколько столетий, но только несколько десятилетий как всемирно признанная научная область деятельности. Эти годы являются периодом интенсивного развития как закрытых, так и открытых исследований в различных областях математики с точки зрения применения ее в криптографии. Основные результаты работы:
СПИСОК ЛИТЕРАТУРЫ
1 Поли́бий (Рολιβιος, лат. Polybius, ?201 до н. э., Мегалополь, Аркадия — ?120 до н. э.) — греческий историк, государственный деятель и военачальник, писатель 2 Дэвид Кан (англ. David Kahn) — писатель и криптограф США, автор фундаментального труда по истории криптографии «Взломщики кодов», консультант Конгресса США по вопросам криптографии. |