preface

At the beginning of this article, we will introduce the knowledge points related to cryptography, which is also for the study of security attack and defense before preparation, only understand the encryption algorithm, you can know how to prevent cracking, is it! This article will begin with a brief introduction to the history of cryptography, and then focus on the RSA encryption algorithm, including the algorithm calculation process.

First, cryptography

What is cryptography?

Cryptography refers to the study of information encryption, crack the technical science of password.

The origins of cryptography date back 2,000 years, and today’s cryptography is mathematically based.

The development history

It is said that Julius Caesar, the ancient Roman general, sent information in code in order to prevent enemy interception. Caesar’s approach is very simple, is to two dozen Roman letters to establish a corresponding table 👇

The picture above is like a cipher book. If you don’t know the cipher book, you can’t understand a message even if it is intercepted. So, there are two problems with the password book 👇

  1. This passwordleak
  2. If the interceptionEnough ciphertextYou can see the frequency of letters, and you can decipher them, and that’s what it’s calledBrute force

For a long time, from the time of Julius Caesar until the 1970s, cryptography was slow to develop because its designers relied largely on experience rather than mathematics. Cryptography today is mathematically based 👇

  • Prior to 1976, all encryption methods followed the same pattern:Encryption and decryptionuseSame algorithm. When exchanging data, the two parties communicating with each other must tell each other the rules, otherwise it cannot be decrypted. So the rules of encryption and decryptionKey (pronounced "month")), its protection is especially important. Passing the key becomes the biggest problem. This encryption method is calledSymmetric Encryption Algorithm
  • In 1976, two American computer scientistsW.Diffie,M. HermanProposed a new idea, can be inThe key is not passed directlyIn the case of completionKey exchange. This is known asDuffy Hermann key exchange algorithm. It opened a new direction of cryptography research.
  • Three MIT mathematicians in 1977Ron Rivest,Adi ShamirandLeonard AdlemanTogether designed an algorithm that could be implementedAsymmetric encryption. The algorithm uses themThree namesNamed, calledRSA algorithm.

Second, the RSA

An encryption algorithm developed in the 1970s. The encryption mode is special and requires two keys: publickey and privatekey. Public key encryption, private key decryption; Encrypt the private key and decrypt the public key. This encryption algorithm is the great RSA.

2.1 Mathematical principles of RSA

2.1.1 Discrete logarithm problem

Why do we talk about discrete logarithms? What does this have to do with encryption and decryption? With such a problem, we look step by step, the ideal encryption and decryption situation should be such that 👉 encryption is simple, decryption is difficult. How can we do this? First let’s look at the mod operation 👇

Mod is the remainder of two numbers x and y.

For example, if we use a prime number 17 as the module (17 is like y), x is a power of 3, and their remainder is 12, what power of 3 is x? 👇

Then we try to write 👇 in order

I get 13. According to the graph above, we can find a rule 👇

3 n mod17 results always between 1 and 16, like a clock 👇

So mod arithmetic is also called clock arithmetic.

So this 3 here is called the original root of 17, and this is 12, and if we go back to n, we have to figure it out all the way, and we have to solve for n by exhaustion. If the modulus gets bigger, then it gets harder to reverse, and that’s the discrete logarithm problem.

2.1.2 Euler function

Euler function concept 👇

Given any positive integer n, how many positive integers <= n form a reciprocal relationship with n?

Mutual relations 👇

If two positive integers have no common factors other than 1, they are said to be coprime.

How many of these values are computed is called the Euler function, denoted by φ(n)(φ pronounced as fai three). For example 👇

  • Compute the Euler function of 8, 1, 3, 5, 7, and 8 mutually

Phi (8) = 4

  • Compute the Euler function of 7, and the mutual 1, 2, 3, 4, 5, 6 of 7

Phi (7) = 6

  • Compute the Euler function of 56

φ(56) = φ(8) * φ(7) = 4 * 6 = 24

Euler function characteristics

1. φ(n)=n-1 when n is prime. If n=A*B 👇 φ(A*B)=φ(A)* φ(B) if n=A*B 👇 φ(A*B)=φ(A)* φ(B)

Based on the above two points:

If N is the product of two relatively prime Numbers P1 and P2, are 👉 phi (N) = phi phi (P1) * (P2) = (P1-1) * (P2)

Euler’s theorem

If two positive integers m and n are mutually prime, then m to the φ(n) minus 1 is divisible by n.

Fermat’s Little theorem

Special case of Euler’s theorem 👉 if two positive integers m and n are mutually prime, and n is prime! So φ(n) is n minus one.

Verify: m = 6, n = 5 (5 is prime) –> 6^4%5 –>24* 24%5 –>24*24

Formula translation

Then we convert the formula 👇

  1. Euler’s theorem 👉 m ^ phi (n) ≡ 1 ^ % n (m) and n co-prime, and 1 ^ ^ k % n ≡ 1, we in the m ^ phi (n) ≡ 1 sides is multiplied by 1 ^ ^ % n k ^ 👇

  1. And we know that 1 times m ≡ m, multiply both sides by m, so 👇

⚠️ Note: Two conditions must be met in this case

  1. M and N are interchangeable
  2. m < n
Die inverse element

If two positive integers e and x are mutually prime, then the integer D must be found such that Ed -1 is divisible by x. So d is the inverse of e with respect to x. The formula is as follows 👇

Assuming the quotient is k, the following formula 👇 can be obtained

When phi (n) = = x, then e * d = k * phi (n) + 1, k * phi (n + 1) familiar with? 👇

Is this equivalent to 👇

Verify: m: 4, n: 15, φ(15) = 8 by modulo inverse element, suppose e: 3, what is d? 8K + 1 = 3d –> d = (8K + 1)/3 -> k= 4 d = 11, k=7 d = 19.

