разное :: мелочи жизни

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

Написав обзорную заметку о криптологии, я подумал, что ее нужно обязательно дополнить конкретным примером: иначе будет просто скучно. По-моему, очень интересны криптосистемы с открытыми ключами, в частности, RSA. Кроме всего прочего, знакомство с ними объясняет механизм цифровой подписи.

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

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

Криптография с открытыми ключами была изобретена в 1976 году Уитфилдом Диффи и Мартином Хеллманом именно для решения проблемы управления ключами. В новой системе каждому участнику выдается два ключа: секретный и не секретный. Их, соответственно, называют личным и открытым ключами.

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

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

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

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

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

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

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

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

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

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

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

Вероятно, что самой известной из криптосистем с открытыми ключами является RSA. RSA была изобретена в 1977 году Роном Ривестом, Ади Шамиром и Леонардом Адлманом. Прежде, чем описать алгоритм RSA, хотелось бы разъяснить используемые ею принципы.

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

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

В-третьих, если записать возведение x в степень n как x^n, то извлечение корня степени n можно считать возведением x в степень 1/n. Тогда обратимость операций возведения в степень и извлечения корня можно представить формулами: y=x^n и x=y^(1/n), или x=(x^n)^(1/n)= x^(n*1/n)=x^1. Пожалуйста, запомните последнюю формулу, она нам пригодится.

Согласен, все это ничего не дает, пока мы оперируем обыкновенными числами по обыкновенным арифметическим правилам. Но если воспользоваться арифметикой вычетов, начало которой заложил Гаусс в 1801 году (!) и которую можно считать частным случаем теории групп, то ситуация коренным образом меняется.

Арифметика вычетов по модулю k имеет все те же правила, что и обычная, пока речь идет о сложении, вычитании и умножении. Отличается от обычной она тем, что числа в ней не принимают значений, больших, чем k, и меньших, чем -k. Другими словами, учитываются лишь остатки от деления чисел на k. В этом смысле в арифметике по модулю 7 числа 8, 15, 22 равны между собой, поскольку остаток от деления на 7 для каждого из них равен 1. Это можно записать так: 8 mod 7 = 15 mod 7 = 22 mod 7 = 1.

Как уже упоминалось, операции сложения, умножения и, следовательно, возведения в степень, сохраняют свою силу. Поэтому 6*5 mod 7 = 30 mod 7 = 2, а 2^5 mod 7 = 32 mod 7 = 4. Получается любопытная вещь: в какую степень ни возведи число, оно не будет расти по величине и не превысит по размеру модуля!

Теперь вспомните формулу из первой посылки: x=(x^a)^b=x^(ab) только в том случае, когда ab=1. Тогда роль "а" играло число n, а роль "b" - число 1/n. В арифметике по модулю появляется и другая возможность, например, 3*5 mod 7 = 15 mod 7 = 1. Говоря словами, в арифметике по модулю 7 операция возведения числа в третью степень равносильна операции извлечения корня пятой степени! Ну как, нравится? Если нравится, то не обольщайтесь: это не так. Просчитайте парочку примеров и проверьте сами...

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

Берем два больших простых числа p и q и находим их произведение n = pq. Выбираем два числа е и d, меньшие, чем n, и такие, что (ed-1) нацело делится на (p-1)(q-1). Иными словами, ed = 1 mod (p-1)(q-1). Е и d называют открытой и личной экспонентами соответственно. Открытым ключом называют пару (n,e), личным - пару (n,d). Множители p и q хранят в секрете или уничтожают.

Считая, что исходное сообщение в электронном виде можно интерпретировать как число, опишем процедуру шифрования и расшифровки при помощи формул. Пусть m - исходное сообщение. Шифрование состоит в вычислении кода c по формуле c = m^e mod n, то есть m возводится в степень e по модулю n. Расшифровка сводится к вычислению m = c^d mod n. А вот формулы для аутентификации. (Помните Машу и Сашу?) Подпись s создается вычислением s = m^d mod n. Подпись проверяется вычислением m = s^e mod n. Если m восстановлено верно, то подпись верна.

Но это все пока только голая теория. Практика выглядит несколько иначе. Во-первых, исходное сообщение считается не одним длинным числом, а разбивается на ряд чисел так, чтобы ни одно из них не превосходило n. Для этого достаточно, чтобы эти числа были, скажем 512-битовыми, а множители p и q - 256 и 258-битовыми соответственно. Приведенные формулы применяются как раз к 512-битовым числам. Зачем этот огород? Иначе, имея дело с арифметикой по модулю n, мы рискуем потерять информацию.

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

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

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

Евгений Щербатюк

© компьютерная газета