A Deep Dive into the ECDHE Algorithm

1. Basics of encryption and number theory

Before we formally talk about ECDHE, we need to talk about the RSA algorithm that is closely related to it. ECDHE was born on the premise of optimizing some features of RSA.

1.1 Asymmetric encryption

RSA algorithm is often used in asymmetric encryption. Asymmetric encryption generates a pair of keys. Common usage scenarios are:

  • Public key encryption, private key decryption. This purpose is to Ensure data transmission security, because the content encrypted by the public key cannot be decrypted by others. Only the person holding the private key can decrypt the actual content;
  • Private key encryption, public key decryption. This purpose is to Ensure data authenticity, because the private key cannot be leaked. If the public key can normally decrypt the content encrypted by the private key, it can be proved that the message was sent by the person holding the identity of the private key.

If you want to understand the RSA algorithm, you first need to start with several elementary number theory concepts.

1.2 Prime number

Prime number, also known as prime number, refers to a natural number greater than 1 that cannot be divided by other natural numbers except 1 and the integer itself. For example: 2, 3, 5, 7, 11, 13, 17, 19... And there are infinitely many prime numbers, and there are 6 ways to prove them (respectively) Euclidean method, Hermitian method, Goldbach method, Furstenberg method, Philip method), among which Euclidean method is the most classic. For the demonstration process, please refer to Volume 9 of "Elements of Geometry".

1.3 Modulo operation

Modular operation: That is, Remainder operation, which refers to dividing one number by another number. The remainder is the remainder, which is the result of finding the remainder.

Congruence: When two integers are divided by the same positive integer, if they get the same remainder, then the two integers are congruent. Suppose two integers a, b, if the remainders obtained by dividing them by a positive integer m are equal, then a and b are said to be congruent modulo m, recorded as:

a≡b(modm)a \equiv b \pmod{m}

Is read as: a is congruent with b modulo m, or, a and b are congruent with respect to modulo m. For example:

26≡14(mod12)26 \equiv 14 \pmod{12}

1.4 Mutual prime relationship

If two positive integers have no other common factor except 1, these two numbers are said to be coprime. For example, 15 and 32 have no common factors, so they are coprime. This shows that Non-prime numbers can also be coprime.

According to the mutual prime relationship, the conclusion can be deduced:

  • Any two prime numbers form a mutually prime relationship, such as 13 and 61.
  • If one number is a prime number, and the other number is not a multiple of the former, the two form a mutually prime relationship., such as 3 and 10.
  • If the larger number among two numbers is a prime number, then the two form a mutually prime relationship, such as 97 and 57.
  • 1 And any natural number are mutually prime., such as 1 and 99.
  • p is an integer greater than 1, then p and p-1 form a mutually prime relationship, such as 57 and 56.
  • p is an odd number greater than 1, then p and p-2 form a mutually prime relationship, such as 17 and 15.

1.5 Euler's totient function

Verification: Given any positive integer n, among the positive integers less than or equal to n, how many are in a coprime relationship with n?

The method of calculating the number of mutually prime relationships is called Euler's totient function, represented by φ(n). For example, among 1 to 8, the ones that form a mutually prime relationship with 8 are 1, 3, 5, and 7, then φ(n) = 4. Euler's totient function is divided into 5 situations:

Case 1: If n=1, then φ(1) = 1.

Because 1 forms a mutually prime relationship with any number (including itself).

Case 2: If n is a prime number, then φ(n) = n-1.

Because a prime number forms a mutually prime relationship with every number less than it. For example, 5 and 1, 2, 3, and 4 all form a mutually prime relationship.

Case 3: If n is a certain power of prime number p, that is, n = p^k (p is a prime number, k is an integer greater than or equal to 1), then

ϕ(pk)=pk−pk−1\phi(p^{k})=p^{k}-p^{k-1}

This is because a number can be relatively prime with n only if it does not contain a prime number p. There are a total of p^(k-1) numbers containing the prime number p, that is, 1×p, 2×p, 3×p,..., p^(k-1)×p. After removing them, the remaining numbers are the numbers that are relatively prime to n. For example

ϕ(8)=ϕ(23)=23−22\phi(8)=\phi(2^{3})=2^{3}-2^{2}

The above formula can also be written in the following form:

ϕ(pk)=pk−pk−1=pk(1−1p)\phi(p^{k})=p^{k}-p^{k-1}=p^{k}(1-\frac{1}{p} )

It can be seen that the above Case 2 is a special case when k=1.

Case 4: If n can be decomposed into the product of two relatively prime integers, n = p1 × p2, then

