Mathematical Methods of Cryptography

Algorithm for recovering plaintext from ciphertext in McEliece cryptosystem

A. K. Kaluzhin, I. V. Chizhov

M. V. Lomonosov Moscow State University

Abstract: An attack on McEiece cryptosystem is considered. In it a plaintext is recovered from a ciphertext by solving the encryption equation. The solution is get in two steps: finding the error vector and solving the system of linear equations. For finding the error vector, the Bernstein–Lange–Peters's algorithm is used together with some optimization techniques. The complexity of the offered attack on the cryptosystem based on Goppa (1024, 524, 50)-code equals $2^{60{,}1}$ bit operations that is 27,5% less than by means of Bernstein–Lange–Peters's algorithm itself.

Keywords: McEliece's cryptosystem, nonstructural attacks, Bernstein–Lange–Peters's algorithm.

UDC: 056.55