Text years of attacks on the RSA Cryptosystem

By Dan Boneh @ Stanford University (Dabo @ CS. Stanford. EDU)

Translator: Jing Ling @ 360esg A-Team (admin @ hackfun. ORG)

1 Introduction

The RSA cryptosystem, invented by Ron Rivest, ADI Shamir and Len Adleman, was first published in the August 1977 issue of Scientific American. Cryptosystems are most commonly used to provide privacy protection and ensure the authenticity of digital data. At present, RSA is deployed in many commercial systems. Web server and browser use it to protect web traffic. It can be used to protect the privacy and authenticity of e-mail. It can also be used to protect remote login session. At the same time, it is also the core of electronic credit card payment system. In short, RSA is often used in applications where digital data security needs to be considered.

Since its initial release, RSA system has been considered vulnerable by many researchers. Although twenty years of research have produced many fascinating attacks, none of them are devastating. These attacks mainly show the danger of improper use of RSA, so it is a very important task to implement RSA safely. Our goal is to use the knowledge of basic mathematics to analyze some of these attacks. In the whole analysis process, we follow the standard naming convention, use Alice and Bob to represent two normal communicators who want to communicate with each other, and Marvin to represent malicious attackers who want to eavesdrop or tamper with the communication between Alice and Bob.

Let's start with a simplified version of RSA encryption. Let it be the product of two prime numbers with the same bit length. The common length size is = 1024 bits (that is, 309 decimal digits), and the prime factor = 512 bits. Let be two integers satisfying, where is the order of the multiplication group. We call it RSA modulus, encryption index, decryption index. It's a public key. As the name implies, the public key is public and used to encrypt messages. It is called a key or private key. Generally, only the receiver of the encrypted message knows that the private key can decrypt the ciphertext.

The message is an integer and satisfies the requirements. It needs to be encrypted, calculated, and decrypted. It needs to be calculated by the legal receiver of the ciphertext. (Note: here is the proof added by the translator)

Euler's theorem: if it is a positive integer and it is a reciprocal prime, then.

It is known that,,, to verify.

Prove:

The left side of the equation is

To the right of the equation is

The right side of the equation is equal to the left side of the equation.

Defining an RSA function, if known, can be easily solved by using the equation, we call it the trapdoor of solving function. In this paper, we study how to solve RSA function without trapdoor. To give a triple, we know that it is very difficult to calculate the root of module in unknown factors. Because it's a finite set, you can enumerate all the elements of until you find them. Unfortunately, this will result in the algorithm having order run time, which is the exponent of its input size, which is the order of. We are interested in algorithms that run at a lower time, that is, the order of (among them) or some small constants (for example, less than 5). Practice shows that these algorithms usually perform well in the input situation discussed. In the whole paper, we call these algorithms efficient algorithms.

In this project, we mainly study RSA function instead of RSA cryptosystem. Generally speaking, it should be very difficult to solve RSA function on random input, which means that given attacker can not calculate plaintext. That's not enough. Cryptosystems have to resist more subtle attacks. If given, it should be very difficult to calculate any information from it, which is called semantic security. We will not discuss these subtle attacks, but we must point out that RSA as mentioned above is not semantically secure: given, some information about plaintext can be easily derived (for example, the Jacobian symbols on can be easily derived). The semantic security of RSA can be guaranteed by adding random processing flow to encryption process.

RSA function is a one-way trapdoor function, which can be easily calculated in the forward direction, but (as we know) it can not be effectively solved in the reverse direction without trapdoor unless in special circumstances. One way trapdoor function can be used for digital signature, which can guarantee the authenticity and non repudiation of electronic documents. For example, they are used to sign digital checks or electronic purchase orders. In order to sign the message using RSA, Alice uses her private key to sign and obtain the signature. After given, anyone can verify the Alice signature on. Because only Alice can generate, one might think that an attacker cannot forge Alice's signature. However, things are not so simple. In order to ensure the security of the signature, some additional measures are needed. Digital signature is an important application of RSA. In this project, we will also study some attacks against RSA digital signature.

RSA key pair can be generated by selecting two random bit prime numbers and multiplying them by each other. Then, for a given encryption index, the extended Euclid algorithm is used. Because the set of prime numbers is dense enough, we can quickly generate random bit prime numbers by repeatedly selecting random bit integers and testing each prime number with probability prime test.

1.1 large number decomposition

