In cryptography, RSA is an algorithm for public-key cryptography. It was the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys and the use of up-to-date implementations. The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... A big random number is used to make a public-key pair. ... A digital signature or digital signature scheme is a type of asymmetric cryptography used to simulate the security properties of a signature in digital, rather than written, form. ... Electronic commerce, commonly known as e-commerce or eCommerce, consists of the buying and selling of products or services over electronic systems such as the Internet and other computer networks. ...

History

The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. Apocryphally, it was invented after a Passover Seder^[1]. Election People This box:      Professor Ronald Lorin Rivest (born 1947, Schenectady, New York) is a cryptographer. ... This article does not cite any references or sources. ... Leonard Adleman Leonard Adleman (born December 31, 1945) is a theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. ... “MIT” redirects here. ... Table set for the Passover Seder The Passover Seder (Hebrew: סֵדֶר, , order, arrangement) is a Jewish ritual feast held on the first night of the Jewish holiday of Passover (the 15th day of Hebrew month of Nisan). ...

Clifford Cocks, a British mathematician working for the UK intelligence agency GCHQ, described an equivalent system in an internal document in 1973, but given the relatively expensive computers needed to implement it at the time, it was mostly considered a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1997 due to its top-secret classification, and Rivest, Shamir, and Adleman devised RSA independently of Cocks' work. Clifford Christopher Cocks is a British mathematician and cryptographer at GCHQ who invented the widely-used encryption algorithm now commonly known as RSA, about three years before it was independently developed by Rivest, Shamir, and Adleman at MIT. He has not been generally recognised for this achievement because his work... Leonhard Euler, considered one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is the field of mathematics. ... The Government Communications Headquarters (GCHQ) is a British intelligence agency responsible for providing signals intelligence (SIGINT) and information assurance. ...

MIT was granted US patent 4405829 for a "Cryptographic communications system and method" that used the algorithm in 1983. The patent expired on 21 September 2000. Since a paper describing the algorithm had been published in August 1977,^[1] prior to the December 1977 filing date of the patent application, regulations in much of the rest of the world precluded patents elsewhere and only the US patent was granted. Had Cocks' work been publicly known, a patent in the US might not have been possible either. “MIT” redirects here. ... is the 264th day of the year (265th in leap years) in the Gregorian calendar. ... Year 2000 (MM) was a leap year starting on Saturday (link will display full 2000 Gregorian calendar). ... The filing date of a patent application is the date the patent application was filed in one or more patent offices. ... A patent application is a request pending at a patent office for the grant of a patent for the invention described and claimed by that application. ... For other uses, see Patent (disambiguation). ... For other uses of terms redirecting here, see US (disambiguation), USA (disambiguation), and United States (disambiguation) Motto In God We Trust(since 1956) (From Many, One; Latin, traditional) Anthem The Star-Spangled Banner Capital Washington, D.C. Largest city New York City National language English (de facto)1 Demonym American...

Operation

RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys for the RSA algorithm are generated the following way: A key is a piece of information that controls the operation of a cryptography algorithm. ...

1. Choose two distinct large random prime numbers and
2. Compute
   • is used as the modulus for both the public and private keys
3. Compute the totient: .
4. Choose an integer such that 1 < < , and and share no factors other than 1 (i.e. e and φ(n) are coprime)
   • is released as the public key exponent
5. Compute to satisfy the congruence relation ; i.e. for some integer .
   • is kept as the private key exponent

Notes on the above steps: In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In number theory, the totient &#966;(n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ... In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

• Step 1: Numbers can be probabilistically tested for primality.
• Step 3: changed in PKCS#1 v2.0 to instead of .
• Step 4: A popular choice for the public exponents is = 2¹⁶ + 1 = 65537. Some applications choose smaller values such as = 3, 5, or 35 instead. This is done to make encryption and signature verification faster on small devices like smart cards but small public exponents may lead to greater security risks.
• Steps 4 and 5 can be performed with the extended Euclidean algorithm; see modular arithmetic.

