Объяснение алгоритмов шифрования с примерами

В основе своей криптография - это наука об использовании кодов и шифров для защиты сообщений.

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

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

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

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

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

Как работает Диффи-Хеллман?

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

Это работает следующим образом:

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

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

Например:

  1. Боб и Алиса договариваются о двух числах: большом простом, p = 29 и основании g = 5.
  2. Теперь Боб выбирает секретное число x (x = 4) и делает следующее: X = g ^ x% p (в данном случае% указывает остаток. Например, 3% 2 равно 3/2, где остаток равен 1). . Х = 5 ^ 4% 29 = 625% 29 = 16
  3. Алиса также выбирает секретное число y (y = 8) и делает следующее: Y = g ^ y% p. Y = 5 ^ 8% 29 = 390,625% 29 = 24
  4. Боб отправляет X Алисе, а Алиса отправляет Y Бобу.
  5. Затем Боб делает следующее: K = Y ^ x% p, K = 24 ^ 4% 29 = 331,776% 29 = 16
  6. Затем Алиса делает следующее: K = X ^ y% p, K = 16 ^ 8% 29 = 4,294,967,296% 29 = 16

Самое замечательное (* возможно, волшебное *) в этом состоит в том, что и Боб, и Алиса имеют одинаковое число, K, и теперь могут использовать его для тайного разговора, потому что никто другой не знает K.

Безопасность этого протокола зависит от нескольких вещей:

  1. (Факт) Относительно легко генерировать простые числа, даже большие простые числа (например, p).
  2. (Факт) Модульное возведение в степень легко. Другими словами, относительно легко вычислить X = g ^ x% p.
  3. (Предположение, основанное на современных вычислительных мощностях и математике) Модульное извлечение корня без простых множителей очень сложно. По сути, очень сложно найти K, не зная x и y, даже если вы отслеживали трафик и видите p, g, X и Y.

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

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

Что такое идеальная прямая секретность?

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

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

Это возможно, если каждый сеанс имеет свой временный ключ для каждого сеанса. Поскольку Diffie-Hellman всегда использует новые случайные значения для каждого сеанса (поэтому генерирует новые ключи для каждого сеанса), он называется Ephemeral Diffie Hellman (EDH или DHE). Многие комплекты шифров используют это для достижения идеальной прямой секретности.

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

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

Вот сообщение Скотта Хелма, в котором более подробно рассказывается об этом и объясняется, как включить это на ваших серверах.

Каковы ограничения Диффи-Хеллмана?

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

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

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

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

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

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

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

Чтобы подробнее узнать о слабых сторонах DH, ознакомьтесь с этим техническим документом и на этом веб-сайте.

ЮАР

RSA назван в честь создателей - Ривеста, Шамира, Адлемана - и представляет собой способ генерации открытых и закрытых ключей.

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

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

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

Итак, как это работает?

  1. Выберите 2 очень больших простых числа (не менее 512 бит или 155 десятичных цифр каждое), x и y (эти числа должны быть секретными и выбираться случайным образом)
  2. Найдите продукт, т.е. z = x * y
  3. Выберите нечетное общедоступное целое число e от 3 до n - 1 и не имеет общих множителей (кроме 1) с (x-1) (y-1) (поэтому оно взаимно простое с x - 1 и y - 1. ).
  4. Найдите наименьшее общее кратное x - 1 и y - 1 и назовите его L.
  5. Вычислите частную экспоненту d из x, y и e. de = 1% L. d является обратным к e% L (вы знаете, что существует обратное, потому что e взаимно просто с z - 1 и y - 1). Эта система работает, потому что p = (p ^ e) ^ d% z.
  6. Выведите (z, e) как открытый ключ и (z, d) как закрытый ключ.

Теперь, если Боб хочет отправить сообщение Алисе, он генерирует зашифрованный текст (C) из простого текста (P), используя эту формулу:

С = Р ^ е% г

Чтобы расшифровать это сообщение, Алиса вычисляет следующее:

P = C ^ d% z

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

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

Вы также можете использовать операции в обратном порядке, чтобы получить цифровую подпись сообщения. Во-первых, вы используете операцию дешифрования открытого текста. Например, s = SIGNATURE (p) = p ^ d% z.

Затем получатель может проверить цифровую подпись, применив функцию шифрования и сравнив результат с сообщением. Например, m = VERIFY (s) = S ^ e% z.

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

Безопасность системы основана на нескольких вещах:

  1. (Факт) Относительно легко генерировать простые числа, даже большие простые числа (например, x и y).
  2. (Факт) Умножение - это просто. Найти z очень просто.
  3. (Предположение, основанное на современной математике) Факторинг - это сложно. Учитывая z, относительно сложно восстановить x и y. Это выполнимо, но требует времени и дорого.

    Согласно одной из оценок, восстановление простых множителей 1024-битного числа на машине стоимостью 10 миллионов долларов займет год. Удвоение размера приведет к экспоненциальному увеличению объема необходимой работы (в несколько миллиардов раз больше).

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

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

4. (Факт) Модульное возведение в степень легко. Другими словами, относительно легко вычислить c = p ^ e% z.

5. (Факт) Модульное извлечение корня - обращение описанного выше процесса - легко, если у вас есть простые множители (если у вас есть z, c, e и простые множители x и y, легко найти p такое, что c = p ^ е% z).

6. (Предположение, основанное на текущей вычислительной мощности и математике) Модульное извлечение корня без простых множителей очень сложно (если у вас есть z, c, e, но не x и y, относительно сложно найти p такое, что c = p ^ e% z, особенно если a достаточно велико).

Хотите узнать больше о математике от более умных людей? Прочтите эту статью.

Отлично, что лучше?

Это зависит от вашего варианта использования. Между этими двумя алгоритмами есть несколько различий - во-первых, совершенная прямая секретность (PFS), о которой мы говорили ранее в контексте Диффи-Хеллмана. Хотя технически вы можете генерировать эфемерные пары ключей RSA и обеспечивать идеальную прямую секретность с помощью RSA, вычислительные затраты намного выше, чем для Diffie-Hellman, а это означает, что Diffie-Hellman является лучшим выбором для реализаций SSL / TLS, где вам нужна идеальная прямая секретность. .  

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

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

Например, хотя протокол Diffie-Hellman был одобрен правительством США и поддержан институциональным органом, стандарт не был выпущен - тогда как RSA (стандартизированный частной организацией) предоставил бесплатный стандарт, а это означает, что RSA стал очень популярным среди частных организаций.

Если вам интересно узнать больше, здесь есть отличная ветка о различиях.

Хотите узнать, как хакеры используют криптографические атаки? Попробуйте этот набор задач от Cryptopals.

Чем больше я узнаю о криптографии, тем больше думаю, что Алисе и Бобу, вероятно, следует просто поговорить лично.

- Пол Рейнхеймер (@preinheimer) 13 марта 2017 г.