Содержание статьи
INFO
Это перевод статьи Ника Салливана, впервые опубликованной в блоге компании Cloudflare. Перевела Алёна Георгиева.
Вообще мы убеждены: чтобы доверять той или иной системе безопасности, нужно понимать технологию, которая за ней стоит. Так что мы решили найти хорошее, относительно доступное руководство по ECC — и поделиться им с читателями. Найти не удалось, и мы написали его сами — оно перед вами.
Предупреждаю: тема сложная, в двух словах о ней не расскажешь. Здесь есть что обсудить, так что устраивайся поудобней. Но если нужны те самые два слова, то вот они: ECC — это новое поколение криптосистем с открытым ключом, которые построены на понятных математических основаниях и обеспечивают куда более серьезную защиту, чем криптосистемы первого поколения вроде RSA. Хочешь обеспечить высокий уровень защиты и сохранить при этом производительность — имеет смысл обратиться к ECC. А если интересуют детали — они ниже.
Криптография с открытым ключом: как все начиналось
Историю криптографии можно разделить на два периода: классический и современный. Водоразделом здесь служит 1977 год, когда одновременно были представлены алгоритм RSA и протокол Диффи — Хеллмана. Случилась настоящая революция: это были первые криптографические системы, где безопасность строилась на теории чисел. Стала возможной безопасная коммуникация без известного обеим сторонам — то есть симметричного — шифра. До этого криптография бесконечно занималась вопросом, как безопасно переслать секретные шифры. Теперь же она могла обеспечить доказательно безопасную коммуникацию между двумя сторонами — без заботы о том, не перехватит ли кто обмен ключами.
Современная криптография стоит на том, что ключ для шифрования данных может быть открытым, а вот ключ для дешифровки лучше оставить в секрете. Такие системы называют криптографическими системами с открытым ключом (public key cryptographic systems). Первая — и все еще самая распространенная из них — RSA. Она названа инициалами тех, кто впервые описал ее алгоритм (Ron Rivest, Adi Shamir, Leonard Adleman).
Хорошей криптографической системе с открытым ключом нужен набор алгоритмов, которые легко пройти в одном направлении и трудно в обратном. В случае с RSA «легкий» алгоритм умножает два простых числа. Его «трудной» парой будет факторизация — разложение получившегося результата на изначальные множители. Алгоритмы с такой характеристикой — «просто в одну сторону, трудно в обратную» — называют односторонней функцией с потайным входом (trapdoor function, TDF). Найти хорошую TDF критично важно для создания безопасной криптографической системы с открытым ключом.
Проще говоря, чем больше разрыв между сложностью прохождения функции в одном направлении и в другом, тем надежней получится криптографическая система, на ней основанная.
Алгоритм RSA в миниатюре
RSA — самая популярная и наиболее понятная из систем с открытым ключом. Ее безопасность опирается на то, что умножение — это быстро, а разложение на множители — медленно. Коротко рассмотрим, как выглядит и работает маленькая RSA-система.
Системы с открытым ключом обычно имеют два компонента: открытый ключ и секретный ключ. Шифрование работает так: берешь сообщение, применяешь к нему математическую операцию — и получаешь число, которое выглядит случайным. При дешифровке берешь это «случайное» число и применяешь другую операцию, чтобы получить исходное сообщение. Зашифрованное с помощью открытого ключа можно расшифровать, только применив секретный ключ.
Компьютеры не очень хорошо справляются с произвольно большими числами. Эту проблему можно решить, если выбрать максимальное значение и иметь дело только с числами, которые меньше максимума. Работает это как в часах с циферблатом и стрелками. Как перевести их, например, на 37 часов? Очевидно, разделить 37 на максимум — то есть 12 — и докрутить остаток. Так и здесь: любые вычисления, дающие результат больше максимума, мы «докручиваем» до числа в допустимом диапазоне.
В RSA максимальное значение (обозначим его max) получают умножением двух случайных простых чисел. Открытый и секретный ключи — это два специально выбранных числа больше нуля, но меньше максимального значения, обозначим их pub и priv. Чтобы зашифровать число, мы перемножаем его pub раз — и всякий раз «докручиваем», когда превышаем максимум. Чтобы расшифровать сообщение, перемножаем его priv раз по тому же правилу — и получаем исходное число. Звучит удивительно, но правда работает. Когда обнаружили эту особенность, она стала большим прорывом.
Чтобы создать пару ключей для RSA, сначала берешь два простых числа, чтобы получить максимум (max). Затем выбираешь число для открытого ключа (pub). До тех пор пока ты знаешь два изначальных простых числа, ты можешь вычислить секретный ключ priv через открытый. Это то, как факторизация соотносится со взломом RSA: разложение максимального значения на исходные множители позволяет вычислить чей-то секретный ключ по открытому и дешифровать личные сообщения.
Рассмотрим все это на конкретном примере. Возьмем простые числа 13 и 7, перемножим и получим максимальное значение 91. В качестве открытого ключа возьмем число 5. А затем, зная изначальные множители и максимум, применим расширенный алгоритм Евклида и получим секретный ключ — 29.
Эти параметры (max = 91, pub = 5, priv = 29) определяют полностью функциональную RSA-систему. Мы можем взять число и перемножить его пять раз для зашифровки, а затем взять получившийся результат, перемножить его 29 раз и получить изначальное число.
Используем эти значения, чтобы зашифровать слово CLOUD.
Чтобы представить сообщение математически, нужно превратить буквы в числа. Для представления латинского алфавита отлично подходит кодировка UTF-8. Каждому символу соответствует свой номер.
В этой кодировке CLOUD выглядит как 67, 76, 79, 85, 68. Все эти числа меньше нашего максимума, поэтому мы можем зашифровать их по отдельности.
67 × 67 = 4489 = 30
INFO
Откуда 30? Поскольку получившееся число 4489 больше максимума, мы «докручиваем» его до нужного нам диапазона (от 0 до 91). Для этого делим 4489 на 91 до целого числа и берем остаток. Этим остатком и будет 30.
4489 = 91 × 49 + 30
30 × 67 = 2010 = 8
8 × 67 = 536 = 81
81 × 67 = 5427 = 58
58 и будет зашифрованной версией 67.
Повторив этот процесс для каждой из букв, мы получим зашифрованное сообщение CLOUD в виде
58, 20, 53, 50, 87
Чтобы расшифровать это запутанное сообщение, берем каждое из получившихся чисел — и точно так же перемножаем 29 раз.
58 × 58 = 3364 = 88 (помни, что мы «докручиваем» число, если оно превышает максимум)
88 × 58 = 5104 = 8
…
9 × 58 = 522 = 67
Вуаля, мы вернулись к 67. Провернув то же самое с остальными числами, мы получим исходное сообщение.
Вывод: ты можешь взять число, перемножить его сколько-то (pub) раз и получить случайно выглядящий результат, а потом перемножить его другое количество (priv) раз и вернуться к изначальному числу.
Продолжение доступно только участникам
Вариант 1. Присоединись к сообществу «Xakep.ru», чтобы читать все материалы на сайте
Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», позволит скачивать выпуски в PDF, отключит рекламу на сайте и увеличит личную накопительную скидку! Подробнее
Вариант 2. Открой один материал
Заинтересовала статья, но нет возможности стать членом клуба «Xakep.ru»? Тогда этот вариант для тебя! Обрати внимание: этот способ подходит только для статей, опубликованных более двух месяцев назад.
Я уже участник «Xakep.ru»
