Overview of cryptography

Cryptography is the technical science of creating and breaking codes. The study of the objective law of cryptography changes, which is applied to the preparation of cryptography to protect the secret of communication, is called cryptography; The application of cracking codes to obtain communication information is called 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 type of encryption is called a 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. Creating a new direction of cryptography research, Asymmetric cryptographic algorithm

Summary of RSA

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.

The mathematics of RSA

Discrete logarithm problem

If you were to design an algorithm that was easy to encrypt and hard to break, what would come to mind? 3xmod17= 123^x \mod 17= 123xmod17=12 The possible value of x is x=16k + 13,k is a positive integer, and there are multiple x’s like that, and there’s no way to tell which one it is

Diffie Hermann key exchange

The euler function

For a positive integer n, how many positive integers less than n are mutually related to n? The first researcher on this problem was called Euler, who was a god-like man, so the solution to this problem is called euler’s function, denoted by φ(n)

For example, φ(8) represents the euler function of computing 8, and the number of mutual prime with 8 is,1,3,5,7, so φ(8) = 4; If φ(7) represents the euler function of computing 7, there are 1,2,3,4,5,6, so φ(7) = 6;

After euler studied this problem, two properties of Euler function were obtained:

  1. If n is prime, then φ(n) = n-1
  2. If A and B are mutually prime, then φ(A * B) = φ(A) * φ(B)

