Криптография с открытым ключом

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

Для установления криптографированной связи с помощью симметричного алгоритма, отправителю и получателю нужно предварительно согласовать ключ и держать его в тайне. Если они находятся в географически удалённых местах, то должны прибегнуть к помощи доверенного посредника, например, надёжного курьера, чтобы избежать компрометации ключа в ходе транспортировки. Злоумышленник, перехвативший ключ в пути, сможет позднее читать, изменять и подделывать любую информацию, зашифрованную или заверенную этим ключом. Глобальная проблема симметричных шифров (от Кольца-декодера капитана Миднайта до DES и AES) состоит в сложности управления ключами: как вы доставите ключ получателю без риска, что его перехватят?

Проблема управления ключами была решена криптографией с открытым, или асимметричным, ключом, концепция которой была предложена Уитфилдом Диффи и Мартином Хеллманом в 1975 году.

Криптография с открытым ключом – это асимметричная схема, в которой применяются пары ключей: открытый (public key), который зашифровывает данные, и соответствующий ему закрытый (private key), который их расшифровывает. Вы распространяете свой открытый ключ по всему свету, в то время как закрытый держите в тайне. Любой человек с копией вашего открытого ключа может зашифровать информацию, которую только вы сможете прочитать.

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

Главное достижение асимметричного шифрования в том, что оно позволяет людям, не имеющим существующей договорённости о безопасности, обмениваться секретными сообщениями. Необходимость отправителю и получателю согласовывать тайный ключ по специальному защищённому каналу полностью отпала. Все коммуникации затрагивают только открытые ключи, тогда как закрытые хранятся в безопасности. Примерами криптосистем с открытым ключом являются Elgamal (названная в честь автора, Тахира Эльгамаля), RSA (названная в честь изобретателей: Рона Ривеста, Ади Шамира и Леонарда Адлмана), Diffie-Hellman (названная, правильно, в честь её создателей) и DSA, Digital Signature Algorithm (изобретённый Дэвидом Кравицом).

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

Требования, выполнение которых обеспечивает безопасность ассиметричной криптосистемы:

1. Вычисление пары ключей получателем на основе начального условия должно быть простым.

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

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

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

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

Концепция асимметричных криптографических систем основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим образом: Функция f является однонаправленной, если для всех х можно легко вычислить функцию у=f(x) и в то же время для большинства y достаточно сложно получить значение x, такое, что f(x)=y, т.е. отсутствует эффективный алгоритм обратного преобразования Y→X.

Примеры однонаправленных функций:

1. Целочисленное умножение. Прямая задача – вычисление произведения двух очень больших простых целых чисел N=P*Q является относительно несложной задачей для ЭВМ. Обратная задача – разложение на множители большого целого числа, т.е. находжение делителей, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам теории чисел при целом N≈2⁶⁶⁴ и Р≈Q для разложения числа N потребуется около 10²³ операций, т.е задача практически неразрешима на современных ЭВМ.

2. Модульная экспонента с фиксированным основанием и модулем. Модельная экспонента с основанием А по модулю N представляет собой функцию f(x)=A^x mod N (т.е. остаток от деления A^x на N. Существую эффективные алгоритмы, позволяющие достаточно быстро вычислить значения функции f(x). Обратная задача – задача нахождения дискретного логарифма, алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. По современным оценкам теории чисел при целых числах A,N ≈2⁶⁶⁴ решение задачи потребует около 10²⁶ операций, т.е. задача имеет в 1000 раз большую вычислительную сложность, чем задача разложения на множители.

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

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

Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных алгоритмов. В криптосистеме RSA открытый ключ К_о, секретный ключ К_с, сообщение M и криптограмма С принадлежат множеству целых чисел от 0 до N-1, где N – модуль: N=P*Q. Здесь P и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают P и Q равной длины и хранят в секрете.

Множество целых чисел с операциями сложения и умножения по модулю N образует арифметику по модулю N (Приложение 1).

Открытый ключ выбирают случайным образом так, чтобы выполнялись условия:

1<К_о<=j(N);

числа К_о и j(N) являются взаимно простыми;

j(N) = (P-1)(Q-1) – функция Эйлера. Эта функция указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N.

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ, такой что К_с = 1 (mod j(N)) или К_с=К_о^-1(mod(P-1)(Q-1)).

Это можно осуществить, так как получатель знает пару простых чисел (P,Q) и может легко найти j(N). К_с и N должны быть взаимно простыми.

Преобразование шифрования определяет криптограмму С=МКо (mod N).

Обращение функции С, т.е. определение значения М по известным С, Ко и N практически неосуществимо при N» 2512.

Задачу расшифрования криптограммы можно решить, используя Kc и С:

М = С^Кс (mod N)

M^KoKc = M (mod N)

Величина j(N) используется в теореме Эйлера:

“Если НОД(Х,N) = 1, то Х^j(N) º 1 (mod N) или в более общей форме Х^nj(N)+1 = X (mod N)»

Отсюда КоКс = n * j(N) + 1 или КоКс º 1 (mod j(N)).

Т.е., если криптограмму С = МКо (mod N) возвести в степень Кс, то восстанавливается исходный текст.

Получатель защищает Кс и пару P, Q и открывает Ко и N (N = P * Q).

Противник знает Ко и N; если бы он мог разложить N на P и Q, то он узнал бы «потайной ход» – тройку P, Q, Ко, откуда можно вычислить j(N) = (P-1)(Q-1), а затем и Кс. Однако, разложение очень большого N на множители вычислительно не осуществимо (при условии, что P и Q имеют более 100 десятичных знаков).

Пример процедуры шифрования и расшифрования.

Пусть А передает сообщение В. В этом случае ключи формирует В.

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

Авторы RSA предлагали P и Q из 50 знаков (считали факторизацию таких чисел недостижимой). В 1994 г. было факторизовано число со 129 знаками путем распределенных вычислений на 1600 процессорах в течении 8 месяцев). Теперь избегают чисел меньше чем с 200 десятичными разрядами. В последнее время используют 250-300 разрядов.

Криптосистемы RSA реализованы как программно, так и аппаратно (спецпроцессоры на СБИС позволяют возводить в большие степени колоссальные числа).

Аппаратная реализация RSA приблизительно в 1000 раз медленнее реализации DES. Одни из лучших – процессоры CYLINK – выполняют 1024 битовое шифрование RSA со скоростью порядка 64 кбит/c.

Программная реализация RSA работает в 100 раз медленнее DES.

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

Это ограничивает область их применения, но не перечеркивает их ценности.

Поиск по сайту: