XI Международная студенческая научная конференция Студенческий научный форум - 2019

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

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

Наибольшую остроту вопрос распределения и доставки ключей приобретает в случае невозможности заранее описать состав информационно-телекоммуникационной сети.

Для решения этой проблемы на основе результатов, полученных классической и современной алгеброй, были предложены системы с открытым ключом (СОК). В СОК для зашифрования не используются секретные ключи – они необходимы только при расшифровании (рис. 1).

Главным понятием СОК является однонаправленная функция с секретом (one-way trapdoor function). Однонаправленную функцию с секретом : легко вычислить для всех , но очень трудно обратить почти для всех значений из . Однако, если используется некоторая секретная информация , то для всех значений легко вычислить величину, удовлетворяющую условию .

Криптосистемы с открытым ключом, использующие однонаправленные функции с секретом, еще называются асимметричными (asymmetric cryptosystems).

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

Эта функция была использована в широко распространенном криптографическом протоколе – протоколе обмена ключами Диффи-Хеллмана (Diffie-Hellman key exchange protocol).

Ранее, в 1974 году, Меркл (Merkle) изобрел механизм согласования криптографического ключа путем явных асимметричных вычислений, получивших название головоломка Меркла.

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

Несмотря на то, что головоломка Меркла не подходит для применения в современных криптографических приложениях, ее влияние на криптосистемы с открытым ключом невозможно переоценить.

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

Первоначально алгоритм Кокса был засекречен и только в декабре 1997 года Группа по электронной защите средств связи (Communications Services Electronic Security Group – CESG) его рассекретила.

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

В настоящее время алгоритмы шифрования с открытым ключом получили широкое распространение в информационных системах.

Так, алгоритм RSA фактически стал стандартом для открытых систем и рекомендован международной организацией по стандартизации ISO, соответствующие приложения лежат в основе электронной коммерции, осуществляемой через Internet.

Суть их состоит в том, что каждым абонентом сети генерируются два ключа, связанные между собой по определенному математическому закону. Один ключ объявляется открытым, а другой закрытым (секретным).

Открытый ключ опубликовуется и доступен любому, кто желает послать сообщение владельцу секретного ключа. Секретный ключ сохраняется в тайне.

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

Рис. 1. Криптосистема с открытым ключом

Таким образом, односторонняя функция с секретом, используемая в асимметричной системе, является взаимнооднозначной, но вместе с тем обладает свойствами необратимости.

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

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

1. Преобразование исходного текста должно быть вычислительно нереализуемым (необратимым) и исключать его восстановление на основе открытого ключа.

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

В основе современных криптосистем с открытым ключом вычислительно необратимые преобразования чаще всего строятся на основе следующих алгоритмических проблем:

– разложение больших чисел на простые множители;

– вычисление логарифма в конечном поле;

– нахождение кратности точки (дискретный логарифм) на эллиптической кривой;

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

Отметим, области применения СОК.

1. Средства шифрования передаваемых и хранимых данных.

2. Средства аутентификации пользователей и проверки целостности данных.

3. Механизмы распределения ключей.

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

Наибольшее распространение получили системы с открытым ключом на основе алгоритма RSA, криптосистема Эль-Гамаля и криптосистемы на основе эллиптических кривых.

Криптосистема RSA, разработанная в 1977 году, получила свое название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.

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

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

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

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HТTP, S-MIME, S/WAN, STT и PCT. Кроме того, алгоритм RSA реализуется как в виде самостоятельных криптографических продуктов (PGP), так и в качестве встроенных средств в некоторых приложениях (Интернет‑браузеры от Microsoft и Netscape).

Напомним ряд положений элементарной теории чисел, лежащих в основе этого алгоритма.

Наибольшим общим делителем двух целых чисел и называется наибольшее целое число, которое делит как так и . Обозначения: или НОД. Числа и называются взаимно простыми, если .

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

Пусть и . Тогда существуют целые числа являющиеся решением уравнения .

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

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

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

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

Рассмотрим степени числа по модулю , где и взаимно просты.

Пусть . Степени 1,2,…10, числа 2 таковы: 2,4,8,5,10,9,7,3,6,1.

Аналогично, степени числа 3 равны 3,9,5,4,1,3,9,5,4. В каждом случае имеется периодичность. Наименьшая длина периода для числа по модулю называется порядком (показателем, периодом) числа по модулю .

Порядок числа по модулю обозначается .

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

Из определения следует, что для простого числа и, кроме того, .

Функция Эйлера является мультипликативной: если , то .

Теорема Эйлера. Если , то .

Доказательство. При теорема верна. Пусть и – все вычеты по модулю , взаимно простые с модулем (по определению, ).

Пусть – один из таких вычетов. Тогда множества и совпадают.

Поэтому . Умножив обе части сравнения на , получим

