Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities |
| |
Authors: | Don Coppersmith |
| |
Affiliation: | (1) IBM Research, T. J. Watson Research Center, Yorktown Heights, NY 10598, U.S.A., US |
| |
Abstract: | We show how to find sufficiently small integer solutions to a polynomial in a single variable modulo N, and to a polynomial in two variables over the integers. The methods sometimes extend to more variables. As applications:
RSA encryption with exponent 3 is vulnerable if the opponent knows two-thirds of the message, or if two messages agree over
eight-ninths of their length; and we can find the factors of N=PQ if we are given the high order bits of P.
Received 21 December 1995 and revised 11 August 1996 |
| |
Keywords: | , Polynomial, RSA, Factoring, |
本文献已被 SpringerLink 等数据库收录! |
|