Внезапно я предлагаю этот вариант EC-ElGamal на стандартной 256-битной эллиптической кривой, используя хэш-и-XOR для части шифрования (почти вдвое меньший размер зашифрованного текста по сравнению с учебником EC-ElGamal) и простой обмен работой/пространством. -off для дальнейшего сжатия сообщения в 32-байтовый зашифрованный текст $м$ из $b$ биты, с небольшим фиксированным $b$ (например. $б=8$).
- Используйте стандартную эллиптическую кривую над полем $\mathbb F_p$ с генератором $G$ порядка $n$, с $р$ и $n$ 256-битные простые числа и (предположительно) 128-битная безопасность. секп256р1 (он же NIST P-256) и secp256k1 квалифицировать. я имею в виду сек1v2 для математики и нотации ECC.
- Генерация ключей:
- Выберите закрытый ключ $д$ случайным образом в промежутке $[1,n)$
- Вычислить открытый ключ $Q\получает д\,G$
- Шифрование $b$-битный открытый текст $м$
- выберите $е$ случайным образом в промежутке $[1,2^{32})$
- Вычислить $F\получает е\,G$
- выберите $к$ случайным образом в промежутке $[1,n)$
- Вычислить $R\получает k\,G$
- Пока $R_x\not\equiv0\pmod{2^b}$
- Вычислить $R\получает R+F$ и $k\получает k+e$, который поддерживает $R=k\,G$
- Если $k\gen$ генератор случайных чисел, который выбрал $к$ скорее всего сломан; прервать или перезапустить шифрование
- Если $R_y$ нечетный, набор $R_y\получает p-R_y$ и $k\получает n-k$, который поддерживает $R=k\,G$
- Вычислить $S\получает k\,Q$ (общая секретная точка)
- Вычислить $u\gets\operatorname{SHA-256}(S_x)\bmod2^b$, куда $S_x$ выражается как 32-байтовая строка байтов
- Вычислить $v\получает u\oplus m$
- Выходной шифртекст 256-бит, состоящий из $256-б$ биты для $R_x$ с низким порядком $b$ биты удалены (они равны нулю по построению), и $b$ биты для $v$
- Расшифровка:
- Из извлечения зашифрованного текста $R_x$ (вставка $b$ младшие биты в нуле) и $v$
- Вычислить $R_y$ соответствие $R_x$ (это стандартный метод отмены точечного сжатия, см. Раздел 1v2 §2.3.4, шаг 2.4.1); если это не удается, прервите расшифровку.
- Если $R_y$ нечетный, набор $R_y\получает p-R_y$
- Вычислить $S\получает д\,R$ (общая секретная точка)
- Вычислить $u\gets\operatorname{SHA-256}(S_x)\bmod2^b$, куда $S_x$ выражается как 32-байтовая строка байтов
- Вычислить и вывести расшифрованный открытый текст $m\gets u\oplus v$
я предполагаю IND-CCA1 (таким образом Индивидуальная цена за конверсию) безопасность до 128-битного уровня при правдоподобных предположениях (сложность варианта решения задачи Диффи-Хеллмана для эллиптической кривой и SHA-256, смоделированного как случайный оракул). Существует тривиальная атака на IND-CCA2 (таким образом, доступ к оракулу дешифрования ставит под угрозу конфиденциальность прошлых сообщений, даже если оракул дешифрования внес исходные зашифрованные тексты в черный список; на практике это не проблема).
Остерегайтесь того, что шифр тривиально податлив. Это позволяет злоумышленнику перевернуть желаемые биты в открытом тексте, изменив эти биты в зашифрованном тексте. Это может быть практическим вопросом. Некоторый уровень смягчения этого возможен путем замены $u\oplus\ldots$ к Формат, сохраняющий шифрование с более широким $u$ как ключ; или/и больше работы или/и места.
Цикл while при шифровании — это компромисс между временем и пространством, поиск $к$ по перечислению, так что это $х$ координировать $R_x$ имеет $b$ младшие биты в нуле, которые не нужно передавать. Поиск оптимизирован, чтобы требовать $\приблизительно2^b$ точечные дополнения, но для $b$ начиная примерно $8$ это станет болью. Использование секретного приращения $e$ и соответствие $F=e\,G$ это приятно иметь в финале $к$ более однообразно (см. примечание), но я не знаю атаки, если мы возьмем $е=1$ и поэтому $F=G$. Дополнительное приращение секрета может помочь смягчить атаки по сторонним каналам.
Если мы хотим частично или полностью избежать компромисса между временем и пространством, мы можем
- тривиально, увеличить размер зашифрованного текста.
- или/и рискнуть создать пользовательскую кривую с битовым размером $n$ и $р$ на несколько бит меньше, чем 256. За каждый 1 бит безопасности, от которого мы отказываемся, мы получаем примерно 2 за $n$ и $р$, таким образом, на битах зашифрованного текста или в 4 раза меньше догадок в цикле while. А для secp256r1 самые известные атаки, возможно, требуют $>2^{140}$ битовые операции (на основе консервативной экстраполяции аналогичного требовать из $>2^{140}$ для Ed25519).
Примечание. В учебнике Диффи-Хеллмана или Эль-Гамаля мы выбираем $к$ равномерно в $[0,n)$. Наш вариант ограничивается $к$ с $к\,G$ наличие $х$ согласовывать с его младшим порядком $b$ биты в нуле. Согласно статистическому аргументу, существует около $n/2^b$ такой $к$. Мы хотели бы выбрать $к$ равномерно в этом подмножестве $[0,n)$. Самым простым было бы повторение для случайного $к$, но это имеет непомерно высокие вычислительные затраты на умножение точек $R\получает k\,G$. Экономим на этом переходя от одного кандидата $к$ к следующему с фиксированным приращением $e$, позволяя обновлять $R$ добавлением одной точки $R\получает R+F$.
Если бы мы использовали фиксированное $е=1$, то $к$ выбранный циклом while, будет иметь различимое свойство (для того, кто знает $к$): вероятность того, что $к$ выбирается пропорционально $j$ вычисляется из $к$ как самый маленький $j>0$ такой, что $k-j$ находится в подмножестве (или $к+1$ если нет такого $j$, что происходит для единичного $к$ в подмножестве). Проблема аналогична неравномерному выбору простого числа, полученному путем выбора случайной начальной точки и поиска следующего простого числа.
Выбрав любой общедоступный фиксированный $e$ не решает проблему, потому что определение $j$ может быть адаптирован к $к-е\,j$ в подмножестве. Однако, выбрав случайный секрет $e$ за каждый выбор $к$ делает. Аналогичный метод используется в генераторах случайных чисел для RSA. У меня нет ссылки, но аргумент в том, что противники не зная $e$ не знаю, что $e$ использовать для теста; они могут проверить на всех $e$ и объединяют результаты, но тогда их тест завален шумом.
Я выбрал верхнюю границу интервала $[1,2^{32})$ за $e$ так что вычисление $F\получает е\,G$ имеет предельные ожидаемые затраты по сравнению с $R\получает k\,G$. Я уверен (без доказательств или ссылок), что этого более чем достаточно, чтобы сделать предвзятость при выборе $к$ практически незаметен даже для гипотетических противников, знающих $к$; а фактические противники могли получить только $к$ через боковой канал.
Последняя мысль: мы могли бы развеять любые опасения, что критерии $R_x\equiv0\pmod{2^b}$ создает слабость, приспосабливая ее к: низкому $b$ немного $R_x$ являются некоторой функцией (имеющей приблизительно равномерное распределение) других битов $R_x$. А $b$-bit CRC подойдет. Приемник может восстановить необходимые младшие биты $R_x$ применив эту функцию.
