RSA details
起因
日常自闭=。=,做个中科大新生赛的RSA,然后把自己给气死了。去年寒假写的脚本,今年各种bug,然后自己RSA和数论|抽代内容也忘得都差不多了,就很烦躁,啥也不会。于是干脆整这样一篇博客,趁着这个双休日,把RSA好好的理解理解,也可以做为以后自己复习用。
使用
先把RSA怎么用给写出来,具体的后面可以慢慢解释
$$
首先是选取两个大质数p和q,然后计算p*q=n\tag{Q1}
$$
$$
和(p-1)*(q-1)=\phi(N)\tag{Q2}
$$
$$
选取整数e(即公钥),使得e满足1<e<\phi(N),(e,\phi(n))=1\tag{Q3}
$$
$$
则存在整数d(即私钥),使得ed\equiv1\pmod{\phi(N)} \tag{Q4}
$$
PS: d也是e在某某里的逆元,这部分群环域的内容忘得差不多了。。。
$$
加密::此时有明文m,使用公钥e进行加密,得到密文c(cipher),c=m^e\pmod{n}
$$
$$
解密::此时有密文c,使用私钥d进行解密,得到明文m(message),m=c^d\pmod{n}\tag{Q5}
$$
这就是整体的使用流程,当然,这里有非常多的细节没有展示,仅仅是下次要用的时候急着拿来用罢了,不仅看客看不懂,我写的也云里雾里:凭什么啊?
Q | question_detail |
---|---|
Q1 | 涉及到RSA的根本原理,即大数分解问题:已知p、q,计算n很容易,但由n计算p、q非常困难 |
Q2 | phi(N)是干什么用的? |
Q3 | 为什么要(e,phi(N))=1? |
Q4 | 为什么存在d?如果存在,要如何计算d? |
Q5 | 为什么能够顺利解密? |