量子通讯争议,到底争些什么?
谈谈第一张黑洞照片
谈谈《物理学咬文嚼字》
量子保密通讯,经典派陷入的N个误区
谈谈RSA算法
谈谈引力波事件触发的多信使天文学
姬扬:推荐《普林斯顿数学指南》,每一个对数学感兴趣的人,每一个想对当代数...
姬扬:从我的求学经历谈科学精神的建立
博文精选举例说明科普的困难
姬扬老师的译作
官方微信
友情链接

谈谈RSA算法

2019-05-20

RSA算法是一种广泛使用的公开密钥加密算法。1977年由Ron RivestAdi ShamirLeonard Adleman提出。2002年,他们三人共同获得了图灵奖。

RSA算法是最流行的公开密钥算法,也是最容易理解和实现的。目前还没有攻击RSA算法的可靠方式。RSA算法的安全性基于对极大整数做因数分解的难度。只要采用足够长的公钥,用RSA加密的信息实际上是不能破解的(1999年实现了512比特公钥的暴力破解)。用于快速因数分解的量子算法(Shor算法),目前还只是停留在理论阶段,具体实现还早得很。

 

RSA算法的流程如下:

1. 选择两个很大的质数pq

2. 计算乘积n=pq

3. 随机选择一个小奇数e(不一定是质数),与(n)=(p1)(q1)互质

4. 计算e(n)的乘法逆ded=1 mod (n)

5. RSA公开密钥就是数对P=(e,n),私钥就是数对Q=(d,n)

6. 加密 c=me mod n m是明文,c是密文)

7. 解密 m=cd mod n

 

随便找本讲加密算法的书,都应该有这些内容,包括数学证明。也会有一些例子,例如《应用密码学》就给出了(p=47,q=71)的例子,而《量子计算和量子信息》把(p=3,q=11)作为习题(用来加密“QUANTUM”)。

 

最后做两个习题,算是娱乐吧。

 

确定公钥和私钥

p=3

q=11

p*q=33

(p-1)*(q-1)=2*10=20

e=3 20互素

d=7

所以公钥就是(3,33),私钥就是(7,33)

 

QUANTUM编码。按照字母表的顺序,Q=17U=21A=1N=14T=20U=21M=13

 

计算密文

明文是Q=17

17^3 (mod 33)=29

密文就是29

恢复明文

29^7 (mod 33)=17

明文就是17=Q

 

用类似方法,可以计算其他字母的密文并恢复其明文。

U 21 21^3 (mod 33)=2129^7 (mod 33)=21

01 1^3 (mod 33)=11^7 (mod 33)=1

N 14 14^3 (mod 33)=55^7 (mod 33)=14

T 20 20^3 (mod 33)=1414^7 (mod 33)=20

U 21 21^3 (mod 33)=2129^7 (mod 33)=21

M 13 13^3 (mod 33)=1919^7 (mod 33)=23

 

 

311太小了,没有意思。换个大一些的质数玩玩吧。

 

从质数表里随便找两个质数

p=1237

q=2539

 

计算pq

p*q=1237*2539=3140743

 

为选择公钥和私钥做准备

(p-1)*(q-1)=1236*2538=3136968=8*392121=8*9*43569=8*9*9*4841=8*9*9*47*103=(2^3)*(3^4)*47*103

欧拉函数是

[(2-1)*2^2]*[(3-1)*3^3)]*(47-1)*(103-1)=4*54*46*102=1013472

 

选择公钥

e=41

(p-1)*(q-1)

 

计算私钥(这里利用了上面的欧拉函数值)

d=918137

因为41^1013472 (mod 3136968)=1

计算得到,41^1013471 (mod 3136968)=918137

具体计算过程(利用windows自带的科学计算器

41^101 (mod 3136968)=391601

391601^100 (mod 3136968)=3005161

3005161^100 (mod 3136968)=3120289

41^3471 (mod 3136968)=1210985

3120289*1210985(mod 3136968)=918137

 

因此,公钥就是(41,3136968),私钥就是(918137,3136968)

 

加密明文 =17

17^41 (mod 3140743)=150572

解密

150572^918137 (mod 3140743)=17

具体过程(利用windows自带的科学计算器

150572^918 (mod 3140743)=2784875

2784875^1000(mod 3140743)=2459448

150572^137 (mod 3140743)=1787715

2459448*1787715 (mod 3140743)=17

 

加密明文UAN=210114(因为现在的密码很长,可以加密不止一个字符)

210114^41 (mod 3140743)=1746134

解密

1746134^918137 (mod 3140743)=210114

具体过程(利用windows自带的科学计算器

1746134^918 (mod 3140743)=1992844

1992844^1000(mod 3140743)=1413562

1746134^137 (mod 3140743)=2909887

1413562*2909887 (mod 3140743)=202114

 

加密明文 TUM=202113

202113^41 (mod 3140743)=336879

解密

336879^918137 (mod 3140743)=202113

具体过程

336879^918 (mod 3140743)=1792236

1792236^1000(mod 3140743)=177322

336879^137 (mod 3140743)=299424

177322*299424 (mod 3140743)=202113

 

 

1】《应用密码学:协议、算法与C源程序》,Bruce Schneier 著,吴世忠 祝世雄 张文政 等译,机械出版社,2000年

2】《量子计算和量子信息(一):量子计算部分》,Michael A. Nielsen, Isaac L. Chuang 著,赵千川 译,清华大学出版社,2003年

 

质数表

https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0%E8%A1%A8/7085686?fromtitle=%E7%B4%A0%E6%95%B0%E8%A1%A8&fromid=1240801&fr=aladdin

 

RSA算法

https://baike.baidu.com/item/RSA%E7%AE%97%E6%B3%95/263310?fromtitle=RSA&fromid=210678&fr=aladdin



关于我们
下载视频观看
联系方式
通信地址

北京市海淀区清华东路甲35号 北京912信箱 (100083)

电话

010-82304210/010-82305052(传真)

E-mail

semi@semi.ac.cn

交通地图
版权所有 中国科学院半导体研究所

备案号:京ICP备05085259号 京公网安备110402500052 中国科学院半导体所声明