3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.