The public key consists of the modulus and the public (or encryption) exponent .
The private key consists of the modulus and the private (or decryption) exponent which must be kept secret. A primality test is an algorithm for determining whether an input number is prime. ... The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of integers a and b: it also finds the integers x and y in Bézouts identity (Typically either x or y is negative). ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

• For efficiency a different form of the private key can be stored:
  • and : the primes from the key generation,
  • and ,
  • .
• All parts of the private key must be kept secret in this form. and are sensitive since they are the factors of , and allow computation of given . If and are not stored in this form of the private key then they are securely deleted along with other intermediate values from key generation.
• Although this form allows faster decryption and signing by using the Chinese Remainder Theorem, it is considerably less secure since it enables side channel attacks. This is a particular problem if implemented on smart cards, which benefit most from the improved efficiency. (Start with y = x^emodn and let the card decrypt that. So it computes y^d(mod p) or y^d(mod q) whose results give some value z. Now, induce an error in one of the computations. Then gcd(z − x,n) will reveal p or q.)

Several related results in number theory and abstract algebra are known under the name Chinese remainder theorem. ... In cryptography, a side channel attack is any attack based on information gained from the physical implementation of a cryptosystem, rather than theoretical weaknesses in the algorithms (compare cryptanalysis). ... A smartcard or smart card is a tiny secure cryptoprocessor embedded within a credit card-sized or smaller (like the GSM SIM) card. ...

Encrypting messages

Alice transmits her public key to Bob and keeps the private key secret. Bob then wishes to send message M to Alice. The names Alice and Bob are commonly used placeholders for archetypal characters in fields such as cryptography and physics. ... The names Alice and Bob are commonly used placeholders for archetypal characters in fields such as cryptography and physics. ...

He first turns M into a number < by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext corresponding to:

This can be done quickly using the method of exponentiation by squaring. Bob then transmits to Alice. Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. ...

Decrypting messages

Alice can recover from by using her private key exponent by the following computation:

Given , she can recover the original message M.

The above decryption procedure works because first

.

Now, , and hence

and

which can also be written as

and

for proper values of and . If is not a multiple of then and are coprime because is prime; so by Fermat's little theorem Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you start with a number, initialized to 1, and repeatedly multiply, for a total of p multiplications, that number by...

and therefore, using the first expression for ,

.

If instead is a multiple of , then

.

Using the second expression for , we similarly conclude that

.

Since and are distinct prime numbers, applying the Chinese remainder theorem to these two congruences yields Several related results in number theory and abstract algebra are known under the name Chinese remainder theorem. ...

.

Thus,

.

A working example

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but you can also use OpenSSL to generate and examine a real keypair.

1. Choose two prime numbers

   p = 61 and q = 53

2. Compute

   n = 61 * 53 = 3233

3. Compute the totient

   

4. Choose e > 1 coprime to 3120

   e = 17

5. Compute such that e.g., by computing the modular inverse of e modulo :

   d = 2753

   17 * 2753 = 46801 = 1 + 15 * 3120.

The public key is (n = 3233, e = 17). For a padded message the encryption function is: In number theory, the totient &#966;(n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ...

The private key is (n = 3233, d = 2753). The decryption function is:

For example, to encrypt m = 123, we calculate

To decrypt c = 855, we calculate

.

Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number x. ... Modular exponentiation is a type of exponentiation performed over a modulus. ...

Padding schemes

When used in practice, RSA is generally combined with some padding scheme. The goal of the padding scheme is to prevent a number of attacks that potentially work against RSA without padding: In cryptography, padding is the practice of adding material of varying length to the plaintext of messages. ...

• When encrypting with low encryption exponents (e.g., e = 3) and small values of the m, (i.e. m<n^1/e) the result of m^e is strictly less than the modulus n. In this case, ciphertexts can be easily decrypted by taking the eth root of the ciphertext over the integers.
• Because RSA encryption is a deterministic encryption algorithm – i.e., has no random component – an attacker can successfully launch a chosen plaintext attack against the cryptosystem, by encrypting likely plaintexts under the public key and test if they are equal to the ciphertext. A cryptosystem is called semantically secure if an attacker cannot distinguish two encryptions from each other even if the attacker knows (or has chosen) the corresponding plaintexts. As described above, RSA without padding is not semantically secure.
• RSA has the property that the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts. That is Because of this multiplicative property a chosen-ciphertext attack is possible. E.g. an attacker, who wants to know the decryption of a ciphertext c=m^e mod n may ask the holder of the secret key to decrypt an unsuspiciously looking ciphertext c' = cr^emod n for some value r chosen by the attacker. Because of the multiplicative property c' is the encryption of mrmod n. Hence, if the attacker is successful with the attack, he will learn mrmod n from which he can derive the message m by multiplying mr with the modular inverse of r modulo n.

