DAY 14- 《公钥密码》-RSA(2)

"我想不到要讲什麽。"
---

RSA演算法

演算法的准备步骤有五个，更准确来说是四个。
当 Alice 要传讯息给 Bob 时，

依据我们前天所讲的结论是会使用到 Bob 的公钥加密，所以首先要先设定公钥。

设定的步骤如下：

1.选择两个大质数，分别是 p和 q。
2. n = p×q
3. $\phi(n)=$ (p-1)(q-1)
4. 选择一个 e ∈{1, 2 , ... , $\phi(n)-1$ }，使得e 跟 $\phi(n)$ 互质。
5.d×e ≡1(mod $\phi(n)$ )

举个例子来说，

算完以上的数字之後，

$k_{pr}=d,\ k_{pub} =(n, e)$

从上面的例子来说，就是私钥是53，公钥是(77, 17)
将公钥公开，私钥藏好。
要注意只能公开 n 跟 e。
私钥是绝对不能被别人知道的数字，也就是公开的数字必须不能推导出私钥（d）。

来看一下要推导出公钥 d 需要哪些东西。
看到第五步，d 是 e 的乘法反元素，所以要知道 d 是多少就得知道 e 和模数 $\phi(n)$ 是多少，
e 跟 n 已经被我们公开了，那就要看光有n 的话能不能把 $\phi(n)$ 算出来。

要想算出 $\phi(n)$ ，看第三步就知道，我们需要 p 跟 q。
而昨天解释过了，光是知道 n 是很难推得 p 跟 q 的，
所以公钥的公开并不会威胁到私钥的隐蔽性。

RSA 的加解密是做指数运算，所有的运算都要 mod n

$y = x^e mod n$
$x = y^d mod n$

我们知道 $2^5=32$ ，也可以很轻易的推论出 $2^5=2\ (mod\ 5)$
但是跟你说 $2^x=2\ (mod\ 5)$ 要你推回 x 等於多少的话是困难的。
当然如果你推出来的话，那是因为数字很小很方便计算。
我们要加密的东西绝对不是2这麽简单的数字。

另外要看到，
$x =y^d =(x^e)^d=x^{ed}=x(mod\ n)$
看到最後一个等号必须使用尤拉定理*来证明，
不过可以简单看成是「d 是 e 的乘法反元素」的结论。

*Euler's Theorem : if a ⊥ n, then $a^{\phi(n)}=1(mod\ n)$ .

RSA有数位签章功能，其算法就是将加密演算法倒过来，
用私钥加密，用公钥解密。

$s = x^d mod n$
$x' = s^e mod n$

其中 s 是签章後的结果，x'则是解密後的解果，
验章的方式是确认x和x'是否相同，
如果相同就认定是本人所签署。
因此签章者必须传送一份签章前的文件供收件者验章。

以上就是 RSA 的介绍，
而实务上 RSA 若要足够安全，建议使用 2048 或 3072 位元的 n。