Применение алгоритма RSA для шифрования потоков данных

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

Проблема защиты информации путем ее преобразования, исВнключающего ее прочтение посторонним лицом, волновала чеВнловеческий ум с давних времен. История криптографии - ровесВнница истории человеческого языка. Более того, первоначально письменность сама по себе была своеобразной криптографичеВнской системой, так как в древних обществах ею владели только избранные. Священные книги древнего Египта, древней Индии тому примеры.

История криптографии условно можно разделить на 4 этапа.

1) наивная криптография.

2) формальная криптография.

3) научная криптография.

4) компьютерная криптография.

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

Большинство из используемых шифров сводились к переВнстановкеили моноалфавитной подстановке. Одним из первых зафиксированных примеров является шифр Цезаря, состоящий в замене каждой буквы исходного текста на другую, отстоящую от нее в алфавите на определенное число позиций. Другой шифр, полибианский квадрат, авторство которого приписываетВнся греческому писателю Полибию, является общей моноалфаВнвитной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицейдля греческого алфавита размер составляет 5x5). Каждая буква исходного текВнста заменяется на букву, стоящую в квадрате снизу от нее.

Этап формальной криптографии(кон. XV века - нач. XX века) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации. Важная роль на этом этапе принадлежит Леону Батисте Альберти, итальянскому архитектору, который одним из первых предложил многоалфавитную подстановку. Данный шифр, получивший имя дипломата XVI века Блеза Вижинера, состоял в последовательном ВлсложенииВ» букв исходного текста с ключом (процедуру можно облегчить с помощью специальной таблицы). Его работа ВлТрактат о шифреВ» (1466) считается перВнвой научной работой по криптологии.

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

Простым но стойким способом многоалфавитной замены (подстановки биграмм) является шифр Плейфера, который был открыт в начале XIX века Чарльзом Уитстоном. Уитстону приВннадлежит и важное усовершенствование - шифрование ВлдвойВнным квадратомВ». Шифры Плейфера и Уитстона использовались вплоть до первой мировой войны, так как с трудом поддавались ручному криптоанализу.

В XIX веке голландец Керкхофф сформулировал главное требование к криптографическим системам, которое остается актуальным и поныне: секретность шифров должна быть осноВнвана на секретности ключа, но не алгоритма.

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

Одной из первых подобных систем стала изобретенная в 1790 году Томасом Джефферсоном, будущим президентом США механическая машина. Многоалфавитная подстановка с помощью роторной машины реализуется вариацией взаимного положения вращающихся роторов, каждый из которых осуществляет ВлпрошитуюВ» в нем подстановку.

Практическое распространение роторные машины получили только в начале XX века. Одной из первых практически используемых машин, стала немецкая Enigma, разработанная в 1917 году Эдвардом Хеберном и усовершенствованная Артуром Кирхом. Роторные машины активно использовались во время второй мировой войны. Помимо немецкой машины Enigma использовались также устройства Sigaba (США), Турех (Великобритания), Red, Orange и Purple2 (Япония). Роторные системы -вершина формальной криптографии так как относительно просто реализовывали очень стойкие шифры. Успешные криптоатаки на роторные системы стали возможны только с появлением ЭВМ в начале 40-х годов.

Главная отличительная черта научной криптографии (30-е - 60-е годы XX века) - появление криптосистем со строгим математическим обоснованием криптостойкости. К началу 30-х годов окончательно сформировались разделы математики, являющиеся научной основой криптологии: теория вероятностей и математическая статистика, общая алгебра, теория чисел, начали активно развиваться теория алгоритмов, теория информации, кибернетика. Своеобразным водоразделом стала работа Клода Шеннона ВлТеория связи в секретных системахВ» (1949), где сформулированы теоретические принципы криптографической защиты информации. Шеннон ввел понятия ВлрассеиваниеВ» и ВлперемешиваниеВ», обосновал возможность создания сколь угодно стойких криптосистем.

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

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

Первым классом криптосистем, практическое применение которых стало возможно с появлением мощных и компактных вычислительных средств, стали блочные шифры. В 70-е годы был разработан американский стандарт шифрования DES (принят в 1978 году). Один из его авторов, Хорст Фейстел (сотрудник IBM), описал модель блочных шифров, на основе которой были построены другие, более стойкие симметричные криптосистемы, в том числе отечественный стандарт шифрования ГОСТ 28147-89.

С появлением DES обогатился и криптоанализ, для атак на американский алгоритм был создано несколько новых видов криптоанализа (линейный, дифференциальный и т.д.), практическая реализация которых опять же была возможна только с появлением мощных вычислительных систем.

В середине 70-х годов произошел настоящий прорыв в современной криптографии - появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 году под названием ВлНовые направления в современной криптографииВ». В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретным ключом. Независимо к идее асимметричных криптосистем подошел Ральф Меркли. Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость которой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электронной цифровой подписи (ЭЦП) и электронных денег.