To avoid these problems, practical RSA implementations typically embed some form of structured, randomized padding into the value m before encrypting it. This padding ensures that m does not fall into the range of insecure plaintexts, and that a given message, once padded, will encrypt to one of a large number of different possible ciphertexts. In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ... A chosen plaintext attack is any form of cryptanalysis which presumes that the attacker has the capability to choose arbitrary plaintexts to be encrypted and obtain the corresponding ciphertexts. ... Semantic security is a widely-used definition for security in an asymmetric key encryption algorithm. ... A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis in which the cryptanalyst chooses a ciphertext and causes it to be decrypted with an unknown key. ... In cryptography, padding is the practice of adding material of varying length to the plaintext of messages. ...

Standards such as PKCS have been carefully designed to securely pad messages prior to RSA encryption. Because these schemes pad the plaintext m with some number of additional bits, the size of the un-padded message M must be somewhat smaller. RSA padding schemes must be carefully designed so as to prevent sophisticated attacks which may be facilitated by a predictable message structure. Early versions of the PKCS standard (i.e. PKCS #1 up to version 1.5) used a construction that turned RSA into a semantically secure encryption scheme. This version was later found vulnerable to a practical adaptive chosen ciphertext attack. Later versions of the standard include Optimal Asymmetric Encryption Padding (OAEP), which prevents these attacks. The PKCS standard also incorporates processing schemes designed to provide additional security for RSA signatures, e.g., the Probabilistic Signature Scheme for RSA (RSA-PSS). In cryptography, PKCS refers to a group of Public Key Cryptography Standards devised and published by RSA laboratories in California. ... An adaptive chosen ciphertext attack is an interactive form of chosen ciphertext attack in which an attacker sends a number of ciphertexts to be decrypted, then uses the results of these decryptions to select subsequent ciphertexts. ... In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. ... In cryptography, PKCS refers to a group of Public Key Cryptography Standards devised and published by RSA laboratories in California. ... RSA-PSS is a new signature scheme that is based on the RSA cryptosystem and provides increased security assurance. ...

Signing messages

Suppose Alice uses Bob's public key to send him an encrypted message. In the message, she can claim to be Alice but Bob has no way of verifying that the message was actually from Alice since anyone can use Bob's public key to send him encrypted messages. So, in order to verify the origin of a message, RSA can also be used to sign a message. A digital signature or digital signature scheme is a type of asymmetric cryptography used to simulate the security properties of a signature in digital, rather than written, form. ...

Suppose Alice wishes to send a signed message to Bob. She produces a hash value of the message, raises it to the power of d mod n (as she does when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he raises the signature to the power of e mod n (as he does when encrypting a message), and compares the resulting hash value with the message's actual hash value. If the two agree, he knows that the author of the message was in possession of Alice's secret key, and that the message has not been tampered with since. In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ...

Note that secure padding schemes such as RSA-PSS are as essential for the security of message signing as they are for message encryption, and that the same key should never be used for both encryption and signing purposes. RSA-PSS is a new signature scheme that is based on the RSA cryptosystem and provides increased security assurance. ...

Security

This article or section needs to be updated. Parts of this article or section are no longer up to date. Please update the article to reflect recent events, and remove this template when finished.

The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i.e., no efficient algorithm exists for solving them. Providing security against partial decryption may require the addition of a secure padding scheme. Image File history File links Gnome_globe_current_event. ... Image File history File links This is a lossless scalable vector image. ... Prime decomposition redirects here. ... In cryptography, the RSA problem is the task of finding eth roots modulo a composite number N whose factors are not known. ... In cryptography, padding is the practice of adding material of varying length to the plaintext of messages. ...

The RSA problem is defined as the task of taking eth roots modulo a composite n: recovering a value m such that c=m^e mod n, where (n, e) is an RSA public key and c is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulus n. With the ability to recover prime factors, an attacker can compute the secret exponent d from a public key (n, e), then decrypt c using the standard procedure. To accomplish this, an attacker factors n into p and q, and computes (p-1)(q-1) which allows the determination of d from e. No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists. See integer factorization for a discussion of this problem. In cryptography, the RSA problem is the task of finding eth roots modulo a composite number N whose factors are not known. ... Prime decomposition redirects here. ...

As of 2005, the largest number factored by a general-purpose factoring algorithm was 663 bits long, using a state-of-the-art distributed implementation. RSA keys are typically 1024–2048 bits long. Some experts believe that 1024-bit keys may become breakable in the near term (though this is disputed); few see any way that 4096-bit keys could be broken in the foreseeable future. Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 256 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. If n is 512 bits or shorter, it can be factored by several hundred computers as of 1999.^{[citation needed]} A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys. It is currently recommended that n be at least 2048 bits long. 2005 is a common year starting on Saturday of the Gregorian calendar. ... This article is about the unit of information. ... For the album by Prince, see 1999 (album) 1999 is a common year starting on Friday of the Gregorian calendar, and was designated the International Year of Older Persons by the United Nations. ... In cryptography and number theory, TWIRL (The Weizmann Institute Relation Locator) is a hypothetical hardware device designed to speed up the sieving step of the general number field sieve integer factorization algorithm. ...

In 1994, Peter Shor published Shor's algorithm, showing that a quantum computer could in principle perform the factorization in polynomial time. However, quantum computation is still in the early stages of development and may never prove to be practical. Peter Shor Peter W. Shor (born August 14, 1959) is an American theoretical computer scientist most famous for his work on quantum computation, in particular for devising a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical computer (see Shors algorithm). ... Shors algorithm is a quantum algorithm for factoring an integer N in O((log N)3) time and O(log N) space, named after Peter Shor. ... The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers. ... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...

See also: RSA Factoring Challenge

The RSA Factoring Challenge is 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. ...

Practical considerations

Key generation

Finding the large primes p and q is usually done by testing random numbers of the right size with probabilistic primality tests which quickly eliminate virtually all non-primes. A primality test is an algorithm for determining whether an input number is prime. ...

p and q should not be 'too close', lest the Fermat factorization for n be successful, if p-q, for instance is less than 2n^1/4 (which for even small 1024-bit values of n is 3x10⁷⁷) solving for p and q is trivial. Furthermore, if either p-1 or q-1 has only small prime factors, n can be factored quickly by Pollard's p − 1 algorithm, and these values of p or q should therefore be discarded as well. Fermats little theorem states that if p is a prime number, then for any integer a, This means that if you take some number a, multiply it by itself p times and subtract a, the result is divisible by p (see modular arithmetic). ... Pollards p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. ...

It is important that the secret key d be large enough. Michael J. Wiener showed in 1990 that if p is between q and 2q (which is quite typical) and d < n^1/4/3, then d can be computed efficiently from n and e. There is no known attack against small public exponents such as e=3, provided that proper padding is used. However, when no padding is used or when the padding is improperly implemented then small public exponents have a greater risk of leading to an attack, such as for example the unpadded plaintext vulnerability listed above. 65537 is a commonly used value for e. This value can be regarded as a compromise between avoiding potential small exponent attacks and still allowing efficient encryptions (or signature verification). The NIST Special Publication on Computer Security (SP 800-78 Rev 1 of August 2007) does not allow public exponents e smaller than 65537, but does not state a reason for this restriction.

Speed

RSA is much slower than DES and other symmetric cryptosystems. In practice, Bob typically encrypts a secret message with a symmetric algorithm, encrypts the (comparatively short) symmetric key with RSA, and transmits both the RSA-encrypted symmetric key and the symmetrically-encrypted message to Alice. The Data Encryption Standard (DES) is a cipher (a method for encrypting information) selected as an official Federal Information Processing Standard (FIPS) for the United States in 1976, and which has subsequently enjoyed widespread use internationally. ... A symmetric-key algorithm is an algorithm for cryptography that uses the same cryptographic key to encrypt and decrypt the message. ...

This procedure raises additional security issues. For instance, it is of utmost importance to use a strong random number generator for the symmetric key, because otherwise Eve (an eavesdropper wanting to see what was sent) could bypass RSA by guessing the symmetric key. A random number generator is a computational or physical device designed to generate a sequence of elements (usually numbers), such that the sequence can be used as a random one. ...

Key distribution

As with all ciphers, how RSA public keys are distributed is important to security. Key distribution must be secured against a man-in-the-middle attack. Suppose Eve has some way to give Bob arbitrary keys and make him believe they belong to Alice. Suppose further that Eve can intercept transmissions between Alice and Bob. Eve sends Bob her own public key, which Bob believes to be Alice's. Eve can then intercept any ciphertext sent by Bob, decrypt it with her own secret key, keep a copy of the message, encrypt the message with Alice's public key, and send the new ciphertext to Alice. In principle, neither Alice nor Bob would be able to detect Eve's presence. Defenses against such attacks are often based on digital certificates or other components of a public key infrastructure. It has been suggested that Mafia Fraud Attack be merged into this article or section. ... In cryptography, a public key certificate (or identity certificate) is a certificate which uses a digital signature to bind together a public key with an identity &#8212; information such as a the name of a person or an organisation, their address, and so forth. ... Diagram of a public key infrastructure In cryptography, a public key infrastructure (PKI) is an arrangement that binds public keys with respective user identities by means of a certificate authority (CA). ...

Timing attacks

Kocher described a new attack on RSA in 1995: if the attacker Eve knows Alice's hardware in sufficient detail and is able to measure the decryption times for several known ciphertexts, she can deduce the decryption key d quickly. This attack can also be applied against the RSA signature scheme. In 2003, Boneh and Brumley demonstrated a more practical attack capable of recovering RSA factorizations over a network connection (e.g., from a Secure Socket Layer (SSL)-enabled webserver). This attack takes advantage of information leaked by the Chinese remainder theorem optimization used by many RSA implementations. Paul C. Kocher is an American cryptographer and cryptography consultant, currently the president of Cryptography Research, Inc. ... Year 2003 (MMIII) was a common year starting on Wednesday of the Gregorian calendar. ... Dan Boneh is an associate professor of Computer Science and Electrical Engineering at Stanford University. ... Secure Sockets Layer (SSL) and Transport Layer Security (TLS), its successor, are cryptographic protocols which provide secure communications on the Internet. ... Several related results in number theory and abstract algebra are known under the name Chinese remainder theorem. ...

One way to thwart these attacks is to ensure that the decryption operation takes a constant amount of time for every ciphertext. However, this approach can significantly reduce performance. Instead, most RSA implementations use an alternate technique known as cryptographic blinding. RSA blinding makes use of the multiplicative property of RSA. Instead of computing c^d mod n, Alice first chooses a secret random value r and computes (r^ec)^d mod n. The result of this computation is r m mod n and so the effect of r can be removed by multiplying by its inverse. A new value of r is chosen for each ciphertext. With blinding applied, the decryption time is no longer correlated to the value of the input ciphertext and so the timing attack fails. In cryptography, blinding is a technique by which an agent can provide a service to (i. ...

Adaptive chosen ciphertext attacks

In 1998, Daniel Bleichenbacher described the first practical adaptive chosen ciphertext attack, against RSA-encrypted messages using the PKCS #1 v1 padding scheme (a padding scheme randomizes and adds structure to an RSA-encrypted message, so it is possible to determine whether a decrypted message is valid.) Due to flaws with the PKCS #1 scheme, Bleichenbacher was able to mount a practical attack against RSA implementations of the Secure Socket Layer protocol, and to recover session keys. As a result of this work, cryptographers now recommend the use of provably secure padding schemes such as Optimal Asymmetric Encryption Padding, and RSA Laboratories has released new versions of PKCS #1 that are not vulnerable to these attacks. Year 1998 (MCMXCVIII) was a common year starting on Thursday (link will display full 1998 Gregorian calendar). ... Daniel Bleichenbacher (born August 4, 1964) is a German cryptographer, currently a researcher at Bell Labs. ... An adaptive chosen ciphertext attack is an interactive form of chosen ciphertext attack in which an attacker sends a number of ciphertexts to be decrypted, then uses the results of these decryptions to select subsequent ciphertexts. ... In cryptography, padding is the practice of adding material of varying length to the plaintext of messages. ... Secure Sockets Layer (SSL) and Transport Layer Security (TLS), its successor, are cryptographic protocols which provide secure communications on the Internet. ... In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. ...

Branch prediction analysis (BPA) attacks

Many processors use a branch predictor to determine whether a conditional branch in the instruction flow of a program is likely to be taken or not. Usually these processors also implement simultaneous multithreading (SMT). Branch prediction analysis attacks use a spy process to discover (statistically) the private key when processed with these processors. In computer architecture, a branch predictor is the part of a processor that determines whether a conditional branch in the instruction flow of a program is likely to be taken or not. ... Simultaneous multithreading, often abbreviated as SMT, is a technique for improving the overall efficiency of superscalar CPUs. ...

Simple Branch Prediction Analysis (SBPA) claims to improve BPA in a non-statistical way. In their paper, "On the Power of Simple Branch Prediction Analysis", the authors of SBPA (Onur Aciicmez and Cetin Kaya Koc claim to have discovered 508 out of 512 bits of an RSA key in 10 iterations.

See also

• Clifford Cocks
• Quantum cryptography
• Cryptographic key length
• Computational complexity theory
• Diffie-Hellman
• RSA Factoring Challenge
• List of software patents

Clifford Christopher Cocks is a British mathematician and cryptographer at GCHQ who invented the widely-used encryption algorithm now commonly known as RSA, about three years before it was independently developed by Rivest, Shamir, and Adleman at MIT. He has not been generally recognised for this achievement because his work... Quantum cryptography, or quantum key distribution (QKD), uses quantum mechanics to guarantee secure communication. ... In cryptography, the key size (alternatively key length) is a measure of the number of possible keys which can be used in a cipher. ... As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ... Diffie-Hellman key exchange is a cryptographic protocol which allows two parties to agree on a secret key over an insecure communication channel. ... The RSA Factoring Challenge is 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. ... Notable software patents include: RSA Patent - a famous software patent on the ground-breaking and highly unobvious algorithm for public key encryption, widely used for secure communications in many industries nowdays (RSA) Karmarkar Patent - a famous software patent on the highly non-trivial mathematical algorithm for solving linear programming problems...

Notes

1. ^ ^{a b} SIAM News, Volume 36, Number 5, June 2003, "Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders", by Sara Robinson

References

• Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7
• R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120–126. 1978. Previously released as an MIT "Technical Memo" in April 1977. Initial publication of the RSA scheme.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.7: The RSA public-key cryptosystem, pp.881–887.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

• PKCS #1: RSA Cryptography Standard (RSA Laboratories website)
  • The PKCS #1 standard "provides recommendations for the implementation of public-key cryptography based on the RSA algorithm, covering the following aspects: cryptographic primitives; encryption schemes; signature schemes with appendix; ASN.1 syntax for representing keys and for identifying the schemes".
• Thorough walk through of RSA
• Online RSA Encryption Application
• RSA demo with Java and Javascript
• How the RSA Cipher Works
• Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (free PDF downloads), see Chapter 8
• Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: On the Power of Simple Branch Prediction Analysis
• A New Vulnerability In RSA Cryptography, CAcert NEWS Blog
• Example of an RSA implementation with PKCS#1 padding (LGPL source code)
• RSA implementation in the Tcl programming language
• A New Method of Serial Modular Multiplication describes a hardware design that does multiplication and modulo reduction simultaneously in a bit-serial fashion, speeding up operations such as RSA by a large factor. Creating the FAP4 chip is an informal description of implementing a chip (the world's first RSA chip, in 1985) using this design.