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

- Односторонни функции с секретом и ассиметричные системы

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

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

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

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

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

Главным понятием СОК является однонаправленная функция с секретом (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. Преобразование исходного текста должно быть вычислительно нереализуемым (необратимым) и исключать его восстановление на основе открытого ключа.

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

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

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

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

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

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

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

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

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

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

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

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

- Криптосистема RSА

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

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

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

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

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

В криптосистеме RSA зашифрование блока сообщения m производится по формуле c = E_e,n(m), а для расшифрования применяется операция m = E_d,n(c). Таким образом, открытым и секретным ключом криптосистемы являются соответственно (e, n) и d.

Построение ключа d при известных e,d,p,q легко осуществимо. При наличии соответствующих параметров функции E_e,n и E_d,n также легко вычисляются.

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

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

Рассмотрим принципы организации информационного обмена с использованием системы RSA. Вначале абонент i выбирает пару различных простых чисел p_i и q_i. Затем он вычисляет n_i = p_iq_i, выбирает случайный вычет e _i, взаимно простой с φ (n_i), и находит .

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

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

Очевидно, для того чтобы найти d_i, достаточно знание сомножителей p_i, q_i. Для современных технологических возможностей время выполнения наилучших из известных алгоритмов разложения для значений n ≈ 2¹⁰²⁴ слишком велико.

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

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

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

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

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

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

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

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

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

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

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

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

Ведь приходится использовать аппарат арифметики больших чисел.

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

- Криптосистема Эль-Гамаля

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

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

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

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

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

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

Открытым ключом является тройка чисел p,g,y, = g^x(p).

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

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

Затем вычисляются числа a = g^x(p) – лазейка и b = y^xm(p) – шифртекст.

Криптограммой является пара блоков данных a,b.

Для расшифрования достаточно получить сомножитель y^k, что можно сделать с помощью секретного ключа, вычислив значение a^x = g^kx(p).

Действительно y^k = g^xk(p), поэтому m = a^-xb(p).

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

-Криптосистемы на основе эллиптических кривых

Для построения СОК могут быть использованы эллиптические кривые – математические объекты, определенные над конечными полями.

Для случаев характеристик поля p = 2, p = 3, p > 3, алгоритмы вычисления значений, связанных с реализацией подобных СОК, существенно различны. Вместе с тем, основные принципы, на основе которых построены СОК на эллиптических кривых, в идейном смысле одинаковы.

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

Множество решений сравнения y² = x³ + ax + b(mod p) можно расширить таким образом, что расширенное множество станет коммутативной группой E. Эта группа называется группой точек на эллиптической кривой.

Групповой закон в группе E называется сложением. Основной причиной, позволяющей построить группу E, является возможность построения новых решений уравнения кривой, исходя из уже известных. Оказывается, если даны решения P₁(x₁,y₁) и P₂(x₂,y₂) то «практически всегда» можно найти третье решение, используя знание координат первых двух.

Операция, сопоставляющая двум (возможно, одинаковым) точкам их «сумму» P₁(x₁,y₁) + P₂(x₂,y₂) = P₃(x₃,y₃), в аффинных координатах записывается в виде дробных выражений, поэтому при вычислениях может возникнуть особенность, если в соответствующем знаменателе появится нулевое значение (по модулю p).

Очевидно, это единственная ситуация, когда возникает особенность.

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

Можно показать, что если для операции «+» считать O нейтральным элементом, то расширенное множество точек кривой превращается в коммутативную группу, а сама операция – в групповой закон.

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

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

Групповой закон в аффинных координатах был открыт при исследованиях эллиптических кривых над обычным полем вещественных чисел, что «подсказало» вид соответствующих преобразований над конечными полями.

Сложение двух точек ЭК над полем вещественных чисел можно сформулировать в виде геометрического построения, связывающего координаты точек-слагаемых с координатами точки-суммы (рис.14).

Для этого следует учитывать, что если прямая пересекает ЭК в двух точках расширенной кривой, то она пересекает кривую в третьей точке (точка касания считается двойной точкой).

Рис. 14. График эллиптической кривой y² = x³ - 3x + 4 (а), сложение двух

точек (б), кратная точка (в).

Для сложении точек P и Q кривой (рис. 14.б) проводим через P и Q прямую. Она пересечет ЭК в некоторой третьей точке Проведем через прямую, параллельную оси ординат, которая пересечет ЭК в некоторой точке R, которую примем за сумму точек кривой: R = P + Q.

Если P = Q, то точка является пересечением кривой и касательной к кривой в точке P. В соответствующих случаях полагаем, что прямые параллельные оси ординат проходят через бесконечно удаленную точку O.

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

Как правило, при построении СОК на эллиптической кривой используется точка G большого простого порядка n. Все операции в СОК осуществляются над точками вида kG, которые образуют циклическую подгруппу группы E.

Стойкость СОК основана на сложности задачи дискретного логарифмирования на кривой. Эта задача состоит в нахождении скалярного множителя k из соотношения P = kG и, в общем случае, является вычислительно недоступной.

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: