Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1
The paper analyzes the post-quantum AJPS-1 cryptosystem, which participated in the first round of the NIST post-quantum crypto primitives competition. The weak values of the public key of the cryptosystem are found and the necessary conditions for the public key to ensure t...
Saved in:
| Date: | 2023 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Subjects: | |
| Online Access: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/324 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Physico-mathematical modeling and informational technologies |
| Download file: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479696831152128 |
|---|---|
| author | Yadukha, Dariya |
| author_facet | Yadukha, Dariya |
| author_institution_txt_mv | [
{
"author": "Dariya Yadukha",
"institution": "аспірантка НН ФТІ НТУУ «КПІ ім. Ігоря Сікорського», асистент кафедри математичних методів захисту інформації НН ФТІ НТУУ «КПІ ім. Ігоря Сікорського», пр. Берестейський, 37, 03056, м. Київ"
}
] |
| author_sort | Yadukha, Dariya |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | The paper analyzes the post-quantum AJPS-1 cryptosystem, which participated in the first round of the NIST post-quantum crypto primitives competition. The weak values of the public key of the cryptosystem are found and the necessary conditions for the public key to ensure the security of the cryptosystem are given. By generalizing other known attacks on AJPS-1, recommendations for choice of secret and public keys are given. The double encryption approach has been applied to the AJPS-1 cryptosystem, and it has been proved that there are no restrictions on the public key in this case. |
| first_indexed | 2026-06-09T01:10:23Z |
| format | Article |
| fulltext |
154
doi.org/10.15407/fmmit2023.37.154
Визначення необхідних умов на значення ключів
постквантової криптосистеми AJPS-1
Дарія Ядуха1
1 аспірантка НН ФТІ НТУУ «КПІ ім. Ігоря Сікорського», асистент кафедри математичних методів захисту
інформації НН ФТІ НТУУ «КПІ ім. Ігоря Сікорського», пр. Берестейський, 37, 03056, м. Київ,
e-mail: dariya.yadukha@gmail.com
У роботі проведено аналіз постквантової криптосистеми AJPS-1, яка є учасником першого
раунду конкурсу постквантових криптопримітивів NIST. Знайдено слабкі значення
відкритого ключа криптосистеми та наведено необхідні умови на значення відкритого
ключа для забезпечення захищеності криптосистеми. Узагальнюючи інші відомі атаки на
AJPS-1, сформовано рекомендації щодо вибору особистого та відкритого ключів.
Застосовано підхід подвійного шифрування до криптосистеми AJPS-1 та доведено, що в
такому випадку не буде виникати обмежень на вибір відкритого ключа.
Ключові слова: криптосистема AJPS, постквантова криптосистема, число
Мерсенна, вага Геммінга
Вступ. Останні кілька років активно розвивається постквантова криптографія,
задачею якої є розробка криптографічних примітивів, які є стійкими до атак як з
використанням класичного, так і квантового комп’ютерів. З 2017 року триває
конкурс постквантових криптопримітивів під егідою Національного інституту
стандартів і технологій США (NIST), після закінчення якого будуть опубліковані
перші версії стандартів постквантової криптографії [1]. Одним з учасників
першого раунду конкурсу є механізм інкапсуляції Mersenne-756839, який
оснований на криптосистемі AJPS [2]. Особливістю криптосистеми AJPS є
використання арифметики за модулем числа Мерсенна, яка може бути ефективно
реалізована шляхом застосування алгоритмів швидкого обчислення
трудомістких операцій за модулем числа Мерсенна, таких як редукція,
множення, пошук оберненого тощо [3]. Криптосистема AJPS має дві версії – для
шифрування біту повідомлення (AJPS-1) та для шифрування блоку бітів
повідомлення (AJPS-2).
1. Опис криптосистеми AJPS-1
Криптосистема AJPS-1 [2] дозволяє зашифрувати один біт повідомлення
b{0,1}. При побудові криптосистеми задається параметр захищеності .
Відкритими параметрами криптосистеми є числа ,12 n
nM n та ,h ,
де h – фіксоване число, яке задовольняє умовам
2h
nC та .164 22 hnh Тут
і надалі для спрощення запису ототожнюємо числа за модулем числа Мерсенна
УДК 003.26.09
mailto:dariya.yadukha@gmail.com
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 154-158
155
та двійкові рядки довжини n. Це можливо, оскільки між множинами цих об'єктів
існує взаємно однозначне відображення. Позначимо множину чисел, які за
модулем числа Мерсенна
nM мають вагу Геммінга h, як
,)mod(:, hMxHamxHM nhn де Ham(x) позначає вагу Геммінга числа х.
1) Створення ключів: числа F та G обираються випадково та незалежно з
множини .,hnHM Особистим ключем є число G, а відкритим ключем – число
.mod1
nMGFH
2) Шифротекст C обчислюється за формулою ,) mod ()1( n
b MBHAС
де A та B – незалежно і рівноймовірно обрані значення з множини .,hnHM
3) Для розшифрування обчислюється значення ), mod ( nMGCHamd
після чого біт b визначається таким чином:
) (,
2,1
2,0
2
2
ннярозшифрувапомилкаінакше
hndякщо
hdякщо
b .
Коректність розшифрування ґрунтується на Лемі 1.
Лема 1. [2] Для довільних чисел
nBA }1,0{, та числа Мерсенна
nM
виконуються співвідношення:
1. )()() mod( BHamAHamMBAHam n ;
2. )()() mod( BHamAHamMBAHam n ;
3. Якщо
nA 0 , то )() mod( AHamnMAHam n .
Стійкість криптосистеми AJPS-1 базується на складності задачі MLHRSP [2] –
Задачі ділення чисел з малою вагою Геммінга за модулем числа Мерсенна
(англ. Mersenne Low Hamming Ratio Search Problem).
Означення 1 (MLHRSP). Маючи число Мерсенна ,nM n-бітове число H і ціле
число h, знайти два n-бітових числа F, G, кожне ваги Геммінга щонайбільше h,
таких, що .mod 1
nMGFH
2. Умови на значення ключів криптосистеми AJPS-1
Одним з напрямків обґрунтування захищеності будь-якої криптосистеми є аналіз
побудованих на криптосистему атак та оцінка їх успішності. Частину
побудованих на AJPS-1 атак можливо застосувати лише за умови, що
виконується певне припущення про вигляд чисел F та G.
1) Атака «Слабкий ключ» [4] є успішною, якщо усі одиниці у двійковому
представленні чисел F та G знаходяться у правій частині двійкового
представлення, тобто якщо кожне з чисел F, G менше за .nM Атака дозволяє
визначити значення особистого ключа за допомогою методу раціональної
реконструкції, тобто методу пошуку раціонального числа, використовуючи
Дарія Ядуха
Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1
156
результат редукції цього числа за деяким модулем. Cкладність атаки .2 )1(2 oh n
2) Атака «Slice-and-Dice» з використанням алгоритму LLL [5] побудована
аналогічно до атаки «Слабкий ключ». В цій атаці на числа F та G накладається
умова, щоб усі їхні ненульові значення бітів знаходились згруповано у одній
частині бінарного запису числа. Атака використовує ідею розділення бінарного
представлення числа на проміжки, які будуть використовуватись для побудови
решітки. Якщо інтервали підібрані правильно, то найкоротшими векторами
побудованої решітки будуть значення F та G. Складність такої атаки
ho 2))1(2( для деякої малої константи .0 Також при реалізації цієї
атаки можна використовувати SVP-оракули для пошуку F та G. Такий спосіб
дозволяє збільшити ймовірність успіху атаки до ,)1(
2
2
1 h
o однак також
збільшує час виконання операції редукції решітки до .2 )()2( hoh
Слід зауважити, що, навіть якщо потрібні для атак умови виконуються,
складність описаних атак є все одно досить великою, що унеможливлює їх
використання на практиці. Однак, для підвищення стійкості криптосистеми
AJPS-1, можна виконувати низку необхідних перевірок при застосуванні
алгоритму створення ключів, і виконувати кроки алгоритму створення ключів
повторно у випадку порушення однієї з вимог.
Також при визначенні умов на алгоритм створення ключів варто врахувати
необхідні умови на значення відкритого ключа криптосистеми AJPS-1.
Твердження 1. У криптосистемі AJPS-1 при виконанні однієї з умов:
1)mod( 1)( 1
nMHHamабоHHam
можливе дешифрування шифротексту без використання особистого ключа.
Доведення. Розглянемо випадки, коли можливе розшифрування без знання
особистого ключа. Для розшифрування знаходять значення d:
).mod)()1(()mod( n
b
n MGBHAHamMGCHamd
Відповідно до значення біту b, можливі випадки:
1) Якщо b = 0, то, застосувавши Лему 1, маємо:
).())()()(()mod)(( GHamBHamHHamAHamMGBHAHamd n
Оскільки за умовою криптосистеми числа A, B та G мають вагу Геммінга h, то
отримаємо ).1)((2 HHamhd Для того, щоб при розшифруванні отримати
біт 0, потрібно, щоб виконувалась нерівність .2 2hd Отже, дешифрування біту
0 без використання особистого ключа можливе при 1)( HHam .
2) Якщо ж b = 1, то, відповідно до Леми 1, маємо:
).())()()((()mod)(( GHamBHamHHamAHamnMGBAHHamnd n
Оскільки Ham(A) = Ham(B) = Ham(G) = h, то ).1)((2 HHamhnd Для того,
щоб результатом розшифрування був біт 1, має виконуватись умова ,2 2hnd
тобто отримаємо таку нерівність:
22 2)1)(( hnHHamhn .
Отже, розшифрування біту 1 без використання особистого ключа можливе
при виконанні умови ,1)( HHam як і у випадку розшифрування біту 0.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 154-158
157
Умова 1)mod( 1
nMHHam отримується аналогічно, врахувавши, що
nMFHG mod1
.
Узагальнюючи умови на значення F та G наведених атак, а також
враховуючи обмеження на значення H криптосистеми AJPS-1, що описані у
Твердженні 1, сформуємо рекомендації для алгоритмів створення ключів
криптосистеми AJPS-1.
Твердження 2 (Рекомендації для алгоритму створення ключів
криптосистеми AJPS-1). Нехай в результаті застосування алгоритму створення
ключів AJPS-1 отримано G – особистий ключ, F – секретний параметр
криптосистеми, nMGFH mod 1 – відкритий ключ. Для забезпечення
захищеності від описаних атак (а саме атак Слабкий ключ, Slice-and-Dice та
атаки, що наведена у Твердженні 1) необхідно, щоб значення F, G та H
задовольняли таким умовам:
1) Хоча б одне з чисел F та G має бути більшим або рівним ,nM тобто має
виконуватись така умова:
.
,
n
n
MG
MF
2) В бінарному записі хоча б одного з чисел F та G одиниці не згруповані
разом (є хоча б один нуль між h одиницями), тобто виконується умова:
.,02
,,0,2
hnjMG
hniMF
h
j
h
i
3) Число H задовольняє таким умовам:
.1)mod( 1)( 1
nMHHamтаHHam
Якщо хоча б одна з наведених умов не виконується, то необхідно повторно
застосувати алгоритм створення ключів. Якщо усі умови виконуються, то G та H
можна використовувати для подальшої роботи криптосистеми.
Доведення. Пункт 1 отримано з умови атаки «Слабкий ключ». Розглянемо
обґрунтування пункту 2. Умовою застосування атаки «Slice-and-Dice» є вимога,
щоб усі одиниці у двійковому представленні чисел F та G знаходились
згруповано. Оскільки числа F та G мають вагу Геммінга h, то h одиниць мають
знаходитись поруч (без нулів між ними) у двійковому записі цих чисел.
Розглянемо число Мерсенна .12 h
hM У двійковому записі воно має вигляд
11…1, причому одиниць рівно h. Таким чином, число hM є одним з «слабких»
значень для чисел F, G. При множенні на двійку отримаємо
,10...11mod2 nh MM тобто ще одне «слабке» значення для чисел F та G.
Оскільки числа F, G за умовою криптосистеми є n-бітовими, то максимальний
степінь двійки, на який можна домножити hM для отримання «слабкого»
значення, є (n – h), адже множення на степінь двійки за модулем числа Мерсенна
є циклічним зсувом числа вліво [3]. Пункт 3 ґрунтується на Твердженні 1.
Дарія Ядуха
Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1
158
Іншим способом запобігти атакам, що використовують слабкі значення
відкритого ключа H, які описано у Твердженні 1, є застосування схеми
подвійного шифрування, у якій шифротекст, отриманий у результаті першого
шифрування, використовуються як відкритий ключ при другому шифруванні.
Лема 3. Якщо у криптосистемі AJPS-1 шифротекст буде обчислений як
),()1( 22 BHAС C
b де )()1( 11
*
BHAH b
C , біт
*b {0,1}
обирається випадково, та
hnHMBBAA ,2121 ,,, , то атака, що описана у
Твердженні 1, не буде успішною при будь-яких значеннях відкритого ключа H.
Доведення. Слідує з Леми 1 та умови алгоритму створення ключів AJPS-1,
розглядаємо 4 варіанти комбінацій можливих значень бітів b та b*.
Висновки. У роботі виконано аналіз постквантової криптосистеми AJPS-1,
здійснено огляд деяких відомих атак на AJPS-1, а саме атаки «Слабкий ключ» та
«Slice-and-Dice» з використанням алгоритму LLL. Також у роботі визначено
обмеження на значення відкритого ключа криптосистеми AJPS-1. Узагальнюючи
вимоги для можливого застосування наведених атак та знайдені обмеження на
значення відкритого ключа, сформовано рекомендації для алгоритмів створення
ключів AJPS-1, які дозволяють підвищити захищеність криптосистеми. Також
доведено, що застосування підходу подвійного шифрування у AJPS-1 дозволяє
уникнути виникнення слабких значень відкритого ключа.
Література
[1] Post-Quantum Cryptography Standardization. National Institute of Standards and Technology,
Available:https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Cryptography-
Standardization.
[2] D. Aggarwal, A. Joux, A. Prakash, M. Santha. A New Public-Key Cryptosystem via Mersenne
Numbers. IACR Cryptology ePrint Archive. – Available: https://eprint.iacr.org/2017/481.
[3] S. Baktir, B. Sunar. Optimal Extension Field Inversion in the Frequency Domain. Arithmetic of
Finite Fields. Siena: Springer, 2008.
[4] M. Beunardeau, A. Connolly, R. Geraud, D. Naccache. On the Hardness of the Mersenne Low
Hamming Ratio Assumption. Available: https://eprint.iacr.org/2017/522.
[5] M. Tiepelt, A. Szepieniec. Quantum LLL with an Application to Mersenne Number Cryptosystems.
Progress in Cryptology – LATINCRYPT 2019.
The necessary conditions for the key generation of the quantum-
resistant AJPS-1 cryptosystem
Dariya Yadukha
The paper analyzes the post-quantum AJPS-1 cryptosystem, which participated in the first round
of the NIST post-quantum crypto primitives competition. The weak values of the public key of the
cryptosystem are found and the necessary conditions for the public key to ensure the security of
the cryptosystem are given. By generalizing other known attacks on AJPS-1, recommendations for
choice of secret and public keys are given. The double encryption approach has been applied to
the AJPS-1 cryptosystem, and it has been proved that there are no restrictions on the public key in
this case.
Отримано 12.03. 23
https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%82%D0%BA%D0%B8%D0%BD,_%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%B9_%D0%90%D1%80%D1%81%D0%B5%D0%BD%D1%8C%D0%B5%D0%B2%D0%B8%D1%87
https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%82%D0%BA%D0%B8%D0%BD,_%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%B9_%D0%90%D1%80%D1%81%D0%B5%D0%BD%D1%8C%D0%B5%D0%B2%D0%B8%D1%87
https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%82%D0%BA%D0%B8%D0%BD,_%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%B9_%D0%90%D1%80%D1%81%D0%B5%D0%BD%D1%8C%D0%B5%D0%B2%D0%B8%D1%87
https://eprint.iacr.org/2017/481
https://eprint.iacr.org/2017/522
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-324 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:10:23Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/ce/53bcdb977c31dcffa582042f9747d2ce.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-3242025-02-21T17:31:10Z The necessary conditions for the key generation of the quantum- resistant AJPS-1 cryptosystem Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1 Yadukha, Dariya криптосистема AJPS, постквантова криптосистема, число Мерсенна, вага Геммінга The paper analyzes the post-quantum AJPS-1 cryptosystem, which participated in the first round of the NIST post-quantum crypto primitives competition. The weak values of the public key of the cryptosystem are found and the necessary conditions for the public key to ensure the security of the cryptosystem are given. By generalizing other known attacks on AJPS-1, recommendations for choice of secret and public keys are given. The double encryption approach has been applied to the AJPS-1 cryptosystem, and it has been proved that there are no restrictions on the public key in this case. У роботі проведено аналіз постквантової криптосистеми AJPS-1, яка є учасником першого раунду конкурсу постквантових криптопримітивів NIST. Знайдено слабкі значення відкритого ключа криптосистеми та наведено необхідні умови на значення відкритого ключа для забезпечення захищеності криптосистеми. Узагальнюючи інші відомі атаки на AJPS-1, сформовано рекомендації щодо вибору особистого та відкритого ключів. Застосовано підхід подвійного шифрування до криптосистеми AJPS-1 та доведено, що в такому випадку не буде виникати обмежень на вибір відкритого ключа. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-29 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/324 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 154-158 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 154-158 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/324/292 Авторське право (c) 2023 Дарія Ядуха (Автор) |
| spellingShingle | криптосистема AJPS постквантова криптосистема число Мерсенна вага Геммінга Yadukha, Dariya Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1 |
| title | Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1 |
| title_alt | The necessary conditions for the key generation of the quantum- resistant AJPS-1 cryptosystem |
| title_full | Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1 |
| title_fullStr | Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1 |
| title_full_unstemmed | Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1 |
| title_short | Визначення необхідних умов на значення ключів постквантової криптосистеми AJPS-1 |
| title_sort | визначення необхідних умов на значення ключів постквантової криптосистеми ajps-1 |
| topic | криптосистема AJPS постквантова криптосистема число Мерсенна вага Геммінга |
| topic_facet | криптосистема AJPS постквантова криптосистема число Мерсенна вага Геммінга |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/324 |
| work_keys_str_mv | AT yadukhadariya thenecessaryconditionsforthekeygenerationofthequantumresistantajps1cryptosystem AT yadukhadariya viznačennâneobhídnihumovnaznačennâklûčívpostkvantovoíkriptosistemiajps1 AT yadukhadariya necessaryconditionsforthekeygenerationofthequantumresistantajps1cryptosystem |