Шифрование и расшифрование по алгоритму RSA

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

2 Практическая реализация системы шифрования RSA

Этапы компьютерной разработки и реализации алгоритма:

Первый этап - постановка задачи и  определение цели программной              реализации. Для осуществления первого этапа необходимо:

– понять, как устроен конкретный объект, каковы его структура и основные свойства;

– научиться управлять процессом и определить наилучшие  способы управления при заданных целях и критериях.

Второй этап – разработка математической модели.

На этом этапе  выделяется существенная информация  об объекте, и выводятся уравнения и формулы, по которым будет строиться  компьютерная программа.

Третий этап – создание алгоритма  решения задачи.

Это творческий и трудно формализуемый процесс. В настоящее время наиболее распространены приемы структурного и объектно-ориентированного  программирования. На этом этапе создается   алгоритм  построения  будущей модели.

Четвертый этап – компьютерная реализация.

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

2.1 Постановка задачи

Безопасность передачи данных по каналам связи является актуальной. Современные компьютерные сети не исключение. К сожалению, в сетевых операционных системах (Windows NT/XP, Novell и т.д.) иностранного производства, как следствие, из-за экспортных соображений уровень алгоритмов шифрования заметно снижен.

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

2.2 Математическое исследование поставленной задачи

В 1978 г. американцы Р. Ривест, А. Шамир и Л. Адлеман (R.L.Rivest. A.Shamir. L.Adleman) предложили пример функции , обла­дающей рядом замечательных достоинств. На её основе была построена реально используемая система шифрования, получившая название по пер­вым буквам имен авторов – система RSA. Эта функция такова, что:

– существует достаточно быстрый алгоритм вычисления значений ;

– существует достаточно быстрый алгоритм вычисления значений об­ратной функции ;

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

Еще до выхода из печати статьи копия доклада в Массачусетском Технологическом институте, посвящённого системе RSA, была послана известному популяризатору математики М. Гарднеру, который в 1977 г. в журнале Scientific American опубликовал статью посвящённую этой системе шифрования. В русском переводе заглавие статьи Гарднера зву­чит так: «Новый вид шифра, на расшифровку которого потребуются мил­лионы лет». Именно эта статья сыграла важнейшую роль в распростране­нии информации об RSA, привлекла к криптографии внимание широких кругов неспециалистов и фактически способствовала бурному прогрессу этой области, произошедшему в последовавшие 20 лет.

Пусть и натуральные числа. Функция реализующая схему RSA, устроена следующим образом

                                                                                                      (1)

Для расшифровки сообщения достаточно решить сравнение

                                                                                                                    (2)

При некоторых условиях на и это сравнение имеет единственное решение .

Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так назы­ваемая функция Эйлера. Эта функция натурального аргумента обозна­чается и равняется количеству целых чисел на отрезке от 1 до , взаимно простых с . Так и для любого простого числа и натурального . Кроме того, для лю­бых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители.

Если показатель степени в сравнении (2) взаимно прост с , то сравнение (2) имеет единственное решение. Для того, чтобы найти его, определим целое число , удовлетворяющее условиям

                                                                                        (3)

Такое число существует, поскольку , и притом единствен­но. Здесь и далее символом будет обозначаться наибольший общий делитель чисел и . Классическая теорема Эйлера, утверждает, что для каждого числа , взаимно простого с , выполняется сравнение и, следовательно.

                                                                                                    (4)

Таким образом, в предположении , единственное решение срав­нения (2) может быть найдено в виде

                                                                                                            (5)

Если дополнительно предположить, что число состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предпо­ложения . Действительно, обозначим и . Тогда делится на , а из (2) следует, что . Подобно (4), теперь легко находим . А кроме того, имеем . Получившиеся сравнения в силу дают нам (5).

Функция (1), принятая в системе RSA, может быть вычислена доста­точно быстро. Обратная к функция вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции (1) будут выполнены указанные выше свойства 1) и 2).