ϕ(n)=ϕ(p1p2)=ϕ(p1)ϕ(p2)\phi(n)=\phi(p1p2)=\phi(p1)\phi(p2)

That is, the Euler's totient function of the product is equal to the product of the Euler's totient function of each factor. For example

ϕ(56)=ϕ(8×7)=ϕ(8)ϕ(7)=4x6=24\phi(56)=\phi(8×7)=\phi(8)\phi(7)=4x6=24

For specific proof, please refer to "Chinese Remainder Theorem".

Scenario 5:

Because any positive integer greater than 1 can be written as the product of a series of prime numbers.

n=p1k1p2k2...prkrn=p_{1}^{k1}p_{2}^{k2}...p_{r}^{kr}

According to the conclusion of Case 4, we get

ϕ(n)=ϕ(p1k1)ϕ(p2k2)...ϕ(prkr)\phi(n)=\phi(p_{1}^{k1})\phi(p_{2}^{k2})...\phi(p_{r}^{kr})

Then based on the conclusion of Case three, we get

ϕ(n)=ϕ(p1k1)ϕ(p2k2)...ϕ(prkr)(1−1p1)(1−1p2)...(1−1pr)\phi(n)=\phi(p_{1}^{k1})\phi(p_{2}^{k2})...\phi(p_{r}^{kr})(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{r}})

Which is equivalent to

ϕ(n)=n(1−1p1)(1−1p2)...(1−1pr)\phi(n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{r}})

The above is Universal calculation formula for Euler's totient function.

1.6 Euler’s Theorem

If two positive integers a and n are relatively prime, then Euler's totient function φ(n) of n can make the following equation hold:

aϕ(n)≡1(modn)a^{\phi (n)} \equiv 1 \pmod{n}

In other words, the remainder when a raised to the power of φ(n) is divided by n is 1. In other words, a raised to the power of φ(n) minus 1 can be divisible by n. This is the famous Euler’s theorem.

For example, 3 and 7 are relatively prime, and Euler's totient function φ(7) of 7 is equal to 6, so 3 raised to the sixth power (729) minus 1 can be divisible by 7 (728/7=104).

Euler's theorem can greatly simplify certain operations. For example, 7 and 10 are relatively prime. According to Euler’s theorem,

7ϕ(10)≡1(mod10)7^{\phi (10)} \equiv 1 \pmod{10}

It is known that φ(10) is equal to 4, so the single digit of 7 raised to the fourth power must be 1.

7ϕ(4k)≡1(mod10)7^{\phi (4k)} \equiv 1 \pmod{10}

Therefore, mental arithmetic can calculate the single digit number of any power of 7 (for example, 7 raised to the power of 222).

Euler’s theorem has a special case:

Assume that the positive integer a and the prime number p are relatively prime, because φ( p ) of the prime number p is equal to p-1, then Euler’s theorem can be written as

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

This is the famous Fermat’s Little Theorem. It is a special case of Euler's theorem.

Euler’s theorem is the core of the RSA algorithm. Once you understand this theorem, you can understand RSA.

1.7 Modular Multiplicative Inverse

If two positive integers a and n are relatively prime, then the integer b can be found so that ab-1 is divisible by n, or the remainder of ab divided by n is 1.

ab≡1(modn)ab \equiv 1 \pmod{n}

At this time, b is called a’s “Modular Multiplicative Inverse”.

For example, 3 and 11 are relatively prime, then the Modular Multiplicative Inverse of 3 is 4, because (3 × 4)-1 can be divided by 11. Obviously, there is more than one Modular Multiplicative Inverse. The integer multiples of 4 plus or minus 11 are all Modular Multiplicative Inverse {…,-18,-7, 4, 15, 26,…} of 3, that is:

If b is the Modular Multiplicative Inverse of a, then b+kn are all Modular Multiplicative Inverse of a.

Euler’s theorem can be used to prove that Modular Multiplicative Inverse must exist.

aϕ(n)=a∗aϕ(n)−1≡1(modn)a^{\phi (n)}=a * a^{\phi (n)-1} \equiv 1 \pmod{n}

You can see that the φ(n)-1 power of a is the Modular Multiplicative Inverse of a.

2. Starting from RSA

After popularizing the above number theory theorem, the details of the RSA algorithm will be officially launched.

2.1 RSA simple mathematical model

Assuming that Smallfan wants to use the RSA algorithm for encrypted communication with Jenning, then he needs to generate the public key and private key as follows:

The first step is to randomly select two unequal prime numbers p and q.

Suppose 3 and 11 are selected. (In practical applications, the larger the two prime numbers, the more difficult it is to crack.)

