HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
, the RSA problem summarizes the task of performing an RSA private-key operation given only the
public key Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic al ...
. The RSA algorithm raises a ''message'' to an ''
exponent Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to r ...
'',
modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is ...
a
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor In mathematics, a divisor of an integer n, also called a factor ...
''N'' whose factors are not known. Thus, the task can be neatly described as finding the ''e''th roots of an arbitrary number, modulo N. For large RSA
key size In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...
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 Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic a ...
and
digital signatures A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
. More specifically, the RSA problem is to efficiently compute ''P'' given an RSA public key (''N'', ''e'') and a ciphertext ''C'' ≡ ''P'' ''e'' (mod ''N''). The structure of the RSA public key requires that ''N'' be a large
semiprime In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime ...
(i.e., a product of two large
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s), that 2 < ''e'' < ''N'', that ''e'' be
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
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 method known to solve the RSA problem is by first factoring the modulus ''N,'' a task believed to be impractical if ''N'' is sufficiently large (see
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are s ...
). 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.


See also

*
Strong RSA assumption In cryptography, the strong RSA assumption states that the RSA problem is intractable even when the solver is allowed to choose the public exponent ''e'' (for ''e'' ≥ 3). More specifically, given a modulus ''N'' of unknown factorizati ...
*
RSA Factoring Challenge The 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 cryptogr ...
*
Rabin cryptosystem The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization. The Rabin trapdoor function has the advantage that invert ...
, whose equivalency to factoring is known


References


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 Straight may refer to: Slang * Straight, slang for heterosexual ** Straight-acting, an LGBT person who does not exhibit the appearance or mannerisms of the gay stereotype * Straight, a member of the straight edge subculture Sport and games * S ...
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 Antoine Joux (born 1967) is a French cryptographer,"Antoine Joux, Prix Gödel 2013"
Bullet ...
, 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. {{Computational hardness assumptions Computational hardness assumptions Public-key cryptography