Combining the above two properties, if A, B are prime Numbers, phi (A * B) = phi phi (A) * (B) = (A – 1) * (1 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


m phi ( n ) m o d     n ≡ 1 M ^ {phi (n)} \ mod n \ 1 equiv

For euler’s theorem above, Fermat had a little theorem that if two positive integers m and n are mutually prime, and n is prime, then m to the n-1 minus 1 is divisible by n


m ( n – 1 ) m o d     n ≡ 1 m^{(n – 1)} \mod n \equiv 1

Die inverse element

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, and d is the modulo antielement of e with respect to x


e ∗ d m o d     x ≡ 1 e \ast d \mod x \equiv 1

Combine Euler’s theorem with modular inverse elements

Because ^ 1 k = 1 m phi mod n (n) ≡ 1 m ^ {phi (n)} \ mod n \ equiv phi 1 m (n) modn ≡ 1 mk after both sides k power of phi mod n (n) ≡ 1 m ^ phi (n)} {k \ mod n \ equiv 1 mk phi (n) modn ≡ 1

Since 1 * m = m, multiply both sides by m to get mkφ(n)+1modn≡ mm^{kφ(n) +1} \mod n \equiv MMK φ(n)+1modn≡m

After transforming the modular inverse elements E ∗dmodx≡ 1e \ast d \mod x \equiv 1e∗dmodx≡1, e∗d≡k∗x+1e \ast d \equiv k * x+1e ∗d≡k∗x+1 is obtained

And then you combine these two things


m e ∗ d m o d     n ≡ m m^{e * d} \mod n \equiv m

Among them, m and n are interprime,e and φ(n) are interprime, and d that meets the condition must be found. We can take several examples to verify it

Let m = 3,n = 17,e = 5,m,n mutual prime,e and φ(17) mutual prime,d = 16k+15\frac{16k +1}{5} 516K +1, when k is 4,d is 13, plug into the above equation to verify 35∗13mod 173 ^ {5 * 13} \mod 1735∗13mod17 is determined to equal 3

Try a few more m’s, and n will show that as long as m < n, the above equation will always be true, and mutual prime is no longer needed… As for why, I also don’t understand, it would be good to know, if there is god know, please don’t hesitate to give advice


m e ∗ d m o d     n ≡ m m^{e * d} \mod n \equiv m

At this point, the m < n, e and phi (n) co-prime, d = k ∗ phi (n) + 1 e \ frac {k * phi (n) + 1} {e} ek ∗ phi (n) + 1

RSA Algorithm Description

In fact, after obtaining me∗dmodn≡ mm^{e * d} \mod n \equiv mme∗dmodn≡m, we are very close to the actual use of RSA algorithm, memod N ≡Cm^e \mod n \equiv Cmemodn≡C, this process is called encryption, then find Cdmod nC^d \mod nCdmodn will find the result is still M, this process is called decryption, where the public key is N and E, the private key is N and D, M stands for plaintext, C stands for ciphertext

Description:

  1. N can be very large, typically 1024 bits in length. (The largest integer that humans have decomposed so far, 232 decimal bits, 768 binary bits)
  2. (p1, p2) φ(n) = (P1-1) * (P2-1)
  3. And then we get e and d from φ(n)

A total of 6 numbers are generated: P1, p2, n, φ(n), e, and D. The other 4 numbers are not public except the public key which uses N and E. At present, the way that PI JRSA obtains D is as follows:

  1. To solve the private key d, since e * d = k * φ(n) + 1, we need to know e and φ(n);
  2. E is open, but to get φ(n), you have to know p1 and p2;
  3. Since n is p1 times p2, you have to factor n to figure it out;

RSA terminal drill

Mac terminals can use OpenSSL to run RSA commands. 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.openssl genrsa -out private.pem 1024

  2. Extracting a public key from a private key:openssl rsa -in private.pem -pubout -out public.pemYou can view the contents of the public and private keys

  3. You can also use commandsopenssl rsa -in private.pem -text -out private.txtConvert the private key into text and view the contents

  4. Next we use the public key to encrypt a piece of text:openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txtYou can see that message. TXT has changed from password 123456 to a mess.

  5. Decryption using a private key:openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt

In macOS, we cannot directly use pem files, we need to use der format and P12 format files

  1. The first thing you need is a certificate request file, which those of you who have done iOS development should be familiar withopenssl req -new -key private.pem -out rsacert.csr

  2. When we configure the certificate, we usually use the certificate request file generated above to go to the Apple server to sign the certificate, but now we are just demonstrating, we will sign the certificate ourselves:openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt

  3. Generate a P12 file from a CRT file:openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crtAfter setting and reconfirming the password, you get the P12 file

In fact, in daily development, certificates, we iOS developers directly use these things, basically do not need us iOS development to generate configuration

RSA code walkthrough

In iOS, CRT files cannot be directly used. You need to convert them to der files. Run the following command:

openssl x509 -outform der -in rsacert.crt -out rsacert.der

  1. Load the public and private keysAmong themRSACryptorIs the encapsulated RSA utility class,If you need it, you can download it yourself

  2. encryptionhello worldAnd output the encryption result

  3. The decryption process

Summary of the Hash

A Hash is a Hash algorithm that transforms an input of arbitrary length into an output of fixed length, which is the Hash value. This transformation is a compression mapping, that is, the space of hash values is usually much smaller than the space of input, and different inputs may be hashed into the same output, so it is impossible to determine a unique input value from the hash value. Simply put, it is a function that compresses a message of any length into a message digest of a fixed length

The characteristics of the hash

  1. The algorithm is public
  2. Operation on the same data, the result is the same
  3. Different operations on different data, such as MD5, will result in 128-bit binary by default. The 128-bit binary is usually hard to read, so it is usually displayed in 32-bit hexadecimal.
  4. The hash algorithm cannot be reversed
  5. Information digest, information fingerprint, information ID card, is used to do data identification

The purpose of the hash

  1. The user password is encrypted
  2. Search engine
  3. copyright
  4. A digital signature

Hash Is used to encrypt user passwords

Generally, the plaintext data of the user’s password is not transmitted on the network. Otherwise, when the user’s account password is leaked, it will be investigated for legal responsibility. The reason why there is no password retrieval function in the market is that the user’s password is not stored on the server in plain text.

We first use the simplest way to encrypt the user’s password :(this article is based on iOS platform, and the third party used can be downloaded here)

  1. MD5 is executed for the passwordYou can use terminal to verify the above encryption result is correct, terminal command is as follows:md5 -s "123456"

    You can see that the encryption results are consistent; But there are some websites that record md5 values for common passwords, such as:www.cmd5.com; So the passwords we use, even with MD5 encryption, are too easy to crack… What better way to encrypt it?

  2. MD5 + Salt (an arbitrary string)The result of this encryption will be better than the simple use of MD5 above, but once the salt is leaked, it is easy to crack the password, and the website above can still be very good query out

  3. HMAC encryption scheme takes user registration as an example. When the user enters the account, many apps or websites will let the user check the validity of the account. The server will generate the key corresponding to the account and send it to the client. The client records the key returned by the server locally, encrypts the password entered by the user with HMAC, and sends the encryption result to the server for record and saving. This is considered successful registration! When a user logs in next time, the client searches for the key corresponding to the local account, performs HMAC calculation with the password entered by the user, and sends the key to the server for authentication. In this way, compared with the above method of only adding salt, the safety is higher; When a user logs in to a new device, the client does not have a key corresponding to the account. In this case, the user needs to request the server to obtain the key value before entering the account password. After receiving this request, the server can query whether the device lock is enabled for the current account. If the device lock is enabled, the server asks the device with the key value whether the current device is allowed to log in. If the device does not agree, the new device automatically fails to log in. If the user agrees, the key value corresponding to the account is returned to the requested device, so that the user also has the key required for login on the new device, and then performs HMAC with the password and sends it to the server for login verification. Have you seen it on QQ, wechat and other apps with device locks

  4. HMAC + timestamp After using the above HMAC encryption scheme, password security is indeed much higher; But you can be safer by adding a timestamp; After the user enters the account password and clicks login, the generated HMAC password is used to combine the current time to minutes, such as 202106120112, and the RESULT obtained by MD5 encryption is sent to the server. At this time, the server will use the saved HMAC password to combine the timestamp of the current minute and perform an MD5 to match the result sent by the client. If the result is the same, the login succeeds. If not, then use the previous one minute timestamp, do the MD5 again, and match the result sent by the client (why try the last one minute again, because it is possible to add a minute in the process of sending); In this way, when a user logs in, the password is valid for a maximum of 2 minutes. After 2 minutes, the password is different. Hackers will be confused

Hash is used for search engines

Is mainly used to search, each word in the hash operation after the result is the same, such as Shanghai, iOS, programmers in the baidu search, no matter how to arrange these three words, can search to the same news, because these three words corresponding results after hash value addition, no matter how to arrange, the three words are the same;

Hash for copyright

Baidu cloud when uploading movies, some movies will have the function of second transmission; If the hash value is the same, and you compare some additional information, you can confirm that it’s the same movie, so you don’t need to upload it again; YouTube, for example, hashes and records videos uploaded by users so that each video uploaded by the user has an ID similar to an ID card

Hash Indicates the digital signature of the user

What is a digital signature? Foreigners like to sign their names. There is a bill after using the credit card, and the cardholder needs to sign it. The purpose of signing is to show that what is signed belongs to the signer; Digital signature means signing a string of binary data to identify whose binary data it is Take for example: you buy a commodity of 100 yuan online, your consumption information is sent to the server, the server receives your consumption information, deducts 100 yuan from your account, and then returns the deduction result to the user, this world was so simple; But if there is a malicious hackers in the middle, he tampered with the consumer information you sent to the server, instead of your consumption of 1000 yuan, then the server receives the message, after deduction of 1000 yuan in your account, and will deduct the results back, this time the hackers then returned from the server to your deductions information tampering, tell you successful consumption of 100 yuan, don’t we You realize something’s wrong, and you turn around and you’re missing $900… So the server needs to confirm that the consumption information is sent by you and has not been tampered with by a third party. How do you do that? First use hash to consumer information to get the result of a 128 – bit encryption, and then use the RSA public key to encrypt the results, and then the information consumption, the consumption of RSA public-key encryption hash value information sent to the server, the server after receiving the results, using the RSA private key to decrypt the get a hash value of consumer information, then use the received The consumption information is encrypted with hash. If the two hash values are the same, the consumption information has not been modified by a third party. If the consumption information is different, the consumption information has been modified. The hash value of the consumption information encrypted by RSA is called a digital signature

Symmetric encryption algorithm

Introduction to the

Symmetric encryption (also known as private key encryption) is an encryption algorithm that uses the same key for encryption and decryption. Sometimes called traditional cryptographic algorithm, the encryption key can be calculated from the decryption key, and the decryption key can also be calculated from the encryption key. In most symmetric algorithms, the encryption key and decryption key are the same, so this encryption algorithm is also called secret key algorithm or single key algorithm. It requires the sender and receiver to agree on a key prior to secure communication. The security of symmetric algorithms depends on the key, and leaking the key means that anyone can decrypt the message they send or receive, so the confidentiality of the key is crucial to the security of communication.

The characteristics of

Symmetric encryption algorithm is characterized by open algorithm, small computation, fast encryption speed and high encryption efficiency.

Common symmetric encryption algorithms

DES

Data encryption standards are now used sparingly because of their low strength

3DES

Encrypt the same data three times using three keys

AES

Advanced encryption standards, including Apple’s keychain access, are used by the NATIONAL Security Agency

Application mode

ECB :(Electronic Code Book), Electronic codebook mode, each piece of data is encrypted independently; The most basic encryption mode, that is, commonly understood encryption, the same plaintext will always be encrypted into the same ciphertext, no initial vector, vulnerable to passbook replay attacks, rarely used in general.

CBC :(Cipher Block Chainning) : indicates the Cipher Block link mode. The plaintext is encrypted after xOR operation with the previous ciphertext. Therefore, the same ciphertext will be encrypted after different initial vectors are selected. This is the most widely used ciphertext mode. CBC encrypted ciphertext is context-dependent, but plaintext errors are not passed to subsequent groups, but if one group is lost, all subsequent groups are invalidated (synchronization errors). CBC can effectively ensure the integrity of secret messages. If a data block is lost or changed during transmission, subsequent data cannot be decrypted properly.

There are other modes, but they are not very common, such as Cipher Feedback Mode(CFB) encryption Feedback Mode, and Output Feedback Mode(OFB) Output Feedback Mode

Terminal drill for symmetric encryption

Message. TXT contains the following contents:

The DES algorithm is used for ECB mode encryption, and the key is ABC:openssl enc -des-ecb -K 616263 -nosalt -in message.txt -out msg1.bin

Modify a number in the plaintext

Use the same encryption method to generate the second ciphertext msg2.bin:openssl enc -des-ecb -K 616263 -nosalt -in message.txt -out msg2.bin

Bin and msg2.bin are compared. It is found that only one number is changed in the plaintext, while the whole block of the corresponding ciphertext is changed, which vividly illustrates the principle of ECB mode

Then let’s try CBC mode:

openssl enc -des-cbc -iv 0102030405060708 -K 616263 -nosalt -in message.txt -out msg3.bin

Use CBC mode to generate the msg4.bin file after modifying the plaintext content back to its original appearance

openssl enc -des-cbc -iv 0102030405060708 -K 616263 -nosalt -in message.txt -out msg4.bin

The comparison between MSg3.bin and MSg4.bin shows that after one change in THE CBC mode, the whole of the later changes are changed. The two comparisons clearly illustrate the difference between the ECB mode and THE CBC mode

Code walkthroughs for symmetric encryption

AES algorithm,ECB mode for encryption (EncryptionTools download) Verify the result with the terminal:echo -n hello | openssl enc -aes-128-ecb -K 616263 -nosalt | base64

The AES algorithm is used for encryption in CBC modeTerminal verification result:echo -n hello | openssl enc -aes-128-cbc -K 616263 -nosalt -iv 0102030405060708 | base64 Terminal verification decryption result:echo -n u3W/N816uzFpcg6pZ+kbdg== | base64 -D | openssl enc -aes-128-cbc -K 616263 -iv 0102030405060708 -nosalt -d

The [EncryptionTools sharedEncryptionTools] singleton uses AES by default. If you want to use another algorithm, you can specify [EncryptionTools sharedEncryptionTools].algorithm = <#CCAlgorithm#>

Symmetric encryption function CCCrypt()

    CCCryptorStatus cryptStatus = CCCrypt(kCCEncrypt,
                                          self.algorithm,
                                          option,
                                          cKey,
                                          self.keySize,
                                          cIv,
                                          [data bytes],
                                          [data length],
                                          buffer,
                                          bufferSize,
                                          &encryptedSize);
Copy the code

Parameter 1: kCCEncrypt indicates encryption, and kCCDecrypt indicates decryption. Parameter 2: Encryption algorithm,AES,DES… Parameter 3: Encryption mode :ECB,CBC… Parameter 4: key required for encryption parameter 5: key length parameter 6: iv Initialization vector (required in CBC mode, not required in ECB mode) Parameter 7: encrypted data, that is, plaintext parameter 8: length of encrypted data, plaintext parameter 9: memory address of ciphertext parameter 10: Ciphertext buffer size parameter 11: size of the encryption result

In iOS, symmetric encryption will eventually lead to this function. If someone has some ideas about your APP, they will debug your APP. On this CCCrypt, a symbol breakpoint will be set, and all parameters of this function will be obtained, and the user’s plaintext password will be revealed.The register reads the seventh argument to this functionregister read x6(x0 is the first) clear text data