The second step is to calculate the product n of p and q.

n=3∗11=33n = 3*11 = 33

n is the key length. 33 written in binary is 100001. There are 6 digits in total, so the key is 6 digits. In practical applications, the RSA key is generally 1024 bits, and in important cases it is 2048 bits.

The third step is to calculate Euler's totient function φ(n) of n.

1
2
3
4
5
∵ n is a prime number, which can be known according to Euler's Totient Function
φ(n) = n-1
n = p1 × p2
φ(n) = φ(p1p2) = φ(p1)φ(p2)
∴ φ(n) = (p-1)(q-1)
ϕ(33)=2∗10=20\phi (33)=2 * 10 = 20

The fourth step is to randomly select an integer e, the condition is 1< e < φ(n), and e and φ(n) are relatively prime.

Suppose between 1 and 20, 17 is randomly selected.

The fifth step is to calculate the modular multiplicative inverse of e for φ(n).

The so-called "Modular Multiplicative Inverse" means: there is an integer d that can make the remainder of ed divided by φ(n) equal to 1.

ed≡1(modϕ(n))ed \equiv 1 \pmod{\phi(n)}

This formula is equivalent to

ed−1=kϕ(n)ed - 1 = k\phi(n)

So, finding modular multiplicative inverse is essentially solving the following linear equation of two variables. (-k = y)

ex+ϕ(n)y=1ex + \phi(n)y = 1

It is known that e=17, φ(n)=20,

17x+20y=117x + 20y = 1

According to "Extended Euclidean Algorithm", the integer solution is (x, y) = (-7, 6), that is, d = -7.

The sixth step is to encapsulate n and e into public keys, and encapsulate n and d into private keys.

n=20, e=17, d=-7, so the public key is (20, 17) and the private key is (20, -7).

Note: In actual applications, the data of public key and private key are expressed in ASN.1 format.

2.2 Encryption and decryption

2.2.1 Encryption

Back to the above scenario, assuming Jenning wants to send encrypted information m to Smallfan, she will encrypt m using the public key (n, e) given by Smallfan. It should be noted here that m must be an integer (the string can take an ascii value or unicode value), and m must be less than n.

The so-called "encryption" is to calculate c of the following formula:

me≡c(modn)m^{e} \equiv c \pmod{n}

Smallfan’s public key is (20, 17), assuming m is 2, then the following equation can be calculated:

217≡12(mod20)2^{17} \equiv 12 \pmod{20}

So, c equals 12, Jenning sent 12 to Smallfan.

2.2.2 Decryption

Smallfan gets the 12 sent by Jenning and uses his own private key (20, -7) to decrypt it. It can be proved that the following equation must hold:

cd≡m(modn)c^{d} \equiv m \pmod{n}

In other words, the remainder when c raised to the power of d divided by n is m. Now, c = 12, the private key is (20, -7), then

12−7≡2(mod20)12^{-7} \equiv 2 \pmod{20}

Therefore, the original text before encryption is 2.

At this point, the entire process of "encryption-decryption" is completed.

For the specific verification process, please refer to Teacher Ruan’s RSA algorithm principle (2)

2.2.3 Long content encryption

Public key (n, e) can only encrypt integers m less than n, so what should you do if you want to encrypt integers greater than n? There are two solutions:

  1. Divide the long message into several short messages, and encrypt each segment separately;
  2. First select a "symmetric encryption algorithm" (such as DES), use the key of this algorithm to encrypt the information, and then use the RSA public key to encrypt the DES key.

2.3 Reliability Analysis

Reviewing the key generation steps above, there are six numbers in total:

1
2
3
4
5
Two randomly generated prime numbers p and q
The product n of p and q
Euler's Totient Functionφ(n)
A randomly generated integer e in the interval 1-φ(n) that is relatively prime to φ(n)
e

Among these six numbers, two (n and e) are used in the public key, and the remaining four numbers are not public. The most critical one is d, because n and d constitute the private key. Once d is leaked, it means the private key is leaked.

Make a hypothesis: Can d be deduced when n and e are known?

1
2
3
∵ ed≡1 (mod φ(n)). ∴ Only by knowing e and φ(n) can we calculate d.
∵ φ(n) = (p-1)(q-1). ∴ Only by knowing p and q can we calculate φ(n).
∵ n = pq. ∴ Factor n to find p and q.

Conclusion: If n can be factored, d can be calculated, which means the private key has been cracked.

For example, you can factor 33 (3×11), but It’s hard factor the following larger integers.

1
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

It is equal to the product of two prime numbers like this:

1
2
3
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

Note: As of 2023, the industry generally believes that RSA 1024 is already generally unsafe. According to the current computing power model, it will be cracked soon in our lifetime, and the introduction of quantum computers will undoubtedly accelerate all this.

Currently there are different computing power models, so the prediction results given under each model are different, but generally speaking, it is basically believed that 1024bit RSA is no longer suitable for use.

  • Lenstra/Verheul model concluded that 1007-1028bit RSA became unsafe around 2002-2006.
  • ECRYPT-CSA model concludes that 1024bit RSA becomes unsafe around 2010-2017.
  • NIST model considers 1024bit RSA to be insecure after 2016.
  • ANSSI model believes that 2048bit RSA will become insecure around 2014-2020.
  • BSI model believes that 2000bit RSA will become insecure around 2018-2022.

The conclusions of different computing power models can be found on the website keylength.com/en/.

2.4 Forward secrecy problem

As mentioned in the reliability analysis section, the possibility of brute force cracking of RSA is currently high. In addition, in actual HTTPS application scenarios, private keys are often stored on the server side. Developers, operation and maintenance personnel who hold private keys may intentionally or unintentionally cause the leakage of private keys. Once the private key of the server is leaked, all TLS communication ciphertext intercepted by third parties in the past will be cracked. This is The biggest flaw of RSA: does not have forward secrecy.

To this end, HTTPS gradually transitions to adopt a private key negotiation method of ephemeral, secure, and decentralized, which is the focus of this article: ECDHE algorithm.

3. discrete logarithm

3.1 Basic theorem

ECDHE key agreement algorithm is an evolution of the DH algorithm, which is based on discrete logarithm.

Discrete logarithm is a combination of two mathematical concepts of "discrete + logarithm". The value of logarithmic operation can be continuous, but the value of discrete logarithm cannot be continuous, so it is also named "discrete". discrete logarithm adds "modulo operation" on the basis of logarithmic operation, which means taking the remainder.

If for an integer b and a primitive root a of a prime number p, a unique exponent i can be found such that:

ai mod p=ba^{i} \bmod{p} = b

Then the index i is called the discrete logarithm of b modulo p with base a as the base.

3.2 Clarification of modulus P

The base a and the modulus p are public parameters of discrete logarithm, that is to say, they are public, b is a real number, and i is a logarithm. Once you know the logarithm, you can use the formula above to calculate the true number. But conversely, knowing the real number makes it difficult to derive the logarithm.

According to the proof part of Euler's theorem, it can be seen that when the modulus p is a large number, even if the base a and the real number b are known, it is difficult to calculate the discrete logarithm with the current computing level. This is the mathematical basis of the DH algorithm.

For information on prime factorization and reverse derivation of logarithms from real numbers, you can read Chapter 7 of this article.

4. DH and DHE algorithms

4.1 Symmetric key generation based on DH

Assume that Jenning and Smallfan agree to use the DH algorithm to exchange keys. Based on discrete logarithm, Jenning and Smallfan need to first determine the modulus P and the base G as the parameters of the algorithm. These two parameters are public.

Then Jenning and Smallfan each generate a random integer as Private key. The private keys of both parties must be strictly kept and cannot be leaked. Jenning's private key is represented by a, and Smallfan's private key is represented by b.

Now Jenning and Smallfan both have P and G and their respective private keys, so they can calculate Public key:

  • Jenning’s public key is denoted as A,
A=Ga mod pA = G^{a} \bmod{p}
  • Smallfan is denoted as B,
B=Gb mod pB = G^{b} \bmod{p}

A and B are also public because according to the principle of discrete logarithm, it is very difficult to calculate the logarithms a and b backward from the real numbers (A and B).

After both parties exchange their respective DH public keys, the holding status of both parties is as follows:

1
2
Jenning has 5 numbers in hand: P, G, a, A, B
Smallfan also has 5 numbers in his hand: P, G, b, A, B

Then Jenning performs the operation:

K1=Ba mod pK_{1} = B^{a} \bmod{p}

Smallfan performs the operation:

K2=Ab mod pK_{2} = A^{b} \bmod{p}

Because the power operation of discrete logarithm has commutative law, the result obtained by Smallfan is also K, that is:

K=Ab mod p=(ga mod p)b mod p=gab mod p=(gb mod p)a mod p=Ba mod pK = A^{b} \bmod{p} = (g^{a} \bmod{p})^{b} \bmod{p} = g^{ab} \bmod{p} = (g^{b} \bmod{p})^{a} \bmod{p} = B^{a} \bmod{p}

