Introduction to RSA encryption

1. Cause Formation

Security safety

Faced with attacks, getting the identity of the user.

More and more authentication factors.

=> Strong authentication security technology is based on information encryption.

Coding:

Classic coding.

Symmetric encryption.

Asymmetric encryption: is an encryption system that uses the key to encrypt and the key to decrypt differently. On the basis of analyzing integers into prime factors, it later became the famous and widely used RSA coding system today.

2. RSA And Digital Signature

A digital signature is a form of electronic signature. It is a form of data used to authenticate other data

Digital signatures use an asymmetric encryption system. In most cases, it is also possible to check the integrity of the data.

Digital signature is similar to hand signature in many ways, but installing and using digital signature is much more difficult.

How to use digital signature

Signing and authenticating a digital signature using the RSA encryption system is similar to the encryption process that decrypts above. However, the roles of public and private keys are slightly different.

Should use hash for digital signature

A bulletin can be very long, so using the hash of the message will reduce the time and size of the character.

Hash functions are one-way functions, so even if we have a hash, it is impossible to know what the original message was like.

The hash length is fixed and is usually very small, so digits won’t take up too much space

Can the hash value be used to verify that the received message is intact?

How digital signatures work

Benefit

Signature forgery or text forge: text can only be signed if there is a secret key (kept secret by the signer). Therefore an imposter cannot sign for the signer.

Edit signed text: editing signed text produces a hash other than the original hash used to sign the text. Thus, the signature validator will be able to detect the modified text by comparing the 2 hashes.

Unable to exploit his signature: if everyone knows that the public key belongs to the signer, the signature on the document must belong to the signer. The signer cannot deny signing the document.

Some things to apply

When used with a digital signature, this hash function must be secure, eg SHA-256, which makes it almost impossible to find two documents with the same hash.

Attach the newly created digital signature to the signed text.

Use to create digital signatures when using commonly used applications such as Word, Excel

3. How to Create a Key

According to the Fec-ma theorem: where p is a prime number, for any m <p: mp-1 = 1 (mod p)

Where q is a number other than p, and m is prime together with both p and q, we have: [mp-1]q-1 = 1 (mod p)

is similar to q: [mq-1]p-1 = 1 (mod q) => m(q-1)(p-1) = 1 (mod pq)

Power 2 sides up s times (s positive integers) and multiply the 2 sides by m: ms(q-1)(p-1)+1 = m(mod pq)

Basic formula of RSA encoding ms(q-1)(p-1)+1 = m(mod pq)

Analyze s(q-1)(p-1)+1 product of 2 keys: choose e prime together with (q-1) (p-1)

=> there exists an inverse d of e such that: ed=1 (mod (p-1)(q-1)) or: ed = s (p-1) (q-1) +1

In summary: med = m(mod pq)

The basic point of key generation in RSA is to find a set of 3 natural numbers e, d and n such that: need security so that even knowing e, n or even m cannot find d .

=> Specifically, the key of RSA is generated as follows:

Choose 2 prime numbers p and q

Calculate n = pq . Later, n will be used as a module in both the public key and the private key.

Calculate a pseudo-prime number using the Carmichale function as follows: λ(n) = BCNN(λ(p), λ(q)) = BCNN(p − 1, q − 1)

This value will be kept confidential.

Choose a natural number e in the range (1, λ (n)) such that e and λ (n) are prime together ƯCLN(e, λ(n)) = 1

Calculate the number d as the modulo inverse of e modulo mod λ (n) d ≡ 1/e (mod λ(n)) hay de ≡ 1 (mod λ(n)).

The public key will be a set of numbers (n, e), and the private key will be a set of numbers (n, d).

=> Keep the private key very carefully as well as the prime numbers p and q because it can calculate the keys very easily.

4. Encoding and Decoding

After receiving the public key (e, n) and private key (d):

Ecryption: me mod n = c

Decryption: cd mod n = m

Inside:

m is the original message.

e, n are the public key.

c is the encrypted data.