Given the RSA public key, the first attack we think of is the decomposition modulus, which can be calculated by the factor attacker, and then the decryption index can also be calculated. We call this method of decomposition modulus a violent attack against RSA. Although the decomposition algorithm has been improved steadily, the current technology level is far from threatening the security of RSA when RSA is used correctly. Large integer decomposition is the beauty of computational mathematics, but the subject of this paper is not large integer decomposition. For the sake of completeness, by the way, the current common digital domain sieve method is the most efficient decomposition method. It takes time to decompose the bit integers, and it is so attractive to attack RSA methods that take longer than this range, such as violent search methods, and some old methods that RSA has not been published for a long time.

Our purpose is to study the attack method of decrypting messages without directly decomposing the RSA module. It is worth noting that some sparse sets of RSA modules can be easily decomposed. For example, if the quality factor of the product is less than, then it can be decomposed in less than time.

As mentioned above, RSA is not secure if there is an efficient factorization algorithm, and vice versa. This is a long-standing open question: must there be a factor to effectively calculate the number of modules? Is RSA as hard to crack as factorization? We put forward specific open questions below.

Open question 1

Given and satisfied, define function:,. Is there a polynomial time algorithm to calculate a given factor and an oracle for a given result?

Most recently, evidence provided by Boneh and Venkatesan shows that in a relatively small case, the answer to the above question may be No. In other words, in a relatively small case, there may not be polynomial time reduction from decomposition to RSA cracking. Their experiments show that the positive answer to a small problem in a certain model will produce an effective factorization algorithm. We note that a positive answer to open question 1 can lead to a "chosen ciphertext attack" on RSA. Therefore, the negative answer may be what everyone likes.

Next, we prove that public private key and decomposition are equivalent. It can be seen that hidden factorization is meaningless for anyone who knows it.

Fact 1

For RSA public key, given private key can effectively decompose modulus. On the contrary, given factorization, the private key can be calculated effectively.

Prove

The factorization of, because we know, then we can work it out, and vice versa. We now prove that a given can be decomposed. Given, calculated. According to the definition of sum, we know that it is a multiple of. Because it is even, where is odd and. For each, so it's the square root of the unit module. According to the Chinese remainder theorem, 1 has four square root modules. Two of the square roots are, and the other two are, where and are satisfied. Using any of the last two square roots, the factorization is revealed by calculation. A straightforward argument shows that if one of the elements in the sequence is randomly selected, the probability of,,..., being the unified square root is at least 1 / 2, thus revealing the decomposition of, all elements in the sequence can be effectively calculated in time, among which.

2 basic attack

Let's start by describing some of the old basic attacks that illustrate RSA's blatant abuse. Although there are many such attacks, we will give just two examples.

2.1 common mode

In order to avoid generating different modules for each user, one might want to fix one once and for all, using the same for all users. A trusted central authority can provide users with a unique pair from which they can generate public and private keys.

At first glance, this seems to work: the ciphertext for Alice can't be decrypted by Bob because Bob doesn't know. However, this is not correct and the resulting system is unsafe. In fact, Bob can use his own index to decompose. Once decomposed, Bob can calculate Alice's private key from her public key. This observation by Simmons shows that RSA modules should not be used by more than one entity.

2.2 blindness

Let it be Bob's private key, but his corresponding public key. Suppose the attacker Marvin wants Bob to sign the message. Of course Bob is not a fool. He refuses to sign. But Marvin can try the following: he randomly selects one and sets it. Then he asked Bob to sign the random message. Bob may be willing to sign something that doesn't seem to be a problem, but recall that Marvin now simply calculates Bob's initial signature.

This so-called blinding technique enables Marvin to obtain an effective signature on a message of his choice by having Bob sign on a random "blinded" message. Bob didn't know what he was actually signing. Because most signature schemes apply "one-way hash" algorithm to messages before signature, this kind of attack is not a serious problem. Although we describe blinding as an attack, it is actually a useful attribute needed to implement anonymous digital cash (cash that can be used to buy goods, but it will not disclose the identity of the buyer).

3 low private key index

To reduce encryption time (or signature generation time), people may want to use small values instead of random ones. Since modular exponentiation takes a linear time of, small can improve performance by at least 10 times (for 1024 bit modules). Unfortunately, a clever attack discovered by M. Wiener shows that a small one can lead to a complete breach of the cryptosystem.

Theorem 2 (M. Wiener)