Для вычисления функции (1) достаточно знать лишь числа и . Именно они составляют открытый ключ для шифрования. А вот для вы­числения обратной функции требуется знать число . оно и является «се­кретом», о котором речь идёт в пункте в). Казалось бы. ничего не стоит. зная число . разложить его на простые сомножители, вычислить затем с помощью известных правил значение и, наконец, с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реа­лизованы достаточно быстро, за исключением первого. Именно разложе­ние числа на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю её историю и на очень интенсивные поиски в течение последних 20 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до , и. деля на них , найти требуемое разложение. Но, учитывая, что количество простых в этом промежутке, асимптотически равно , на­ходим, что при , записываемом 100 десятичными цифрами, найдётся не менее простых чисел, на которые придётся делить при разложе­нии его на множители. Очень грубые прикидки показывают, что компью­теру, выполняющему миллион делений в секунду, для разложения числа таким способом на простые сомножители потребуется не менее, чем лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно.

Авторы схемы RSA предложили выбирать число в виде произведе­ния двух простых множителей и , примерно одинаковых по величине. Так как

                                                                                               (6)

то единственное условие на выбор показателя степени в отображении (1) есть

                                                                                                  (7)

Итак, лицо, заинтересованное в организации шифрованной переписки с помощью схемы RSA, выбирает два достаточно больших простых числа и . Перемножая их, оно находит число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются, число остается секретным. Теперь любой может отправлять зашифрованные с помощью (1) сообщения организатору этой системы, а организатор легко сможет расшифровывать их с помощью (5).

Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифро­вали таким способом некоторую английскую фразу. Сначала она стан­дартным образом (а=01, b=02, .... z=26, пробел=00) была записана в виде целого числа , а затем зашифрована с помощью отображения (1) при

m=11438162575788886766932577997614661201021829672124236256256184293570 6935245733897830597123563958705058989075147599290026879543541

и . Эти два числа были опубликованы, причем дополнительно сообщалось, что . где и - простые числа, записываемые со­ответственно 64 и 65 десятичными знаками. Первому, кто расшифрует соответствующее сообщение

,

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, А. К. Lenstra и Р. С. Leyland сообщили о расшифровке фразы. Числа и оказались равными

.

Этот замечательный результат (разложение на мно­жители 129-значного десятичного числа) был достигнут благодаря ис­пользованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта, и продолжавшейся после предварительной теоретической под­готовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединённых сетью Inter­net. Наконец, отметим, что премия в 100$ была передана в Free Software Foundation.

2.3 Создание алгоритма

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

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

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

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

– а втором шаге, после ввода данных, программа производит зашифровку сообщения;

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

Криптографический алгоритм с открытым ключом RSA основан на том, что перемножить два числа намного проще, чем разложить произведение на множители. Для шифрования исходной последовательности необходимо сначала сгенерировать два больших простых числа p и q. Найти n = p*q. Выбрать число e (обычно порядка 10000) взаимно простое с phi = (p-1)(q-1), т.е. числа e и phi не имеют никаких общих делителей, кроме 1. Генерируется число d такое, что ed = 1(mod phi) - запись означает, что (ed-1) делится на phi. Числа n и е публикуются как открытый ключ, а число d держится в секрете - это закрытый ключ.

Сообщение зашифровывается по формуле y=xe(mod n), где x – исходное сообщение, а y – зашифрованное. Расшифровывается с помощью закрытого ключа d следующим образом: x=yd(mod n).

Надежность алгоритма заключается в том, что для восстановления закрытого ключа d необходимо знать числа p и q. Их можно получить, разложив на множители число n, но если числа p и q достаточно большие, то эта задача становится практически неразрешимой.

2.4 Компьютерная реализация

Для реализации алгоритма шифрования данных RSA в данной курсовой работе использовалась среда программирования Delphi.

В данной работе были использованы следующие компоненты Delphi:

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

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