summary

The whole derivation process is shown below 👇

2.1.3 Diffie Hermann key exchange

The figure above shows the data transfer process in combination with the previous example, which is basically divided into the following steps 👇

  1. The service sidetakeRandom number 15(confidential, not telling anyone), 3^15^%17 results obtained(6)Sent to theThe client. The middle three could intercept6
  2. The clientTake a random number13(confidential, don’t tell anyone), 3^13^%17 get12Send to the server. The middle three could intercept12
  3. The clientgetThe service sideSend the6You do 6^13^%17The data of 10
  4. The service sidegetThe clientSend the12You can do 12 to the 15 to the %1710

In this process, the client and server get the same value of 10, and the single intermediate third party intercepts 6 and 12, which is the Diffi Hellman key exchange. What the client and server actually want to exchange is data 10.

The principle of the whole process is shown below 👇

I found the roots of 3 and 17, and that’s when I split.

2.1.4 RSA

The birth of RSA

M ^e*d^ % n ≡ m is split by the Diffi Hellman key exchange, as shown below 👇

  • Encryption: m^e^ % n = c
  • C ^d^ % n = m
  • Public key: N and E
  • Private key: n and D
  • Clear: m
  • Cipher: c

instructions

  1. N is going to be very large, and the length is going to be1024Two bits. (The largest integer that humans have decomposed so far, 232 decimal bits, 768 binary bits)
  2. Because we need to solve φ(n), so according toThe euler functionThe simplest way is to multiply two prime numbers to get 👉 prime numbers p1 and p2 👉 φ (n) = (P1-1) * (P2-1)
  3. And then we get e and d from φ(n).

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. If you want toSo let's figure out the private key D. Due to theE *d = φ(n)*k + 1So you have to knoweandPhi (n)
  2. eYes, but to getPhi (n)Must knowp1 和 p2
  3. Due to then=p1*p2. Only willnYou have to factor it out.

That’s when it’s hard to crack.

2.2 RSA Terminal Commands

Since the Mac system has OpenSSL(open source encryption library) built in, we can directly use commands on the terminal to perform RSA operations. There are three common commands for the RSA algorithm in OpenSSL 👇

  • genrsa👉 Generate and enter oneRsa key
  • rsautl👉 useRsa keyforEncryption, decryption, signature, checkingEtc.
  • rsa👉 processingRsa key format conversionThe problem
The sample
  • The RSA private key is generated. The key length is 1024 bits 👇

openssl genrsa -out private.pem 1024

  • Extract the public key from the private key

openssl rsa -in private.pem -pubout -out public.pem

  • Converts the private key to clear text

openssl rsa -in private.pem -pubout -text -out private.txt

Open private.txt to view 👇

  • Public key encryptionData &Private key to decrypt thedata

Encryption: openssl rsautl -encrypt-in message. TXT -inkey public.pem -pubin-out enc.txt

Decryption: Openssl rsautl-decrypt -in enc.txt -inkey private.pem -out dec.txt

The procedure of the instruction in the figure above 👇

  1. vi message.txtnewmessage.txtFile, press I to enter insert mode, typePassword: LGPerson, press Esc to exit the editing mode, and enter “:wq” to save the configuration and exit
  2. cat message.txt To viewmessage.txt File contents, confirmPassword: LGPersonWriting in the
  3. Using the public keypublic.pemEncrypt and generate an encrypted fileenc.txt
  4. Viewing encrypted Filesenc.txt
  5. Using the private keyprivate.pemDecrypt to generate decrypted filesdec.txt
  6. View decrypted filesdec.txt

Look again at the size of the enc.txt and dec.txt files 👇

Enc. TXT file 128 bytes, Dec. TXT file 16 bytes.

  • In turn, throughThe private key encryptionData &A public key to decryptdata

At this point it becomes signature and validation 👇

Openssl rsautl -sign-in message. TXT -inkey private.pem -out sign.txt

TXT -inkey public.pem -pubin -out verify.txt

The directory for all files generated above is 👇

conclusion

  • Encryption algorithms are mathematical knowledge!
  • Symmetric encryption (traditional encryption algorithm, Key)
  • RSA (name of three people) asymmetric encryption! (Modern encryption algorithms)

    • The original root 👉 3^n^ %17 = 12, find n, 3 is the original root of 17

    • The euler function

      • Given any positive integer n, how many positive integers <= n form a reciprocal relationship with n
      • The characteristics of
        1. whenN is primewhenPhi (n) = n - 1.
        2. If n can be factored intoTwo mutually good integerstheproduct, such asn=A*BthePhi (A * B) = phi phi (A) * (B)

    • Euler’s theorem 👉 If two positive integers m and n are mutually prime, then m to the φ(n) minus 1 is divisible by n

    • Fermat’s little theorem 👉 If two positive integers m and n are mutually prime, and n is prime! So φ(n) = n-1 👉 m^n-1^

    • The modular inverse element 👉 m^(e*d)^ mod n ≡ m

* Diffie Herman key exchangeCopy the code

  • RSA algorithm
    • RSA: Unpicking the product of two (large) prime numbers is hard! So RSA is relatively secure!
    • Encrypt M^e^ mod N = C, decrypt C^d^ mod N = M
    • Cipher C.Clear M.Public keys N and E ， Private keys N and D
    • Conditions (there are 6 numbers!) :
      • NIt’s made up of two big onesPrime numbers (P1, P2)You get!
      • Just for the sake of conveniencePhi (N) 👉 φ(N) = (P1-1) * (P2-1)
      • D 是 ERelative to thePhi (N)theDie inverse element