ВЫЧИСЛИТЕЛЬНО ЭФФЕКТИВНЫЙ МЕТОД ОПРЕДЕЛЕНИЯ УСРЕДНЁННЫХ ЛИНЕЙНЫХ СВОЙСТВ ПСЕВДО-ДИНАМИЧЕСКИХ ПОДСТАНОВОК
Ключевые слова:
Псевдо-случайные функции, линейный криптоанализ, псевдо-динамические подстановки
Аннотация
Псевдо-динамические подстановки PD-sbox могут стать эффективной заменой фик-
сированных подстановок в псевдо-случайных функциях, так как обладают положительны-
ми свойствами как фиксированных подстановок (малый расход вычислительных ресурсов),
так и динамических подстановок (способных кардинально усложнять применение стати-
стических методов криптоанализа). Проблемой активного внедрения псевдо-динамических
подстановок является, в том числе, отсутствие вычислительно эффективного метода
определения усреднённых линейных свойств для всего множества генерируемых при помо-
щи PD-sbox эквивалентных подстановок, при этом в большинстве случаев интересует
только определение максимальных значений преобладания (смещения) bias(α, β) от идеаль-
ного значения 1/2. Для решения этой проблемы предлагается оригинальный метод, со-
стоящий в том, что максимальные значения преобладания рассчитываются только для
относительно небольших фиксированных подстановок, входящих в состав PD-sbox, а ре-
зультирующие максимальные значения преобладания получаются путём итерационного
вычисления с использованием логико-вероятностного выражения для операции Исключающего ИЛИ-НЕ (XNOR). Эффектом применения предложенного метода является карди-
нальное снижение вычислительных операций и, соответственно, возможность определе-
ния на типовом персональном компьютере максимальных значений преобладания bias(α, β)
для 16-элементных PD-sbox, состоящих из 8-битовых фиксированных подстановок (что
является недостижимым при использовании тривиального метода).
Литература
1. Preneel B. Final report of European project number IST-1999-12324, named New European
Schemes for Signatures, Integrity, and Encryption. Berlin Heidelberg NewYork London Paris
Tokyo Hong Kong Barcelona Budapest: Springer-Verlag, 2004.
2. Matsui M. The first experimental cryptanalysis of the data encryption standard, Y. Desmedt
(ed.), CRYPTO, Lecture Notes in Computer Science, Vol. 839. Springer, 1994, pp. 1-11.
3. Harpes C., Kramer G.G., Massey J.L. A generalization of linear cryptanalysis and the applicability
of Matsui’s piling-up lemma, L.C. Guillou, J.-J. Quisquater (eds.), EUROCRYPT, Lecture
Notes in Computer Science, Vol. 921. Springer, 1995, pp. 24-38.
4. Selçuk A.A. On probability of success in linear and differential cryptanalysis, J. Cryptology,
2008, Vol. 21 (1), pp. 131-147.
5. Bogdanov A., Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block
Ciphers. Designs, Codes and Cryptography. Springer, US, 2012, pp. 1-15.
6. Long Wen, Meiqin Wang, Andrey Bogdanov, Huaifeng Chen. Multidimensional zerocorrelation
attacks on lightweight block cipher HIGHT: Improved cryptanalysis of an ISO
standard, Information Processing Letters, 2014, Vol. 114, Issue 6, pp. 322-330. Available at:
https://doi.org/10.1016/j.ipl.2014.01.007.
7. Andrey Bogdanov, Elif Bilge Kavun, Elmar Tischhauser, Tolga Yalçın. Large-scale highresolution
computational validation of novel complexity models in linear cryptanalysis, Journal
of Computational and Applied Mathematics, 2014, Vol. 259, Part B, pp. 592-598.
Available at: https://doi.org/10.1016/j.cam.2013.10.020.
8. Eichlseder M., Leander G., & Rasoolzadeh S. (Accepted/In press). Computing Expected Differential
Probability of (Truncated) Differentials and Expected Linear Potential of (Multidimensional)
Linear Hulls in SPN Block Ciphers. In Progress in Cryptology - IndoCrypt 2020.
9. Logachev O.A., Sal'nikov A.A., Yashchenko V.V. Bulevy funktsii v teorii kodirovaniya i
kriptologii [Boolean functions in coding theory and cryptology]. Moscow: Moskovskiy tsentr
nepreryvnogo matematicheskogo obrazovaniya, 2004, 470 p.
10. Security Advisory 2868725: Recommendation to disable RC4. Security Research and Defense
Blog. Available at: http://blogs.technet.com/b/srd/archive/2013/11/12/security-advisory-
2868725-recommendation-to-disable-rc4.aspx.
11. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy podstanovki:
osnova sovremennykh simmetrichnykh kriptoalgoritmov [Pseudo-dynamic substitutions: the basis
of modern symmetric cryptoalgorithms], Nauchnoe obozrenie [Scientific Review], 2014, No. 12,
pp. 162-166. Available at: http://www.sced.ru/ru/files/7_12_1_2014/7_12_1_2014.pdf.
12. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Issledovanie lineynykh kharakteristik
psevdo-dinamicheskikh podstanovok [Investigation of linear characteristics of pseudodynamic
substitutions], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2015, No. 5 (166), pp. 111-123.
13. Polikarpov S.V., Kozhevnikov A.A. Psevdo-dinamicheskie podstanovoki: issledovanie lineynykh
svoystv [Pseudo-dynamic substitutions: investigation of linear propertie], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 8 (169), pp. 19-31.
14. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy
podstanovki: issledovanie differentsial'nykh kharakteristik [Pseudo-dynamic substitutions: research
of differential characteristics], Fiziko-matematicheskie metody i informatsionnye
tekhnologii v estestvoznanii, tekhnike i gumanitarnykh naukakh: sbornik materialov
mezhdunarodnogo nauchnogo e-simpoziuma [Physical and mathematical methods and information
technologies in natural science, engineering and humanities: collection of materials of
the international scientific e-symposium]. Electron. text data. Russia. Moscow, 2014. Kirov:
MTSNIP, 2015, pp. 77-89.
15. Sergey Polikarpov, Konstantin Rumyantsev and Dmitry Petrov. Computationally efficient
method for determining averaged distribution of differentials for pseudo-dynamic substitutions,
AIP Conference Proceedings 1952, 020091. 2018.
16. Polikarpov S., Petrov D., Kozhevnikov A. On A Class Pseudo-Dynamic Substitutions
PD-Sbox, With A Perfect Averaged Distribution of Differentials in Static Mode of Work, Proceedings
of the 2017 International Conference on Cryptography, Security and Privacy. Wuhan,
China: ACM, 2017, pp. 17-21. (ICCSP 17). ISBN 978-1-4503-4867-6. DOI:
10.1145/3058060.3058087. Available at: http://doi.acm.org/10.1145/3058060.3058087.
17. Kozhevnikov A.A., Polikarpov S.V., Rumyantsev K.E. On differential properties of a symmetric
cryptoalgorithm based on pseudo-dynamic substitutions, Matematicheskie voprosy
kriptografii [Mathematical questions of Cryptography], 2016, Vol. 7:2, pp. 91-102. Available
at: https://doi.org/10.4213/mvk186.
18. Polikarpov S.V., Kozhevnikov A.A., Rumyantsev K.E., Prudnikov V.A. Psevdosluchaynaya
funktsiya PCOLLAPSER, obespechivayushchaya ekstremal'nyy parallelizm obrabotki
informatsii [Pseudo-random function PCOLLAPSER providing extreme parallelism of information
processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2019, No. 5 (207), pp. 88-100.
19. Matsui Mitsuru. Linear Cryptoanalysis Method for DES Cipher, Advances in Cryptology -
EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques,
Lofthus, Norway, May 23-27, 1993, Proceedings, 1993, pp. 386-397. Available at:
http://dx.doi.org/10.1007/3-540-48285-7_33.
20. Ryabinin I.A. Logiko-veroyatnostnyy analiz problem i nadezhnosti, zhivuchesti i bezopasnosti:
ocherki raznykh let [Logical-probabilistic analysis of problems and reliability, survivability
and safety: essays from different years]. YURGTU, 2009. 599 p. Available at:
https://books.google.ru/books?id=7ACRkgAACAAJ.
Schemes for Signatures, Integrity, and Encryption. Berlin Heidelberg NewYork London Paris
Tokyo Hong Kong Barcelona Budapest: Springer-Verlag, 2004.
2. Matsui M. The first experimental cryptanalysis of the data encryption standard, Y. Desmedt
(ed.), CRYPTO, Lecture Notes in Computer Science, Vol. 839. Springer, 1994, pp. 1-11.
3. Harpes C., Kramer G.G., Massey J.L. A generalization of linear cryptanalysis and the applicability
of Matsui’s piling-up lemma, L.C. Guillou, J.-J. Quisquater (eds.), EUROCRYPT, Lecture
Notes in Computer Science, Vol. 921. Springer, 1995, pp. 24-38.
4. Selçuk A.A. On probability of success in linear and differential cryptanalysis, J. Cryptology,
2008, Vol. 21 (1), pp. 131-147.
5. Bogdanov A., Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block
Ciphers. Designs, Codes and Cryptography. Springer, US, 2012, pp. 1-15.
6. Long Wen, Meiqin Wang, Andrey Bogdanov, Huaifeng Chen. Multidimensional zerocorrelation
attacks on lightweight block cipher HIGHT: Improved cryptanalysis of an ISO
standard, Information Processing Letters, 2014, Vol. 114, Issue 6, pp. 322-330. Available at:
https://doi.org/10.1016/j.ipl.2014.01.007.
7. Andrey Bogdanov, Elif Bilge Kavun, Elmar Tischhauser, Tolga Yalçın. Large-scale highresolution
computational validation of novel complexity models in linear cryptanalysis, Journal
of Computational and Applied Mathematics, 2014, Vol. 259, Part B, pp. 592-598.
Available at: https://doi.org/10.1016/j.cam.2013.10.020.
8. Eichlseder M., Leander G., & Rasoolzadeh S. (Accepted/In press). Computing Expected Differential
Probability of (Truncated) Differentials and Expected Linear Potential of (Multidimensional)
Linear Hulls in SPN Block Ciphers. In Progress in Cryptology - IndoCrypt 2020.
9. Logachev O.A., Sal'nikov A.A., Yashchenko V.V. Bulevy funktsii v teorii kodirovaniya i
kriptologii [Boolean functions in coding theory and cryptology]. Moscow: Moskovskiy tsentr
nepreryvnogo matematicheskogo obrazovaniya, 2004, 470 p.
10. Security Advisory 2868725: Recommendation to disable RC4. Security Research and Defense
Blog. Available at: http://blogs.technet.com/b/srd/archive/2013/11/12/security-advisory-
2868725-recommendation-to-disable-rc4.aspx.
11. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy podstanovki:
osnova sovremennykh simmetrichnykh kriptoalgoritmov [Pseudo-dynamic substitutions: the basis
of modern symmetric cryptoalgorithms], Nauchnoe obozrenie [Scientific Review], 2014, No. 12,
pp. 162-166. Available at: http://www.sced.ru/ru/files/7_12_1_2014/7_12_1_2014.pdf.
12. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Issledovanie lineynykh kharakteristik
psevdo-dinamicheskikh podstanovok [Investigation of linear characteristics of pseudodynamic
substitutions], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2015, No. 5 (166), pp. 111-123.
13. Polikarpov S.V., Kozhevnikov A.A. Psevdo-dinamicheskie podstanovoki: issledovanie lineynykh
svoystv [Pseudo-dynamic substitutions: investigation of linear propertie], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 8 (169), pp. 19-31.
14. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy
podstanovki: issledovanie differentsial'nykh kharakteristik [Pseudo-dynamic substitutions: research
of differential characteristics], Fiziko-matematicheskie metody i informatsionnye
tekhnologii v estestvoznanii, tekhnike i gumanitarnykh naukakh: sbornik materialov
mezhdunarodnogo nauchnogo e-simpoziuma [Physical and mathematical methods and information
technologies in natural science, engineering and humanities: collection of materials of
the international scientific e-symposium]. Electron. text data. Russia. Moscow, 2014. Kirov:
MTSNIP, 2015, pp. 77-89.
15. Sergey Polikarpov, Konstantin Rumyantsev and Dmitry Petrov. Computationally efficient
method for determining averaged distribution of differentials for pseudo-dynamic substitutions,
AIP Conference Proceedings 1952, 020091. 2018.
16. Polikarpov S., Petrov D., Kozhevnikov A. On A Class Pseudo-Dynamic Substitutions
PD-Sbox, With A Perfect Averaged Distribution of Differentials in Static Mode of Work, Proceedings
of the 2017 International Conference on Cryptography, Security and Privacy. Wuhan,
China: ACM, 2017, pp. 17-21. (ICCSP 17). ISBN 978-1-4503-4867-6. DOI:
10.1145/3058060.3058087. Available at: http://doi.acm.org/10.1145/3058060.3058087.
17. Kozhevnikov A.A., Polikarpov S.V., Rumyantsev K.E. On differential properties of a symmetric
cryptoalgorithm based on pseudo-dynamic substitutions, Matematicheskie voprosy
kriptografii [Mathematical questions of Cryptography], 2016, Vol. 7:2, pp. 91-102. Available
at: https://doi.org/10.4213/mvk186.
18. Polikarpov S.V., Kozhevnikov A.A., Rumyantsev K.E., Prudnikov V.A. Psevdosluchaynaya
funktsiya PCOLLAPSER, obespechivayushchaya ekstremal'nyy parallelizm obrabotki
informatsii [Pseudo-random function PCOLLAPSER providing extreme parallelism of information
processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2019, No. 5 (207), pp. 88-100.
19. Matsui Mitsuru. Linear Cryptoanalysis Method for DES Cipher, Advances in Cryptology -
EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques,
Lofthus, Norway, May 23-27, 1993, Proceedings, 1993, pp. 386-397. Available at:
http://dx.doi.org/10.1007/3-540-48285-7_33.
20. Ryabinin I.A. Logiko-veroyatnostnyy analiz problem i nadezhnosti, zhivuchesti i bezopasnosti:
ocherki raznykh let [Logical-probabilistic analysis of problems and reliability, survivability
and safety: essays from different years]. YURGTU, 2009. 599 p. Available at:
https://books.google.ru/books?id=7ACRkgAACAAJ.