This K is the symmetric encryption key used between Jenning and Smallfan, which can be used as a session key. This is also

It can be seen that during the entire key agreement process, Jenning and Smallfan disclosed 4 pieces of information: P, G, A, and B, where P and G are the parameters of the algorithm, A and B are public keys, and a and b are the private keys kept by both parties. The attacker cannot obtain these two private keys, so the attacker can only start from the public P, G, A, and B to calculate the discrete logarithm (private key).

Question: Why did Jenning and Smallfan calculate public key=G^private key mod p instead of public key=G^private key?

4.2 Comparison with RSA

RSA’s solution is: public key encryption and private key decryption. In DH key exchange, both parties generate the same key. That is: Shared Key. Although it is called key exchange in name, in fact, the two parties do not actually exchange keys, but generate an identical shared key through calculation. Therefore, a more accurate name should be Diffie-HellmanKey Agreement.

4.3 Sensitive private key

After the birth of DH, the static DH algorithm is commonly used. The so-called static means that the private key of one party is static. It is precisely because of this feature that once the private key is leaked, the DH algorithm Does not have forward secrecy, so the DH algorithm has been abandoned at present;

4.4 DHE algorithm

Since in the static DH algorithm, one party is fixed and the other is temporarily generated, so it is not safe to use a method where both parties are not fixed and the private keys of both communicating parties are temporarily generated. This DH algorithm is called the DHE algorithm (E stands for Ephemeral, temporary). The DHE algorithm is based on the DH algorithm and the generation process will not be described in detail.

5. ECDHE principle

5.1 ECC algorithm

5.1.1 Performance issues that need to be resolved urgently

Since the DHE algorithm needs to generate the base G and the modulus P each time, and perform multi-order operations on G, that is, multiplication operations, the load on the CPU is very large in the HTTPS high-concurrency communication scenario, so Using elliptic curve (ECC) DH (Diffie-Hellman) algorithm (referred to as ECDHE algorithm) To understand the ECDHE algorithm, you first need to understand elliptic curve encryption algorithm (ECC).

5.1.2 What is ECC

ECC is the abbreviation of Elliptic Curve Cryptography (elliptic curveCryptography). It is a public key encryption algorithm based on elliptic curve mathematics. Its essence is to use the discrete logarithm problem to achieve encryption. The main advantage of ECC is to provide faster performance and a higher level of security while using smaller keys.

5.1.3 What is elliptic curve

Wolfram MathWorld gives a very precise definition:
An elliptic curve is a set of points defined by y^2 = x^3 + ax + b and satisfying 4a^3 + 27b^2 ≠ 0.
4a^3 + 27b^2 ≠ 0 This restriction is to ensure that the curve does not contain singular points (in mathematics, it means that there is a tangent line at any point on the curve).

Example elliptic curve:

5.1.4 Discrete logarithm problem

The discrete logarithm problem was mentioned in the previous article, and it was explained that the RSA algorithm is based on the prime factorization of large numbers, that is, it encrypts the feature that it is easy to multiply two prime numbers, but it is difficult to decompose their composite numbers.

The ECC algorithm defines the formula in finite fieldFp: Q=kP. When the large number k and point P are known, it is easy to find point Q. However, it is difficult to find k when point P and point Q are known. The ECC algorithm also uses discrete logarithm are used for encryption. Point Q is the public key, the large number k is the private key, and point P is the base point. The biggest practical difference from RSA is mainly the key length.

5.1.5 Principle of elliptic curve encryption algorithm

Describes an elliptic curve on Fp. Six parameters are commonly used: T=(p, a, b, n, x, y).
(p, a, b) is used to determine an elliptic curve. p is the number of points in the prime field, a and b are the two large numbers within it;
x, y are the coordinates of the base point of G, which are also two large numbers;
n is the order of the base point of point G;
The above six quantities can describe an elliptic curve, and sometimes we also use h(elliptic The integer part of dividing the number p of all points on the curve by n).

Now we describe a process of encrypted communication using elliptic curve:

  1. Select an elliptic curve Ep(a, b) and take a point on the elliptic curve as the base point P.
  2. Choose a large number k as the private key and generate the public key Q=kP.
  3. Transmit Ep(a, b) and points Q and P to the user.
  4. After receiving the information, the user encodes the plaintext to be transmitted to a point M on Ep(a, b), and generates a random integer r.
  5. Public key encryption (ciphertext C is a point pair): C={rP, M+rQ}
  6. Private key decryption (M + rQ - k(rP), the decryption result is point M), the formula is as follows:
1
M + rQ - k(rP) = M + r(kP) - k(rP) = M
  1. Decode point M to get the plaintext.

Suppose there is a third party H during the encryption process. H can only know the elliptic curve Ep(a, b), the public key Q, the base point P, and the ciphertext point C. However, it is very difficult to find the private key k through the public key Q and the base point P or to find the random number r through the ciphertext point C and the base point P. Therefore, the security of data transmission can be guaranteed.

About elliptic curve and abelian group.

5.2 Key agreement based on ECDHE

ECDHE algorithm takes advantage of the ECC elliptic curve characteristics based on the DHE algorithm, and can calculate the public key and final session key with less calculation.

Jenning and Smallfan’s process for using the ECDHE key exchange algorithm:

  • Both parties have decided in advance which elliptic curve to use and the base point G on the curve. Both parameters are public;
  • Each party randomly generates a random number as Private key d, and multiplies it with the base point G to obtain Public Key Q (Q = dG). At this time, Jenning’s public and private keys are Q1 and d1, and Smallfan’s public and private keys are Q2 and d2;
  • Both parties exchange their respective public keys. Finally, Jenning’s calculation point (x1, y1) = d1Q2, Smallfan’s calculation point (x2, y2) = d2Q1. Since the elliptic curve can satisfy the multiplicative commutative and associative laws, d1Q2 = d1d2G = d2d1G = d2Q1, so The x-coordinates of both parties are the same, so it is a shared key, which is the session key.

In this process, the private keys of both parties are randomly and temporarily generated, and are not public. Even based on the public information (elliptic curve, public key, base point G), it is difficult to calculate the discrete logarithm (private key) on the elliptic curve.

6. TLS based on ECDHE

6.1 Why ECDHE