Из теоремы Эйлера следует малая теорема Ферма: , где – простое, .

Случай можно учесть в выражении .

Существует общая формула для при известном каноническом разложении на степени простых чисел.

Пусть , тогда .

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

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

В криптосистеме RSA зашифрование блока сообшения производится по формуле , а для расшифрования применяется операция . Таким образом, открытым и секретным ключом криптосистемы являются соответственно и .

Построение ключа при известных легко осуществимо. При наличии соответствующих параметров функции и также легко вычисляются.

Если известны и , но и неизвестны, то представляет собой одностороннюю функцию с секретом.

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

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

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

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

Очевидно, для того чтобы найти , достаточно знание сомножителей ,. Для современных технологических возможностей время выполнения наилучших из известных алгоритмов разложения для значений слишком велико.

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

1. Выберем простые числа: , .

2. Вычислим и .

3. Выберем случайное значение , .

5. Вычислим секретный ключ

Открытый ключ – .

Зашифруем сообщение: .

, , .

Для расшифрования возведем каждый блок в степень по модулю 33: , , .

Секретный ключ для учебной системы легко найти перебором. На практике это невыполнимо, т.к. реальный размер модуля (длина битового представления) находится в диапазоне от 512 до 4096 битов.

Основные усилия в ходе практической реализации RSA приходятся на генерацию случайных больших простых чисел.

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

В случае неуспеха выбираем число и так далее. Однако при больших такой подход неосуществим.

Заметим, что из теории чисел известно, что вероятность того, что наудачу выбранное число порядка будет простым, оценивается как .

В принципе в качестве и можно использовать «почти» простые числа, то есть такие числа, для которых вероятность того, что они простые, стремится к 1. Но в случае, если использовано составное число, а не простое, криптостойкость RSA падает. Имеются неплохие алгоритмы, которые позволяют генерировать «почти» простые числа с произвольно малой вероятностью ошибки.

Другая проблема – какой длины следует использовать ключи?

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

1. Сомножители RSA – модуля должны выбираться случайно и быть одинаковой длины.

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

3. Длина открытого ключа должна быть строго более 16 битов.

4. До 2010 года разрешается использовать значения модуля длиной не менее 1536 битов, однако рекомендуется – не менее 2048 битов.

5. С 2010 года по 2020 год разрешается использовать значения модуля длиной не менее 2048 битов.

6. После 2020 года предполагается использовать значения модуля длиной не менее 4096 битов.

Следующий немаловажный аспект реализации RSA – вычислительный. Ведь приходится использовать аппарат арифметики больших чисел.

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

В отличие от RSA асимметричная криптосистема Эль-Гамаля основана на проблеме дискретного логарифма.

Соответствующая односторонняя функция является показательной функцией по простому модулю : секретные параметры входят в показатели степеней.

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

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

В криптосистеме Эль-Гамаля для построения пары асимметричных ключей выбирается большое простое число и два псевдослучайных числа, меньших .

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

Открытым ключом является тройка чисел .

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

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

Затем вычисляются числа – лазейка и – шифртекст. Криптограммой является пара блоков данных .

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

Действительно , поэтому .

Таким образом, обеспечивается защищенный информационный обмен без предварительной рассылки секретных ключей.

Список используемой литературы

Васильева, И. Н. Криптографические методы защиты информации: учебник и практикум для академического бакалавриата / И. Н. Васильева. — М.: Издательство Юрайт, 2018. — 349 с.

Введение в теоретико-числовые методы криптографии [Электронный ресурс] : учебное пособие / М.М. Глухов [идр.]. — Санкт-Петербург: Лань, 2011. — 400 с. — Режим доступа: https://e.lanbook.com/book/68466.

Басалова, Г.В. Основы криптографии [Электронный ресурс] : учебное пособие / Г.В. Басалова. — Москва:, 2016. — 282 с. — Режим доступа: https://e.lanbook.com/book/100302.

Герман, О. Н. Теоретико-числовые методы в криптографии: Учебное пособие. / О. Н. Герман, Ю. В. Нестеренко. — М.: Издательский центр «Академия», 2012. — 300 с.

Запечников, С. В. Криптографическиеметодызащитыинформации: учебник для академического бакалавриата / С. В. Запечников, О. В. Казарин, А. А. Тарасов. — М. : Издательство Юрайт, 2015. — 309 с.

Молдовян, II. А. Практикум по криптосистемам с открытым ключом / II. А. Молдовян. — СПб.: БХВ-Петербург, 2007. – 304 с.

Ян, Сонг Й. Криптоанализ RSA / Сонг Й. Ян ; пер. с англ. Ю. Р. Айдарова. — М. ; Ижевск : НИЦ «Регулярная и хаотическая динамика» : Ижевский институт компьютерных исследований, 2011.- 285, с.

Код для цитирования: Скопировать