The failure of Mceliece PKC based on Reed — Muller codes
This paper describes new algorithm for breaking McEliece cryptosystem, being built on Reed — Muller binary code RM(r, m).The algorithm calculates the private key from the public key using O(n + n log 2 n) bit operations, where n = 2 , d = (r, m — 1). In case of limited d, the attack has a polynomial complexity. Practical results of implementation show that McEliece cryptosystems, based on the Reed — Muller binary code of length n = 65526 bits, can be broken in less than 7 hours on a personal computer.
Download file
Counter downloads: 238
Keywords
криптосистема Мак-Элиса, коды Рида — Маллера, полиномиальная сложность атаки, McEliece cryptosystem, Reed — Muller code, polynomial attack, McEliece cryptosystem, Reed — Muller code, polynomial attackAuthors
| Name | Organization | |
| Chizhov I. V. | Lomonosov Moscow State University | ivchizhov@gmail.com |
| Borodin M.A. | Lomonosov Moscow State University | bor1m@mail.ru |
References
Мак-Вильямс Ф. Дж., Слоэн Н.Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида — Маллера // Дискретная математика. 1994. Т. 6. №2. С. 3-20.
Minder L. and Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // LNCS. 2007. V. 4515. P. 347-360.
