# Low-Exponent RSA with Related Messages

@inproceedings{Coppersmith1996LowExponentRW, title={Low-Exponent RSA with Related Messages}, author={Don Coppersmith and Matthew K. Franklin and Jacques Patarin and Michael K. Reiter}, booktitle={EUROCRYPT}, year={1996} }

In this paper we present a new class of attacks against RSA with low encrypting exponent. The attacks enable the recovery of plaintext messages from their ciphertexts and a known polynomial relationship among the messages, provided that the ciphertexts were created using the same RSA public key with low encrypting exponent.

#### Topics from this paper

#### 176 Citations

Development of the attack against RSA with low public exponent and related messages

- Computer Science
- CompSysTech '07
- 2007

Problems of security of the asymmetric cryptographic algorithm RSA are considered, which might occur when choosing small values of public keys and related plaintexts and a development of the well… Expand

Large decryption exponents in RSA

- Mathematics, Computer Science
- Appl. Math. Lett.
- 2003

A class of RSA encryption exponents whose corresponding decryption exponents have a bitlength almost equal to the bitlength of the RSA modulus is analysed. In this way, the attacks to small… Expand

Protocol Failures for RSA-Like Functions Using Lucas Sequences and Elliptic Curves

- Computer Science
- Security Protocols Workshop
- 1996

We show that the cryptosystems based on Lucas sequences and on elliptic curves over a ring are insecure when a linear relation is known between two plaintexts that are encrypted with a “small” public… Expand

A Survey of Attacks on the RSA Cryptosystem, with Implementations in Java

- Computer Science
- 2004

We discuss attacks made against the underlying structure of the RSA algorithm, which exploit weaknesses in the choice of values for the encryption and decryption keys, and their relation to the RSA… Expand

Sparse RSA Secret Keys and Their GenerationChae

- 1996

In this paper we consider the problem of reducing the computational load by use of restricted key parameters in the RSA system. We present various methods for generating RSA key parameters that can… Expand

Modulus Search for Elliptic Curve Cryptosystems

- Computer Science
- ASIACRYPT
- 1999

This work proposes a mathematical problem, and shows how to solve it elegantly, related with elliptic curve cryptosystems (ECC). Expand

Mathematical Attacks on RSA Cryptosystem

- Computer Science
- 2006

The integer factoring attacks, attacks on the underlying mathematical function, as well as attacks that exploit details in implementations of the algorithm are described. Expand

High-Speed Cryptography

- Computer Science
- ISW
- 1997

A new method is presented for achieving high speed encryption and decryption using large-block cryptosystems that amplifies the encrypting speed of any cryptosSystem, and it is provably reducible to the latter. Expand

Cryptanalysis of RSA-type cryptosystems: A visit

- Computer Science, Mathematics
- Network Threats
- 1996

The main focus is the way how some known attacks on RSA were extended to LUC, KMOV and Demytko's system, and some directions for the choice of the most appropriate RSA-type system for a given application. Expand

Factoring RSA moduli when a message is close to a multiple of the primes

- Computer Science, Mathematics
- Int. J. Comput. Math. Comput. Syst. Theory
- 2018

It is shown that it is possible to factor N in polynomial time in when a low public exponent is used. Expand

#### References

SHOWING 1-10 OF 14 REFERENCES

On Key Distribution and Authentication in Mobile Radio Networks

- Computer Science
- EUROCRYPT
- 1993

This paper presents a new secure and efficient key distribution protocol for mobile communication networks based on low exponent RSA and shows that the protocol shown is not secure. Expand

Optimal Asymmetric Encryption

- Computer Science
- EUROCRYPT
- 1994

A slightly enhanced scheme is shown to have the property that the adversary can create ciphertexts only of strings for which she “knows” the corresponding plaintexts—such a scheme is not only semantically secure but also non-malleable and secure against chosen-ciphertext attack. Expand

Finding a Small Root of a Univariate Modular Equation

- Mathematics, Computer Science
- EUROCRYPT
- 1996

We show how to solve a polynomial equation (mod N) of degree k in a single variable x, as long as there is a solution smaller than N1/k. We give two applications to RSA encryption with exponent 3.… Expand

A method for obtaining digital signatures and public-key cryptosystems

- Computer Science
- CACM
- 1983

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important… Expand

A method for obtaining digital signatures and public-key cryptosystems

- Computer Science
- CACM
- 1978

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key, soriers or other secure means are not needed to transmit keys. Expand

Verifiable Signature Sharing

- Computer Science
- EUROCRYPT
- 1995

Efficient VΣS schemes for exponentiation based signatures and discrete log based signatures are presented that can tolerate the malicious (Byzantine) failure of the sharer and a constant fraction of the proxies. Expand

Protocol failures in cryptosystems

- Computer Science
- 1988

The author surveys a collection of protocols in which the level of security or authentication required by the system is actually attained, not because of a failure of the cryptoalgorithm used, but rather because of shortcomings in the design of the protocol. Expand

Solving Simultaneous Modular Equations of Low Degree

- Mathematics, Computer Science
- SIAM J. Comput.
- 1988

It is shown that a protocol by Broder and Dolev is insecure if RSA with a small exponent is used and the RSA cryptosystem used with asmall exponent is not a good choice to use as a public-key cryptos system in a large network. Expand

How to share a secret

- Computer Science
- CACM
- 1979

This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces. Expand

Key Distribution Protocol for Digital Mobile Communication Systems

- Computer Science
- CRYPTO
- 1989

A key distribution protocol is proposed for digital mobile communication systems that can be used with a star-type network and a countermeasure is proposed to cope with a possible active attack by a conspiracy of two opponents. Expand