要说起RSA算法的话就不得不提欧拉这个伟大的数学家,他在数学的很多方面都有很多研究,而RSA也正是基于他在数论上的欧拉公式才建立起来的。欧拉公式稍后再说,先简单说一下公钥密钥的非对称算法的概念,平常我们用的加密算法往往都是对称的,也就是说加密密钥和解密密钥是一样的,比如凯撒密码,你把每个字母后移3位,a变成d,b变成e,这里3就是加密密钥,然后解密的时候前移3位,这时候3就是解密密钥,非对称加密顾名思义就是加密密钥和解密密钥是不同的,恩,数学就是能干很多神奇的事情啊。
数论在很长的一段时间里被认为是没用的,纯数学的,优美的理论,一直到1976年。当时在美国斯坦福大学的迪菲(Diffie)和赫尔曼(Hellman)两人提出了公开密钥密码的新思想(论文”New Direction in Cryptography”),再后来,1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出了RSA。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
首先介绍欧拉函数,$$\phi(n)$$表示是小于或等于n的正整数中与n互质的数的数目,比如$$\phi(6)=2$$,小于6和6互质的只有1和5。并且如果n的分解式为$$n=p_1^{m_1}*p_2^{m_2}…*p_s^{m_s}$$那么$$\phi(n)=p_1^{m_1-1}*(p_1-1)*p_2^{m_2-1}*(p_2-1)…*p_s^{m_s-1}*(p_s-1)$$,然后有欧拉定理如果n,m是整数且gcd(n,m)=1,那么:
$$m^{\phi(n)}=1\quad (mod\quad n)$$
话说费马小定理就是欧拉定理的特殊性形式,下面开始说明RSA的主要步骤。
- 首先选出两个素数p,q,令n=p*q
- 再选出e,满足gcd(e,(p-1)*(q-1))=1
- 计算出d,满足d*e=1 (mod (p-1)*(q-1))
- 丢弃p,q(不要让其他人知道)公布n,e保留d,到这一步就是d作为密钥,e作为公钥
- 发送密文时,令$$C=M^e\quad (mod \quad n)$$
- 发送密文时,令$$M=C^d\quad (mod \quad n)$$
让我们具体一点,比如A要给B传送数据M=52,B选出p=17,q=11则n=187,选出e=7,算出d=23,A通过查询知n=187,e=7,计算$$C=M^e\quad (mod \quad n)$$得出C=35发给B,B通过计算$$M=C^d\quad (mod \quad n)$$得出M=52
好了我们来简单说明一下RSA的正确性吧,因为选取的p和q是素数,所以$$\phi(n)=(p-1)*(q-1)$$,因为d*e=1 (mod (p-1)*(q-1)),设$$d*e=k*\phi(n)+1$$,则$$C^d=(M^e)^d=M^{e*d}=M*(M^{\phi(n)})^k=M\quad (mod \quad n)$$
那么这种非对称加密算法解决了什么问题呢,首先他解决了密钥在非安全信道传播的问题,简单说你和别人想要加密传输资料,但是加密需要把密钥告诉对方才可以,这时候就可以直接把公钥发给对方,即使公钥被其他人截获,也无法通过公钥推算出密钥,换言之,除了拥有密钥的你之外,别人是不能解密内容的。另外公钥密钥还有一个用途就是数字签名了,一份东西你用私钥加密,别人都可以用公钥解密,因为别人没有私钥,所以加密的只可能是你,这样就是可以防止抵赖等,而且公钥密钥还有一系列很有意思的用途这里就不展开说了。数论,密码学神马的还是很有趣的啊。
牛人额,我正在学数论,不久就到密码学了:)
@阿弋聆风: 感觉现在数论的主要应用就都是密码学了
@isnowfy: 额,貌似有位大神为数论没有应用价值而高兴。另外,可以做个友链吗,你的我做好了:)
@阿弋聆风: 这,那这位大神也太神了,专注于纯理论研究,但是数论有时也需要其他领域的知识,比如费马大定理的证明。友链加上了,话说我的id写错了,最后是fy不是fly。。。
我想问一个问题,为什么使用和公钥不同的密钥解密可以得到原文。。写完关于RSA的论文,突然发现这个问题还没有搞懂,,,难道是前人聪明的智慧么?
@风起江水寒: 不对称密钥的发明是因为当时想要搞出一个密钥分发的系统,于是发明了不对称密钥这种密码方式,发明肯定算是前人的智慧,建议你可以去看看《密码故事》这本书,讲了很多密码的由来