论文标题
地图的局部反转：对对称加密，RSA和ECDLP的新攻击
Local inversion of maps: A new attack on Symmetric encryption, RSA and ECDLP
论文作者
论文摘要
本文介绍了用于局部地图的算法，并显示了一些重要的计算问题，例如对对称加密算法的密码分析，RSA算法并解决椭圆曲线离散日志问题（ECDLP）如何作为局部反转问题来解决。该方法被称为\ emph {局部反转攻击}。它利用了由密码分析问题和给定数据定义的地图生成的复发序列的\ emph {线性复杂性}（LC）的概念。结果表明，当复发的LC在输入到地图的位长度以多项式顺序的结合到界限时，可以在多项式时间内完成局部反转。因此，一种不完整的局部反转算法，该算法搜索在计算上指定的指定限制的解决方案可以估计由此类数据定义的导致低LC定义的隐性弱病例的密度。这种情况可能会偶然发生，但不能在实践中避免，并且是加密原始词的致命不安全感缺陷，这些缺陷被错误地假定为基于指数的平均病例复杂性而被错误地假定为安全。 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）作为局部反转问题。结果表明，当给定数据的相应复发的LCS很小时，这些问题的解决方案实际上可能是可行的时间和内存资源。
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.
