RSA encryption and decryption details

0x01 RSA Summary

RSA The algorithm is an asymmetric cryptographic algorithm . Asymmetric cryptography is also called public key cryptography , It means that each pair of encryption contains a public key （ May be known to others ） And a private key （ May not be known to everyone ）. Effective security requires maintaining the privacy of the private key ; Public keys can be publicly distributed without compromising security .

RSA The security of depends on the practical difficulty of decomposing the product of two large primes , But relatively slow , Can be called “ Break down the problem ”.

RSA application

• The client sends its public key to the server and requests some data
• The server encrypts the data with the public key of the client and sends the encrypted data
• The client receives this data and decrypts it

0x02 RSA Detailed algorithm flow

RSA Four steps of algorithm

• Key generation
• Key distribution
• encryption
• Decrypt

About RSA The relevant formula

n = p * q

ø(n) = (p - 1) * (q - 1)

ed ≡ 1 mod ø(n) 

c = m**e mod n

m = c**d mod n

simple example

It is known that ：P = 11,q = 29,e = 3

seek d

Through the formula ：
ø(n) = (p - 1) * (q - 1)

φ(n) = (p-1)(q-1) = (11-1)*(29-1) = 280

Through the formula ：
ed ≡ 1 mod ø(n)

“≡” It's the sign of congruence in number theory
If two integers ed and 1 Satisfy ed-1 Can be ø(n) to be divisible by , It's called an integer ed And 1 To mold ø(n) congruence

1 < d < ø(n)

3d ≡ 1 mod 280
3d mod 280 = 1
d = 187

Through the formula ：
n = p * q

n = 11 * 29 = 319

Public key （n,e）
Private key （n,d）
obtain ：
Public key （319,3）
Private key （319,187）

Or use a script to solve d：
gmpy2.invert(e,(p-1)*(q-1))

What is the maximum number that can be encrypted with this key pair

The encryption function is ：
c(m) = m^e mod n

The decryption function is ：
m(c) = c^d mod n

RSA The length of the name text that the algorithm can encrypt at one time is proportional to the length of the key .

len_in_byte(raw_data) = len_in_bit(key)/8-11

If less than this length , You need to supplement the data , be called padding, Without data complement, users cannot determine the true length of the decrypted content .

n The length of the key is the length of the key ,n = 319,n The binary of is 100111111, The key is 9 position ,RSA The maximum length of the actual encrypted plaintext is also 1024bits

When encrypting plaintext m = 23 when , Seeking ciphertext c

The encryption function is ：
c(m) = m^e mod n

 

c(m) = 23^3 mod 319 = 12167 mod 319
c(m) = 45

import gmpy2
n = 319
e = 3
m = 23
print(pow(m, e, n))

When ciphertext c = 23 when , Ask for clear text m

The decryption function is ：
m(c) = c^d mod n

m(c) = 23^187 mod 319
m(c) = 199

import gmpy2
n = 319
d = 187
c = 23
print(pow(c,d,n))