Given and satisfied, the attacker can calculate it effectively.

Prove

It is proved that there is a satisfaction based on the approximation of continuous fraction. So,

So, yes approximation, although Marvin doesn't know, he might use to approximate. Because, we have.

Using substitution, we get:

Now, because, we know. So we get:

This is a classical approximation relation, which is fractional and very approximate within the constraints. In fact, all fractions like this are convergence of continued fraction expansion. So the first thing we do is to calculate the convergence of the continued fraction, one of which is equal to. Because, we have, so it's a minimalist score. This is a linear time algorithm that can calculate the key.

Since it is usually 1024 bits, it must be at least 256 bits long to avoid this attack. This is unfortunate for low-power devices such as smart cards, which can save a lot of energy. However, it is not impossible. Wiener puts forward many technologies that can realize fast decryption and are not vulnerable to attacks

Use large: let's say that instead of reducing the modulus, we use it as a public key, for some of the large ones.

Obviously, instead of being used for message encryption, when a large value is used, the above proof is no longer small. A simple calculation shows that if, no matter how small, the above attacks cannot be carried out. However, a large value will lead to an increase in encryption time.

Using CRT:

Another method is to use the Chinese Remainder Theorem (CRT). Let's assume that both and are small, such as 128 bits. Then the following ciphertext can be decrypted quickly: first, calculate and.

The CRT is then used to calculate a unique value that satisfies the sum

The satisfied equation. The key point is that although the sum is small, the value of can be very large, about the order of magnitude. Therefore, the attack of theorem 2 is no longer applicable. We note that if given, there is an attack that allows attackers to factorize in time. So, and cannot be too small.

We don't know if all of these methods are safe. What we know is that Wiener attacks don't work for them. Recently, the theorem 2 improved by Boneh and durfee proves that as long as the attacker can calculate it effectively. These results show that the boundary of Wiener is not fixed. The right boundary might be. As of the time of writing, it is still an unsolved problem.

Open question 2

If Marvin knows the relationship between and, can he work it out effectively?

4 low public key index

To reduce encryption or signature verification time, a small public key index is usually used. The minimum possible value of is 3, but it is recommended to prevent some attacks. When using values, signature verification requires 17 times of multiplication, while when using random, it requires about 1000 times of multiplication. Unlike the attack in the previous section, when used for an hour, the attack is not just to break.

4.1 coppersmith theorem

The most powerful attack against RSA low public key index is based on a theorem of copper Smith, which has many applications. Here we only discuss some of them, and prove that LLL lattice reduction algorithm is as follows.

Theorem 3 (coppersmith) makes it an integer, which is a quadratic univariate polynomial. Suppose Marvin can find all satisfied integers effectively after given, and the running time is determined by the time needed to run LLL algorithm on the lattice of dimension and.

This theorem provides an algorithm for effectively finding all the less than roots of modules. The smaller the algorithm is, the shorter the running time of the algorithm is. The power of this theorem is that it can find the small roots of polynomials. When the modulus is prime, at present, there is no better rooting algorithm than coppersmith theorem. There is no reason not to use coppersmith theorem.

We summarize the main idea behind the proof of coppersmith's theorem. We adopt the simplified method proposed by howgrave Graham, give a polynomial, define it, and the proof depends on the following observation.

Lemma 4

Let it be a polynomial of degree and a positive integer. If it is satisfied, then it is true.

From Schwarz inequality, it is proved that:

Because, we come to a conclusion.

Lemma points out that if it is a low norm polynomial, all the small roots of are also roots on integers. Lemma shows that to find a small root, we need to find another low norm polynomial with the same root as the module, so that we can easily find the root on the integer. Therefore, we can find a polynomial with low norm, that is, norm less than. This is equivalent to looking for integer linear combinations with low norm polynomials. However, in most cases, there is no nontrivial linear combination with sufficiently small norm.

Coppersmith has found the trick to solve this problem: if it works, then for any. More generally, the following polynomials are defined:

For some predefined, it's a root of the module, where and. To use lemma 4, we must find an integer linear combination of polynomials so that the norm of is less than (recall the upper bound of satisfaction). Because of the relaxed upper bound of norm (yes, not), we can prove that for large enough, there is always a bound that the linear combination satisfies the requirements. Once found, lemma 4 means that it has roots as integers, so it can be easily found.

