RSA Algorithm Is a common asymmetric encryption algorithm used to encrypt sensitive information transmitted over the network. This article introduces the process of RSA algorithm and an unexpected attack method.

RSA

The RSA algorithm flow is as follows:

  1. Find two mutually compatible numbers, p and q, and calculate N = p*q

  2. Determine a number e such that e is mutually prime with (p-1)(q-1), and tell the other party that the public key is (N, e)

  3. Determine the private key D such that e* D-1 is divisible by (p-1)(q-1)

  4. The message carrier transmits the messageM, encrypted ciphertextCTo:

  5. The receiver receives ciphertext messagesCDecrypt the messageM: 

RSA algorithm relies on Euler’s theorem, a simplified version is roughly a and P are mutually prime, then,

.a 的 p-1The power ofpTake over for1, (a 的 p-1The power of minus1Can be divided exactly byp).

The proof of Euler’s theorem is more complex, there was a wonderful proof of the way, but because of the wechat public number of words limited, here it is omitted (what? What does this have to do with Fermat? If you really want to see it, you can see the references at the end of the article.)

For example

N = pq, take two prime numbersp=11, q = 3, N = p * q = 33, takee 与 (p-1)(q-1) = 20Relatively prime numbere = 3And then throughDetermine the private key,

Take onedmake3*d -120 is divisible, let’s sayd=7ord=67. (3 * 7-1 = 20Of course it’s divisible by 20,3 * 67-1 = 200It’s also divisible by 20.)

So the public key is(N=33, e=3)The private keyd=7ord=67.

Suppose the encrypted messageM=8Through the encryption algorithmGet the ciphertextC=8^3 % 33 = 17

Now, decryption by, get clear textM = 17^7 % 33 = 8orM=17^67 % 33=8Isn’t it amazing? (here^How many powers does it have?

The BC command, an Amway calculator tool, supports computations of arbitrary precision, whereas simple Mac computations can be easily done by Alfred.



RSA crack

If you need to decrypt RSA, you need to find p and q so that Pq =33. If you know p and q, you can use the public key N and e to deduce the private key D. However, the decomposition of large numbers has always been a difficult problem in mathematics. Of course, the above case is relatively simple, and it becomes particularly difficult when N is large. Someone once spent five months time breakdown the number 3950587458326514452641976780061448199602077646030493645413937605157935562652945068360972784246821953509 3544305870490251995655335710209799226484977949442955603 (159 digits), RSA – 155 (512 bits) [from wikipedia].

This road doesn’t work, so some people go the other way, Stanford researchers used two hours to hack the 1024-bit RSA private key of OpenSSL 0.9.7. Remote Timing Attacks are Practical The idea is that the modulo exponentials are bit by bit, and a bit of one takes a lot more work than a bit of zero. Therefore, by obtaining a large number of messages and their encryption time, the contents of the private key can be roughly deduced based on statistics.

Timing Attack

Timing Attack is a kind of side-channel Attack (or “side-channel Attack”, Side Channel Attack, referred to as SCA), which mainly exploits the characteristic that different input will have different execution time. For a specific example, playFrameWok is used to verify that the data in the cookie(session) is valid (including the validation of the signature), which is why I wrote this article.

def safeEquals(a: String, b: String) = {  

if (a.length ! = b.length) {

    false
  } else {    var equal = 0
    for (i <- Array.range(0, a.length)) {
      equal |= a(i) ^ b(i)
    }
    equal == 0
  }
}Copy the code

This function is used to compare whether two strings are equal or not. If the length of the string is not equal, it is possible to return this function immediately. By xor, 1^1=0, 1^0=1, 0^0=0, if each bit is equal, the two strings must be equal, and the final equal must be 0, otherwise it is 1. But for efficiency’s sake, shouldn’t we be able to return false as soon as we find a 1 in the middle? (as shown below)

for (i <- Array.range(0, a.length)) {  

if (a(i) ^ b(i) ! = 0) // or a(i) ! = b[i] return false

}Copy the code

Combined with the method name safeEquals, you may have seen a lot of efficiency measures related to security, such as delayed computation, but such delayed returns are still rare. This method allows safeEquals(” abcDefghijklmn “, “XBCDEFghijklmn “) to take the same amount of time as safeEquals(” abcDefGhijklmn “,” abcDefGhijklmn “). Prevent brute force cracking of the string to be compared by changing the input a lot and counting the runtime, ignoring attacks on the length of the string to be compared.

For example, if a user sets the password as password, and enumerates the first digit from a to Z, p0000000 will run faster than any of the other digits from a to Z, so you can guess that the first digit of the user’s password is likely to be P. And then iterate over and over and over and finally crack the user’s password. If the password is encrypted using hash, the hashed ciphertext can be obtained using this attack.

Of course, from a theoretical point of view, this is really easy to understand. As mentioned above, there have been papers published in the academic circle that use this timing attack method to crack OpenSSL 0.9.7 RSA encryption algorithm. But is there such an attack problem in practice? Because it doesn’t always feel right to count the elapsed time, which is too sensitive to the environment, network, memory, CPU load, etc. However, the safeEquals approach is also used in various software implementations.

The bug in MessageDigest. IsEqual was fixed in Release Notes in JDK 1.6.0_17.

The change of the diff [source] (http://hg.openjdk.java.net/jdk6/jdk6/jdk/rev/562da0baf70b) for detailed information:

In order to prevent timing attacks (especially those related to signature/password authentication, etc.), various languages provide security comparison functions for response, such as “the world’s best programming language” — PHP:

// Compares two strings using the same time whether they're equal or not.



// This function should be used to mitigate timing attacks; for instance, when testing crypt() password hashes.



bool hash_equals ( string $known_string , string $user_string )



//This function is safe against timing attacks.

boolean password_verify ( string $password , string $hash )Copy the code

All language version is implemented with the version is the same as the above, remove every two strings to xor (^) and or (|), finally, whether the result is 0 to determine whether two strings are equal.

References:

  • Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimension

  • Remote Timing Attacks are Practical

  • Principle of RSA Algorithm

  • Fermat’s Little theorem

Click “Read the original article” for a better experience, including links to related materials. If you think this article has gained you a little bit, please like it below. Please do not hesitate to scan the following TWO-DIMENSIONAL code to follow my public account. If you can help forward it, it will be better. Mua.