ISSP \ Домен 06. Криптография. Часть 4

В этой части рассмотрены следующие вопросы:

• Типы асимметричных систем
• Алгоритм Диффи-Хеллмана
• RSA
• Односторонние функции
• Эль Гамаль
• Криптосистемы на основе эллиптических кривых
• LUC
• Knapsack
• Доказательство с нулевым разглашением

6. Типы асимметричных систем

Как было описано ранее в этом Домене, использование симметричной криптографии в чистом виде имеет три недостатка:

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

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

6.1. Алгоритм Диффи-Хеллмана

Первым недостатком симметричной криптографии, который было решено исправить, стало безопасное распространение симметричного ключа. Над этой проблемой работали Диффи и Хеллман, которые в итоге разработали первый алгоритм с асимметричными ключами, названный их именем.

Чтобы понять, как работает алгоритм Диффи-Хеллмана, представим себе следующий пример. Таня и Эрика хотят передавать данные по шифрованному каналу с использованием алгоритма Диффи-Хеллмана. Они обе генерируют свою пару ключей (открытый и закрытый) и обмениваются открытыми ключами. Программное обеспечение Тани берет ее закрытый ключ (являющийся просто числовым значением) и открытый ключ Эрики (другое числовое значение) и передает их в алгоритм Диффи-Хеллмана. Программное обеспечение Эрики берет ее закрытый ключ и открытый ключ Тани и также передает их в алгоритм Диффи-Хеллмана на своем компьютере. В результате на выходе из алгоритма Таня и Эрика получают одно и то же общее значение, которое используется для создания экземпляров симметричных ключей.

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

ПРИМЕЧАНИЕ. Приведенный пример описывает процедуру соглашения о ключах (key agreement), которая может выполняться способами, отличными от обмена ключами (key exchange). Соответствующие функции других асимметричных алгоритмов будут обсуждаться далее в этом Домене. При выполнении функции обмена ключами отправитель зашифровывает симметричный ключ на предварительно полученном открытом ключе получателя.

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

Оригинальный алгоритм Диффи-Хеллмана уязвим к атаке «человек посередине» (Man in the middle - MitM-атака), поскольку он не производит аутентификации перед обменом открытыми ключами. Вернемся к нашему примеру. При получении Эрикой открытого ключа, она не может быть уверена, что это открытый ключ Тани. Что если Ланс отправил Эрике свой открытый ключ от имени Тани? Эрика примет его ключ, думая, что это ключ Тани. Рассмотрим последовательность выполнения такой атаки, показанной на Рисунке 6-18:

Рисунок 6-18. Атака «человек посередине»

1. Таня отправляет свой открытый ключ Эрике, но Ланс перехватывает ключ в процессе передачи и не позволяет ему дойти до Эрики.
2. Ланс отправляет свой открытый ключ Эрике, представляясь Таней. Эрика думает, что это открытый ключ Тани.
3. Эрика отправляет свой открытый ключ Тане, но Ланс также перехватывает ее ключ в процессе передачи и не позволяет ему дойти до Тани.
4. Ланс отправляет свой открытый ключ Тане, представляясь Эрикой. Таня думает, что это открытый ключ Эрики.
5. Таня объединяет с помощью алгоритма Диффи-Хеллмана свой закрытый ключ с открытым ключом Ланса и создает симметричный ключ S1.
6. Ланс объединяет свой закрытый ключ с открытым ключом Тани и создает симметричный ключ S1.
7. Эрика объединяет свой закрытый ключ с открытым ключом Ланса и создает симметричный ключ S2.
8. Ланс объединяет свой закрытый ключ с открытым ключом Эрики и создает симметричный ключ S2.
9. Теперь Таня и Ланс имеют общий симметричный ключ S1, а Эрика и Ланс имеют другой общий симметричный ключ S2. Таня и Эрика думают, что у них есть общий симметричный ключ, они не знают о вмешательстве Ланса.
10. Таня пишет сообщение Эрике, используя свой симметричный ключ S1 для зашифрования, и отправляет его.
11. Ланс перехватывает сообщение и расшифровывает его на симметричном ключе S1, читает или изменяет сообщение и перешифровывает его на симметричном ключе S2, а затем отправляет Эрике.
12. Эрика берет свой симметричный ключ S2, расшифровывает на нем сообщение и читает его, не догадываясь, что его изменил Ланс.

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

