![Board logo](images/default/logo.gif)
标题: [数值计算] 批处理求质数与批处理RSA算法 [打印本页]
作者: cjiabing 时间: 2012-2-25 21:36 标题: 批处理求质数与批处理RSA算法
本帖最后由 cjiabing 于 2012-2-27 12:10 编辑
质数,又称素数,指在一个大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数)。
比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
维基百科:http://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0
素数近来被利用在密码学上,所谓的公钥就是将想要传递的信息在编码时加入素数,编码之后传送给收信人,任何人收到此信息后,若没有此收信人所拥有的密钥,则解密的过程中(实为寻找素数的过程),将会因为找素数的过程(分解质因数)过久,使即使取得信息也会无意义。
百度百科:http://baike.baidu.com/view/1767.htm
一、用批处理找出 1000 以内的素数!~
可以用排除法,从2开始找往上找,1000/2=500, 如果能被2整除就排除掉,如果被3整除就排除掉,……,直到剩下的都不被其他数整除。
可以用余数来判断,有余数的可能是素数,但还要进一步分析,可我不熟悉批处理这个余数到底是怎么回事,跟理解的有出入。
1000以内质数表
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 (168个)
二、RSA算法——请试用批处理来演示RSA算法?
RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在(美国麻省理工学院)开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的所有密码攻击,已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但那时想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。
22、21楼有演算介绍。
素数与密码的算法:http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
详细:http://blog.csdn.net/fireseed/article/details/327444
百度百科:http://baike.baidu.com/view/7520.htm
作者: QIAOXINGXING 时间: 2012-2-25 22:46
本帖最后由 QIAOXINGXING 于 2012-2-26 13:44 编辑
- @echo off&setlocal enabledelayedexpansion&cd /d "%~dp0"
- set "n=0"
- for /l %%i in (2 1 1000) do (
- set "a=%%i"
- set /a "b=a/2+1"
- if !b! gtr 32 set /a "b=32"
- call :1
- if "!c!"=="!b!" set /a "n+=1"&echo !n!:!a!
- )
- pause
- :1
- for /l %%a in (2 1 !b!) do (
- set "c=%%a"
- set /a "d=a%%c"
- if "!d!"=="0" goto :eof
- )
复制代码
作者: find 时间: 2012-2-25 22:48
http://www.bathome.net/thread-53-1-1.html
http://www.bathome.net/thread-2372-1-1.html
http://www.bathome.net/thread-11449-1-1.html
http://www.bathome.net/thread-3635-1-1.html
作者: ivor 时间: 2012-2-26 02:23
说实话我还不知道怎么利用素数用与密码
作者: Demon 时间: 2012-2-26 10:15
- Input: an integer n > 1
-
- Let A be an array of Boolean values, indexed by integers 2 to n,
- initially all set to true.
-
- for i = 2, 3, 4, ..., while i ≤ n/2:
- if A[i] is true:
- for j = 2i, 3i, 4i, ..., while j ≤ n:
- A[j] = false
-
- Now all i such that A[i] is true are prime.
复制代码
作者: cjiabing 时间: 2012-2-26 11:11
回复 4# ivor
谢谢大家!~我正在弄,把普通字符翻译成素数,然后将素数的解因子做成密钥,就可以成为密码了!~
想了一个晚上哦。
作者: applba 时间: 2012-2-26 11:13
本帖最后由 applba 于 2012-2-27 19:03 编辑
- @echo off
- SETLOCAL EnablEdElayEdExpansion
-
- for /l %%a in (3,1,100) do (
- set /a flag=1
- set /a n=%%a-1
- for /l %%A in (2,1,!n!) do (
- set /a r=%%a %% %%A
- if !r! equ 0 ( set /a flag=0 )
- )
- if !flag! equ 1 set "s=!s! %%a"
- )
- echo %s%
- pause
复制代码
作者: cjiabing 时间: 2012-2-26 12:25
RSA算法,要进行幂运算,数学盲,还是等plp626来解决算了!~
作者: find 时间: 2012-2-26 15:42
回复 8# cjiabing
初中数学课本上就已经有幂运算了吧
作者: jinzeyu 时间: 2012-2-26 15:58
本帖最后由 jinzeyu 于 2012-2-26 19:38 编辑
- @echo off&setlocal enabledelayedexpansion&echo 2 是质数&(for /l %%a in (3,2,1000) do call:1 %%a)&echo 计算完成&pause>nul&exit
- :1
- set a=32&if %1 lss 32 set /a a=%1-1
- for /l %%b in (3,2,!a!) do (
- set /a i=%1%%%%b
- if "!i!"=="0" (set $%1=.&goto 2)
- )
- :2
- if not defined $%1 echo %1 是质数
复制代码
作者: RuiIsRui 时间: 2012-2-26 16:19
本帖最后由 RuiIsRui 于 2012-2-26 20:42 编辑
11 以下的5个数不在............我是写来算6位质数的,改给你用了- @echo off&setlocal Enabledelayedexpansion
- set/a MinShu=10
- set/a MaxShu=1000
- set/a N=0
- for /l %%i in (%MinShu%,1,%MaxShu%) do (
- set/a JShu=%%i
- call:AA
- )
- echo %MinShu% ~ %MaxShu% 有 %N% 个质数
- pause
- exit
- :AA
-
- for %%i in (2,3,5,7,11) do (
- set/a b=%JShu%%%%%i
- if "!b!"=="0" GOTO:eof
- )
-
- set/a MinShu2=%JShu%/10
- for /l %%i in (12,1,%MinShu2%) do (
- set/a d=%JShu%%%%%i
- if "!d!"=="0" GOTO:eof
- )
- echo 质数%N%.素数:%JShu%
- set/a N+=1
- GOTO:eof
复制代码
作者: cjiabing 时间: 2012-2-26 16:38
回复 9# find
谢谢您的链接!我的都忘记搜索了。
有跟学跟学会跟还记得的关系可没有多大的关联了,特别是用批处理来表达幂,这种体力活还是留给专业的plp626合适!~
作者: cjiabing 时间: 2012-2-26 16:47
回复 7# applba
结果是- 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57
- 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
复制代码
9能被3除不属于素数。
作者: cjiabing 时间: 2012-2-26 16:49
回复 10# jinzeyu
后面的应该对,但开头被你漏掉好多个了:
-
- 2 是质数
- 37 是质数
- 41 是质数
- 43 是质数
- 47 是质数
复制代码
作者: cjiabing 时间: 2012-2-26 16:55
回复 11# RuiIsRui
你的没有看见前面几个呢- 质数0.素数:13
- 质数1.素数:17
- 质数2.素数:19
- 质数3.素数:23
- 质数4.素数:29
- 质数5.素数:31
- 质数6.素数:37
复制代码
作者: jinzeyu 时间: 2012-2-26 18:03
本帖最后由 jinzeyu 于 2012-2-26 19:37 编辑
回复 14# cjiabing
哦 抱歉 代码写错了
下面是正确代码- @echo off&setlocal enabledelayedexpansion&echo 2 是质数&(for /l %%a in (3,2,1000) do call:1 %%a)&echo 计算完成&pause>nul&exit
- :1
- set a=32&if %1 lss 32 set /a a=%1-1
- for /l %%b in (3,2,!a!) do (
- set /a i=%1%%%%b
- if "!i!"=="0" (set $%1=.&goto 2)
- )
- :2
- if not defined $%1 echo %1 是质数
复制代码
作者: cjiabing 时间: 2012-2-26 19:15
回复 16# jinzeyu
还是不行,还有:33 不是质数,35 不是质数
你用2、3、和5来作为最基本的除数来处理。质数或素数是一个不被其他整数整除的,33能被3整除,所以不是。
作者: jinzeyu 时间: 2012-2-26 19:37
回复 17# cjiabing
额
下面的再帮忙看看......- @echo off&setlocal enabledelayedexpansion&echo 2 是质数&(for /l %%a in (3,2,1000) do call:1 %%a)&echo 计算完成&pause>nul&exit
- :1
- set a=32&if %1 lss 32 set /a a=%1-1
- for /l %%b in (3,2,!a!) do (
- set /a i=%1%%%%b
- if "!i!"=="0" (set $%1=.&goto 2)
- )
- :2
- if not defined $%1 echo %1 是质数
复制代码
作者: cjiabing 时间: 2012-2-26 20:15
回复 18# jinzeyu
嗯,不错,这回对了。
作者: RuiIsRui 时间: 2012-2-26 20:16
本帖最后由 RuiIsRui 于 2012-2-26 20:33 编辑
- @echo off&setlocal Enabledelayedexpansion
-
- set/a MinShu=2
- set/a MaxShu=1000
- set/a N=0
- for /l %%i in (%MinShu%,1,%MaxShu%) do (
- set/a JShu=%%i
- call:AA
- )
- echo %MinShu% ~ %MaxShu% 有 %N% 个质数
- pause
- exit
- :AA
-
- set/a MinShu2=%JShu%/2
- for /l %%i in (2,1,%MinShu2%) do (
- set/a d=%JShu%%%%%i
- if "!d!"=="0" GOTO:eof
- )
- echo 质数%N%.素数:%JShu%
- set/a N+=1
- GOTO:eof
复制代码
回复 15# cjiabing
哎哟........我那样写是为了我算6位7位时能快捷一点嘛...
作者: cjiabing 时间: 2012-2-26 20:31
回复 20# RuiIsRui
本版规则
1、求代码、寻求代码解释、探讨代码得失的帖子均可发在本版块;
2、标题或顶楼内容模糊(未说明代码功能或问题所在)的帖子一律关闭;
3、请使用 code 标记把代码部分括起来(选中代码后,单击回复框的 <> 按钮),以便复制;
4、求助时,务必在顶楼一次性把问题交代清楚,建议给出有针对性的样本;
5、问题解决后,请编辑顶楼帖子在标题前面注明[已解决],并给回答者加分。(所加的分数由论坛供应)
绿色通道
如何编辑帖子、评分、加 code 以及怎样搜索: 批处理之家论坛使用常见问题FAQ
作者: RuiIsRui 时间: 2012-2-26 20:36
回复 21# cjiabing
大侠,帮帮我这个嘛,我的vbs实在是菜到家了..
http://www.bathome.net/thread-15644-1-1.html
作者: cjiabing 时间: 2012-2-26 20:57 标题: 批处理实现RSA算法——RSA算法的基本原理
本帖最后由 cjiabing 于 2012-2-26 21:44 编辑
转载个文章,并做阅读批注,方便大家阅读和理解。
1、在RSA算法中,我们先要获得两个不同的质数P和Q做为算法因子。
2、再找出一个正整数E,使得E与 ( P - 1 ) * ( Q - 1 ) 的值互质,这个E就是私钥。
3、找到一个整数D,使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立,D就是公钥1。
4、设N为P和Q的乘积,N则为公钥2。
5、加密时先将明文转换为一个或一组小于N的整数I,并计算ID mod N的值M,M就密文。
6、解密时将密文ME mod N,也就是M的E次方再除以N所得的余数就是明文。
7、因为私钥E与( P - 1 ) * ( Q - 1 )互质,而公钥D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N,如果想要得到E,必须得出( P - 1 ) * ( Q - 1 ),因而必须先对N进行因数分解。如果N很大那么因数分解就会非常困难,所以要提高加密强度P和Q的数值大小起着决定性的因素。一般来讲当P和Q都大于2128时,按照目前的机算机处理速度破解基本已经不大可能了。
1978年
RSA加密算法是最常用的非对称加密算法,CFCA在证书服务中离不了它。但是有不少新来的同事对它不太了解,恰好看到一本书中作者用实例对它进行了简化而生动的描述,使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读,希望能够对时间紧张但是又想了解它的同事有所帮助。
RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名,这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这恰恰说明该算法有一定的可信性,目前它已经成为最流行的公开密钥算法。
RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。
RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表:
可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解RSA加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到:
一、什么是“素数”?
素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。
二、什么是“互质数”(或“互素数”)?
小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”这里所说的“两个数”是指自然数。
判别方法主要有以下几种(不限于此):
(1)两个质数一定是互质数。例如,2与7、13与19。
(2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与 26。
(3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。
(4)相邻的两个自然数是互质数。如 15与 16。
(5)相邻的两个奇数是互质数。如 49与 51。
(6)大数是质数的两个数是互质数。如97与88。
(7)小数是质数,大数不是小数的倍数的两个数是互质数。如 7和 16。
(8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,这两个数为互质数。等等。
三、什么是模指数运算?
指数运算谁都懂,不必说了,先说说模运算。模运算是整数运算,有一个整数m,以n为模做模运算,即m mod n。怎样做呢?让m去被n整除,只取所得的余数作为结果,就叫做模运算。例如,10 mod 3=1;26 mod 6=2;28 mod 2 =0等等。
——实际上模运算简称为除法取余运算可能比较好理解,不过批处理对除法的运算刚好反其道而行,它不取余而是去掉余数!~
模指数运算就是先做指数运算,取其结果再做模运算。如
好,现在开始正式讲解RSA加密算法。
算法描述:
(1)选择一对不同的、足够大的素数p,q。
复制代码
(2)计算n=pq。
复制代码
(3)计算f(n)=(p-1)(q-1),同时对p, q严加保密,不让任何人知道。
- f(n)=(23-1)*(29-1)=22*28=616
复制代码
(4)找一个与f(n)互质的数e,且1<e<f(n)。
- 与616互质并小于616的数E为:615——相邻的两个自然数是互质数。
- 这个数作为密码的私钥。
- 其实,用f(n)-1即可得到E。这个f(n)实际上用n表示就可以了——数学盲的人可以这样理解。
- 与其相邻的质素:607 、613 、617 、619 、631
复制代码
(5)计算d,使得de≡1 mod f(n)。这个公式也可以表达为d ≡e-1 mod f(n)
这里要解释一下,≡是数论中表示同余的符号。公式中,≡符号的左边必须和符号右边同余,也就是两边模运算结果相同。显而易见,不管f(n)取什么值,符号右边1 mod f(n)的结果都等于1;符号的左边d与e的乘积做模运算后的结果也必须等于1。这就需要计算出d的值,让这个同余等式能够成立。
(6)公钥KU=(e,n),私钥KR=(d,n)。
(7)加密时,先将明文变换成0至n-1的一个整数M。若明文较长,可先分割成适当的组,然后再进行交换。设密文为C,则加密过程为:。
(8)解密过程为:。
实例描述:
在这篇科普小文章里,不可能对RSA算法的正确性作严格的数学证明,但我们可以通过一个简单的例子来理解RSA的工作原理。为了便于计算。在以下实例中只选取小数值的素数p,q,以及e,假设用户A需要将明文“key”通过RSA加密后传递给用户B,过程如下:
(1)设计公私密钥(e,n)和(d,n)。
- 令:p=3 q=11
- 得:n=p×q=3×11=33;
- f(n)=(p-1)(q-1)=2×10=20;
- 取e=3 (3与20互质)
- 则e×d≡1 mod f(n)
- 即3×d≡1 mod 20。
复制代码
d怎样取值呢?可以用试算的办法来寻找。试算结果见下表:
通过试算我们找到,当d=7时,e×d≡1 mod f(n)同余等式成立。
复制代码
因此,可令d=7。从而我们可以设计出一对公私密钥,加密密钥(公钥)为:KU =(e,n)=(3,33),解密密钥(私钥)为:KR =(d,n)=(7,33)。
(2)英文数字化。
将明文信息数字化,并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值,即:
则得到分组后的key的明文信息为:11,05,25。
(3)明文加密
用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡Me(mod n)得:
因此,得到相应的密文信息为:11,31,16。
(4)密文解密。
用户B收到密文,若将其解密,只需要计算M= Cd(mod n),即:
用户B得到明文信息为:11,05,25。根据上面的编码表将其转换为英文,我们又得到了恢复后的原文“key”。
你看,它的原理就可以这么简单地解释!
当然,实际运用要比这复杂得多,由于RSA算法的公钥私钥的长度(模长度)要到1024位甚至2048位才能保证安全,因此,p、q、e的选取、公钥私钥的生成,加密解密模指数运算都有一定的计算程序,需要仰仗计算机高速完成。
最后简单谈谈RSA的安全性
首先,我们来探讨为什么RSA密码难于破解?
在RSA密码应用中,公钥KU是被公开的,即e和n的数值可以被第三方窃听者得到。破解RSA密码的问题就是从已知的e和n的数值(n等于pq),想法求出d的数值,这样就可以得到私钥来破解密文。从上文中的公式:d ≡e-1 (mod((p-1)(q-1)))或de≡1 (mod((p-1)(q-1))) 我们可以看出。密码破解的实质问题是:从Pq的数值,去求出(p-1)和(q-1)。换句话说,只要求出p和q的值,我们就能求出d的值而得到私钥。
当p和q是一个大素数的时候,从它们的积pq去分解因子p和q,这是一个公认的数学难题。比如当pq大到1024位时,迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。因此,RSA从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。
然而,虽然RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。
此外,RSA的缺点还有:A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。B)分组长度太大,为保证安全性,n 至少也要 600 bits 以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。因此,使用RSA只能加密少量数据,大量的数据加密还要靠对称密码算法。
作者: cjiabing 时间: 2012-2-27 12:09
本帖最后由 cjiabing 于 2012-2-27 12:21 编辑
推荐:十分简明:http://www.cnblogs.com/midea0978/articles/65244.html
来自:http://www.xfocus.net/articles/200503/778.html
RSA算法基础->实践
讲讲自己学习RSA中的实践过程,已经对RSA熟悉的看家就不用在此浪费时间了。
<一>基础
RSA算法非常简单,概述如下:
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e<t并且e与t互素(就是最大公因数为1)
取d*e%t==1
这样最终得到三个数: n d e
设消息为数M (M <n)
设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则 m == M,从而完成对c的解密。
注:**表示次方,上面两式中的d和e可以互换。
在对称加密中:
n d两个数构成公钥,可以告诉别人;
n e两个数构成私钥,e自己保留,不让任何人知道。
给别人发送的信息使用e加密,只要别人能用d解开就证明信息是由你发送的,构成了签名机制。
别人给你发送信息时使用d加密,这样只有拥有e的你能够对其解密。
rsa的安全性在于对于一个大数n,没有有效的方法能够将其分解
从而在已知n d的情况下无法获得e;同样在已知n e的情况下无法
求得d。
<二>实践
接下来我们来一个实践,看看实际的操作:
找两个素数:
p=47
q=59
这样
n=p*q=2773
t=(p-1)*(q-1)=2668
取e=63,满足e<t并且e和t互素
用perl简单穷举可以获得满主 e*d%t ==1的数d:
C:\Temp>perl -e "foreach $i (1..9999){ print($i),last if $i*63%2668==1 }"
847
即d=847
最终我们获得关键的
n=2773
d=847
e=63
取消息M=244我们看看
加密:
c=M**d%n = 244**847%2773
用perl的大数计算来算一下:
C:\Temp>perl -Mbigint -e "print 244**847%2773"
465
即用d对M加密后获得加密信息c=465
解密:
我们可以用e来对加密后的c进行解密,还原M:
m=c**e%n=465**63%2773 :
C:\Temp>perl -Mbigint -e "print 465**63%2773"
244
即用e对c解密后获得m=244 , 该值和原始信息M相等。
<三>字符串加密
把上面的过程集成一下我们就能实现一个对字符串加密解密的示例了。
每次取字符串中的一个字符的ascii值作为M进行计算,其输出为加密后16进制
的数的字符串形式,按3字节表示,如01F
代码如下:
#!/usr/bin/perl -w
#RSA 计算过程学习程序编写的测试程序
#watercloud 2003-8-12
#
use strict;
use Math::BigInt;
my %RSA_CORE = (n=>2773,e=>63,d=>847); #p=47,q=59
my $N=new Math::BigInt($RSA_CORE{n});
my $E=new Math::BigInt($RSA_CORE{e});
my $D=new Math::BigInt($RSA_CORE{d});
print "N=$N D=$D E=$E\n";
sub RSA_ENCRYPT
{
my $r_mess = shift @_;
my ($c,$i,$M,$C,$cmess);
for($i=0;$i < length($$r_mess);$i++)
{
$c=ord(substr($$r_mess,$i,1));
$M=Math::BigInt->new($c);
$C=$M->copy(); $C->bmodpow($D,$N);
$c=sprintf "%03X",$C;
$cmess.=$c;
}
return \$cmess;
}
sub RSA_DECRYPT
{
my $r_mess = shift @_;
my ($c,$i,$M,$C,$dmess);
for($i=0;$i < length($$r_mess);$i+=3)
{
$c=substr($$r_mess,$i,3);
$c=hex($c);
$M=Math::BigInt->new($c);
$C=$M->copy(); $C->bmodpow($E,$N);
$c=chr($C);
$dmess.=$c;
}
return \$dmess;
}
my $mess="RSA 娃哈哈哈~~~";
$mess=$ARGV[0] if @ARGV >= 1;
print "原始串:",$mess,"\n";
my $r_cmess = RSA_ENCRYPT(\$mess);
print "加密串:",$$r_cmess,"\n";
my $r_dmess = RSA_DECRYPT($r_cmess);
print "解密串:",$$r_dmess,"\n";
#EOF
测试一下:
C:\Temp>perl rsa-test.pl
N=2773 D=847 E=63
原始串:RSA 娃哈哈哈~~~
加密串:5CB6CD6BC58A7709470AA74A0AA74A0AA74A6C70A46C70A46C70A4
解密串:RSA 娃哈哈哈~~~
C:\Temp>perl rsa-test.pl 安全焦点(xfocus)
N=2773 D=847 E=63
原始串:安全焦点(xfocus)
加密串:3393EC12F0A466E0AA9510D025D7BA0712DC3379F47D51C325D67B
解密串:安全焦点(xfocus)
<四>提高
前面已经提到,rsa的安全来源于n足够大,我们测试中使用的n是非常小的,根本不能保障安全性,
我们可以通过RSAKit、RSATool之类的工具获得足够大的N 及D E。
通过工具,我们获得1024位的N及D E来测试一下:
n=0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005D
BDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B
47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2
BC511951
d=0x10001
e=0xE760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C2995
4C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2
C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B
1965
设原始信息
M=0x11111111111122222222222233333333333
完成这么大数字的计算依赖于大数运算库,用perl来运算非常简单:
A) 用d对M进行加密如下:
c=M**d%n :
C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x11111111111122222222222233
333333333, 0x10001, 0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5F
CD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F0
17F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD6
0438941D2ED173CCA50E114705D7E2BC511951);print $x->as_hex"
0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd
45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b
3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91
f1834580c3f6d90898
即用d对M加密后信息为:
c=0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd
45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b
3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91
f1834580c3f6d90898
B) 用e对c进行解密如下:
m=c**e%n :
C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x17b287be418c69ecd7c39227ab
681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3
866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb4764414
65f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898, 0xE760A
3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D
86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF
2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A
592D2B1965, 0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90
B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF
1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941
D2ED173CCA50E114705D7E2BC511951);print $x->as_hex"
0x11111111111122222222222233333333333
(我的P4 1.6G的机器上计算了约5秒钟)
得到用e解密后的m=0x11111111111122222222222233333333333 == M
C) RSA通常的实现
RSA简洁幽雅,但计算速度比较慢,通常加密中并不是直接使用RSA 来对所有的信息进行加密,
最常见的情况是随机产生一个对称加密的密钥,然后使用对称加密算法对信息加密,之后用
RSA对刚才的加密密钥进行加密。
最后需要说明的是,当前小于1024位的N已经被证明是不安全的
自己使用中不要使用小于1024位的RSA,最好使用2048位的。
作者: applba 时间: 2012-2-27 18:59
回复 13# cjiabing
瀑布汗哟。笔误呢。
for /l %%A in (2,2,!n!)
实为
for /l %%A in (2,1,!n!)
你再试试。
作者: cjiabing 时间: 2012-2-27 21:27
回复 25# applba
嗯,对了,不过效率低了点!
作者: cjiabing 时间: 2012-2-27 21:36
回复 22# RuiIsRui
我连VB都不懂呢!~
作者: batman 时间: 2012-2-28 10:25
本帖最后由 batman 于 2012-2-28 10:27 编辑
建议cjiabing去参看一下论坛挑战区的批处理验证哥德赫猜想一帖
作者: cjiabing 时间: 2012-2-28 22:49
回复 28# batman
啊,哥啊?批嫩做吗?
作者: powerbat 时间: 2012-2-28 22:53
不要把算法和语言混为一谈。。。
作者: garyng 时间: 2012-3-2 11:47
RSA算法类似这个的?- @ECHO OFF
- SETLOCAL ENABLEDELAYEDEXPANSION
- SET PRIME=2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
- SET CHARS=a b c d e f g h i j k l m n o p q r s t u v w x y z
- SET PASSWORDVALUE=1
- SET INPUT=
- SET /P INPUT=Insert password:
- IF "%INPUT%"=="" "%~0"
- ECHO Authenticating...
- :OVERLOOP
- SET CURRENTPOSITION=0
- :SUBLOOP
- IF /I "!INPUT:~%CHARACTERPOSITION%,1!"=="!CHARS:~%CURRENTPOSITION%,1!" SET /A PASSWORDVALUE*=!PRIME:~%CURRENTPOSITION%,3!
- SET /A CURRENTPOSITION+=3
- IF NOT %CURRENTPOSITION%==78 GOTO :SUBLOOP
- SET /A CHARACTERPOSITION+=1
- IF NOT "!INPUT:~%CHARACTERPOSITION%,1!"=="" GOTO :OVERLOOP
- :END
- ENDLOCAL&IF NOT %PASSWORDVALUE%==1065435274 GOTO :ACCESSDENIED
- ECHO You have been authenticated. Welcome aboard!
- GOTO :SILENTPAUSE
- :ACCESSDENIED
- ECHO Access denied!
- :SILENTPAUSE
- PAUSE > NUL
复制代码
作者: andycker 时间: 2022-10-2 00:00
学习了,你写的不错
欢迎光临 批处理之家 (http://bathome.net./) |
Powered by Discuz! 7.2 |