Combinatorics-algebraic models in cryptography

V. G. Skobelev

Prikladnaâ diskretnaâ matematika, no. 11 (2009), pp. 74-114.

Résumé

These lectures are devoted to the characterization of descriptive, algorithmic and metric applied aspects of combinatorics-algebraic models for investigation of modern cryptography problems. Some basic ways for application of chaotic dynamics models and methods are presented. Linear and non-linear automata described by systems of equations over the ring $\mathbf Z_{p^k}$ are characterized. Some subsets of invertible automata for design of symmetric stream ciphers are considered.

Bibliographie

[1] Skobelev V. V., Skobelev V. G., Analiz shifrsistem, IPMM NAN Ukrainy, Donetsk, 2009, 479 pp.

[2] Logachev O. A., Salnikov A. A., Yaschenko V. V., Bulevy funktsii v teorii kodirovaniya i kriptologii, MTsNMO, M., 2004, 470 pp. | MR

[3] Skobelev V. G., Speranskii D. V., “Identifikatsiya bulevykh funktsii metodami lineinoi algebry”, Ukrainskii matematicheskii zhurnal, 47:2 (1995), 260–268 | MR | Zbl

[4] Moldovyan A. A., Moldovyan N. A., Guts N. D., Izotov B. V., Kriptografiya. Skorostnye shifry, BKhV-Peterburg, SPb, 2002, 496 pp.

[5] Huffman D. A., “Canonical forms for information-lossless finite state logical machines”, IRE Transactions Circuit Theory, CT-6 (1959), 41–59, Special Supplment | DOI | Zbl

[6] Even S., “On information-lossless automata of finite order”, IEEE Transactions on Electronic Computers, 14 (1965), 561–569 | DOI | Zbl

[7] Kurmit A. A., Avtomaty bez poteri informatsii konechnogo poryadka, Zinatne, Riga, 1972, 266 pp. | MR

[8] Gill A., Lineinye posledovatelnostnye mashiny, Nauka, M., 1974, 298 pp. | MR | Zbl

[9] Faradzhev R. G., Lineinye posledovatelnostnye mashiny, Sov. radio, M., 1975, 248 pp.

[10] Agibalov G. P., “Raspoznavanie operatorov, realizuemykh v lineinykh avtonomnykh avtomatakh”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1970, no. 3, 99–108 | MR | Zbl

[11] Agibalov G. P., Yufit Ya. G., “O prostykh eksperimenakh dlya lineinykh initsialnykh avtomatov”, Avtomatika i vychislitelnaya tekhnika, 1972, no. 2, 17–19 | MR | Zbl

[12] Speranskii D. V., Eksperimenty s lineinymi i bilineinymi konechnymi avtomatami, SGU, Saratov, 2004, 144 pp.

[13] Glushkov V. M., Sintez tsifrovykh avtomatov, Fizmatlit, M., 1962, 476 pp. | MR

[14] Babash A. V., “Priblizhennye modeli konechnykh avtomatov”, Obozrenie prikladnoi i promyshlennoi matematiki, 12:2 (2005), 108–117

[15] Skobelev V. V., “Postroenie stoikikh k chastotnomu analizu kriptosistem na osnove regulyarnykh kombinatornykh struktur”, Iskusstvennyi intellekt, 2004, no. 1, 88–96

[16] Skobelev V. V., “Razrushenie chastot bukv na osnove regulyarnykh kombinatornykh struktur”, Trudy IPMM NANU, 17, 2008, 185–193

[17] Skobelev V. G., Zaitseva E. E., “Shifry na osnove fraktalov”, Trudy IPMM NANU, 12, 2006, 63–68 | MR

[18] Zaitseva E. E., Skobelev V. G., “Shifr na osnove otobrazheniya Mandelbrota”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2007, no. 23, 107–113

[19] Shnaier B., Prikladnaya kriptologiya. Protokoly, algoritmy, iskhodnye teksty na yazyke SI, Triumf, M., 2003, 816 pp.

[20] Skobelev V. G., Lokalnye algoritmy na grafakh, IPMM NAN Ukrainy, Donetsk, 2003, 217 pp.

[21] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, M., 1982, 384 pp. | MR | Zbl

[22] Stenli R., Perechislitelnaya kombinatorika, Mir, M., 1990, 440 pp. | MR

[23] Skobelev V. V., “Tochnaya formula dlya chisla obratimykh matrits nad konechnym koltsom”, Trudy IPMM NANU, 18, 2009, 63–68

