In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4 [22]. We call these the Rational Multivariate Public Key Cryptosystems (RMPKC). These cryptosystems are constructed via composition of two quadratic rational maps into one quartic rational map, which becomes the public key. In this paper, we present a cryptanalysis of RMPKC.;This cryptanalysis demonstrates success against two separate problems in mathematics which are difficult to solve: factorization of maps and solving multivariate non-linear polynomial equations. We first perform a factorization of the public key quartic rational map into two components which are quadratic. We then attack each quadratic component, providing a way to solve the quadratic equations.;Our cryptanalysis is of the strong type. We take a public key and create a private key. The cryptanalyst can decrypt a message equally as fast as the owner of the original private key.;Our work involving the factorization of maps starts applying work published by Faugere and Perret, who set out to do basically the same thing. Their method, however, was insufficient to attach RMPKC. We enhance the method using projections to lower dimensions.;Our work involving the solution of quadratic equations is inspired by a thorough analysis of the structure of RMPKC and identification of weaknesses within.
展开▼
