RSA a little bit of thought

author

1976 year , American computer scientist W.Diffie and M.Hellman Put forward “ Exchange keys without passing them ”¹.
1977 year , Three mathematicians at MIT implemented this algorithm ,RSA is short for author’s lastname,Ron Rivest、Adi Shamir,Leonard Adleman.

Time

It’s invented in 1977.

scene

The three functions of digital signature , Anti counterfeiting , tamper-proof , Visit repudiation .

Anyone can verify this signature through Xiaoming's public key , If the verification passes , To be sure , This message was sent by Xiao Ming .

Digital signature algorithm in e-commerce 、 Online payment plays a very important role in these fields ：

First , Signatures are not acceptable forge , Because the private key is only known by the signer , So no one else can forge a signature .

secondly , The message cannot Tampering , If the original message is tampered with , Then verifying the signature will fail .

Last , Signatures are not acceptable Deny . If the signature is verified , that , The message must have been sent by the signer himself , He could not deny that he had sent this

Logic

be based on “ It is not feasible to deduce the decryption key from the known encryption key ” Cryptosystem . Public key PublicKey, Private key PrivateKey perhaps Secret Key, The public key is encrypted , Private key decryption ; Private key encryption , Public key decryption .
RSA By discrete logarithm , Euler function 、 Euler theorem 、 Modular inverse elements , And the knowledge of exchange key rules .
SK：Secret Key/Private Key — （ A secret ）
PK: Public Key — ( Open )

programme

discrete logarithm

m^k mod n = 1~ n-1. m yes n The original root .

Euler function

φ（m）= { And m Reciprocal number } The number of elements in the set of .
When m When itself is a prime number φ(m) = m-1; Such as φ(5)= 5-1=4.

 When m Can be decomposed into the product of two coprime integers , Such as m = A*B,AB Coprime ,
 that  **φ(n)=φ(A*B) = φ(A)*φ(B)=(A-1)*(B-1)**

for example

φ(35) = φ(57) = φ(5)φ(7)=(5-1)(7-1) = 46=24.

1---2---3---4---6---8---9---11                        8
12--13--16--17--18--19--22--23                        8
24--26--27--29--31--32--33--34                        8
\--------------------------------------------------------------/
                                                    **24**

φ(56)=φ(7*8)=φ(7)*φ(8)=(7-1)φ(8)= 64=24.
φ(8)= {1—3—5—7} = 4.

1---3---5---9---11---13---15---17                      8
19--23--25--27--29---31---33---37                      8
39--41--43--45--47---51---53---55                      8
\--------------------------------------------------------------/
                                                    **24**

* because 24=(5-1)*(7-1)=(7-1)φ(8) =φ(56)=φ(35) , therefore , By pushing back 24 The factor of is not tenable .

Euler theorem

If it's a positive integer m,n Coprime , m ^φ(n) mod n = 1.
According to the Euler function , When n Prime number ,m^(n-1) mod n = 1.

m ^φ(n)  mod n  = 1
[m ^φ(n) mod n]^k = 1^k
m ^k*φ(n)  mod n = 1
[m ^k*φ(n) mod n]*m = 1*m
m ^k*φ(n)+1  mod n = m

Modular inverse elements

If it's a positive integer m,n Coprime , that m*d mod n = 1 , d Namely m Yes n The modulo inverse elements of .
for example ：
m = 3,n=5;
3*d mon 5 = 1, that d = 12.

hypothesis k yes mon Quotient of process , that kn+1 = md.
for example 5k +1 = 3d
When k =1, d=2
k=4, d=7
k=10, d=17
…

RSA

m^e mod n = c encryption

c^d mod n = m Decrypt

Public key ： n and e Private key ： n and d Plaintext : m Ciphertext : c
Remember the conditions ？m < n;d yes e Relative to φ(n) The modulo inverse elements of .

Explain ：

1、n It's going to be very big , The length is generally 1024 Bits .（ The largest integer that human beings have decomposed ,232 Decimal digits ,768 Bits ）;

2、 Because of the need to find φ(n), So according to the characteristics of Euclidean function , The easiest way n Multiply two prime numbers to get : Prime number ：p1、p2,Φ(n) = (p1 -1) * (p2 - 1);

3、 Finally by φ(n) obtain e and d .

A total of 6 A number ：p1、p2、n、φ(n)、e、d.

About RSA The safety of the ：

Except for the public key n and e The rest 4 The number is not public .

Now crack RSA obtain d This is done as follows ：

1、 To find the private key d . Because of e*d = φ(n)*k + 1. Need to know e and φ(n);

2、e Yes, I know. , But to get φ(n), You have to know p1 and p2.

3、 Because of n=p1*p2. Only will n Factorization can be used to calculate

A text with footnotes .¹

---

1. RSA The mathematical principles of https://kknews.cc/history/z84oz43.html ︎︎