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 adver ...

, 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'', modulo 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 other than 1 and itself. Every positive integer is composite, prime, ...

''N'' whose

factors Factor, a Latin word meaning "who/which acts", may refer to: Commerce * Factor (agent), a person who acts for, notably a mercantile and colonial agent * Factor (Scotland), a person or firm managing a Scottish estate * Factors of production, su ...

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 al ...

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 nu ...

(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 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 because the only ways ...

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 suf ...

). 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

References

Further reading