How to find it effectively remains to be proved. To achieve this, we must explain some basic facts about lattice. Let it be a linearly independent vector. A (full rank) lattice is a set of all linear combinations of integers of. The determinant of is defined as the determinant of a square matrix, and its determinant is a vector.

In our example, we consider polynomials as vectors and study the lattice they form. Let,, then the dimension of the lattice. For example, when it is a quadratic univariate polynomial, the resulting lattice is composed of rows of the following matrices:

Elements correspond to coefficients of polynomials whose values we ignore, and all empty elements are zero. Since the matrix is triangular, its determinant is the product of elements on the diagonal (as shown above), our goal is to find the short vector in this lattice.

A classical conclusion of Hermite shows that a lattice of any dimension contains a non-zero vector, and its norm is satisfied, in which is a constant only depending on. The bound of Hermite can be used to prove that for large enough, our lattice contains a norm vector whose demand is less than. The question is whether we can effectively construct short vectors in which the length is less than Hermite bound. LLL algorithm is an effective algorithm, which just can be achieved.

Fact 5 (LLL)

Suppose is a lattice made up of. When it is used as input, the LLL algorithm outputs a vector to meet the following requirements:

The LLL algorithm runs for a quarter of the input length.

LLL algorithm (named after its inventors, L. lovasz, a. Lenstra and H. Lenstra Jr) has many applications in computational number theory and cryptography. Its discovery in 1982 provides an effective algorithm for Factorization of polynomials over integers and, more generally, for Factorization of polynomials over number rings. LLL algorithm is often used to attack various cryptosystems. For example, many cryptosystems based on "knapsack problem" are cracked by LLL algorithm.

Using LLL algorithm, we can prove coppersmith theorem. To ensure that the vectors generated by LLL algorithm meet the bounds of lemma 4, we need to meet the following requirements:

Where is the dimension of. The conventional calculation shows that the constraints can be satisfied for large enough ones. In fact, at that time, the sum was enough. Therefore, the running time is mainly determined by the LLL algorithm running on the lattice with dimension.

A natural question is whether coppersmith theorem can be applied to binary and multivariate polynomials. If there are roots and proper bounds, can Marvin find them effectively? Although the same technique seems to be applicable to some bivariate polynomials, it is still an open problem to be proved. As more and more results depend on the binary expansion of coppersmith's theorem, rigorous algorithms will be very useful.

Open question 3

It is found that the coppersmith theorem can be extended to the general conditions of bivariate polynomials.

4.2 hastad broadcast attack

As the first application of coppersmith theorem, we improve the old attack proposed by hastad. Suppose Bob wants to send encrypted messages to multiple parties. Each party has its own RSA key. We assume it's smaller than all. Bob naively encrypts it with each public key and sends the ciphertext to. Marvin, the attacker, can eavesdrop Bob's external connection and collect the ciphertext transmitted.

For simplicity, all public key indices are assumed to be 3. A simple argument shows that Marvin was able to calculate. In fact, Marvin gets, where:

For all of them, we can assume that Marvin can factorize some. Therefore, the Chinese Remainder Theorem (CRT) is applied to the satisfaction given by. Because it's less than all, we have, then it holds on integers, so Marvin can get it by calculating the real root. More generally, if all the public key exponents are equal, Marvin can calculate them as long as they are. However, this kind of attack is only feasible when a smaller value is used.

Hastad proposed a stronger attack method. In order to defend against hastad's attacks, consider naive defense against these attacks. Bob may "fill in" messages before encryption, rather than broadcast encrypted ones. For example, if it's bit long, Bob can send it to. Marvin was unable to launch an attack because he was encrypted with different messages. However, hastad proved that this kind of linear padding is not safe. In fact, he proved that applying any fixed polynomials to messages before encryption can not prevent attacks.

Suppose that Bob has a fixed common polynomial for each participant. In order to broadcast the message, Bob sends the encryption of to. Marvin got it through wiretaps, among them. Hastad shows that Marvin can calculate plaintext from all ciphertexts if there are enough participants. The following theorem is a stronger version of hastad's original conclusion.

Theorem 6 (hastad) is a set of relative prime numbers in pairs. Let it be a polynomial of degree. Suppose there is a unique satisfaction:

Suppose, given, we can find it effectively.

