RSA密码体制的安全性分析和算法实现
42
四川理工学院学报(自然科学版)2009年2月
善口,(modn)。在条件0≤口,b《厅一1下证明了唯一性。
引理3设P,q为两个不同的素数,几=Pq。若正整数。有
a
g
l,(rood4,(凡))
(6)
则任取正整数m,有
m4£m,rood(t/,)
(7)
其中咖(/7,)为欧拉函数,其值为从1到n和n互素的整
数的个数。
证
由条件(6)式可知口=s咖(n)+1,其中s为整
数。如果设(n,m)=1,由费马定理可知
m州神i
1,rood(,1)
(8)
于是
m4im岫¨)+1;m,rood(,1)
(9)
现在设(n,m)≠1且n
I
m,则显然n
m4一/7/,,即
m。;m,(modn)。如果设(//,,m)≠1且g/,除不尽m,由,l=Pq,P,q为素数,所以P
l
m,q除不尽tn或者qI
m,
p除不尽rti,。由厅的对称性,我们只证明pm,q除不尽
m这种情形。由q除不尽m有(q,m)=1,由费马定理可知:m+‘9’兰1,(modq)。注意到n=Pq,咖(71,)=咖(p)咖(g),则m坤‘“’“毒m,mod(q),即qI(m‘+‘“’”一m)。已设Pl
m,由(p,q)=1可知厅I(m州町”一m)。
2
RSA密码系统
给定两个不同的大素数P,q,记1/,=Pq,则咖(,})=咖(p)咖(9)=(p—1)(g—1)=
pg—P—q+1=n+1一P—q
(10)
由此式可知在知道站后,算出咖(忍)等价于算出了p或g,即将t/,作因式分解,所以我们自然地取//,为公钥,p和q为私钥。
现在任取Ⅱ∈{1,2,…,西(n)一l},使得(珏,咖(n))=1。于是存在秽∈{1,2,…,咖(n)一1},使得
比移耋1,(mod4,(乃))(11)
这样我们得到了t,。
加密方案为:任给明文m,0≤m≤//,,则密文为m“;mo,(modn)
(12)解密方案:在受到密文m。后,则mo…§m,(bmodn)
(13)证明如下:今m09毫m”,(bmodn),由式(11),聊=
s4,(,1)+1,其中s为整数。于是%”暑m”z∥町“,
(bmodn),由弓I理3可知,口=s4,(n)+l;l,(mod4)(n))。
所以证明了rIlft’Em,(bmodn),0≤m<n。
因此接收者获得明文m。
这时,发言人知道“,收信人知道t,。可以看出,这个数据移必须是绝对保密的。而数据Ⅱ即使让敌方知道也
没有关系。因为从M求出秽的办法是用式(11),而敌方不知西(n),便求不出口。由此可见,对于RSA密码体制,私钥为移,咖(n),公钥为“,n。注意到“,口可以随时更
万方数据
换,但是n不能随时更换。所以破译RSA密码体制的关
键是知道凡,且知道它是哪两个素数的乘积,如何来分
解因子。
目前公认最好的方法是用数域上的所谓指标方法,对于小于1001柏的整数,已能由比较快的方法分解因子。
但对于大于100200的正整数仍有相当困难。
3关于RSA密码体系安全性分析和简化计算的方法
(1),l=Pq,其中P和q为不同素因子,且P,q>
100140。因为如果P,q不足够大的话,我们可以通过计算机很快算出n的分解。
(2)I
P—q
I不可太小,否则通过计算机在而附近
搜索到P,q。但是IP—q
I也不宜太小,否则可能在0或
者n附近搜索出P,q。
(3)(P一1,g—1)越小越好,P一1和q一1都应有大素数因子。
(4)不能用两个互索的公钥n。,Ⅱ:将同一明文发给
两个不同的收信人。事实上,若将同一明文作出两个密
文m“EmO’,(modn),m“毒mo”,(modn),其中(Ⅱ1,“:)=1。敌方截获到密文m。’,m。”后,对公钥“。,“:先做推演。已知存在正整数伽1,∞2,使得训lMI+埘2吻=1,于是(m0’)”(m0“)“兰m”“““im,(bmodn),从而解出
明文。
(5)对公钥址的选取的要求。将私钥秽按II,进位写成
Ⅳ
秽=∑A;u‘
(14)
则A。,A1'...,AⅣ中等于零的个数越少越好。事实上,敌
方截获密文mo—m“,(modn),作mI;m矿”,(modn),.|}
=0,l,…。如果m0,m1,. 为循环序列,即存在正整数
Z,使得mf署m0,(modn),即m“…毒m“,(modn)。于是
m拙1“l
m“皇m,(modn),即(m“)“im,(modn),或
~
m。;m,(modn)。由此可见,若勘=∑A。址‘中只有一个互而
A;不等于零,则t,=H‘。所以如果A。,Al'.一,A。中不等于
零的A。的很多,则序列m。,ml’.~般不是循环序列。
(6)由加密方案和解密方案可知,要计算m“;m。,(modn)和IIlo。;m,(bmodn)都需要计算大方幂的乘积,
这是很浪费时间的,这是lISA密码体制的缺点。虽然已经想出了一些办法来简化计算的方法,但是实际工作量
还是很大。下面给出两种简化计算的方法。
(i)将Ⅱ写成二进制H=E
ai2‘,其中口;∈{o,
1},于是
m“=(m2。)~(m2’)4... (m2。)‘
(15)
即要计算m25心,(modn),0≤i≤s。这里当t2.‘=0,无
此因子;当a。=1,有此因子。
RSA公钥密码体制的算法实现及其安全性分析_专业资料。本文阐述了公开密钥密码体制RSA算法的原理及实现技术,并对其进行了安全性分析,在此基础上,给出了RSA算法实现的具...
RSA密码体制的实现及数字... 8页 免费RSA加密算法...RSA 加密算法的安全性分析* 肖媛媛 ( 潍坊学院, 山东 潍坊 261061) 摘要: ...
国防科学技术大学 硕士学位论文 RSA密码算法体制的研究及其实现 姓名:刘长军 申请学位级别:硕士 专业:信息与通信工程 指导教师:唐朝京;林嘉宇 2002.11.1 国防科学...
在阐述公钥密码体制RSA的算法原理和它的加密和解密算法的基础上,给出一个具体的...实现也变得越来越难以忍 受,这对RSA的应用带来了很重的负担,对进行大量安全 ...
公钥密码RSA体制及安全性分析_专业资料。RSA算法是一种公钥密码算法。RSA是一个基于数论的非对称密码体制,RSA的安全性是依赖于大整数素因子分解的困难性问题。其经历...
是 由其密钥的私密性来保证的; 而 RSA 则是一种公钥密码体制, 不仅加密算法本身可以公开, 甚至加密用的密钥也可 【摘 具体实现过程及安全性进行深入探讨和分析...
公钥密码体制RSA安全分析及... 3页 免费 大整数的分解 12页 免费 浅谈大数计算...开密码技术RSA算法的实现及保密性分析开密码技术RSA算法的实现及保密性分析隐藏>...
1.3RsA公钥密码算法的实现 RSA运用两个指数e和d,这里e是公共的而d是私密的。...纰憋A安全性讨论RSA算法的体制构造是基于数论的欧拉定理.它的安全性依赖于大效...
信息内容, 使非法用户无法获取 信息真实内容的一种手段 密钥, 是密码体制安全的...RSA算法的分析与实现 RSA算法的硬件实现 RSA算法应用及实现细节 RSA算法的一种快...
RSA算法的安全性分析_专业资料。RSA算法的安全性分析在今天的信息社会里, 通信安全...密钥, 是密码体制安全的关键 . 公开密钥密码体制的产生主要是由于常规密钥密码...
热门文档