Learning records 568@RSA Public key system and its decryption proof mode II

summary

RSA The basic operation of public key system is the operation of exponential power under module , Its decryption idea is to seek the inverse element under the module .
Suppose Party A intends to establish its own RSA Public key system , A first selects two large prime numbers p and q, And calculate n=p*q. Then select a positive integer e, send 1<e<n And gcd(e,Φ(n))=1, Finally, it is found that e In the mold Φ(n) The inverse element under d, namely ed ≡ 1 (mod Φ(n)). A general (e,n) Public as public key , take d,p,q and (n) Keep it secret and use it (d,n) As the private key .
It is assumed that Party B needs to express M Use Party A's RSA The public key system is encrypted and sent to Party A , among M Less than n The positive integer .RSA The encryption algorithm is as follows ：

1. C = $M^e$ mod n
2. Party a received C After use RSA The decryption algorithm will C Decrypt ,M = $C^d$ mod n.

The core of the proof of its decryption in the last article is the use of the Chinese Remainder Theorem , This article uses another way to prove .

Decryption proof

Basics

• Euler theorem ： Make a and n Is two mutually prime positive integers , be $a^{\Phi (n)}$ ≡ 1 (mod n)
• Fermat's small Theorem ： Make p As a prime number ,a Is a positive integer and is not p to be divisible by , be $a^{p-1}$ ≡ 1 (mod p)

prove

As far as I'm concerned , I never fear mistakes , Unless it turns out I'm wrong , Otherwise, I never think I've done anything wrong . actually , Only I give full play to my experience , I will feel at ease . At a certain time , The performance of the market does not prove me wrong , Only the characteristics of rise or fall can determine whether my market position is right or wrong . Only by the power of knowledge , I can win . If it fails , It must have been my own mistake .