RSA problem
Encyclopedia
In cryptography
, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key
. The RSA algorithm raises a message to an exponent, modulo
a composite number
N whose factors
are not known. As such, the task can be neatly described as finding the eth roots of an arbitrary number, modulo N. For large RSA key size
s (in excess of 1024 bits), no efficient method for solving this problem is known; if an efficient method is ever developed, it would threaten the current or eventual security of RSA-based cryptosystems -- both for public-key encryption and digital signatures.
More specifically, the RSA problem is to efficiently compute P given an RSA public key (N, e) and a ciphertext C ≡ Pe (mod N). The structure of the RSA public key requires that N be a large semiprime
(i.e., a product of two large prime number
s), that 2 < e < N, that e be coprime
to φ
(N), and that 0 ≤ C < N. C is chosen randomly within that range; to specify the problem with complete precision, one must also specify how N and e are generated, which will depend on the precise means of RSA random keypair generation in use.
, the most efficient means known to solve the RSA problem is to first factor the modulus N, which is believed to be impractical if N is sufficiently large (see integer factorization
). The RSA key setup routine already turns the public exponent e, with this prime factorization, into the private exponent d, and so exactly the same algorithm allows anyone who factors N to obtain the private key. Any C can then be decrypted with the private key.
Just as there are no proofs that integer factorization is computationally difficult, there are also no proofs that the RSA problem is similarly difficult. By the above method, the RSA problem is at least as easy as factoring, but it might well be easier. Indeed, there is strong evidence pointing to this conclusion: that a method to break the RSA method cannot be converted necessarily into a method for factoring large semiprimes. This is perhaps easiest to see by the sheer overkill of the factoring approach: the RSA problem asks us to decrypt one arbitrary ciphertext, whereas the factoring method reveals the private key: thus decrypting all arbitrary ciphertexts, and it also allows one to perform arbitrary RSA private-key encryptions. Along these same lines, finding the decryption exponent d indeed is computationally equivalent to factoring N, even though the RSA problem does not ask for d. An algorithm for this is, for example, given in .
In addition to the RSA problem, RSA also has a particular mathematical structure that can potentially be exploited without solving the RSA problem directly. To achieve the full strength of the RSA problem, an RSA-based cryptosystem must also use a padding scheme
like OAEP
, to protect against such structural problems in RSA.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
. The RSA algorithm raises a message to an exponent, modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
a composite number
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
N whose factors
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
are not known. As such, the task can be neatly described as finding the eth roots of an arbitrary number, modulo N. For large RSA key size
Key size
In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...
s (in excess of 1024 bits), no efficient method for solving this problem is known; if an efficient method is ever developed, it would threaten the current or eventual security of RSA-based cryptosystems -- both for public-key encryption and digital signatures.
More specifically, the RSA problem is to efficiently compute P given an RSA public key (N, e) and a ciphertext C ≡ Pe (mod N). The structure of the RSA public key requires that N be a large semiprime
Semiprime
In mathematics, a semiprime is a natural number that is the product of two prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... ....
(i.e., a product of two large prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s), that 2 < e < N, that e be coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to φ
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
(N), and that 0 ≤ C < N. C is chosen randomly within that range; to specify the problem with complete precision, one must also specify how N and e are generated, which will depend on the precise means of RSA random keypair generation in use.
, the most efficient means known to solve the RSA problem is to first factor the modulus N, which is believed to be impractical if N is sufficiently large (see integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
). The RSA key setup routine already turns the public exponent e, with this prime factorization, into the private exponent d, and so exactly the same algorithm allows anyone who factors N to obtain the private key. Any C can then be decrypted with the private key.
Just as there are no proofs that integer factorization is computationally difficult, there are also no proofs that the RSA problem is similarly difficult. By the above method, the RSA problem is at least as easy as factoring, but it might well be easier. Indeed, there is strong evidence pointing to this conclusion: that a method to break the RSA method cannot be converted necessarily into a method for factoring large semiprimes. This is perhaps easiest to see by the sheer overkill of the factoring approach: the RSA problem asks us to decrypt one arbitrary ciphertext, whereas the factoring method reveals the private key: thus decrypting all arbitrary ciphertexts, and it also allows one to perform arbitrary RSA private-key encryptions. Along these same lines, finding the decryption exponent d indeed is computationally equivalent to factoring N, even though the RSA problem does not ask for d. An algorithm for this is, for example, given in .
In addition to the RSA problem, RSA also has a particular mathematical structure that can potentially be exploited without solving the RSA problem directly. To achieve the full strength of the RSA problem, an RSA-based cryptosystem must also use a padding scheme
Padding (cryptography)
-Classical cryptography:Official messages often start and end in predictable ways: My dear ambassador, Weather report, Sincerely yours, etc. The primary use of padding with classical ciphers is to prevent the cryptanalyst from using that predictability to find cribs that aid in breaking the...
like OAEP
Optimal Asymmetric Encryption Padding
In cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....
, to protect against such structural problems in RSA.
See also
- Strong RSA assumptionStrong RSA assumptionIn cryptography, the strong RSA assumption states that the RSA problem is intractable even when the solver is allowed to choose the public exponent e...
- RSA Factoring ChallengeRSA Factoring ChallengeThe RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography...
- Computational hardness assumptionsComputational hardness assumptionsIn cryptography, a major goal is to create cryptographic primitives with provable security. In some cases cryptographic protocols are found to have information theoretic security, the one-time pad is a common example. In many cases, information theoretic security cannot be achieved, and in such...
Further reading
- Breaking RSA may be as difficult as factoring, D. Brown, 2005. This unrefereed preprint purports that solving the RSA problem using a Straight line program is as difficult as factoring provided e has a small factor.
- Breaking RSA Generically is Equivalent to Factoring, D. Aggarwal and U. Maurer, 2008. This Eurocrypt 2009 paper (link is to a preprint version) proves that solving the RSA problem using a generic ring algorithm is as difficult as factoring.
- When e-th Roots Become Easier Than Factoring, Antoine Joux, David Naccache and Emmanuel Thomé, 2007. This Asiacrypt 2007 paper (link is to a preprint version) proves that solving the RSA problem using an oracle to some certain other special cases of the RSA problem is easier than factoring.