技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 数论的应用-RSA公钥算法

数论的应用-RSA公钥算法

浏览:2586次  出处信息

要说起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就是他们三人姓氏开头字母拼在一起组成的。

首先介绍欧拉函数,表示是小于或等于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)

那么这种非对称加密算法解决了什么问题呢,首先他解决了密钥在非安全信道传播的问题,简单说你和别人想要加密传输资料,但是加密需要把密钥告诉对方才可以,这时候就可以直接把公钥发给对方,即使公钥被其他人截获,也无法通过公钥推算出密钥,换言之,除了拥有密钥的你之外,别人是不能解密内容的。另外公钥密钥还有一个用途就是数字签名了,一份东西你用私钥加密,别人都可以用公钥解密,因为别人没有私钥,所以加密的只可能是你,这样就是可以防止抵赖等,而且公钥密钥还有一系列很有意思的用途这里就不展开说了。数论,密码学神马的还是很有趣的啊。

建议继续学习:

  1. RSA 公钥格式转换之PHP实现    (阅读:4998)
  2. 为什么要用公钥/私钥而不是密码去做SSH身份验证    (阅读:4695)
  3. 公钥私钥加密解密数字证书数字签名详解    (阅读:4013)
  4. 千万不要迷信规律:大反例合集    (阅读:3766)
  5. 跨越千年的RSA算法    (阅读:2987)
  6. 几个精彩的数论问题    (阅读:1743)
  7. RSA 算法是如何诞生的    (阅读:1827)
  8. 密码学及公钥基础设施入门    (阅读:1178)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:P和NP那些事
后一篇:查找第K小的元素 >>
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1