Zero knowledge proof based on RSA algorithm

Scenario: P proves to V that he knows the private key of user S (eMagnedPhoneN)

Proof step (zero knowledge)

1. P ≡ V jointly selects random numbers an and b to satisfy the ab and e mod N.

2. PPerry V produces a random ciphertext C together.

3.P calculation: M ≡ C ^ d mod N Magi X ≡ M ^ a mod N and pass X to V

4.V calculate and judge whether X ^ b mod N = C is valid

Zero knowledge proof is designed to prevent private transmission in the process of proof:

M ≡ C ^ d mod N

C ≡ M ^ e mod N

Convert the second formula above so that V can be decrypted without private d during decryption, so P needs to add a step in the intermediate process: X ≡ M ^ a mod N and pass X to V to receive X to determine whether C = X ^ b mod N is true. In fact, the whole process is still the process of RSA encryption and decryption, only adding a link to replace d, so that V can be decrypted without d.

C ≡ M ^ e mod N = > X ≡ M ^ a mod N (ab ≡ e mod N)

C = X ^ b mod N

Thorough analysis:

The understanding of "≡": the congruence symbol means that the two are the same as dividing by the same remainder.

So 5 ≡ 8 mod3 ≡ 11mod3. Both 5 and 8 are multiples of a difference of 3, so

M ≡ C ^ d mod N, which means M = C ^ d + karma N.