|||
python或perl语言都提供了很方便的对大整数计算的功能,这在C或Fortran中不易实现,需调用相关的库或另编程序。
多年前听公开课,一位老师给学生讲电子商务安全,涉及到公钥密码,讲得生动,但没公式没具体的例子,总觉不合适,后来想想,找几个数做例子因涉及到大整数运算,可能还真有点难度。
有python或perl进行大数运算,就很容易了。
RSA加密算法是1977年Ron Rivest、Adi Shamir和Leonard Adleman一起提出的。所以别说数论或陈景润研究的没多大用,这就是最好的应用例证。
找两个大质数p、q,设n=p*q ,r=(p-1)*(q-1),
找e与r互质,且e<r
找d满足(d*e) mod r =1,(mod为取余)
(n,e) 就是公钥,(n,d)就是私钥,也可互换,
设M为明文整数 (把明文分解转换为小于n的数),C为密文
则加密过程为 C=M^e mod n
解密过程为 M=C^d mod n (^表示乘方运算)
一、不编程用python验证
设p=23,q=31,则n是23*31=713,r=(23-1)*(31-1)=660
设e=53,可找到一个d=137,(不想编程,用excel公式=MOD((A1*53),660))往下一拉就可找到(A列填自然数,B列写公式)。
则有(713,53),(713,137)为公钥和私钥。
如把公钥给对方,其对123加密:写123**53%713,加密结果为216。
用私钥解密:216**137%713,解密结果为123。
123**53是582064223547422878717064247856117219999744776198031672118462507358927240593089706379581941870601919048920591883。216*137更是一个大数。
二、用perl验证
同上例选23,31,找数d
>perl -e "foreach $d (1..1000){ print($d),last if 53*$d%660==1 }"
得出137。
对456加密及解密
D:>perl -Mbigint -e "print 456**53%713"
654
D:>perl -Mbigint -e "print 654**137%713"
456
其实23,37都是很小的素数,数字游戏,也挺有意思
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 08:54
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社