IOS Reverse (1)- Cryptography (RSA)

To talk about reverse, then certainly not cryptography, because all reverse (attack and defense) is the decryption of encrypted data. So we must initially understand the encryption of what way, after all, know yourself know your enemy, in order to win.

Next, I will talk about cryptography from the following four aspects: 1, what is cryptography 2, RSA mathematics principles 3, RSA terminal commands 4, summary

1. What is cryptography

The history of cryptography can be traced back roughly 2,000 years to the legend that Julius Caesar sent messages in code to prevent enemy interception. What Caesar did was simply to create a table of correspondence for the two dozen Roman letters. In this way, if you do not know the password book, even if the interception of a message can not understand.

For a long time, from the days of Julius Caesar until the 1970s, cryptography evolved very slowly, because designers relied largely on experience. Mathematics is not applied.

Before 1976, all encryption methods followed the same pattern: encryption and decryption used the same algorithm. When exchanging data, the two parties communicating with each other must tell each other the rules, otherwise it cannot be decrypted. Then the encryption and decryption rules (referred to as the key), it is particularly important to protect. Passing the key becomes the biggest problem. This encryption method is called the Symmetric encryption Algorithm.

In 1976, two American computer scientists Diffie (W.Diffie), Herman (M. Helman) put forward a new idea, can not directly transfer the key under the situation, complete the key exchange. This is called the “Diffie Hermann key exchange” algorithm. It opened a new direction of cryptography research.

In 1977, three M.I.T. mathematicians, Ron Rivest, Adi Shamir and Leonard Adleman, devised an algorithm that could implement asymmetric encryption. The algorithm, named after the three of them, is called THE RSA algorithm.

That is to say, “Diffi Hermann key exchange” is a turning point in the history of cryptography.

2. Mathematical principle of RSA

Let’s first use all the formula theorems listed: 1, modular operation 2, Euler function φ 3, Euler’s theorem, Fermat’s little theorem 4, modular elements 5, Duffy Hermann key exchange

1. Modular operation

Complementation and Modulo Operation overlap but not coincide. The main difference is in the division of negative integers. Here are some examples of negative numbers for your understanding: 7 mod 4 =1 (quotient = -1 or -2, -2<-1, -2<-1) 7 mod 4 =1 (quotient = -1 or -2, -2<-1, -2<-1, -2<-1) (1 =1, 1<2, take the quotient =1)

Conclusion: When two integers are complementary, the sign of their values is the sign of the divisor.

2, Euler function φ (read fai, three tones)

φ(n) = φ(A) * φ(B) if n can be decomposed into the product of two prime numbers A and B, then φ(n) = φ(A) * φ(B)

Euler’s theorem, Fermat’s little theorem

First of all here to say, custom is the theorem is proved, how to prove no matter, of course you can also increase to prove, anyway I don’t care (…… & % $%…… & % &… &%), haha

If m and n are positive integers and m and n are mutually prime, then:

If n is prime, then:

Formula conversion:

4. Modular inverse elements

If two positive integers e and x are mutually prime, then the integer D must be found such that e times d minus 1 is divisible by x. So d is the modulo antielement of e with respect to x.

5. Diffie Hermann key exchange

The original root

That process

==> 3^(13 * 15) mod 17 = 3^(13 * 15) mod 17 ((m^e mod n)^d) mod n = m^(e*d) mod n ==> (3^13 mod 17)^13 mod 17 = (3^15 mod 17)^15 mod 17 because 3^13 mod 17 = 12 3^15 mod 17 = 6 ==> 6^13 mod 17 = 12^15 mod 17 = 10Copy the code

set

 m=3  ,e=13  ,d=15  ,n=17  ,C=12
Copy the code

So:

 m^e mod n = c
 c^d mod n = (m^e mod n)^d mod n = m^(e*d) mod n
Copy the code

And because of the modulo inverse element up here, we end up with

 m^(e*d) mod n = m
Copy the code

So the final conclusion is drawn:

m^e mod n = c
c^d  mod n = m
Copy the code

This formula is our final RSA encryption formula!! Among them:

Public key: N and E Private key: N and D Plaintext: m Ciphertext: c D is the modulo inverse element of e to φ(n).Copy the code

1. N can be very large, usually 1024 bits long. (at present, the largest integer that mankind has decomposed, 232 decimal bits, 768 binary bits) 2, because of the need to find φ(n), so according to the characteristics of the Euclidian function, the simplest way n is obtained by multiplying two prime numbers: Prime numbers: p1, P2 φ(n) = (p1-1) * (p2-1) 3, finally from φ(n) get e and D. A total of six numbers are generated: P1, P2, n, φ(n), e, and D

About RSA security: except for the public key which uses N and E, the other four numbers are not public. At present, decrypting RSA to obtain D is as follows: 1. To obtain the private key D. Because e*d = φ(n)k + 1. You know e and φ(n). 2, e is known, but to get φ(n), we must know p1 and p2. 3. Since n=p1p2. You can only figure out if you factor n.

3. Run the RSA terminal command

OpenSSL(open source encryption library) is built into the Mac system, so we can directly use the command on the terminal to play RSA. The common commands in OpenSSL are mainly three:

1. Generate an RSA private key. The key length is 1024 bits

// Generate a 1024bit RSA private key. Openssl genrsa -out private.pem 1024Copy the code

2. Extract the public key from the private key

Openssl rsa -in private.pem -pubout-out public.pemCopy the code

3. Convert the private key to plain text

Openssl rsa -in private.pem -text -out private. TXT cat private. TXTCopy the code

4. Encrypt data with public key and decrypt data with private key

// Create a new file and enter any content in the file. TXT // View the file cat message. TXT // Encrypt the file using the public key openssl rsautl - encrypt-in message. TXT -inkey TXT // Decrypts data using the private key openssl rsautl-decrypt -in enc. TXT -inkey private.pem -out dec.txt // View the encrypted file cat enc. TXT // View the decrypted file cat dec.txtCopy the code

5. Encrypt data with the private key and decrypt data with the public key

TXT -inkey private.pem -out enc_2. TXT // Public key encryption openssl rsautl -verify-in enc_2.txt -inkey public.pem -pubin -out dec_2.txtCopy the code

4. Conclusion:

1. RSA ensures security because it does not use a set of data for encryption and decryption. 3. If quantum computers were ever to become ubiquitous (extremely fast), 1024 bits would no longer be enough to make RSA secure.