ПРИМЕЧАНИЕ. Хотя алгоритм Диффи-Хеллмана уязвим к атаке «человек посередине», это не означает, что такой вариант компрометации возможен всегда при использовании этого алгоритма. Большинство реализаций включают в себя другие программные компоненты или протоколы, которые компенсируют эту уязвимость. Однако как специалист по безопасности, вы должны знать об этой проблеме.

ПРИМЕЧАНИЕ. MQV (Menezes-Qu-Vanstone) – это криптографическая функция соглашения о ключах аутентификации, очень похожая на алгоритм Диффи-Хеллмана. Для создания сеансовых ключей выполняется обмен открытыми ключами пользователей. Это обеспечивает защиту от получения сеансового ключа атакующим, поскольку для успешной ему нужны закрытые ключи обоих пользователей.

6.2. RSA

Название RSA состоит из имен его создателей (Рон Ривест, Ади Шамир и Леонард Адлеман). Алгоритм RSA является алгоритмом с открытыми ключами, он стал самым популярным асимметричным алгоритмом с момента их появления. Фактически RSA является признанным во всем мире стандартом, он может использоваться для цифровой подписи, обмена ключами и шифрования. Он был разработан в 1978 году в Массачусетском технологическом институте (MIT - Massachusetts Institute of Technology) и обеспечил как аутентификацию, так и шифрование ключей.

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

ПРИМЕЧАНИЕ. Простое число – это положительное целое число, не имеющее собственных делителей, что означает, что это число можно разделить без остатка только на единицу и само это число.

В чем заключается отличие между криптографией с открытыми ключами и инфраструктурой открытых ключей (PKI)?
Криптография с открытыми ключами использует асимметричный алгоритм. Понятия асимметричного алгоритма и криптографии с открытыми ключами взаимозаменяемы и, по сути, означают одно и то же. Примером асимметричного алгоритма является RSA, криптосистема на основе эллиптических кривых (ЕСС- Elliptic Curve Cryptosystem), алгоритм Диффи-Хеллмана, Эль Гамаль (El Gamal), LUC и Knapsack. Эти алгоритмы используются для создания ключевых пар (открытый/закрытый ключ), выполнения обмена ключами или соглашения о ключах, установки и проверки цифровых подписей.

Отметим, что алгоритм Диффи-Хеллмана может выполнять только соглашение о ключах и не может устанавливать и проверять цифровую подпись.

Инфраструктура открытых ключей (PKI - Public key infrastructure) – это не алгоритм, протокол или приложение – это инфраструктура, основанная на криптографии с открытыми ключами.

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

В настоящее время RSA реализован во множестве приложений, его используют операционные системы Microsoft, Apple, Sun, Novell, он применяется на аппаратном уровне в сетевых картах, системах защищенной телефонии, смарт-картах. Он может использоваться в качестве протокола обмена ключами, т.е. для шифрования симметричного ключа с целью его безопасной передачи получателю. RSA чаще всего используется совместно с симметричным алгоритмом DES, который был заменен алгоритмом AES. Таким образом, если в качестве протокола обмена ключами используется RSA, криптосистема сначала создает симметричный ключ для алгоритма DES или AES. Затем криптосистема зашифровывает симметричный ключ на открытом ключе получателя и отправляет его получателю. При этом симметричный ключ защищен, поскольку только человек, имеющий соответствующий закрытый ключ сможет расшифровать это сообщение и извлечь симметричный ключ.

Ныряем в математику

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

Алгоритм создает открытый ключ и закрытый ключ с помощью функции, выполняющейся над большими простыми числами. Если данные зашифрованы на открытом ключе, только с помощью соответствующего закрытого ключа можно расшифровать их. Процесс расшифрования обычно является тем же самым разложением на множители произведения двух простых чисел. Например, у меня есть секрет (зашифрованное сообщение), а вам, чтобы вскрыть этот секрет, нужно взять определенное большое число и разложить его на два сомножителя, получив в результате два числа, которые запианы у меня на листке бумаги. Кажется, что это совсем просто, но если это числа порядка 2^300, задача усложняется.

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

1. Выбираем два случайных больших простых числа р и q.
2. Вычислям их произведение n = pq. 
3. Выбираем случайное целое число e (e < 1 < (p-1)(q-1)) в качестве ключа зашифрования. Убеждается, что е и (p-1)(q-1) являются взаимно простыми.
4. Рассчитываем ключ расшифрования d. ed=1 mod (p-1)(q-1) или d=e^-1 mod ([p-1][q-1]).
5. Открытый ключ = (n,e).
6. Закрытый ключ = (n,d).
7. Исходные простые числа p и q уничтожаются безопасным образом.