d is the private key which is usually a very large number, the product of two primes.

For example, we have public key (e = 7, n = 33) and private key (d = 3) and assume m = 2 Encryption is c = 27 mod 33 = 29

Descryption is m = 293 mod 33 = 2

c is the ciphertext.

d is the plaintext.

To summarize, we have the following parameters:

p = 3

q = 11

φ (n) = 20

n = 33

e = 7

d = 3

Summary of RSA algorithm:

As an asymmetric encryption algorithm.

The algorithm of the algorithm is based on 4 main steps:

Biology lock

Share key

Encode

Decryption

The security of RSA is mainly based on a random number generator that generates two primes p and q initially.

Inverse computation of p and q from n is almost impossible with two 2048-bit primes.

But calculating d from p and q is very easy.

Therefore, if any party can guess or find out the vulnerability of that random number generator, then RSA should be dismissed.

It has recently been suggested that the US Department of Homeland Security (NSA) installed a backdoor into the Dual Elliptic Curve random number generator to enable the NSA to crack the RSA 10,000 times faster.

5. Weakness and Attack Method

Small n number

If the number n is small (length n <256 bits), the number n can be split into prime factors easily by built-in tools such as factordb.

The recommended length of n is 1024 bits.

But there have been cases where n is large, but the division of n into prime factors is already available in databases of sites such as factordb or alpertron.

This is a very easy way to find p and q so it is usually tried first.

Small e number, small m number

One major disadvantage of RSA encryption is that the encryption speed is much slower than DES encryption, so in some cases to increase the speed, the encoder will encrypt the document with a different encryption key. will be encrypted using RSA.

At the same time to optimize the encoding time, the number e is also selected in the form e = 2n + 1, then the smallest e is e = 3.

If we choose small e and the message M (small m) -> ciphertext: c = m3 (mod n). Because m is small so m3 <n then the whole module has no effect, So to find people m from c we cso m = c1 / 3

Attack repeatedly

Initially we have 2 numbers p, q respectively 3, 5 => n = p * q = 15 => choose m = 7.

Calculate φ (n) = (p-1) * (q-1) = 8 => choose e = 3.

Calculate c = me mod n = 13

c1 = ce mod n = 7

c2 = c1e mod n = 13

Since c2 = c => m = c1 = 7

Small p – q effect – Fermat Attack

The chosen p and q have the same bit length to produce a strong RSA code, but this can cause q and p to be too close together for an attacker to easily split n into prime factors. Condition (p – q) <n¼

Hastad Broadcast Attack – Hastad Broadcast Attack

In LAN, e number is sometimes set the same for computers of the same level. That is, e1 = e2 = … = e = 3

The attack scenario occurs if the server sends the same broadcast message m (encrypted as c1, c2, … to multiple computers on the network, and we get at least e ciphertext c1, c2, .. ., ce. At this point, we should be able to restore the plaintext m with no difficulty.

Assuming e = 3, let M = m3. Our task is to solve the system of congruent equations:

After calculating M, we will find m (equal to the square root of M).

Common modulus – Common modulus

Similar to the example in the previous section but instead of e being the same, this time n overlap, meaning that n1 = n2 = … = n and the number e is chosen randomly. Thus, each member of the network will be given a separate set of parameters (n, ei, di).

Since ed ≡ 1 (mod φ (n)), there exists a number k such that ed – kφ (n) = 1. Therefore: k = (ed-1)/φ(n) > (ed-1)/n

Then we will brute-force the number of k from (ed-1) / n or more, reverse compute φ (n) = (ed-1) / k, until we get the result that φ (n) is an integer. Yes φ (n) we easily calculate the Private Key of victim: dvictim = evictim-1 mod φ (n)

Key distribution

Suppose C can send A any key and can cause A to believe it is a public key of B. At the same time C can read information exchanged between A and B. Then, C will send A his own public key (which A thinks is B’s key). Then C will read all the encryption text sent by A, decrypt with his secret key, keep a copy, and encrypt with B’s public key and send to B