context

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. This encryption and decryption using the same rules of encryption is called symmetric encryption algorithm. Then the protection of encryption and decryption rules (referred to as keys) is particularly important, and the risk of transferring keys has always been a hidden danger. Until 1976, two American computer scientists: W.Diffie, Herman (M. Helman) put forward a new idea, which can complete the key exchange without directly transferring the key, creating a new direction of cryptography research. This is the “Diffiermann key exchange” algorithm, which is still a symmetric encryption algorithm, but the key no longer needs to be passed. The switching principle is shown in the figure below:

The original root
Discrete logarithm problem



RSA



Euler’s theorem

For two mutually prime positive integers m and n, m^φ(n) mod n ≡ 1 when M

Another concept to understand based on this is the modular 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. So d is the modulo inverse element of e with respect to x e*d mod x ≡ 1 is the same as e*d ≡ k*x + 1, where k is a positive integer

Knock on the blackboard!! Duang! Duang! Duang! We hit the core algorithm of RSA:

When e is interprime with φ(n), m^(e*d) mod n ≡ m

Chicken is not chicken frozen, can not open the sen! Still a little confused? Never mind, let’s continue:

Suppose we encrypt m to transport encryption: m^e mod n = c, decryption: C ^d mod n = m^(e*d) mod n = m

N + E is the public key in RSA, n+ D is the private key in RSA, and C is the encrypted ciphertext.

Supplement:

  1. N will be very large, typically 1024 bits, but 2048 bits is a safer bet. (The largest integer that humans have decomposed so far, 232 decimal bits, 768 binary bits)
  2. Phi (n) = (p1-1) * (p2-1) = (p1-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, the idea of decrypting RSA to obtain private key D is as follows:

  1. Because e*d = φ(n)*k + 1. E is public, so you have to know φ(n)
  2. To get φ(n), you have to know p1 and p2
  3. And since n is p1 times p2, we have to factor n to figure out p1, p2
  4. If a quantum computer succeeds, the RSA encryption algorithms now used in banks and networks can be broken, and all encryption algorithms derived from the power of factoring large prime numbers can be destroyed.

Later, I will continue to analyze the principles of iOS certificate signature, and at the same time, I will sort out and compare common encryption algorithms, and attach the code implementation of each algorithm in iOS. Welcome to exchange learning experience ~