The core purpose of the TLS handshake is key exchange. The server and the client "negotiate" to obtain the master key (the so-called "negotiation" means exchanging several random numbers with each other. You say a number, I say a number, and finally calculate a result based on everyone's numbers).

Regardless of RSA or ECDHE, the final formula for calculating the master key is the same:

1
Client Random + Server Random + pre-master = master secret

The first two random numbers are completely clear text, and the key to confidentiality lies in pre-master.

  • In RSA, pre-master is simply generated by the client. It is encrypted by the server’s public key and sent to the server. The server uses the private key to decrypt it and obtain it. pre-master. Once the server's private key is compromised, the master key can be calculated by the attacker, and the past master key can be leaked (RSA does not have "forward security").

  • In ECDHE, the server generates an "elliptic curve public key" Server Params, corresponding to A in the formula, encrypts it with the private key and sends it to the client; the client also generates an "elliptic curve public key" Client Params, corresponding to B in the formula, uses the server's public key to encrypt it and sends it to the server; and the private keys a and b are kept by the server and the client respectively. Then the client and server calculate locally pre-master:

1
2
On the client: A ^ b % P = Server Params ^ b % P = pre-master
On the server: B ^ a % P = Client Params ^ a % P = pre-master

It can be seen that in ECDHE, even if the server's private key is cracked, all you get is the Client Params sent by the client. Without the private keys a and b of the elliptic curve, it is impossible to calculate pre-master.

Even if the attacker has powerful computing power and can further crack the private key of the elliptic curve, the server and client use the elliptic curve to randomly generate the private key in each key agreement, so the ECDHE algorithm has forward secrecy.

6.2 Four-Message Handshake

6.2.1 TLS first handshake

The client will first send a "Client Hello" message, which contains the TLS version number used by the client, the supported cipher suite list, and the generated Random number (Client Random).

6.2.2 TLS second handshake

The server receives the client's "hello" and also returns a "Server Hello" message. The message contains the TLS version number confirmed by the server and a Random number (Server Random). Then it selects a suitable cipher suite from the client's cipher suite list. At this time, the key agreement algorithm is selected. ECDHE.

Then, in order to prove its identity, the server sends the "Certificate" message, and the certificate is also sent to the client.

Note: This step is very different from the RSA handshake process: because the server selects the ECDHE key agreement algorithm, it will send "Server Key Exchange" message.

This process server does three things:

  1. Select the corresponding elliptic curve. The selected elliptic curve is equivalent to the base point G of the elliptic curve. It is also determined. These will be disclosed to the client;
  2. Generate a random number as the private key of the server-side elliptic curve and keep it locally;
  3. Calculate the server’s elliptic curve public key based on the base point G and the private key, which will be disclosed to the client.

In order to ensure that the public key of this elliptic curve is not tampered with by a third party, the server will use the RSA signature algorithm to sign the elliptic curve public key of the server.

Then, there is the "Server Hello Done" message. The server and the client indicate: "This is the information I provided, and the greeting is complete."

At this point, the two TLS handshakes have been completed. Currently, the client and server share this information through plain text: Client Random, Server Random, elliptic curve used, elliptic curve base point G, The public key of the server-side elliptic curve, this information is very important and is the material for subsequent generation of session key.

6.2.3 TLS third handshake

After receiving the certificate from the server, the client verifies the authenticity of the certificate through CA certificate chain and generates a random number as the private key of the client's elliptic curve. Then it generates the client's elliptic curve public key based on the information previously provided by the server, and then sends it to the server with the "Client Key Exchange" message.

At this point, both parties have the other party’s elliptic curve public key, their own elliptic curve private key, and the elliptic curve base point G. Therefore, both parties calculate the point (x, y), where the x coordinate value is the same for both parties. When we talked about the ECDHE algorithm earlier, we said that x is the session key, But in actual application, x is not the final session key.

The final session key is generated using three materials: "Client random number + Server random number + x (shared key calculated by ECDHE algorithm)".

The reason why is so troublesome is because the TLS designers do not trust the reliability of the "pseudo-random numbers" on the client or server. In order to ensure true complete randomness, three unreliable random numbers are mixed together to increase the degree of "randomness".

Then, the client will send the "Encrypted Handshake Message" message, make a summary of the previously sent data, and then encrypt it with the symmetric key, allowing the server to verify whether the symmetric key generated this time can be used normally.

6.2.4 TLS Four-Message Handshake

Finally, the server will perform the same operation and send "Change Cipher Spec" and "Encrypted Handshake Message" messages. If both parties verify that the encryption and decryption are OK, the handshake is officially completed and the encrypted sending and receiving phase is entered.

6.3 Performance

Using ECDHE, the client can actually send encrypted HTTP data before the TLS Four-Message Handshake. However, for the RSA handshake process, the TLS Four-Message Handshake must be completed before application data can be transmitted.

ECDHE saves a message round-trip time compared to the RSA handshake process. This is a bit of a "jump start". It is called "TLS False Start", which is similar to "TCP Fast Open". The application data is sent before the connection is fully established, which improves the efficiency of transmission.

6.3.1 Understanding TLS False Start

Let’s look at HTTP first. In the least ideal situation, a normal HTTP to reach TTFB (Time To First Byte) needs to go through the following process: 1 DNS query RT, 1 TCP handshake RT, and at least one HTTP request and response RT. We assume that the RTT between the client and the server is 50ms (50ms is also the delay value of the Chinese network from south to north). We do not consider DNS here, so under this assumption, it takes 100ms for HTTP to reach the TTFB.

Let’s look at the HTTPS process again. Compared to HTTP, HTTPS has two more RTTs for negotiating the TLS tunnel (time factors such as encryption and decryption calculations and OCSP are ignored here). DNS is also not considered. Under this assumption, it takes 200ms for HTTPS to reach TTTFB.

It can be seen that the communication time of HTTPS is exactly twice that of HTTP, which is also one of the important reasons why HTTPS is considered slow.

Just imagine, if you can reduce the RT of the HTTPS communication process and increase the time from 200ms to 150ms, it will directly reduce the time consumption by 1/4. This is obvious for the performance improvement and bandwidth saving of high-concurrency and high-load servers.

Of course there is a way.

TLS False Start is an optimization method proposed by Google. Its approach is: in the second phase of TLS negotiation, after the client sends ChangeCipherSpec and Finished, it immediately sends encrypted application layer data without waiting for confirmation from the server.

The following figure shows the HTTPS communication process after enabling TLS False Start.

6.3.2 Comparison with RSA

TLS version 1.2 uses the RSA key exchange algorithm, which requires 4 handshakes, which means it costs 2 RTT, before application data can be transmitted.

So if possible, try to use the ECDHE key exchange algorithm (used in TLS version 1.3) to replace the RSA algorithm, because this algorithm supports "TLS False Start", the client can send encrypted application data after the third handshake and before the fourth handshake of the TLS protocol, thereby reducing the TLS handshake message round trip reduced from 2 RTT to 1 RTT.

ECDHE algorithm is implemented based on elliptic curve. Different elliptic curves have different performances. You should try to choose x25519 Curve. This curve is currently the fastest elliptic curve.

6.3.3 TLS 1.3 Optimization

In summary, if possible, directly upgrade TLS 1.2 to TLS 1.3. TLS 1.3 greatly simplifies the handshake steps. It only takes 1 RTT to complete the TLS handshake, and it is more secure.

In the TLS 1.2 handshake, 4 handshakes are generally required. First, the encryption algorithm to be used is negotiated through the Client Hello (1st handshake) and Server Hello (2nd handshake) messages, and then the public keys are exchanged (3rd and 4th handshake), and then the final session key is calculated. The left part of the figure below is the TLS 1.2 handshake process:

The right part of the above picture is the handshake process of TLS 1.3. It can be seen that TLS 1.3 merges the two messages Hello and public key exchange into one message, thus reducing it to only 1 RTT to complete the TLS handshake.

The specific method is:

  • The client brings the supported elliptic curves and the public keys corresponding to these elliptic curves in the Client Hello message.
  • After receiving the message, the server selects an elliptic curve and other parameters, and then returns the message with the public key of the server. After this RTT, both parties already have the materials to generate the session key, so the client can calculate the session key and encrypt the application data for transmission.

Also note: TLS 1.3 abolishes the RSA and DH algorithms that do not support forward secrecy, and only supports the ECDHE algorithm.

7. Let’s talk about quantum computing again

7.1 Imagination of the past

Many people worry that quantum computers will be able to crack some of the encryption codes used to send secure messages. The so-called encryption code encrypts data using a "trapdoor" function, which is very easy to execute in one direction, but not in the opposite direction (prime factorization, discrete logarithm). This makes it easy to encrypt data, but very difficult to decode it without the help of a special key.

These encryption systems have never been unbreakable. Instead, their security is demonstrated by the large amount of time it takes a classical computer to complete the decoding. Modern encryption methods are specifically designed to take a long time to decode, making them virtually unbreakable.

But quantum computers change that thinking. Quantum computers are much more powerful than conventional computers and should be able to crack these codes with ease.

This raises an important question – when will quantum computers be powerful enough to do this? After that, all information protected by this form of encryption will become insecure.

So computer scientists are trying to figure out the resources that might be needed to build such a quantum computer, and how long it would take to build such a machine. The previous answer was always decades.

7.2 The terrifying science of quantum computing

Back in 1994, American mathematician Peter Shor discovered a quantum algorithm that outperformed classical algorithms. Shor's algorithm has a large factor and is a key factor in cracking passwords based on trapdoor functions.

The trapdoor function is based on a multiplication process, which is easy to perform in one direction but difficult to perform in the opposite direction. For example, multiplying two numbers is simple: 593 times 829 equals 491, 597. But it is difficult to figure out which two prime numbers must be multiplied to get 491, 597.

As the number increases, the calculation becomes increasingly difficult. In fact, computer scientists believe it is nearly impossible for a classical computer to factor out numbers larger than 2048 bits, the most commonly used base form of RSA encryption. For specific benchmarks, please refer to Quantum computer can break 2048-bit RSA encryption in 8 hours, which will not be expanded upon in this article.

Shor showed that a sufficiently powerful quantum computer could easily do this, a result that sent shockwaves throughout the security industry.

Since then, quantum computers have continued to become more powerful. In 2012, physicists used a four-qubit quantum computer to factor 143. Then in 2014, they used similar equipment to break out 56153.

In 2019, a research report by Craig Gidney of Google and Martin Ekera of KTH Royal Institute of Technology in Stockholm, Sweden [How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits] showed that this answer needs to be revised. Gidney and Ekera have shown how a quantum computer can perform calculations using 20 million qubits. They demonstrated that such a device would take only 8 hours to complete the calculations. They said: "This result has reduced the maximum number of qubits required to decompose a 2048-bit RSA integer by nearly two orders of magnitude."

Just recently in December 2022, Chinese researchers such as Tsinghua University and Zhejiang University published a paper on the preprint platform arxiv, reporting that the number of qubits required to crack a 2048-bit RSA key can be significantly reduced, and existing quantum computers can do it. If proven true, this research will mark an important moment in the history of computer security: Government, military and security agencies, bank securities and all data that needs to be protected will no longer be safe! (News source)

7.3 Possible alternative algorithms

The quantum encryption algorithm represented by BB84 protocol is as unbreakable as the classic "one-time pad", and does not have the great risk that the latter may have in the process of exchanging keys. Regarding quantum key distribution, the author does not know much about it and will not mislead. I will talk about it later when it may be in-depth.

References
Xiaolin Coding - 3.5 How to optimize HTTPS?
Ruan Yifeng’s web log - RSA algorithm principle (1)
Ruan Yifeng’s web log - RSA algorithm principle (2)
TLS False Start How exactly does it speed up the website?
The lingering “classic”——About BB84 quantum key distribution protocol (1)