Русская Википедия:Обмен ключами на основе обучения с ошибками

Материал из Онлайн справочника
Версия от 19:34, 31 августа 2023; EducationBot (обсуждение | вклад) (Новая страница: «{{Русская Википедия/Панель перехода}} В криптографии обмен ключами при обучении с ошибками — криптографический алгоритм, позволяющий двум сторонам создавать и обмениваться секретным ключом,...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

В криптографии обмен ключами при обучении с ошибками — криптографический алгоритм, позволяющий двум сторонам создавать и обмениваться секретным ключом, который они используют для шифрования сообщений между собой. RLWE-KEX (Шаблон:Lang-en) является одним из алгоритмов с открытым ключом, который предназначен для защиты от противника, обладающего квантовым компьютером. Это важно, потому что криптографические системы с открытым ключом, широко используемые сегодня, легко взламываются квантовым компьютеромШаблон:Sfn. RLWE-KEX является одним из множества постквантовых криптографических алгоритмов, основанных на сложности решения математических задач, связанных с криптографией на решёткахШаблон:Sfn.

Предпосылки

С 1980-х безопасность криптографического обмена ключами и цифровых подписей в Интернете была главным образом основана на небольшом числе основных криптосистем с открытым ключом. Криптостойкость этих алгоритмов основывается на маленьком количестве задач, сложных для вычислений классическими методами, но довольно легко решаемых с помощью квантового компьютера[1]. Эти задачи — факторизация двух тщательно подобранных простых чисел, трудность вычисления дискретного логарифма в выбранном конечном поле и трудность вычисления дискретного логарифма в подобранной группе точек эллиптической кривой. Существует мнение, что квантовые компьютеры будут доступны уже через 10-15 лет[2]. Если квантовые компьютеры с достаточной памятью были бы построены, все криптосистемы с открытым ключом, основанные на этих трех классических трудных задачах, стали бы крайне уязвимымиШаблон:Sfn. Такой тип криптографии с открытым ключом используется сегодня для защиты интернет-сайтов, авторизационной информации компьютера и для предотвращения компьютеров от получения вредоносного программного обеспечения[3].

Криптография, которая не поддается взлому квантовым компьютером, называется квантово-защищенной или постквантовой криптографией. Один из классов этих алгоритмов основан на концепции «обучение с ошибками», введенной Шаблон:Не переведено 3 в 2005 году[4]. Специализированная форма обучения с ошибками работает в кольце многочленов над конечным полем. Эта специализированная форма называется кольцом обучения с ошибками или RLWEШаблон:Sfn.

Существует множество криптографических алгоритмов, которые работают с использованием парадигмы RLWE. Есть криптосистема с открытым ключом, гомоморфные алгоритмы шифрования и RLWE цифровая подпись алгоритма в дополнение к открытому ключу. Обмен ключами является типом асимметричного шифрования, который устанавливает общий секретный ключ между двумя взаимодействующими агентами на линии связи. Классическим примером обмена ключами является протокол Диффи — Хеллмана (и, как его расширение, Протокол Диффи — Хеллмана на эллиптических кривых). Обмен состоит из одной передачи с одного конца линии и одной передачи с другого конца линииШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ.

RLWE обмен ключами разработан как квантово-безопасная замена для протоколов, которые используются для обеспечения безопасности создания секретных ключей по ненадежным каналам связи. Также как и протокол Диффи—Хеллмана, RLWE обеспечивает криптографическое свойство «совершенно прямой секретности»Шаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ, целью которого является снижение эффективности программ массового наблюдения и убеждение, что нет долгосрочных секретных ключей, которые могут быть скомпрометированы, что позволит осуществить объемную расшифровку.

Описание алгоритма

Введение

Используя простое число q, RLWE работает в кольце многочленов по модулю полинома Ф(х) с коэффициентами в поле целых чисел по модулю q (кольцо Fq[x]/Φ(x))Шаблон:SfnШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ. Полином a(x) выражается следующим образом:

a(x) = a0 + a1x + a2x2 + … + an-3xn-3 + an-2xn-2 + an-1xn-1

Коэффициенты этого полинома являются целыми числами по модулю q. Полином Φ(x) = xn +1, где n является степенью 2 (в большинстве случаев значения для n = 256, 512 или 1024).

RLWE-KEX использует полиномы, которые считаются «малыми» по отношению к мере, называемой «бесконечной» нормойШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ. Бесконечная норма для многочлена — значение наибольшего коэффициента полинома, когда коэффициенты рассматриваются как элементы множества {<math>{-\tfrac{q-1}{2}}</math>,…, 0, …, <math>\tfrac{q-1}{2}</math>}. Для обеспечения безопасности алгоритма необходимо генерировать случайные полиномы s(x), малые по отношению к бесконечной норме. Это делается случайным формированием коэффициентов для многочлена (sn-1, …, s0), которые гарантированно или с большой вероятностью будут небольшими. Есть два распространенных способа:

  1. Использование дискретного равномерного распределения — коэффициенты полинома небольшой равномерной пробы из набора малых коэффициентов. Пусть b — целое число, намного меньшее q. При выборе случайным образом коэффициентов из множества { -b, -b+1, -b+2. … −2, −1, 0, 1, 2, … , b-2, b-1, b}, полином будет небольшим по отношению к a(x). Синг предлагает использовать b = 5Шаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ. Таким образом, коэффициенты будут выбраны из множества { q-5, q-4, q-3, q-2, q-1, 0 , 1, 2, 3, 4, 5 }.
  2. Использование дискретного нормального распределения — коэффициенты выбираются случайным образом для нечетного значения q с помощью выборки из множества { <math>-\tfrac{q-1}{2}</math>; <math>\tfrac{q-1}{2}</math> } в соответствии с дискретным распределением Гаусса с математическим ожиданием 0 и дисперсией σ. Этот метод сложнее, чем дискретное равномерное распределение, но он позволяет доказать безопасность алгоритмаШаблон:Sfn.

Пусть случайные небольшие полиномы будут соответствовать распределению, обозначенному как D. Число q будет нечетным простым таким, что q ≡ 1 mod 4 и
q ≡ 1 mod 2n с целью минимизировать количество операций выбора случайного бита на границе множествШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ. Это позволит реализовать алгоритм наиболее эффективно Шаблон:Sfn. Степень полинома Ф(x) является степенью 2Шаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ.

Пусть фиксированный многочлен а(х) — общий для всех пользователей сети, генерируемый с помощью криптографическистойкого генератора псевдослучайных чисел. Взяв а(х), произвольно выбираются небольшие многочлены s(x) и e(x), s(x) — закрытый ключ в обмене открытыми ключами. Соответствующим открытым ключом будет многочлен t(х) = а(х)s(х) + е(х)Шаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ. Безопасность обмена ключами основана на трудности найти пару небольших многочленов s'(х) и e'(х)таких, что для данной t(х) а(х)s'(х) + е'(х) = t(х).

Обмен ключами

Обмен ключами происходит между агентами обмена ключами Алисой, обозначенной как A, и Бобом, обозначенным как B. И A, и B знают q, n, a(x) и умеют генерировать небольшие полиномы в соответствии с распределением DШаблон:SfnШаблон:Sfn.

Первоначальные действия АлисыШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ:

  1. Генерация двух малых полиномов sA(x) и eA(x) путём выборки из распределения D.
  2. Вычисление tA(x) = a(x)•sA(x) + eA(x).
  3. Отправка tA(x) Бобу.

Действия БобаШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ:

  1. Генерация двух малых полиномов sB(x) и eB(x) путём выборки из распределения D.
  2. Вычисление v(x) = tA(x)·sB(x) + eB(x) . Заметим, что v(x) = a(x)sA(x)sB(x) + eA(x)sB(x) + eB(x) и что eB(x) + eA(x)sB(x) также будет малым, так как eB(x) был выбран малым, коэффициенты eA(x)sB(x) ограничены в росте и также будут малы.
  3. Распределение коэффициентов v(x) сглаживается с помощью цикла по коэффициентам и случайной корректировки определенных значений. От j=0 до n-1:
    1. Если vj = 0, то придумать случайный бит(обозначим b). Если он — 0, то vj = 0, иначе vj = q-1.
    2. Если vj = <math>\tfrac{q-1}{4}</math>, то придумать случайный бит(b). Если он — 0 то vj = <math>\tfrac{q-1}{4}</math> иначе vj = <math>\tfrac{q+3}{4}</math>.
  4. Формирование 2 битовых потоков cj и uj длины n из коэффициентов v(x) с помощью следующих преобразований. От j=0 до n-1:
    1. Записать cj как младший бит от целой части 4vj/q, то есть <math display="inline">c_j = \lfloor 4 v_j/q \rfloor\mod 2</math>.
    2. Записать <math>u_j = \lfloor 2v_j\rceil\mod 2</math>.
  5. Формирование ключа k как конкатенации un-1, …, u0.
  6. Формирование строки «согласования»(C) длины n, как конкатенации cn-1, …, c0.
  7. Вычисление tB(x) = a(x)·sB(x) + eB(x).
  8. Отправка tB(x) и C Алисе.

Дальнейшие шаги АлисыШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ:

  1. Получение tB(x) и C от Боба.
  2. Вычисление w(x) = tB(x)·sA(x) + eA(x) = a(x)sA(x)sB(x) + eB(x)sA(x) + eA(x).
  3. Формирование битового потока uj длины n следующим образом:
    1. Если cj = 0 и <math>\tfrac{-q}{8}</math> ≤ wj < <math>\tfrac{3q}{8}</math> тогда uj = 0, иначе uj = 1.
    2. Если cj = 1 и <math>\tfrac{-3q}{8}</math> ≤ wj < <math>\tfrac{q}{8}</math> тогда uj = 0, иначе uj = 1.
  4. Формирование ключа k, как конкатенации un-1, …, u0.

Если обмен ключами сработает должным образом то строки un-1, …, u0 у Алисы и Боба будут совпадатьШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ. В зависимости от специфики выбранных параметров n, q, σ и b, есть вероятность того, что tA(x) и tB(x) будут совпадать. Параметры для обмена ключами должны быть выбраны так, чтобы вероятность этой ошибки при обмене ключами была очень мала — гораздо меньше, чем вероятность неопределяемых искажений или сбоев устройств.

Выбор параметров

Обмен работает в кольце многочленов степени не больше n-1 по модулю многочлена Φ(х). Предполагается, что n — степень 2 , а q — простое, q ≡ 1 mod 4. Исходя из работы Пейкерта, Синг предложил два набора параметров для RWLE-KEXШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ.

Для 128-битовой защиты: n = 512, q = 25601 и Φ(x) = x512 + 1

Для 256-битовой защиты: n = 1024, q = 40961 и Φ(x) = x1024 + 1

Так как обмен ключами использует случайную ограниченную выборку, есть вероятность того, что будут сгенерированы одинаковые ключи для Алисы и Боба. Предположим, гауссов параметр σ = <math>\tfrac{8}{\sqrt {2 \pi}}</math> или используется равномерная выборка при b = 5, тогда вероятность ошибки совпадения открытых ключей меньше, чем 2−71 и 2−75 для 128 разрядных параметров и меньше 2−91 и 2−97для 256-битных параметров соответственноШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ.

В работе Алким, Дука, Попплеманн и Швабе (ноябрь 2015) рекомендуют следующие параметры: n = 1024, q = 12289, и Φ(x) = x1024 + 1, так как они обеспечивают эффективность и безопасность алгоритма. В случае 256-битовой защиты этот набор обеспечивает вероятность ошибки совпадения 2−110 Шаблон:Sfn.

Надежность алгоритма

Вычислительная сложность взлома RLWE-KEX того же порядка, что и решение кратчайшей векторной задачи (SVP) в идеальной решеткеШаблон:Sfn. Лучшим способом оценить практическую безопасность данного набора параметров решетки является Шаблон:Cite web. В соответствии с алгоритмом BKZ 2.0, основные параметры обмена, перечисленные выше, будут обеспечивать больше чем 128 и 256 бит безопасности соответственноШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ.

Примеры реализации

В 2014 году Дуглас Стебила сделал патч для OpenSSL 1.0.1f. на основе работ, опубликованных в книге «Post-quantum key exchange for the TLS protocol from the ring learning with errors problem». Программное обеспечение работы Синга находится на Шаблон:Cite webШаблон:Неавторитетный источникШаблон:Нет АИШаблон:SfnШаблон:Неавторитетный источникШаблон:Нет АИ.

Ещё одним вариантом применения алгоритма является работа Чжана, Динга, Снука и Дагделена Шаблон:Cite web. Концепция создания алгоритма Диффи-Хеллмана впервые была представлена французскими исследователями Агиларом, Габоритом, Лачармом, Шреком и Земором на PQCrypto 2010 года в их докладе Шаблон:Cite webШаблон:Неавторитетный источникШаблон:Нет АИ. Затем эта тема была расширена и положила начало более строгим исследованиям Пейкерта в его Шаблон:Cite webШаблон:Sfn.

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Криптосистемы с открытым ключом

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Обмен_ключами_на_основе_обучения_с_ошибками&oldid=10497069