В 80-90-е годы появились совершенно новые направления криптографии: вероятностное шифрование, квантовая криптография и другие. Осознание их практической ценности еще впереди. Актуальной остается и задача совершенствования симметричных криптосистем. В 80-90-х годах были разработаны нефейстеловские шифры (SAFER, RC6 и др.), а в 2000 году после открытого международного конкурса был принят новый национальный стандарт шифрования США - AES.

1. ПОСТАНОВКА ЗАДАЧИ

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

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

2. АЛГОРИТМ RSA

Труды Евклида и Диофанта, Ферма и Эйлера, Гаусса, Чебышева и Эрмита содерВнжат остроумные и весьма эффективные алгоритмы решения диофантовых уравнений, выяснения разрешимости сравнений, построения больших по тем временам простых чисел, нахождения наилучших приближений и т.д. В последние два десятилетия, благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ, исследоваВнния по алгоритмическим вопросам теории чисел переживают период бурВнного и весьма плодотворного развития.

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

Но возможности ЭВМ имеют определённые границы. Приходится разВнбивать длинную цифровую последовательность на блоки ограниченной длины и шифровать каждый такой блок отдельно. Мы будем считать в дальнейшем, что все шифруемые целые числа неотрицательны и по велиВнчине меньше некоторого заданного (скажем, техническими ограничениВнями) числа m. Таким же условиям будут удовлетворять и числа, получаеВнмые в процессе шифрования. Это позволяет считать и те, и другие числа элементами кольца вычетов . Шифрующая функция при этом может рассматриваться как взаимнооднозначное отображение колец вычетов

а число представляет собой сообщение в зашифрованном виде.

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

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

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

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

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

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

2.1. система шифрования RSA

Пусть и натуральные числа. Функция реализующая схему 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.2.Сложность теоретико-числовых алгоритмов

Сложность алгоритмов теории чисел обычно принято измерять колиВнчеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, предВнписанных алгоритмом. Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях. Ясно, что перемножить два стозначных числа значительно сложнее, чем два однозначных, хотя при этом и в том, и в другом случае выполняется лишь одна арифметическая опеВнрация. Поэтому иногда учитывают ещё и величину чисел, сводя дело к так называемым битовым операциям, т. е. оценивая количество необхоВндимых операций с цифрами 0 и 1, в двоичной записи чисел.

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

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

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

2.2.1. Алгоритм вычисления

1. Представим в двоичной системе счисления , где , цифры в двоичном представлении, равны 0 или 1, .

2. Положим и затем для вычислим

.

3) есть искомый вычет .

Справедливость этого алгоритма вытекает из сравнения

,

легко доказываемого индукцией по .

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

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

2.2.2. Алгоритм Евклида

1. Вычислим - остаток от деления числа на , , .

2. Если , то есть искомое число.

3. Если , то заменим пару чисел парой и перейдем к
   шагу 1.

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

Доказательство. Положим и определим - последовательность делителей, появляющихся в процессе выполнения шаВнга 1 алгоритма Евклида. Тогда

.

Пусть также , , , , - последовательВнность Фибоначчи. Индукцией по от до легко доказывается неравенство . А так как , то имеем неравенства и .

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

2.2.3. Алгоритм решения уравнения

0) Определим матрицу .

1) Вычислим - остаток от деления числа на , , .

2. Если , то второй столбец матрицы даёт вектор
   решений уравнения.

3. Если , то заменим матрицу матрицей .

4. Заменим пару чисел парой и перейдем к шагу 1.

Если обозначить через матрицу , возникающую в процессе рабоВнты алгоритма перед шагом 2 после делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство . Поскольку числа и взаимно просты, имеем , и это доказыВнвает, что алгоритм действительно даёт решение уравнения . Буквой мы обозначили количество делений с остатком, которое в точВнности такое же, как и в алгоритме Евклида.

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

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

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

Мы будем иногда использовать слова детерминированный алгоритм, чтобы отличать алгоритмы в обычном смысле от вероятностных алгоВнритмов.

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

. (8)

Например, речь может идти о решении квадратичных сравнений, если степень многочлена равна 2. Другими словами, мы должны отыскать в поле все элементы, удовлетворяющие уравнению .

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

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

Таким образом, обсуждая далее задачу нахождения решений сравнеВнния (8), мы можем предполагать, что в кольце многочленов спраВнведливо равенство

2.2.4. Алгоритм нахождения делителей многочлена в кольВнце

1) Выберем каким-либо способом элемент .

2. Вычислим наибольший общий делитель .

3. Если многочлен окажется собственным делителем , то многочлен распадётся на два множителя и с каждым из них незавиВнсимо нужно будет проделать все операции, предписываемые настоящим алгоритмом для многочлена .

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

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

Количество решений уравнения в поле не превосходит . Это означает, чт

Вместе с этим смотрят:

"Инкарнация" кватернионов

* Алгебры и их применение

*-Алгебры и их применение

10 способов решения квадратных уравнений

Cпособы преобразования комплексного чертежа, применение при изображении предметов