Шифр Эль-Гамаля
Шифр Эль-Гамаля (Тахер Эль-Гамаль, 1985) — асимметричный шифр: зашифровать сообщение может кто угодно по открытому ключу, а расшифровать — только владелец секретного ключа. Его стойкость основана на трудности задачи дискретного логарифма, а по устройству он — прямое продолжение протокола Диффи–Хеллмана.
Зачем нужна асимметричная криптография
У симметричных шифров один ключ на двоих, и его нужно как-то доставить собеседнику. Для сети из n участников нужно n(n − 1)/2 секретных ключей и надёжные каналы для каждого. В 1976 году Уитфилд Диффи и Мартин Хеллман предложили другой подход: у каждого участника пара ключей — открытый, который публикуется, и секретный, который никому не передаётся. Вычислить секретный ключ по открытому должно быть практически невозможно.
Задача дискретного логарифма
Пусть p — простое, g — первообразный корень по модулю p. Дискретный логарифм числа y — такое x, что g^x ≡ y (mod p).
Вычислить y = g^x mod p легко: быстрое возведение в степень требует около 2·log₂ x умножений. Обратная задача — найти x по y — для больших p считается трудной. Метод «шаг младенца — шаг великана» решает её за O(√p) операций, лучшие известные алгоритмы (решето числового поля) — за субэкспоненциальное время, но для p из 2048 бит и это недостижимо. Такие функции — лёгкие в одну сторону и трудные в обратную — называют односторонними.
Протокол Диффи–Хеллмана
- Алиса и Боб открыто договариваются о p и g.
- Алиса выбирает секретное a и отправляет A = g^a mod p; Боб выбирает секретное b и отправляет B = g^b mod p.
- Алиса вычисляет B^a, Боб — A^b. Оба получают общий секрет K = g^(ab) mod p.
Противник видит p, g, A, B, но чтобы найти g^(ab), ему, по-видимому, нужно решить задачу дискретного логарифма.
Схема Эль-Гамаля
Шифр Эль-Гамаля — это Диффи–Хеллман, в котором «половинка» получателя опубликована заранее, а общий секрет служит маской для сообщения.
Выбрать большое простое p и первообразный корень g; выбрать секретный ключ x, 1 < x < p − 1; вычислить y = g^x mod p. Открытый ключ — (p, g, y), секретный — x.
Выбрать случайный сеансовый ключ k, 1 < k < p − 1, и вычислить
Шифртекст — пара (a, b).
s = a^x = g^(kx) = (g^x)^k = y^k (mod p), поэтому b·s⁻¹ = y^k·M·(y^k)⁻¹ = M (mod p). Обратный элемент s⁻¹ существует, так как s не делится на простое p; его находит расширенный алгоритм Евклида или формула s⁻¹ = s^(p−2) mod p (малая теорема Ферма).
Ключи: p = 23, g = 5 (первообразный корень: p − 1 = 22 = 2·11, 5^2 = 2 ≢ 1, 5^11 ≡ 22 ≢ 1), секретный x = 6, открытый y = 5^6 mod 23 = 8.
Шифрование M = 10 с k = 3: a = 5^3 mod 23 = 10, y^k = 8^3 mod 23 = 6, b = 6·10 mod 23 = 14. Шифртекст (10, 14).
Расшифрование: s = 10^6 mod 23 = 6 (совпало с y^k), s⁻¹ = 4, так как 6·4 = 24 ≡ 1; M = 14·4 mod 23 = 56 mod 23 = 10.
Роль сеансового ключа k
Число k отправитель выбирает заново для каждого сообщения (в лаборатории — для каждого символа) и сразу забывает. Получателю оно не нужно: маску y^k он восстанавливает из a = g^k своим секретным x.
- Вероятностное шифрование. Без случайного k одинаковые символы давали бы одинаковые шифртексты, и шифр вскрывался бы частотным анализом. Со свежим k каждое «о» шифруется по-новому.
- Повтор k раскрывает сообщения. При одном k маска одинакова, и b_1·b_2⁻¹ = M_1·M_2⁻¹ (mod p): зная одно сообщение, противник вычисляет другое без секретного ключа.
- Утечка k раскрывает сообщение: M = b·(y^k)⁻¹ вычисляется по открытому ключу.
Условие НОД(k, p − 1) = 1, которое часто приводят в учебниках, для шифрования не обязательно — оно нужно в подписи Эль-Гамаля, где вычисляется k⁻¹ mod (p − 1).
Свойства
- Расширение шифртекста. Каждое число M превращается в пару, поэтому шифртекст вдвое длиннее.
- Мультипликативный гомоморфизм. Покомпонентное произведение шифртекстов (a_1·a_2, b_1·b_2) расшифровывается в M_1·M_2. Это полезно в электронном голосовании, но означает, что шифртекст можно подделать, не зная сообщения (шифр пластичен).
- Стойкость при пассивном противнике сводится к задаче Диффи–Хеллмана: по g^x и g^k вычислить g^(xk).
- Размер ключа. Сегодня для конечных полей рекомендуют p не меньше 2048 бит (или эллиптические кривые). В лаборатории — до 1024 бит.
- Подгруппа простого порядка. Если g — первообразный корень, символ Лежандра (a/p) выдаёт чётность k, а (y/p) — чётность x; отсюда противник узнаёт, является ли M квадратичным вычетом, — один бит информации о сообщении. Поэтому на практике g берут порождающим подгруппы большого простого порядка q | p − 1.
- Большой простой делитель p − 1. Если p − 1 состоит только из малых простых, логарифм находится быстро (алгоритм Полига–Хеллмана). В генераторе лаборатории p − 1 = R·q с простым q примерно половинной длины.
- Гибридное шифрование. Длинные сообщения не шифруют посимвольно: асимметричная часть передаёт случайный ключ, а данные шифрует симметричный шифр (например, AES).
Где взять большое простое p
Ключ начинается с простого числа нужной длины — например, 1024 или 2048 бит. Пробное деление для таких чисел неприменимо; в лаборатории p строится по цепочке с доказательством простоты по критерию Поклингтона, а заодно получается разложение p − 1, без которого нельзя проверить, что g — первообразный корень. Подробно — в статье «Простые числа и тесты простоты».
Введите ключи вручную (попробуйте p = 23, g = 5, x = 6 — коды символов должны быть меньше p, поэтому для текста понадобится p побольше) или сгенерируйте большое простое. Разбор покажет ключи, сертификат простоты и таблицы шифрования и расшифрования для каждого символа. Открыть шифр Эль-Гамаля →
Вопросы для самопроверки
- Зашифруйте M = 7 на ключах из примера (p = 23, g = 5, y = 8) с k = 2 и расшифруйте обратно.
Ответ
a = 25 mod 23 = 2, y^2 = 64 mod 23 = 18, b = 18·7 mod 23 = 126 mod 23 = 11. Расшифрование: s = 2^6 mod 23 = 18, s⁻¹ = 9 (18·9 = 162 = 7·23 + 1), M = 11·9 mod 23 = 99 mod 23 = 7. - Почему при расшифровании не нужно знать k?
Ответ
Маска y^k равна a^x, а a есть в шифртексте, x — у получателя. - Два сообщения зашифрованы с одним k: b_1 = 14, b_2 = 6 (mod 23), и известно M_1 = 10. Найдите M_2.
Ответ
M_2 = M_1·b_2·b_1⁻¹ mod 23; 14⁻¹ = 5 (14·5 = 70 = 3·23 + 1), M_2 = 10·6·5 mod 23 = 300 mod 23 = 1.