Обмен ключами на основе обучения с ошибкамиВ криптографии обмен ключами при обучении с ошибками — криптографический алгоритм, позволяющий двум сторонам создавать и обмениваться секретным ключом, который они используют для шифрования сообщений между собой. RLWE-KEX (англ. Ring Learning with Errors Key Exchange) является одним из алгоритмов с открытым ключом, который предназначен для защиты от противника, обладающего квантовым компьютером. Это важно, потому что криптографические системы с открытым ключом, широко используемые сегодня, легко взламываются квантовым компьютером[1]. RLWE-KEX является одним из множества постквантовых криптографических алгоритмов, основанных на сложности решения математических задач, связанных с криптографией на решётках[2]. ПредпосылкиС 1980-х безопасность криптографического обмена ключами и цифровых подписей в Интернете была главным образом основана на небольшом числе основных криптосистем с открытым ключом. Криптостойкость этих алгоритмов основывается на маленьком количестве задач, сложных для вычислений классическими методами, но довольно легко решаемых с помощью квантового компьютера[3]. Эти задачи — факторизация двух тщательно подобранных простых чисел, трудность вычисления дискретного логарифма в выбранном конечном поле и трудность вычисления дискретного логарифма в подобранной группе точек эллиптической кривой. Существует мнение, что квантовые компьютеры будут доступны уже через 10-15 лет[4]. Если квантовые компьютеры с достаточной памятью были бы построены, все криптосистемы с открытым ключом, основанные на этих трех классических трудных задачах, стали бы крайне уязвимыми[1]. Такой тип криптографии с открытым ключом используется сегодня для защиты интернет-сайтов, авторизационной информации компьютера и для предотвращения компьютеров от получения вредоносного программного обеспечения[5]. Криптография, которая не поддается взлому квантовым компьютером, называется квантово-защищенной или постквантовой криптографией. Один из классов этих алгоритмов основан на концепции «обучение с ошибками», введенной Одедом Регев в 2005 году[6]. Специализированная форма обучения с ошибками работает в кольце многочленов над конечным полем. Эта специализированная форма называется кольцом обучения с ошибками или RLWE[7]. Существует множество криптографических алгоритмов, которые работают с использованием парадигмы RLWE. Есть криптосистема с открытым ключом, гомоморфные алгоритмы шифрования и RLWE цифровая подпись алгоритма в дополнение к открытому ключу. Обмен ключами является типом асимметричного шифрования, который устанавливает общий секретный ключ между двумя взаимодействующими агентами на линии связи. Классическим примером обмена ключами является протокол Диффи — Хеллмана (и, как его расширение, Протокол Диффи — Хеллмана на эллиптических кривых). Обмен состоит из одной передачи с одного конца линии и одной передачи с другого конца линии[8][неавторитетный источник][источник не указан 3275 дней]. RLWE обмен ключами разработан как квантово-безопасная замена для протоколов, которые используются для обеспечения безопасности создания секретных ключей по ненадежным каналам связи. Также как и протокол Диффи—Хеллмана, RLWE обеспечивает криптографическое свойство «совершенно прямой секретности»[9][неавторитетный источник][источник не указан 3275 дней], целью которого является снижение эффективности программ массового наблюдения и убеждение, что нет долгосрочных секретных ключей, которые могут быть скомпрометированы, что позволит осуществить объемную расшифровку. Описание алгоритмаВведениеИспользуя простое число q, RLWE работает в кольце многочленов по модулю полинома Ф(х) с коэффициентами в поле целых чисел по модулю q (кольцо Fq[x]/Φ(x))[10][8][неавторитетный источник][источник не указан 3275 дней]. Полином a(x) выражается следующим образом:
Коэффициенты этого полинома являются целыми числами по модулю q. Полином Φ(x) = xn +1, где n является степенью 2 (в большинстве случаев значения для n = 256, 512 или 1024). RLWE-KEX использует полиномы, которые считаются «малыми» по отношению к мере, называемой «бесконечной» нормой[11][неавторитетный источник][источник не указан 3275 дней]. Бесконечная норма для многочлена — значение наибольшего коэффициента полинома, когда коэффициенты рассматриваются как элементы множества {,…, 0, …, }. Для обеспечения безопасности алгоритма необходимо генерировать случайные полиномы s(x), малые по отношению к бесконечной норме. Это делается случайным формированием коэффициентов для многочлена (sn-1, …, s0), которые гарантированно или с большой вероятностью будут небольшими. Есть два распространенных способа:
Пусть случайные небольшие полиномы будут соответствовать распределению, обозначенному как D. Число q будет нечетным простым таким, что q ≡ 1 mod 4 и Пусть фиксированный многочлен а(х) — общий для всех пользователей сети, генерируемый с помощью криптографическистойкого генератора псевдослучайных чисел. Взяв а(х), произвольно выбираются небольшие многочлены s(x) и e(x), s(x) — закрытый ключ в обмене открытыми ключами. Соответствующим открытым ключом будет многочлен t(х) = а(х)s(х) + е(х)[11][неавторитетный источник][источник не указан 3275 дней]. Безопасность обмена ключами основана на трудности найти пару небольших многочленов s'(х) и e'(х)таких, что для данной t(х) а(х)s'(х) + е'(х) = t(х). Обмен ключамиОбмен ключами происходит между агентами обмена ключами Алисой, обозначенной как A, и Бобом, обозначенным как B. И A, и B знают q, n, a(x) и умеют генерировать небольшие полиномы в соответствии с распределением D[10][17]. Первоначальные действия Алисы[17][неавторитетный источник][источник не указан 3275 дней]:
Действия Боба[17][неавторитетный источник][источник не указан 3275 дней]:
Дальнейшие шаги Алисы[17][неавторитетный источник][источник не указан 3275 дней]:
Если обмен ключами сработает должным образом то строки un-1, …, u0 у Алисы и Боба будут совпадать[18][неавторитетный источник][источник не указан 3275 дней]. В зависимости от специфики выбранных параметров n, q, σ и b, есть вероятность того, что tA(x) и tB(x) будут совпадать. Параметры для обмена ключами должны быть выбраны так, чтобы вероятность этой ошибки при обмене ключами была очень мала — гораздо меньше, чем вероятность неопределяемых искажений или сбоев устройств. Выбор параметровОбмен работает в кольце многочленов степени не больше n-1 по модулю многочлена Φ(х). Предполагается, что n — степень 2 , а q — простое, q ≡ 1 mod 4. Исходя из работы Пейкерта, Синг предложил два набора параметров для RWLE-KEX[19][неавторитетный источник][источник не указан 3275 дней]. Для 128-битовой защиты: n = 512, q = 25601 и Φ(x) = x512 + 1 Для 256-битовой защиты: n = 1024, q = 40961 и Φ(x) = x1024 + 1 Так как обмен ключами использует случайную ограниченную выборку, есть вероятность того, что будут сгенерированы одинаковые ключи для Алисы и Боба. Предположим, гауссов параметр σ = или используется равномерная выборка при b = 5, тогда вероятность ошибки совпадения открытых ключей меньше, чем 2−71 и 2−75 для 128 разрядных параметров и меньше 2−91 и 2−97для 256-битных параметров соответственно[19][неавторитетный источник][источник не указан 3275 дней]. В работе Алким, Дука, Попплеманн и Швабе (ноябрь 2015) рекомендуют следующие параметры: n = 1024, q = 12289, и Φ(x) = x1024 + 1, так как они обеспечивают эффективность и безопасность алгоритма. В случае 256-битовой защиты этот набор обеспечивает вероятность ошибки совпадения 2−110 [20]. Надежность алгоритмаВычислительная сложность взлома RLWE-KEX того же порядка, что и решение кратчайшей векторной задачи (SVP) в идеальной решетке[21]. Лучшим способом оценить практическую безопасность данного набора параметров решетки является алгоритм сокращения BKZ 2.0 .. В соответствии с алгоритмом BKZ 2.0, основные параметры обмена, перечисленные выше, будут обеспечивать больше чем 128 и 256 бит безопасности соответственно[22][неавторитетный источник][источник не указан 3275 дней]. Примеры реализацииВ 2014 году Дуглас Стебила сделал патч для OpenSSL 1.0.1f. на основе работ, опубликованных в книге «Post-quantum key exchange for the TLS protocol from the ring learning with errors problem». Программное обеспечение работы Синга находится на GitHub .[неавторитетный источник][источник не указан 3275 дней][23][неавторитетный источник][источник не указан 3275 дней]. Ещё одним вариантом применения алгоритма является работа Чжана, Динга, Снука и Дагделена «Post Quantum Authenticated Key Exchange from Ideal Lattices» .. Концепция создания алгоритма Диффи-Хеллмана впервые была представлена французскими исследователями Агиларом, Габоритом, Лачармом, Шреком и Земором на PQCrypto 2010 года в их докладе «Noisy Diffie-Hellman Protocols» . Дата обращения: 1 декабря 2015. Архивировано из оригинала 24 сентября 2015 года.[неавторитетный источник][источник не указан 3275 дней]. Затем эта тема была расширена и положила начало более строгим исследованиям Пейкерта в его работе .[24]. См. такжеПримечания
Литература
|