Эллиптическая криптография (Elliptic Curve Cryptography, ECC) — штука популярная, мощная и при этом не очень понятная. Мы в Cloudflare используем ее везде: от защиты HTTPS-соединений наших клиентов до передачи данных между серверами. В этой статье я попытаюсь на простых примерах показать, как все это работает.
Это перевод статьи Ника Салливана, впервые опубликованной в блоге компании 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-система.
Системы с открытым ключом обычно имеют два компонента: открытый ключ и секретный ключ. Шифрование работает так: берешь сообщение, применяешь к нему математическую операцию — и получаешь число, которое выглядит случайным. При дешифровке берешь это «случайное» число и применяешь другую операцию, чтобы получить исходное сообщение. Зашифрованное с помощью открытого ключа можно расшифровать, только применив секретный ключ.
Компьютеры не очень хорошо справляются с произвольно большими числами. Эту проблему можно решить, если выбрать максимальное значение и иметь дело только с числами, которые меньше максимума. Работает это как в часах с циферблатом и стрелками. Как перевести их, например, на 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 
Откуда 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) раз и вернуться к изначальному числу.
Материалы из последних выпусков становятся доступны по отдельности только через два месяца после публикации. Чтобы продолжить чтение, необходимо стать участником сообщества «Xakep.ru».
Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», увеличит личную накопительную скидку и позволит накапливать профессиональный рейтинг Xakep Score! Подробнее
1 год5380 р. |
1 месяц720 р. |
Я уже участник «Xakep.ru»
Читайте также
Последние новости
2009-2024 © Все права защищены.
This website - is fan-site, not an official Huawei website. The Huawei logo is a trademark of Huawei Technologies. Other trademarks are the property of their respective owners.
|