文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > RSA密码体制的安全性分析和算法实现
侵权投诉

RSA密码体制的安全性分析和算法实现

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,有此因子。

上一页第2页

你可能喜欢

  • RSA加密算法
  • 应用密码学
  • 开题报告
  • 中国剩余定理
  • 数字签名的应用
  • RSA算法
  • 密码算法

热门文档

相关文档

  • 【论文】RSA公钥密码体制的算法实现及其安全性分析

    RSA公钥密码体制的算法实现及其安全性分析_专业资料。本文阐述了公开密钥密码体制RSA算法的原理及实现技术,并对其进行了安全性分析,在此基础上,给出了RSA算法实现的具...

  • RSA加密算法的安全性分析

    RSA密码体制的实现及数字... 8页 免费RSA加密算法...RSA 加密算法的安全性分析* 肖媛媛 ( 潍坊学院, 山东 潍坊 261061) 摘要: ...

  • RSA密码算法体制的研究及其实现

    国防科学技术大学 硕士学位论文 RSA密码算法体制的研究及其实现 姓名:刘长军 申请学位级别:硕士 专业:信息与通信工程 指导教师:唐朝京;林嘉宇 2002.11.1 国防科学...

  • 公钥密码体制RSA安全分析及应用

    在阐述公钥密码体制RSA的算法原理和它的加密和解密算法的基础上,给出一个具体的...实现也变得越来越难以忍 受,这对RSA的应用带来了很重的负担,对进行大量安全 ...

  • 【论文】公钥密码RSA体制及安全性分析

    公钥密码RSA体制及安全性分析_专业资料。RSA算法是一种公钥密码算法。RSA是一个基于数论的非对称密码体制,RSA的安全性是依赖于大整数素因子分解的困难性问题。其经历...

  • 公钥密码体制(RSA)算法及安全性

    是 由其密钥的私密性来保证的; 而 RSA 则是一种公钥密码体制, 不仅加密算法本身可以公开, 甚至加密用的密钥也可 【摘 具体实现过程及安全性进行深入探讨和分析...

  • 开密码技术RSA算法的实现及保密性分析

    公钥密码体制RSA安全分析及... 3页 免费 大整数的分解 12页 免费 浅谈大数计算...开密码技术RSA算法的实现及保密性分析开密码技术RSA算法的实现及保密性分析隐藏>...

  • 浅析RSA算法的安全性

    1.3RsA公钥密码算法的实现 RSA运用两个指数e和d,这里e是公共的而d是私密的。...纰憋A安全性讨论RSA算法的体制构造是基于数论的欧拉定理.它的安全性依赖于大效...

  • RSA算法的安全性分析

    信息内容, 使非法用户无法获取 信息真实内容的一种手段 密钥, 是密码体制安全的...RSA算法的分析与实现 RSA算法的硬件实现 RSA算法应用及实现细节 RSA算法的一种快...

  • RSA算法的安全性分析

    RSA算法的安全性分析_专业资料。RSA算法的安全性分析在今天的信息社会里, 通信安全...密钥, 是密码体制安全的关键 . 公开密钥密码体制的产生主要是由于常规密钥密码...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email