  This paper presents algorithms for local inversion of maps and shows how
several important computational problems such as cryptanalysis of symmetric
encryption algorithms, RSA algorithm and solving the elliptic curve discrete
log problem (ECDLP) can be addressed as local inversion problems. The
methodology is termed as the \emph{Local Inversion Attack}. It utilizes the
concept of \emph{Linear Complexity} (LC) of a recurrence sequence generated by
the map defined by the cryptanalysis problem and the given data. It is shown
that when the LC of the recurrence is bounded by a bound of polynomial order in
the bit length of the input to the map, the local inversion can be accomplished
in polynomial time. Hence an incomplete local inversion algorithm which
searches a solution within a specified bound on computation can estimate the
density of weak cases of cryptanalysis defined by such data causing low LC.
Such cases can happen accidentally but cannot be avoided in practice and are
fatal insecurity flaws of cryptographic primitives which are wrongly assumed to
be secure on the basis of exponential average case complexity. An incomplete
algorithm is proposed for solving problems such as key recovery of symmetric
encryption algorithms, decryption of RSA ciphertext without factoring the
modulus, decrypting any ciphertext of RSA given one plaintext ciphertext pair
created with same public key in chosen ciphertext attack and solving the
discrete logarithm on elliptic curves over finite fields (ECDLP) as local
inversion problems. It is shown that when the LCs of the respective recurrences
for given data are small, solutions of these problems are possible in
practically feasible time and memory resources.