We assume that everything is one yuan. (in fact, for some, the first term coefficient is irreversible in, so the factorization will appear. By multiplying each by an appropriate power, assume that they all have a power. Construct Polynomials:

Where is an integer, known as China's residual coefficient. So it must be unary, because its first term is all modulus, and its number is. In addition, we know. Theorem 6 can now be derived from Theorem 3 because.

The theorem shows that if enough equations are provided, the system of unary equations with relative prime compound modulus can be solved effectively. So, we can know that when the number of participants is at least, Marvin can be calculated from the given ciphertext, where is the maximum value on all. In particular, if everything is equal to, and Bob sends a linearly related message, Marvin can calculate the plaintext as long as he can.

The original theorem of hastad is weaker than the above one. Unlike polynomials, hastad's theorem requires polynomials. The proof of hastad theorem is similar to that of coppersmith theorem mentioned in the previous section. Since hastad's theorem does not use a power in a lattice, a weak bound is obtained.

To summarize this section, we note that to properly defend against the above broadcast attacks, we must use the random fill method instead of the fixed fill method.

4.3 Franklin Reiter related message attack

When Bob sends Alice related encrypted messages with the same modulus, Franklin and Reiter find a clever attack. It's Alice's public key. Suppose it's two different messages. For some known polynomials, it satisfies. To send and to Alice, Bob may naively encrypt the message and transmit the resulting ciphertext. We can know by proof that Marvin can calculate it easily in a given situation. Although the attack is effective for any small size, in order to simplify the proof, we give the lemma.

Lemma 7 (FR)

, is the RSA public key. Let the linear polynomial of satisfy. Then, given that Marvin can calculate in the square time of.

Prove

To ensure the generality of this part of the proof, we use arbitrary to express it (rather than limit it to). Because, we know it's the root of a polynomial. It's also the root. The linear factor is the division of two polynomials. Therefore, Marvin can use Euclid algorithm to calculate the greatest common divisor (GCD) of sum. If GCD is linear, it can be found. GCD can be calculated in the square time of sum.

We prove that GCD must be linear at that time. Polynomial factors will sum into a linear factor and an irreducible quadratic factor (because, therefore, there is only one root in). Because it's not divisible, GCD must be linear. For the case, GCD is almost always linear. However, for some rare sum, it is possible to get a nonlinear GCD, in which case the attack will fail.

For the case, the time required to attack is the square time of. Therefore, this attack can only be applied when a small public key index is used. For large electronic computers, the work of computing GCD is daunting. An interesting question (though it may be difficult), for arbitrary design of such attacks, in particular, can we find the GCD of the above sum in polynomial time?

4.4 coppersmith short fill attack

Franklin Reiter's attack may seem artificial. After all, why does Bob send Alice the encryption of the relevant message? Coppersmith strengthens the attack and proves an important conclusion about the filling attack.

Random fill algorithm can fill plaintext by appending some random bits to one end, but the following attack points out the danger of this simple fill. Suppose Bob sends Alice properly populated encryption. Marvin intercepts the ciphertext and prevents it from reaching its destination. Bob noticed that Alice didn't reply to his message and decided to resend it to Alice. He randomly fills in and transmits the generated ciphertext. Marvin now has two ciphertexts, corresponding to two encryptions of the same message using two different random fills. The following theorem shows that Marvin can work out plaintext even though he does not know the filling algorithm used.

Theorem 8

Set to RSA public key, where length is bit. Command set. Set is the message with the longest length as bit. Defines and, where and are integers of. If Marvin knows the encryption of and (but does not know or), he can effectively calculate M.

Prove

We know that these polynomials have the same roots. In other words, it's the root of the knot. At most. In addition, it is a small root of a module, and Marvin can use the coppersmith theorem (Theorem 3) to find this root effectively. Once known, you can use the Franklin Reiter attack in the previous section to figure it out.

At that time, as long as the fill length is less than the message length, it can be attacked. This is an important conclusion. Note that for recommended values, this attack is useless for standard modulus sizes.

4.5 partial key disclosure attack

Set it to RSA private key, assuming that Marvin knows part of it in some way, such as a quarter. Can he get the rest? When the corresponding public key index is small, the answer is yes, which is surprising. Recently, Boneh, durfee and Frankel proved that as long as it is possible to calculate all parts from a small part of it. The conclusion shows the importance of protecting RSA private key.

Theorem 9 (BDF)

Set to RSA private key, where length is bit. Given the least significant bit, Marvin can calculate it in linear time of.

The proof depends on another perfect and exquisite coppersmith theorem.

Theorem 10 (coppersmith)

Let it be a bit RSA module. Then, given the least significant bit or the most significant bit of, it can be effectively decomposed.

Theorem 9 can easily be inferred from theorem 10. In fact, according to the definition of sum, there is an integer, which makes:

Because, we must have. The program module is reduced and set to obtain:

Because Marvin knows the least significant bit of, he knows the value of, so he gets an equation about sum. For each possible value of, Marvin solves the quadratic equation and gets some candidate values. For these candidates, he uses theorem 10 to try to decompose them. The total number of candidates that can be proved is at most, so after the maximum number of attempts, they will be decomposed.

Theorem 9 is called partial key disclosure attack. For a larger value, as long as there is a similar attack, however, the technology to achieve this attack is a little complex. Interestingly, Cryptosystems Based on discrete logs, such as ElGamal public key systems, do not seem to be susceptible to partial key disclosure attacks. In fact, if the constant part of the sum is given, there is no known polynomial time algorithm to calculate the rest of the sum.

To summarize this section, we will prove that when the encryption index is very small, RSA system will leak half of the most significant bits of the corresponding private key. To understand this, consider an equation where is an integer of. Given this, Marvin can easily calculate:

After that:

So, it's a good approximation. This bound shows that for most, the most significant bit in the middle half is the same as. Since there are only possible values, Marvin can construct a small set of sizes so that one element in the set is equal to half of the most significant bits. In this case, we can know that half of the most significant bits of the system are completely leaked.

5 execute attack

We turn our attention to a completely different kind of attack. These attacks do not attack the underlying structure of RSA functions, but focus on the implementation of RSA.

5.1 timing attack

Think about the smart card that stores the RSA private key. Because the card is tamperproof, the attacker Marvin may not be able to review its contents and make it disclose the key. However, a clever attack by Kocher shows that by accurately measuring the time required for a smart card to perform RSA decryption (or signature), the private decryption index can be quickly discovered.

We will explain how to attack a simple RSA implementation using the "repeated square algorithm.". Set yes to the binary representation of. Based on the observation of, we can know that the repeated square algorithm is used to calculate the most frequently used submodular multiplication. The algorithm works as follows:

Make equal to, equal to 1. For, perform the following steps:

(1) If, make equal to,

(2) Make equal to.

Finally, there is a value of.

At that time, the variable traverses the set of values, and the variable "collects" the appropriate power in the set to obtain.

In order to launch the attack, Marvin requires the smart card to generate signatures on a large number of random messages, and measures the time required for each signature generation.

The attack starts with the least significant bit and works out the bits one at a time. We know it's odd, so. Consider the second iteration. Initially and. If, the smart card calculates the product; otherwise, it does not. Setting is the time spent in smart card computing. Because the calculation time depends on the value of, it is different from each other (the simple modulus reduction algorithm needs different time, depending on the reduced value). Once Marvin gets the physical specifications of the smart card, he measures them (before the attack).

Kocher observed that at the time, the two sets and were related. For example, if, for some, it is much larger than expected, it may be larger than expected. On the other hand, if, then the sum of two sets represents independent random variables. By measuring the correlation, Marvin can determine whether it is 0 or 1. Continue to use this method, he can quickly get,. Note that when using a low public key index, the partial key disclosure attack in the previous section shows that with Kocher's timing attack, only a quarter of the known bits are needed.

There are two ways to defend against attacks. The simplest is to add the appropriate delay so that modular exponentiation always takes a certain amount of time. The second method is based on blindness proposed by Rivest. Before decrypting m, the smart card selects a random and computes it, then applies it to and obtains it, and finally, makes the. In this way, it will be applied to random messages that Marvin does not know, so that Marvin can not launch attacks.

Kocher recently discovered another attack on these lines called power cryptanalysis. Kocher shows that Marvin can easily discover the key by accurately measuring the power consumption of the smart card during signature generation. It has been proved that the power consumption of the card is higher than the normal value during multi precision multiplication. By measuring the length of the high consumption period, Marvin can easily determine whether the card performs one or two multiplication in a given iteration, thus exposing the bit.

Kocher recently discovered another similar attack called energy analysis attack. Kocher points out that by accurately measuring the power consumption of the smart card in the signature generation process, Marvin can usually easily get the secret key. The results show that the power consumption of the card is higher than the normal value in the process of multiple precision multiplication. By measuring the length of the high consumption period, Marvin can easily determine whether the card performs one or two times of multiplication in a given iteration, so as to get the bit.

5.2 random failure

RSA's decryption and signature implementation often use the Chinese Remainder Theorem to accelerate the calculation. Bob, the signer, in order to replace the module, first calculates the result of the signature module sum, and then uses the Chinese Remainder Theorem to combine the result. More precisely, Bob first calculates:

Among them. He then received a signed order:

Among them:

Compared with the two indexes, the running time of the last step of CRT is negligible. Note that the sum is half of the length, and then because the simple implementation of multiplication requires square time, the multiplication speed of the module is 4 times of that of the module, and, yes, half of the length, and the calculation speed is 8 times of that of the module. Therefore, the whole signature time is reduced by four times, and many implementations use this method to improve performance.

Boneh, demillo and Lipton observed the inherent dangers of using CRT. Let's say that when a signature is generated, a small fault on Bob's computer causes it to miscalculate in an instruction. For example, when a value in a register is copied from one location to another, one of the bits is flipped. (the failure may be caused by environmental electromagnetic interference, or it may be caused by rare hardware defects, such as earlier versions of Pentium chips. )

Marvin can easily decompose the modulus of Bob after getting the invalid signature.

As a. K. Lenstra said, we found a new attack. Suppose a single error occurs when Bob generates the signature, then, or one will be miscalculated. If it is correct, it will be incorrect. The signature obtained is. Once Marvin gets it, by calculation, he knows it's a wrong signature. However, it was noted that:

Therefore, it is a non trivial factor.

For an attack to work, Marvin must have a good understanding of it. That is to say, we assume that Bob does not use any random fill method, and the random fill before signature can prevent this kind of attack. For Bob, a simpler defense method is to check the generated signature before sending it to the world. Inspection is particularly important when using CRT acceleration methods. Random failure attack is harmful to many cryptosystems. Many systems, including RSA's non CRT implementation, can use random failure to attack. However, these conclusions are more theoretical.

5.3 bleichenbacher's attack on PKCs 1

Set is bit RSA module, is bit message, where. Before RSA encryption is applied, the message is usually filled in place by adding random bits to it. This method is used in the old version of Public Key Cryptography Standard 1 (PKCs 1). After populating, the message is as follows:

02 random bit 00 M

The generated message is bit long and encrypted directly with RSA. The initial block length containing "02" is 16 bits. As can be seen from the above figure, random padding has been added to the message.

When an application (for example, a web browser) running on Bob's machine receives a message, it decrypts it, checks the initial block, and removes random padding. However, some applications check the "02" initial block and, if it does not exist, return an error message stating "invalid ciphertext.". Bleichenbacher said the error message could have catastrophic consequences: Marvin, the attacker, could use the error message to decrypt the ciphertext of his choice.

Suppose Marvin intercepts a ciphertext for Bob and wants to decrypt it. In order to launch the attack, Marvin randomly selected one, calculated it and sent it to Bob's machine. The application running on Bob's machine receives and attempts to decrypt it. It either responds with an error message, or it doesn't respond at all, if it's well formed. Therefore, Marvin knows whether the 16 most significant bits in the decryption process are equal to 02. In fact, Marvin has such an oracle that he can test whether the 16 most significant bits of decryption are equal to 02 for any of his choices. Bleichenbacher proved that such an oracle was enough to decrypt.

6 Conclusion

After 20 years of research on RSA system, there have been some insightful attacks, but no destructive attacks have been found. The attacks discovered so far mainly illustrate the pitfalls that need to be avoided when implementing RSA. At present, it seems that the correct RSA cryptosystem implementation can be trusted to provide security in the digital world. We divide the attacks against RSA into four categories: (1) basic attacks using the system's blatant misuse; (2) low private key index attacks, which are very serious and should never be used; (3) low public key index attacks; (4) attacks on the execution of RSA system. These continuous attacks show that our research on the basic mathematical structure is not enough. In addition, desmedt and Odlyzko, joye and quisquater, and dejonge and Chaum have proposed some additional attacks. Throughout this paper, we have observed that many attacks can be prevented by properly populating messages before encryption or signing.

Thank

I would like to thank Susan Landau for encouraging me to write the questionnaire and Tony Knapp for helping to edit the manuscript. I would also like to thank mihir bellare, Igor shparinski and r. Venkatesan for their comments on the draft earlier.

This article was published by seebug paper. If you need to reprint it, please indicate the source. Address: https://paper.seebug.org/727/