Том 27, номер 4, 2020 г., Стр. 21-57
УДК 519.7+518.25
Городилова А. А., Токарева Н. Н., Агиевич C. В., Карле К., Горкунов Е. В., Идрисова В. А., Коломеец Н. А., Куценко А. В., Лебедев Р. К., Никова С., Облаухов А. К., Панкратова И. А., Пудовкина М. А., Реймен В., Удовенко А. Н.
О Шестой Международной олимпиаде по криптографии NSUCRYPTO
Аннотация:
Представлены задачи Шестой международной олимпиады по криптографии NSUCRYPTO’2019 вместе с их решениями. Рассмотренные задачи связаны с атаками на шифры и хэш-функции, протоколами, булевыми функциями, полиномами Диксона, простыми числами, роторными машинами и т. д. Обсуждаются несколько открытых проблем по математическим мерам противо- действия атакам по сторонним каналам, APN-инволюциям, S-блокам и т. д. Задача о поиске коллизии для хеш-функции Curl27 была частично решена во время олимпиады.
Табл. 11, ил. 7, библиогр. 21.
Ключевые слова: криптография, шифр, хэш-функция, код Хэмминга, слайдовая атака, пороговая реализация, полином Диксона, APN-функция, олимпиада, NSUCRYPTO.
DOI: 10.33048/daio.2020.27.689
Городилова Анастасия Александровна 1
Токарева Наталья Николаевна 1,2
Агиевич Сергей Валерьевич 3
Карле Клод 4
Горкунов Евгений Владимирович 1,5
Идрисова Валерия Александровна 1
Коломеец Николай Александрович 1
Куценко Александр Владимирович 1,5
Лебедев Роман Константинович 5
Никова Светла 6
Облаухов Алексей Константинович 1
Панкратова Ирина Анатольевна 7
Пудовкина Марина Александровна 8
Реймен Винсент 6
Удовенко Алексей Николаевич 9
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Лаборатория криптографии JetBrains Research,
ул. Пирогова, 1, 630090 Новосибирск, Россия
3. Белорусский гос. университет,
пр. Независимости, 4, 220030 Минск, Беларусь
4. University of Paris 8,
Rue de la Liberte, 2, 93200 Saint-Denis, France
5. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
6. ESAT-COSIC, KU Leuven,
Kasteelpark Arenberg, 10, B-3001 Leuven, Belgium
7. Томский гос. университет,
пр. Ленина, 36, 634050 Томск, Россия
8. Московский гос. технический университет им. Н. Э. Баумана,
ул. 2-я Бауманская, 5/1, 105005 Москва, Россия
9. SnT, University of Luxembourg,
Avenue de l’Universite, 2, L-4365 Esch-sur-Alzette, Luxembourg
е-mail: nsucrypto@nsu.ru
Статья поступила 20 мая 2020 г.
После доработки — 18 августа 2020 г.
Принята к публикации 21 августа 2020 г.
Литература
[1] The official website of NSUCRYPTO. Novosibirsk: Novosibirsk State Univ., 2020. Available at nsucrypto.nsu.ru (accessed Sept. 24, 2020).
[2] Unsolved problems of NSUCRYPTO. Available at nsucrypto.nsu.ru/unsolved-problems (accessed Sept. 24, 2020).
[3] Геут К. Л., Кириенко К. А., Садков П. О., Таскин Р. И., Титов С. С. О явных конструкциях для решения задачи “A secret sharing” // Прикл. дискрет. математика. Прил. 2017. № 10. С. 68–70.
[4] Agievich S. V., Gorodilova A. A., Idrisova V. A., Kolomeec N. A., Shushuev G. I., Tokareva N. N. Mathematical problems of the Second International Students’ Olympiad in Cryptography // Cryptologia. 2017. Vol. 41, No. 6. P. 534–565.
[5] Agievich S. V., Gorodilova A. A., Kolomeec N. A., Nikova S., Preneel B., Rijmen V., Shushuev G. I., Tokareva N. N., Vitkup V. A. Problems, solutions and experience of the First International Students’ Olympiad in Cryptography // Прикл. дискрет. математика. 2015. № 3. С. 41–62.
[6] Gorodilova A. A., Agievich S. V., Carlet C., Gorkunov E. V., Idrisova V. A., Kolomeec N. A., Kutsenko A. V., Nikova S., Oblaukhov A. K., Picek S., Preneel B., Rijmen V., Tokareva N. N. Problems and solutions from the Fourth International Students’ Olympiad in Cryptography (NSUCRYPTO) // Cryptologia. 2019. Vol. 43, No. 2. P. 138–174.
[7] Gorodilova A. A., Agievich S. V., Carlet C., Hou X., Idrisova V. A., Kolomeec N. A., Kutsenko A. V., Mariot L., Oblaukhov A. K., Picek S., Preneel B., Rosie R., Tokareva N. N. The Fifth International Students’ Olympiad in Cryptography – NSUCRYPTO: Problems and their solutions // Cryptologia. 2020. Vol. 44, No. 3. P. 223–256.
[8] Tokareva N. N., Gorodilova A. A., Agievich S. V., Idrisova V. A., Kolomeec N. A., Kutsenko A. V.,Oblaukhov A. K., Shushuev G. I. Mathematical methods in solutions of the problems presented at the Third International Students’ Olympiad in Cryptography // Прикл. дискрет. математика.
2018. № 40. С. 34–58.
[9] Schneier B. Applied cryptography: Protocols, algorithms and source code in C. Hoboken, NJ: Wiley, 1996.
[10] Lewand R. E. Cryptological mathematics. Washington, DC: MAA Press, 2000.
[11] Letter frequency // Wikipedia. San Francisco: Wikimedia Foundation, 2020. Available at en.wikipedia.org/wiki/Letter_frequency (accessed Sept. 24, 2020).
[12] Find words using pattern matching // Litscape.com. Calgary: The Bitmill, 2018. Available at www.litscape.com/word_tools/pattern_match.php (accessed Sept. 24, 2020).
[13] Brinkmann M., Leander G. On the classification of APN functions up to dimension five // Des. Codes Cryptogr. 2008. Vol. 49, No. 1–3. P. 273–288.
[14] De Cannière C. Analysis and design of symmetric encryption algorithms: PhD thesis. Katholieke Univ. Leuven, Heverlee, 2007.
[15] Test server for the problem TwinPeaks3. Available at nsucrypto.nsu.ru/archive/2019/round/2/task/4 (accessed Sept. 24, 2020).
[16] An implementation for the function Curl27 in Java. Available at nsucrypto.nsu.ru/media/Olympiads/2019/Round_2/Tasks/curl27.java (accessed Sept. 24, 2020).
[17] De la Cruz Jiménez R. A. Generation of 8-bit S-boxes having almost optimal cryptographic properties using smaller 4-bit S-boxes and finite field multiplication // Progress in Cryptology – LATINCRYPT 2017. Rev. Sel. Pap. 5th Int. Conf. Cryptol. Inform. Secur. Latin America (Havana, Cuba, Sept. 20–22, 2017). Cham: Springer, 2019. P. 191–206. (Lect. Notes Comput. Sci.; Vol. 11368).
[18] Fomin D. B. New classes of 8-bit permutations based on a butterfly structure // Мат. вопросы криптографии. 2019. T. 10, вып. 2. C. 169–180.
[19] Carlet C. Componentwise APNness, Walsh uniformity of APN functions, and cyclic-additive difference sets // Finite Fields Appl. 2018. Vol. 53. P. 226–253.
[20] Carlet C. On APN exponents, characterizations of differentially uniform functions by the Walsh transform, and related cyclic-difference-set-like structures // Des. Codes Cryptogr. 2019. Vol. 87, No. 2–3. P. 203–224.
[21] Total results of NSUCRYPTO’2019. Available at nsucrypto.nsu.ru/archive/2019/total_results/#data (accessed Sept. 24, 2020).
|