Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The book Algebraic Cryptanalysis (Bard, G.V.; Springer, 2009) speaks about transforming a symmetric scheme into a system of polynomial equations and solving these equations to break the scheme.
But is there no way to do the same with asymmetric schemes? Is it impossible to apply the same techniques to this kind of scheme?
Of course, it is possible. It is possible to take a public key encryption algorithm which takes the private key and the known ciphertext into the known plaintext, convert that into a set of equations in $GF(2)$ with the private key as unknown variables, and solve for those unknown variables. Alternatively, you can take the key generation algorithm, which takes some random bits and converts that into the public and private keys; convert that into a set of equations with the public key output as known, and solve for the private key (and the random bits).
However, the relevant question is "is this (converting the problem into a form that has known NP-hard instances) easier than solving the hard problem directly?" I don't believe it is.
