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 | 为什么能够顺利解密? |
原理
这里的本意是梳理自己有关数论的知识内容,尽可能的不学究,追随RSA的主线走。如果对Q1-Q5感兴趣的,上方表格内点击链接导向页面内容即可。
整除
定义
$$
设a,b是任意两个整数,其中b\not=0,如果存在一个整数q使得等式a=qb成立,则称b整除a或者a被b整除,记作b|a
$$
定理1
$$
设a,b,c\not=0是三个整数,若c|a,c|b,则对任意整数s,t,有c|sa+tb
$$
构造a=pc,b=qc即可
Euclid除法
$$
设a,b是两个整数,其中b>0,则存在唯一的整数q,r使得a=qb+r,0\leq r<b
$$
证明好像有点复杂==,不是很难懂,但也比较难想,有兴趣查资料吧23333
定理2*
$$
设a,b,c是三个不全为零的整数,如果a=qb+c,其中q是整数,则(a,b)=(b,c)
$$
PS:(a,b)表示a和b的最大公因数,这个符号应该目前是第一次出现。
这个定理非常重要,而且并不是十分直观,这也是后面扩展Euclid除法的基础。
$$
设d=(a,b),d’=(b,c),则d|a,d|b,于是d|a+(-q)b=c\\
所以d是b、c的因子,因此d\leq d’;\\
同理,d’\leq d,因此d=d’,即(a,b)=(b,c)
$$
广义Euclid除法
根据上面的a=qb+r以及(a,b)=(b,r),可以进行不停的迭代,由于r是小于b的,所以r也会不停减小,直至为0.(a,b)为算式列中最后一个非零余数
$$
以a=737和b=635为例,求解(a,b):\\
737=1·635+102\\
635=6·102+23\\
102=4·23+10\\
23=2·10+3\\
10=3·3+1\\
3=3·1+0\\
最大公因数为1
$$
定理3
$$
设a,b是任意两个正整数,则s_n+t_nb=(a,b)\\
s_-2=1,s_-1=0,s_j=s_{j-2}-q_js_{j-1}\\
t_-2=0,s_-1=1,t_j=t_{j-2}-q_jt_{j-1}\\
$$
$$
以a=737和b=635为例,求s,t使得s·a+t·b=(a,b)\\
\begin{aligned}1&=10-3·3\\
&=10-3·(23-2·10)\\
&=(-3)·23+7·(102-4·23)\\
&=7·102+(-31)·(635-6·102)\\
&=(-31)·635+193·(737-635)\\
&=193·737+(-224)·635\\
\end{aligned}
$$
这个定理我也看不懂,尤其证明更是复杂,在我的教材上篇幅足足有两页之多,但是实际上操作起来十分易懂。就是从1(或者最大公因数)开始,不断地利用从前的等式代入,直至两个分量满足条件。证明很复杂,但对于理解RSA与否并没有影响,因此略去(其实是看不懂)
定理4
$$
整数a,b互素的充要条件是存在整数s,t,使得sa+tb=1
$$
这个定理是根据定理3证的,但是感觉一般也用不太上,可以当成个性质。
算术基本定理
$$
任一整数n>1都可以表示成素数的乘积,且在不考虑乘积顺序的情况下,该表达式是唯一的
$$
同余
定义
$$
给定一个正整数m和两个整数a,b,若a-b被m整除或m|(a-b),则a,b叫做模m同余,记作a\equiv b;\\否则,叫做模m不同余,记作a\not\equiv b.
$$
几条定理
$$
1.(自反性)任一整数a,a\equiv a\pmod{m}\\
2.(对称性) 若a\equiv b\pmod{m},则b\equiv a\pmod{m}\\
3.(传递性) 若a\equiv b\pmod{m},b\equiv c\pmod{m},则a\equiv c\pmod{m}\\
4.若a_1\equiv b_1\pmod{m},a_2\equiv b_2\pmod{m},则\\
i)a_1+b_1\equiv b_1+b_2\pmod{m},ii)a_1b_1\equiv b_1b_2\pmod{m}
$$
这四条定理很普遍实用,而且很好证,都是从定义出发可得。
$$
设p,q是不同的素数,如果整数a,b满足a\equiv b\pmod{p},a\equiv b\pmod{q},则a\equiv b\pmod{pq}
$$
这条也许有用……注意p、q互素就很容易得出结论了,记录一下。
Euler函数
$$
设m是一个正整数,则m个整数0,1,……,m-1中与m互素的整数的个数,记作\phi(m),通常叫做Euler函数\\
例:m=10,则[0-9]与m互素的数为1,3,7,9,所以\phi(10)=4
$$
逆元定理
$$
设m是一个正整数,a是满足(a,m)=1的整数,则存在唯一的整数a’,1\leq a’<m,使得\\
aa’\equiv1\pmod{m}
$$
这个证明的其中一个证法需要用到剩余系的知识,这个我也许会另开一个帖,在RSA实在塞不下了。
好在教材还不错,有另一个用广义Euclid除法的证明可以贴上来
$$
因为(a,m)=1,根据整除里的定理3,我们可以找到s,t,使得\\
sa+tm=(a,m)=1\\
两边同时模m即可得\\
sa\equiv1\pmod{m},\\
即a’\equiv s\pmod{m}满足aa’\equiv1\pmod{m}
$$
几个Euler函数的求解方法:
$$
1.m,n是互素的两个正整数,则\\
\phi(mn)=\phi(m)\phi(n)\\
2.\phi(p^{\alpha})=p^{\alpha}-p^{\alpha -1}
$$
- 本文作者: crlwebby
- 本文链接: https://crlwebby.github.io/security/crypto/RSA-details/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!