Теперь у нас есть открытый и закрытый ключи, но как они работают вместе?

Если вам нужно зашифровать сообщение m на вашем открытом ключе (e, n), применяется формула C = m^e mod n. Затем вам нужно расшифровать сообщение на вашем закрытом ключе (d, n), для этого применяется формула M = c^d mod n.

Вы можете подумать: «Чудесно. Хотя я не понял этих формул, они выглядят достаточно простыми. Интересно, почему никто не может взломать эти маленькие формулы и вскрыть зашифрованную информацию?». Может кто-то однажды и сможет. Когда люди создадут новые математические инструменты и увеличат вычислительную мощность, воспользуются достижениями криптоанализа, алгоритм RSA однажды может быть взломан. Если мы научимся быстро и легко раскладывать большие числа на их простые сомножители, этот алгоритм не сможет больше обеспечивать безопасность. Но на данный момент ничего подобного нет, и мы можем продолжать использовать RSA в нашей деятельности.

Односторонние функции

Односторонние функции (one-way function) – это математические функции, которые легче рассчитать в прямом направлении, чем в обратном. Например, бросить на пол стакан очень просто, а вот собрать потом с пола все осколки и восстановить стакан практически нереально. Эта аналогия похожа на использование односторонних функций в криптографии, в частности в алгоритме RSA и других асимметричных алгоритмах, основанных на них.

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

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

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

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

Основная мысль этого раздела – это то, что все асимметричные алгоритмы обеспечивают безопасность путем использования математических уравнений, которые просто выполнять в одном направлении и практически невозможно в другом. Это основано на математической сложности этой задачи. Математическая сложность алгоритма RSA основана на сложности разложения больших числел на исходные простые сомножители. Алгоритм Диффи-Хеллмана и Эль Гамаль основаны на сложности расчета логарифмов в конечном поле.

6.3. Эль Гамаль

Эль Гамаль (El Gamal) – это алгоритм с открытыми ключами, который может использоваться для цифровой подписи, шифрования и обмена ключами. Он основан не на сложности разложения на сомножители больших чисел, а на расчете дискретных логарифмов в конечном поле. В действительности Эль Гамаль является расширением алгоритма Диффи-Хеллмана.

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

6.4. Криптосистемы с эллиптическими кривыми

Эллиптические кривые – это богатые математические структуры, с пользой применяемые во множестве различных приложений. Криптосистема с эллиптическими кривыми (ЕСС – Elliptic Curve Cryptosystem) реализует большинство функций RSA: цифровая подпись, безопасное распространение ключей и шифрование. Единственным отличительным фактором ЕСС является ее эффективность. ЕСС более эффективна, чем RSA и другие асимметричные алгоритмы.

На Рисунке 6-19 показан пример эллиптической кривой. В этом математическом поле, точки на кривой объединяются в структуры, называемые группами. Эти точки являются значениями, используемыми в математических формулах процессов зашифрования и расшифрования в ECC. Алгоритм рассчитывает дискретные логарифмы эллиптических кривых, которые отличаются от расчета дискретных логарифмов в конечном поле (который используют Диффи-Хеллман и Эль Гамаль).

Рисунок 6-19. Эллиптические кривые

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

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

6.5. LUC

Этот алгоритм основан на «последовательностях Люка» (Lucas sequences). Он выполняет расчет дискретных логарифмов в конечном поле, но использует последовательности Люка, позволяющие ускорить выполнение расчетов.

6.6. Knapsack

Со временем появились различные версии алгоритмов knapsack. Первый был разработан Меркле и Хеллманом, он мог использоваться только для шифрования, но позднее был доработан для реализации возможностей цифровой подписи. Эти алгоритмы основаны на "задаче рюкзака" (knapsack problem) – математической дилемме, которая иллюстрирует следующий вопрос: если у вас есть несколько различных предметов, каждый из них имеет свой вес, каким образом можно уложить их максимальное количество в рюкзак, чтобы рюкзак имел определенный вес?

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

6.7. Доказательство с нулевым разглашением

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

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

Ссылки по теме:

• “Elliptic Curve Cryptography FAQ v1.12,” by George Barwood (Dec. 12, 1997)

<<< Предыдущий раздел • Содержание • Следующий раздел >>>