RSA加密算法例子解读

RSA加密算法例子解读

如何得到公钥和密钥

---

1. 随机选择两个不相等的质数p$p$和 q$q$

   例如p=61,q=53

2. 在1 ~ (p-1)(q-1) 随机选择一个整数e$e$,并且要与(p-1)(q-1)互质（最大公约数为1）

   1<e<60×52=3120$1<e<60×52=3120$，且需要和3120互质，随便选取一个符合条件的数17

3. 计算二元一次方程，ex+(p−1)(q−1)y=1$ex+(p-1)(q-1)y=1$

   也就是计算 17x+3120y=1,这个很简单，随便拿个数套一下就能得出一个解，例如x=2753，y=-15

4. 公钥为（pq,e）$（pq,e）$和私钥(pq,x)$(pq,x)$

   公钥为（3233，17）
   私钥为（3233，2753）

如何进行加密和解密

---

假设m为明文，c为加密后的明文，n=pq

1. 加密，已知条件为m,（n,e）
   me≡c(modn) $$m^e ≡ c (mod , n)$$

   例如，明文为65，则加密过程为
   $$ 65^17 ≡ c (mod , 3233)
   于是，65加密后，c=2790,因此传输过程中，65不是以65的形式发送的，而是以2790发送的

2. 解密,已知条件为c,(n,d)
   cd≡m(modn) $$c^d ≡ m (mod,n)$$

   也就是求解： 2790^2753 ≡ c (mod , 3233)
   得到c=65