[24] Kharin Yu. S., Bernik V. I., Matveev G. V., Agievich S. V., Matematicheskie i kompyuternye osnovy kriptologii, Novoe znanie, Minsk, 2003, 382 pp.

[25] Skobelev V. G., Zaitseva E. E., “Analiz klassa legko vychislimykh perestanovok”, Kibernetika i sistemnyi analiz, 2008, no. 5, 12–24 | Zbl

[26] Koblits N., Vvedenie v ellipticheskie krivye i modulyarnye formy, Mir, M., 1988, 316 pp. | MR

[27] Koblits N., Kurs teorii chisel i kriptografiya, Nauchnoe izd-vo TVP, M., 2001, 262 pp.

[28] Gorchinskii V. G., “O gomomorfizmakh mnogoosnovnykh universalnykh algebr v svyazi s kriptograficheskimi primeneniyami”, Trudy po diskretnoi matematike, 1, TVP, M., 1997, 67–84 | MR

[29] Lynch N., “I/O automaton models for proofs for shared-key communication systems”, Proceedings of the 12th IEEE Computer Security Foundations Workshop (CSFW'99)., Mordana, Italy, 1999, 16 p.

[30] Devyanin P. N., Modeli bezopasnosti kompyuternykh sistem, Izdatelskii tsentr “Akademiya”, M., 2005, 144 pp.

[31] Bleikhut R., Teoriya i praktika kodov, kontroliruyuschikh oshibki, Mir, M., 1986, 576 pp. | MR

[32] Nilsen M., Chang I., Kvantovye vychisleniya i kvantovaya informatsiya, Mir, M., 2006, 824 pp.

[33] Shuster G., Determinirovannyi khaos, Mir, M., 1985, 255 pp. | MR

[34] Kuznetsov S. P., Dinamicheskii khaos, Fizmatlit, M., 2001, 296 pp.

[35] Dmitriev A. S., “Zapis i vosstanovlenie informatsii v odnomernykh dinamicheskikh sistemakh”, Radiotekhnika i radioelektronika, 36:1 (1991), 101–108 | MR

[36] Dmitriev A. S., “Khaos i obrabotka informatsii v odnomernykh dinamicheskikh sistemakh”, Radiotekhnika i radioelektronika, 38:1 (1993), 1–24 | MR

[37] Andreev Yu. V., Belskii Yu. L., Dmitriev A. S., “Zapis i vosstanovlenie informatsii s ispolzovaniem ustoichivykh tsiklov dvumernykh i mnogomernykh otobrazhenii”, Radiotekhnika i radioelektronika, 39:4 (1994), 114–123

[38] Dmitriev A. S., Starkov S. O., “Peredacha soobschenii s ispolzovaniem khaosa i klassicheskaya teoriya informatsii”, Zarubezhnaya radioelektronika. Uspekhi sovremennoi radioelektroniki, 1998, no. 11, 4–32

[39] Andreev Yu. V., Dmitriev A. S., Kuminov D. A., “Khaoticheskie protsessory”, Radiotekhnika i radioelektronika, 42:10 (1997), 50–79

[40] Kostenko P. Yu., Sivaschenko S. I., Antonov A. V., Kostenko T. P., “Primenenie metodov khaoticheskoi dinamiki dlya obespecheniya informatsionnoi skrytnosti v kommunikatsionnykh sistemakh i setyakh”, Izv. vuzov. Radioelektronika, 49:3 (2006), 63–70

[41] Kostenko P. Yu., Antonov A. V., Kostenko T. P., “Obratnye zadachi khaoticheskoi dinamiki i statisticheskii analiz pri obespechenii informatsionnoi skrytnosti v kommunikatsionnykh sistemakh i setyakh”, Kibernetika i sistemnyi analiz, 2006, no. 5, 96–106 | Zbl

[42] Kostenko P. Yu., Antonov A. V., Kostenko T. P., “Razvitie kontseptsii odnostoronnikh funktsii dlya sistem kriptograficheskoi zaschity informatsii s ispolzovaniem dostizhenii khaoticheskoi dinamiki”, Kibernetika i sistemnyi analiz, 2006, no. 6, 136–146 | MR | Zbl

[43] Grassi G., Mascolo S., Hyperchaos-based secure communications by observer design, Proceedings of the 7th International Workshop on Nonlinear Dynamics of Electronic Systems, Ronne, Denmark, July 15–17, 1999, 157–160

[44] Proceedings of the 7th International Workshop on Nonlinear Dynamics of Electronic Systems, Ronne, Denmark, July 15–17, 1999, Technical University of Denmark, Technical University of Dresden, 1999, 294 pp.

[45] Synchronization: Theory and applications (Yalta, Crimea, Ukraine, May 19–June 1, 2002), NATO Science Series: II. Mathematics, Physics and Chemistry, 109, Kluver Academic Publishers, 2002, 258 pp. | MR

[46] Alia M. A., Samsudin A. B., “New key exchange protocol based on Mandelbrot and Julia fractal sets”, IJCSNS International Journal of Computer Science and Network Security, 7:2 (2007), 302–307

[47] Kuzmin A. S., Kurakin V. L., Nechaev A. A., “Psevdosluchainye i polilineinye posledovatelnosti”, Trudy po diskretnoi matematike, 1, TVP, M., 1997, 139–202 | MR

[48] Skobelev V. V., “Issledovanie struktury mnozhestva lineinykh BPI-avtomatov nad koltsom $\mathbf Z_{p^k}$”, Dopovidi NANU, 2007, no. 10, 44–49 | Zbl

[49] Skobelev V. V., “Analiz struktury klassa lineinykh avtomatov nad koltsom $\mathbf Z_{p^k}$”, Kibernetika i sistemnyi analiz, 2008, no. 3, 60–74 | MR | Zbl

[50] Skobelev V. V., “Kharakteristiki lineinykh odnomernykh avtomatov s lagom $l$ nad konechnym koltsom”, Trudy IPMM NANU, 16, 2008, 190–196 | MR

[51] Kuzmin A. S., Kurakin V. L., Nechaev A. A., “Svoistva lineinykh i polilineinykh rekurrent nad koltsami Galua (I)”, Trudy po diskretnoi matematike, 2, TVP, M., 1998, 191–222 | MR

[52] Skobelev V. G., “Nelineinye avtomaty nad konechnym koltsom $\mathbf Z_{p^k}$”, Kibernetika i sistemnyi analiz, 2006, no. 6, 29–42 | MR | Zbl

[53] Skobelev V. G., “O nekotorykh svoistvakh nelineinykh BPI-avtomatov nad koltsom $\mathbf Z_{p^k}$”, Prikladnaya radioelektronika, 6:2 (2007), 288–299

[54] Skobelev V. V., “Simmetricheskie dinamicheskie sistemy nad konechnym koltsom: svoistva i slozhnost identifikatsii”, Trudy IPMM NANU, 10, 2005, 184–189 | MR | Zbl

[55] Skobelev V. V., “O dvukh tipakh nelineinykh avtomatov nad konechnym koltsom $\mathbf Z_{p^k}$”, Kibernetika i sistemnyi analiz, 2009, no. 4, 57–68 | Zbl

[56] Ashwin P., Ruclidge A. M., Sturman R., “Cyclic attractors of coupled cell systems and dynamics with symmetry”, Synchronization: Theory and applications (Yalta, Crimea, Ukraine, May 19–June 1), NATO Science Series: II. Mathematics, Physics and Chemistry, 109, Kluver Academic Publishers, 2002, 5–23 | MR

[57] Golod P. I., Klimyk A. U., Matematicheskie osnovy teorii simmetrii, NITs “Regulyarnaya i khaoticheskaya dinamika”, Izhevsk, 2001, 528 pp.

[58] Skobelev V. V., Analiz kombinatorno-algebraicheskikh modelei in'ektivnykh diskretnykh preobrazovatelei informatsii, dis. $\dots$ kand. fiz.-mat. nauk. 01.05.01 — teoreticheskie osnovy informatiki i kibernetiki, IPMM NAN Ukrainy, Donetsk, 2009, 128 pp.

[59] Gill A., Vvedenie v teoriyu konechnykh avtomatov, Nauka, M., 1966, 272 pp. | MR | Zbl

[60] Goryashko A. P., “Proektirovanie legko testiruemykh diskretnykh ustroistv”, Avtomatika i telemekhanika, 1984, no. 7, 5–35 | MR | Zbl

[61] Skobelev V. G., “Ob otsenkakh dlin diagnosticheskikh i vozvratnykh slov dlya avtomatov”, Kibernetika, 1987, no. 4, 114–116 | MR

[62] Skobelev V. G., Analiz diskretnykh sistem, IPMM NAN Ukrainy, Donetsk, 2002, 172 pp.

[63] Skobelev V. V., “Kharakteristika nepodvizhnykh tochek lineinykh avtomatov nad konechnym koltsom”, Prikladnaya diskretnaya matematika, 2008, no. 1, 126–130