数论的应用-RSA公钥算法
要说起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互质的数的数目,比如,小于6和6互质的只有1和5。并且如果n的分解式为那么,然后有欧拉定理如果n,m是整数且gcd(n,m)=1,那么:
话说费马小定理就是欧拉定理的特殊性形式,下面开始说明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作为公钥
发送密文时,令
发送密文时,令
让我们具体一点,比如A要给B传送数据M=52,B选出p=17,q=11则n=187,选出e=7,算出d=23,A通过查询知n=187,e=7,计算得出C=35发给B,B通过计算得出M=52
好了我们来简单说明一下RSA的正确性吧,因为选取的p和q是素数,所以,因为d*e=1 (mod (p-1)*(q-1)),设,则
那么这种非对称加密算法解决了什么问题呢,首先他解决了密钥在非安全信道传播的问题,简单说你和别人想要加密传输资料,但是加密需要把密钥告诉对方才可以,这时候就可以直接把公钥发给对方,即使公钥被其他人截获,也无法通过公钥推算出密钥,换言之,除了拥有密钥的你之外,别人是不能解密内容的。另外公钥密钥还有一个用途就是数字签名了,一份东西你用私钥加密,别人都可以用公钥解密,因为别人没有私钥,所以加密的只可能是你,这样就是可以防止抵赖等,而且公钥密钥还有一系列很有意思的用途这里就不展开说了。数论,密码学神马的还是很有趣的啊。
建议继续学习:
- RSA 公钥格式转换之PHP实现 (阅读:4998)
- 为什么要用公钥/私钥而不是密码去做SSH身份验证 (阅读:4695)
- 公钥私钥加密解密数字证书数字签名详解 (阅读:4013)
- 千万不要迷信规律:大反例合集 (阅读:3766)
- 跨越千年的RSA算法 (阅读:2987)
- 几个精彩的数论问题 (阅读:1743)
- RSA 算法是如何诞生的 (阅读:1827)
- 密码学及公钥基础设施入门 (阅读:1178)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:isnowfy 来源: isnowfy
- 标签: RSA 公钥 数论
- 发布时间:2012-12-24 22:40:39
- [53] IOS安全–浅谈关于IOS加固的几种方法
- [52] 如何拿下简短的域名
- [51] 图书馆的世界纪录
- [50] android 开发入门
- [50] Oracle MTS模式下 进程地址与会话信
- [49] Go Reflect 性能
- [46] 【社会化设计】自我(self)部分――欢迎区
- [46] 读书笔记-壹百度:百度十年千倍的29条法则
- [36] 程序员技术练级攻略
- [29] 视觉调整-设计师 vs. 逻辑