Introduction and practice of cryptography

the term:

Plaintext or cleartext : an understandable message that the sender wants to transmit to the recipient.

Ciphertext : Generates an incomprehensible message using plain text encryption of the cryptosystem

Encryption : The process of converting plaintext to ciphertext

Decryption : The process of converting ciphertext to plaintext (encryption reverse)

Traditional cryptography:

It is also known as symmetric key or shared key encryption. The same key is used to encrypt and decrypt messages. Consider the following example as traditional encryption:

You and your roommate use the same key to lock/unlock your door. Therefore, you share the same key to protect your room. Indeed, your roommate can have a copy of your key so he can enter the room while you work, and vice versa.

Traditional cryptosystem algorithms using symmetric keys: Data Encryption Standard (DES), Advanced Encryption Standard (AES)

Advantages: Fast.

Disadvantages: not safe!

The sender and receiver must agree on the key and prevent others from accessing the key. (Doing this) There is a big problem, how to issue a key if the two are not in the same physical location. How can you give your key to your roommate in the US when you are in China!

Practical advice: Change the symmetric key after encrypting each message so that only one message can be leaked in the event of a disaster (password analysis, stealing, etc.).

Key distribution

In the previous paragraph, we discussed the use of symmetric keys in cryptosystems and the lack of an effective way to share keys with roommates securely. Key distribution helps to address this shortcoming. Next, we will explain how to exchange keys through an untrusted communication channel.

Diffie-Hellman key exchange (Diffie-Hellman key exchange)

This key exchange is based on an algorithm that mathematically cannot easily calculate the discrete logarithm of large numbers in a reasonable amount of time. We will use the color overview algorithm before running directly with numbers and abstract formulas.

1. Step 1: Alice and Bob reached a common color agreement.

2. Step 2: Alice chooses that she won't tell Bob's secret color. Bob will do the same thing.

3. Step 3: Alice mixes the common color with the secret color and the result is a mixture. Bob also mixes his secret color with the normal color and will get a mixture different from alice.

4. Step 4: Alice and Bob exchange the mixture. This is the most critical step in communication, because "man-in-the-middle" can access both mixtures. If the middleman has a mixture of both sides, this will also be a problem.

Color decomposition is irreversible. Therefore, the only chance to find two secret colors is to mix all possible colors with the common colors in the first step. Also, keep in mind that secret colors can also be a mixture of many other colors.

Update: Diffie-Hellman won't protect you from man-in-the-middle attacks. To understand why, imagine the attacker receiving all messages from Alice and rebroadcasting them back to Bob.

5. Step 5: Alice will add her secret color to the mixture that Bob sent to her. Bob will follow the same steps.

Finally Alice and Bob will get a common secret color. Now, Alice and Bob can safely exchange the symmetric keys we discussed in the previous chapter because they can encrypt and decrypt any message (sent over the communication channel) using the secret color described above.

Mathematics comes, when we don't have enough color, it's always about math.

Step 1: Alice and Bob have reached two agreements for large numbers: a prime number p (recommended at least 512 bits) and a base number g (the original root modulus of p).

Step 2: Alice chooses a secret integer a. Bob chooses a secret integer b.

Step 3: Alice calculates the common value x = g ^ a mod p. Bob calculates the public value y = g ^ b mod p, where mod is the modulo operator.

Step 4: Alice and Bob exchange x and y.

Step 5: Alice calculates her secret key k_a = y ^ a mod p. Bob calculates his secret key k_b = x ^ b mod p. It can be proved mathematically that k_a = k_b. Alice and Bob now have a common key for encrypting and decrypting the plaintext they want to securely exchange.

example:

If the middleman knows that the secret integers a = 6 and b = 15, he can find the secret key used for communication. Methods as below:

Advantages: Safety. Avoid man-in-the-middle attacks.

Disadvantages: You can't determine the actual identity of the real 'Bob'. (Unable to determine the true identity of 'Bob')

You can also use the XOR (exclusive OR) operator to interpret Diffie-Hellman:

Suppose Alice wants to send the message 'M = Hello' to Bob. The binary representation of the message M is B(M) = 0100100001100101011011000110110001101111. Alice encrypts the message with the key K = 1010101000101110100101010001110010101010.

The equivalent message of the plaintext of the encrypted message L is âKùpÅ Bob receives âKùpÅ and decrypts the message using the same key K that has been exchanged with Alice.

Public key encryption

Security key distribution is addressed by the public key cryptosystem because it does not require secure initial key negotiation between you and your roommate.

Public key cryptosystems are also known as asymmetric key cryptography – as opposed to symmetric keys – using a pair of keys (two separate keys): the public key used for encryption and the private key used for decryption (also known as Secret key). The private key cannot be derived from the public key.

We can analogize the asymmetric key cryptosystem with an email account. Anyone can access your email address (for example, anyone can send you an email at your@email.com), but you are the only one with a login password (which means only you can read the email) ). The public key is your email address and the private key is the password that is logged in with your email address.

How does it work:

Step 1: Create a pair of private keys – public key (we will discuss generating key pairs later).

Step 2: Share your public key with your friends.

Step 3: The sender encrypts the plaintext with your public key (original mail + encryption = ciphertext).

Step 4: The sender sends you a ciphertext.

Step 5: Decrypt the ciphertext (Ciphertext + Decryption = Original Message) using your private key.

Advantages : increased convenience and security.

Disadvantages : Encryption is slow. All public keys – private keys are vulnerable to brute force attacks (this can be avoided by choosing to increase the key size). You cannot verify the identity of a partner (susceptible to impersonation).

Usage : Since increasing the key size results in an excessively large encrypted message output, it takes longer to encrypt and transmit the message. For practical purposes, the public key is prioritized for short message encryption, such as sending a private key or a digital certificate instead of encrypting a long message. Inconveniently, a shorter key length provides lower security, but you are the winner in terms of encrypting message length or transmission time. Therefore, the keys should be replaced frequently.

RSA

RSA is named after the initials of Rivest, Shamir and Adleman. It is the Diffie-Hellman (key exchange algorithm) method described in the previous paragraph and is the next step in the public key cryptosystem. The algorithm is based on the fact that large integers are difficult to decompose.

I will gradually explain the RSA algorithm before I assume that you like mathematics 🙂

First you should know about mod (modulo operations) and prime integers.

Euler's theorem:

Where phi(z) is the Euler's totient function and z is a positive integer.

In short, the Euler function will count the number of primes with z as phi(z). If z is a prime number, then phi(z) = z-1(*).

example:

Let us continue Euler's theorem:

Using mathematical induction we can prove:

This means that when the exponential power of the number x is phi(z)+1, the result is to return itself.

From the (*) equation and the Euler theorem, we get

So far, we don't know anything about RSA. It's time to connect all these equations together.

We assume two prime numbers p, q. Replace z with p * q.

From equation (**) with K = 1 and equation (***) we get:

This means that we can find (p-1)*(q-1)+1 only if we can decompose the p * q number. Think of x as a message. We can choose a random prime number E (encryption key), which must be the prime of (p-1)*(q-1). Then we calculate D (decryption key) as:

Where D is the inverse of mod.

Now we can use the RSA algorithm because we have the public key (E) and the private key (D):

If the result ciphertext ^ E <p * q, there is a short vulnerability attack based on index E and ciphertext for RSA. Longer key encryption is recommended.

Why is this algorithm important? Because protocols like SSL, TLS, SSH, IPSec, and PKI use Diffie-Hellman.

(To be continued)

(Source: Ge Mi Chain)