Finite automata in cryptography

G. P. Agibalov

Prikladnaâ diskretnaâ matematika, no. 11 (2009), pp. 43-73.

Résumé

Here we tell about applications of finite automata as cryptographic primitives and cryptosystems known from the public scientific papers. Some theoretical questions concerning the symmetric stream and automata ciphersystems are considered too.

Bibliographie

[1] Agibalov G. P., “Logicheskie uravneniya v kriptoanalize generatorov klyuchevogo potoka”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2003, no. 6, 31–41

[2] Agibalov G. P., “Logicheskie uravneniya v kriptoanalize szhimayuschego i samoszhimayuschego generatorov”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2004, no. 9(I), 49–54

[3] Fomichëv V. M., Diskretnaya matematika i kriptologiya, DIALOG-MIFI, M., 2003, 400 pp.

[4] Babash A. V., Shankin G. P., Kriptografiya, Solon-R, M., 2002, 512 pp.

[5] Agibalov G. P., Oranov A. M., Lektsii po teorii konechnykh avtomatov, Izd-vo Tom. un-ta, Tomsk, 1984, 185 pp. | MR

[6] Menezes A., van Oorshot P., Vanstone S., Handbook of Applied Cryptography, CRC Press, 1996, 661 pp.

[7] Watanabe D., Furuya S., Yoshida H., Takaragi K., Preneel B., “A New Keystream Generator MUGI”, LNCS, 2365, 2002, 179–194 | Zbl

[8] Joux A., Muller F., “Loosening the KNOT”, LNCS, 2887, 2003, 87–99 | Zbl

[9] Golic J. Dj., Bagini V., Morgari G., “Linear Cryptanalysis of Bluetooth Stream Cipher”, LNCS, 2332, 2002, 238–255 | MR | Zbl

[10] O'Neil S., Gittins B., Landman H., VEST. Hardware-Dedicated Stream Cipher, , October 2005, eSTREAM, 63 p. http://www.ecrypt.eu.org/stream/vest.html

[11] Wolfram S., “Cryptography with Cellular Automata”, LNCS, 218, 1985, 429–432

[12] Michaljevic' M., Zheng Y., Imai H., “Cellular Automaton Based Fast One-Way Hash Function Suitable for Hardware Implementation”, LNCS, 1431, 1998, 217–233

[13] Shennon K. E., “Matematicheskaya teoriya svyazi”, Raboty po teorii informatsii i kibernetike, IL, M., 1963, 243–332

[14] Stamp M., Low R. M., Applied Cryptanalysis. Breaking Ciphers in the Real World, John Wiley Sons, NJ, 2007, 400 pp.

[15] Zakrevskii A. D., “Metod avtomaticheskoi shifratsii soobschenii”, Prikladnaya diskretnaya matematika, 2009, no. 2, 127–137

[16] Mur E. F., “Umozritelnye eksperimenty s posledovatelnostnymi mashinami”, Avtomaty, sb. statei, eds. K. E. Shennon i Dzh. Makkarti, IL, M., 1956, 179–210

[17] Pankratov I. V., “K opredeleniyu ponyatiya samosinkhroniziruyuschegosya potochnogo shifra”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2007, no. 23, 114–117

[18] Pankratov I. V., “O potochnykh i avtomatnykh shifrsistemakh”, Prikladnaya diskretnaya matematika, 2009, prilozhenie # 1, 21–24

[19] Pankratov I. V., “O potochnykh i avtomatnykh shifrsistemakh s simmetrichnym klyuchom”, Prikladnaya diskretnaya matematika, 2009, no. 3, 59–68

[20] Dai Z. D., Ye D. F., Lam K. Y., “Weak Invertability of Finite Automata and Cryptanalysis on FAPKC”, LNCS, 1514, 1998, 227–241 | MR | Zbl

[21] Tao R. J., On Invertability of Some Compound Finite Automata, Technical Report ISCAS–LCS–95–06, Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 10080, China, 1995, June

[22] Tao R. J., Chen S. H., “A Finite Automaton Public Key Cryptosystem and Digital Signatures”, Chinese J. of Comptuter, 8 (1985), 401–409 (in Chinese) | MR

[23] Tao R. J., Chen S. H., “Two Varieties of Finite Automaton Public Key Cryptosystem and Digital Signatures”, J. of Compt. Sci. and Tech., 1:1 (1986), 9–18 | DOI | MR | Zbl

[24] Tao R. J., Chen S. H., Chen X. M., FPKC3: a New Finite Automaton Public Key Cryptosystem, Technical Report ISCAS–LCS–95–07, Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 10080, China, 1995, June

[25] Chen X. M., The Invertability Theory and Application of Quadratic Finite Automata, Doctoral Thesis, Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 10080, China, 1996