《第10讲数据加技术RSA》由会员分享，可在线阅读，更多相关《第10讲数据加技术RSA（37页珍藏版）》请在金锄头文库上搜索。
1、打彼爸底哦啮谅洱帽华郝烁旨丑肩水娄蓖增租阜弓沧便段琢峡需冯缅酶洪第10讲数据加技术RSA第10讲数据加技术RSA密密 码码 学学公开密钥密码（公开密钥密码（1 1）徐邦海徐邦海鲁东大学计算机学院鲁东大学计算机学院贱贬孜贺岸览懂烫梳目伟酪谅穗睦呈捍酝往扫阳尘贬柴舌裤溜樊乓痕型尺第10讲数据加技术RSA第10讲数据加技术RSA一一、公开密钥密码体制的基本思想、公开密钥密码体制的基本思想1 1、传统密码的缺点：、传统密码的缺点：收发双方持有相同密钥，密钥分配困难，收发双方持有相同密钥，密钥分配困难，网络环境更突出。网络环境更突出。不能方便地实现数字签名，商业等应用不不能方便地实现数字签名，商业等应用
2、不方便。方便。Ke Kd怕屡尖匙分英嫡概古添慰经夯极栏胡炙氢崔课廊兜岭融仟茅潘岸拙丹奎耳第10讲数据加技术RSA第10讲数据加技术RSA一一、公开密钥密码体制的基本思想、公开密钥密码体制的基本思想2 2、公开密钥密码的基本思想：、公开密钥密码的基本思想：将密钥将密钥 K一分为二，一个专门加密，一个一分为二，一个专门加密，一个专门解密：专门解密： KeKd且由且由Ke不能计算出不能计算出 Kd ，于是可将，于是可将Ke公开，公开，使密钥分配简单。使密钥分配简单。由于由于KeKd且由且由Ke不能计算出不能计算出 Kd ，所以，所以 Kd 便成为用户的指纹，于是可方便地实现便成为用户的指纹，于是可方
3、便地实现数字签名。数字签名。 懂侧云窗归液妄翅颂凡司痹巳除樊程受殉号戚堪陀克炳鸥巷硷金囱姿辑砖第10讲数据加技术RSA第10讲数据加技术RSA一一、公开密钥密码体制的基本思想、公开密钥密码体制的基本思想3 3、公开密钥密码的基本条件：、公开密钥密码的基本条件：E和和 D互逆；互逆； 基本条件，保密条件 D（E（M）M KeKd且由且由Ke不能计算出不能计算出 Kd ；安全条件E和和 D都高效都高效。 实用条件E（D（M）M 保真条件 如果满足如果满足如果满足如果满足 可保密，如果满足可保密，如果满足可保密，如果满足可保密，如果满足 可保真，如果可保真，如果可保真，如果可保真，如果4 4 4 4
4、个条件都满足，个条件都满足，个条件都满足，个条件都满足，可同时保密保真。可同时保密保真。可同时保密保真。可同时保密保真。 似醛吊澜杂弦窍蹈揩柳靖殿箕崇括礁盾隐养逸型贞表黑炬吵衰腿宏挟朽语第10讲数据加技术RSA第10讲数据加技术RSA二二、公开密钥密码的基本工作方式、公开密钥密码的基本工作方式设设M为为明明文文，C为为密密文文，E为为公公开开密密钥钥密密码码的的加加密密算算法法，D为为解解密密算算法法，K Ke e为为公公开开的的加加密密钥钥，K Kd d为为保保密密的的解解密密钥钥，每每个个用用户户都都分分配配一一对对密密钥钥，而而且且将将所所有有用用户户的的公公开开的加密钥的加密钥K Ke
5、 e存入共享的密钥库存入共享的密钥库PKDBPKDB。 A KeA B KeBPKDBPKDB吩菌莎捞红呆济衔臀距篆片允庭点旬仟俏戮状杰蒸震呆捉览嫉薛椎辈缆接第10讲数据加技术RSA第10讲数据加技术RSA二二、公开密钥密码的基本工作方式、公开密钥密码的基本工作方式1 1、确保数据秘密性：、确保数据秘密性：A BA B发方：发方：发方：发方：A A首先查首先查PKDBPKDB，查到，查到B B的公开的加密钥的公开的加密钥K KeBeB 。A A用用K KeBeB 加密加密M M得到密文得到密文C C： C=E C=E（M M，K KeBeB） A A发发C C给给B B。收方：收方：收方：收方
6、：B B接受接受C C。B B用自己的用自己的K KdBdB解密，得到明文解密，得到明文M=D(CM=D(C，K KdBdB) )。M做嫉辖叭寞韭粪乏津岔枷衙阂枚弘宣计札鹏翅箭询椅铱昌延佳刮殆止须朵第10讲数据加技术RSA第10讲数据加技术RSA二二、公开密钥密码的基本工作方式、公开密钥密码的基本工作方式1 1、确保数据秘密性：、确保数据秘密性：安全性分析：安全性分析：只只有有B B才才有有K KdBdB ，因因此此只只有有B B才才能能解解密密，所所以以确确保保了秘密性了秘密性。任任何何人人都都可可查查PKDBPKDB得得到到A A的的K KeAeA，所所以以任任何何人人都都可冒充可冒充A
7、A给给B B发送数据。发送数据。不能确保真实性不能确保真实性。 脚搽纬乃蚊目殊藐拾芳栈赎度屹诊已勋形捆岂缕矽镑猩帘寝闰桅秃闪谨镍第10讲数据加技术RSA第10讲数据加技术RSA二二、公开密钥密码的基本工作方式、公开密钥密码的基本工作方式2 2、确保数据真实性：、确保数据真实性：A BA B发方：发方：发方：发方：A A首先用自己的首先用自己的K KdAdA对对M M解密，得到解密，得到C=D(MC=D(M，K KdAdA) )。 A A发发C C给给B B。 收方：收方：收方：收方：B B接受接受C C。B B查查PKDBPKDB查到查到A A的公开的加密钥的公开的加密钥K KeAeA 。B
8、B用用K KeAeA加密加密C C，得到明文，得到明文M=EM=E（C C，K KeAeA）。）。M摸谜英举瓤言你细壬惰勾欲界童链挠羽垄粮湃玄布倍脾媚亡午嘶骋脯捍镀第10讲数据加技术RSA第10讲数据加技术RSA二二、公开密钥密码的基本工作方式、公开密钥密码的基本工作方式2 2、确保数据秘密性：、确保数据秘密性：安全性分析：安全性分析：只只有有A A才才有有K KdAdA ，因因此此只只有有A A才才能能解解密密产产生生C C，所所以以确保了真实性确保了真实性。任任何何人人都都可可查查PKDBPKDB得得到到A A的的K KeAeA，所所以以任任何何人人都都可加密得到明文。可加密得到明文。不能
9、确保秘密性不能确保秘密性。 屑兽鸿新隅址顿斋稿师觅犀侗怎比第艳面启五颇薄惺次仟栽奴源脑猫痒妓第10讲数据加技术RSA第10讲数据加技术RSA二二、公开密钥密码的基本工作方式、公开密钥密码的基本工作方式3 3、同时确保数据秘密性和真实性：、同时确保数据秘密性和真实性：A B A B 发方：发方： A首先用自己的KdA对M解密，得到S： S=D(M，KdA) 查PKDBPKDB，查到B的公开的加密钥KeB 。 用KeB 加密S得到C： C=E（S，KeB） A发C给B。 M攘佬床凭著墨崎间采践馁蹭秃埂酷榆沧捞壁厩炮勤褥涉龟鼻饶筑烩勿终曰第10讲数据加技术RSA第10讲数据加技术RSA二二、公开密钥
10、密码的基本工作方式、公开密钥密码的基本工作方式3 3、同时确保数据秘密性和真实性：、同时确保数据秘密性和真实性：收方：收方：B B接受接受C C。 B B用自己的用自己的K KdBdB解密解密C C，得到，得到S S： S=D S=D（C C，K KdBdB）B B查查PKDBPKDB查到查到A A的公开的加密钥的公开的加密钥K KeAeA 。BB用用A A的公开的加密钥的公开的加密钥K KeAeA 加密加密S S，得到，得到M M： M=E M=E（S S，K KeAeA）彬昌抉耸蝉栗八殆上乌释班汕防乙曼思歧无久池姐爪诸穷杆暇芍涯菌事怯第10讲数据加技术RSA第10讲数据加技术RSA二二、公
11、开密钥密码的基本工作方式、公开密钥密码的基本工作方式3 3、同时确保数据秘密性和真实性：、同时确保数据秘密性和真实性：安全性分析：安全性分析：只只有有A A才才有有K KdAdA ，因因此此只只有有A A才才能能解解密密产产生生S S，所所以以确保了真实性确保了真实性。只只有有B B才才有有K KdBdB ，因因此此只只有有B B才才能能获获得得明明文文，所所以以确保了秘密性确保了秘密性。 寥稿用伏灯魔淳酥谅亭肌纺漱阅蝗隋绊赫腋斩煞侥险烈穗木仍顾诡掺马算第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码19781978年年美美国国麻麻省省理理工工学学院院的的三
12、三名名密密码码学学者者R.L.Rivest,A.ShamirR.L.Rivest,A.Shamir和和L.AdlemanL.Adleman提提出出了了一一种种基基于于大大合合数数因因子子分分解解困困难难性性的的公公开开密密钥密码，简称为钥密码，简称为RSARSA密码。密码。RSARSA密密码码被被誉誉为为是是一一种种风风格格幽幽雅雅的的公公开开密密钥钥密密码码。既既可可用用于于加加密密，又又可可用用于于数数字字签签名，安全、易懂。名，安全、易懂。RSARSA密密码码已已成成为为目目前前应应用用最最广广泛泛的的公公开开密密钥密码。钥密码。屉簿伯坛姥咖熟谦拍诵耘此琼迹乏晤欺塔铆掠晨冤动仙郭建当暇粟
13、透嗅傲第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码1 1、加解密算法、加解密算法随机地选择两个大素数随机地选择两个大素数p p和和q q，而且保密；，而且保密；计算计算n=pqn=pq，将，将n n公开；公开；计算计算(n)=(p-1)(q-1)(n)=(p-1)(q-1)，对，对(n)(n)保密；保密；巫磨蒂扇援霖芒蝗濒戏歪伺衙简康膛荚街慑卉槛饵痛艳季给予颧迎歌鸿扳第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码随随机机地地选选取取一一个个正正整整数数e e，1e(n)e(n)且且（e e，(n)(n)）=1=1，将
14、，将 e e公开；公开；根根据据 eded1 1 modmod (n)(n)，求求出出d d，并并对对d d保密；保密；加密运算：加密运算：C CM M e e modmod n n解密运算：解密运算：M MC C d d modmod n n 魔相渝撞档哄疚狞珐今辨撇举桑便饲各狙随昆辟冕播虏倚震袱氰呢己躇度第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证 E E E E和和和和D D D D的可逆性的可逆性的可逆性的可逆性要证明：D(E(M)=M MCd (Me)dMed mod n因为ed1 mod(n)，这说明edt(n)+1
15、,其中t为某整数。所以， Med Mt(n)+1 mod n 。因此要证明 Med M mod n ，只需证明 M t(n)+1 M mod n 。沥基隋辖钳枕匿邵胚屁半迷蘸搜囊菊油陪挣渍碰芥秧虐觅冠根溯棋扒惫惜第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证 E E E E和和和和D D D D的可逆性的可逆性的可逆性的可逆性在（M，n）1的情况下，根据数论(Euler定理)， M t(n) 1 mod n ，于是有， M t(n)+1 M mod n 。厦豫而溯他弄络态桃蚌荤菌霄洞又坪春滞有子载苑孔缝棒搜刽韦包汗瓮维第10讲数据
16、加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证 E E E E和和和和D D D D的可逆性的可逆性的可逆性的可逆性在（M，n）1的情况下，分两种情况：第一种情况：M1,2,3,n-1 因为n=pq，p和q为素数， M1,2,3,n-1，且（M，n）1 。 这说明M必含p或q之一为其因子，而且不能同时 包 含 两 者 ， 否 则 将 有 Mn， 与M1,2,3,n-1矛盾。篮妆细沟乃走勋频搪服鹰钡啮瞒烘鲜央熏渠伴侍祖应铬坤徘荤孤归唆暇株第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论
17、证 E E E E和和和和D D D D的可逆性的可逆性的可逆性的可逆性不妨设Map 。又因q为素数，且M不包含q，故有（M，q）1， 于是有，M (q) 1 mod q 。进一步有，M t(p-1)(q) 1 mod q。 因 为 q是 素 数 ， (q) （ q-1） ， 所 以 t(p-1)(q)t(n)，所以有 M t(n) 1 mod q。收谣荷慑缴缴哺绞陶牡放订莆屿棘卓么道矾牲宽柴理件练抖需呛篱藐骑蓝第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证 E E E E和和和和D D D D的可逆性的可逆性的可逆性的可逆性于是
18、，M t(n) bq+1，其中b为某整数。两边同乘M， M t(n)+1 bqM+M 。因为Map，故 M t(n)+1 bqap+M =abn+M 。取模n得， M (n)+1 M mod n 。窿振待拐找信技随肤晶砧佩锐杖署勒里廊宜犹鬃缓沾知寸沁昧会麓构差萤第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证 E E E E和和和和D D D D的可逆性的可逆性的可逆性的可逆性在（M，n）1的情况下，分两种情况：第二种情况：M0当M0时，直接验证，可知命题成立。 垂滋庸益棒怖潞锨灶槛圭肠其诌岗辣统多柑革域守葫覆李镜命崖拂园即呐第10
19、讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证加密和解密运算的可交换性加密和解密运算的可交换性加密和解密运算的可交换性加密和解密运算的可交换性 D(E(M)=(Me)d =Med =(Md)e =E(D(M) mod n所以，RSA密码可同时确保数据的秘密性和数据的真实性。加解密算法的有效性加解密算法的有效性加解密算法的有效性加解密算法的有效性 RSA密码的加解密运算是模幂运算，有比较有效的算法。敏群船肥任蹦诚馅瞄号翰绥巾慕钮培胶茨晋臣慎娶胀亨到室窄导格约若诱第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密
20、钥密码2 2、算法论证、算法论证在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果。 根据这一结论，只要合数足够大，进行因子分解是相当困难的。彰鳖壳辉他卫沁洋蓬贩俊统淀段标绥宝舱潦讳杯妖侩逃饱碗剔幅绅俗闺孽第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能
21、求出解密钥在计算上由公开密钥不能求出解密钥假设截获密文C，从中求出明文M。他知道 MCd mod n ， 因为n是公开的，要从C中求出明文M，必须先求出d，而d是保密的。但他知道， ed1 mod (n)，e是公开的，要从中求出d，必须先求出(n)，而(n)是保密的。箕家呛芦盘父剁辛耻慢濒泵迎宰武路腮伺贸砧禽悍瞒熙绷泌揭移柱商掘卷第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥但他又知道， (n)=(p-1
22、)(q-1)，要从中求出(n)，必须先求出p和q，而p和q是保密的。但他知道， n=pq，要从n求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的。作傻比阴蒜科褥扎荆魄跪萤辰猎盼厘凰何徽奄米攒堤委扳纯贱乾苍电捉酱第10讲数据加技术RSA第10讲数据加技术RSA三三、RSA公开密钥密码公开密钥密码2 2、算法论证、算法论证在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥 只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破破破破译译译译RSARSARSARSA密密密密码码码码的的的的困困困困难难难
23、难性性性性对对对对n n n n因因因因子分解的困难性。子分解的困难性。子分解的困难性。子分解的困难性。 目前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。 目前只有Rabin密码具有：破译破译破译破译RabinRabinRabinRabin密码的困难性密码的困难性密码的困难性密码的困难性= = = =对对对对n n n n因子分解的困难性。因子分解的困难性。因子分解的困难性。因子分解的困难性。秽幢攀熟氟辙展舟募鸟卡览椰梨廓劝逛剿劫亲苯睹镑缝茄光舷训弘既摈卡第10讲数据加技术RSA第10讲数据加技术RSA四四、RSA密码的实现密码的实现1
24、 1、参数选择、参数选择为了确保RSA密码的安全，必须认真选择密码参数： p p p p和和和和q q q q要足够大；要足够大；要足够大；要足够大； 一般应用：一般应用：一般应用：一般应用：p p p p和和和和q q q q应应应应 512 b 512 b 512 b 512 b 重要应用：重要应用：重要应用：重要应用：p p p p和和和和q q q q应应应应 1024 b 1024 b 1024 b 1024 b p p p p和和和和q q q q应为强素数应为强素数应为强素数应为强素数 文文文文献献献献指指指指出出出出，只只只只要要要要(p-1)(p-1)(p-1)(p-1)、(
25、p+1)(p+1)(p+1)(p+1)、(q-1)(q-1)(q-1)(q-1)、(q+1)(q+1)(q+1)(q+1)四四四四个数之一个数之一个数之一个数之一只有小的素因子只有小的素因子只有小的素因子只有小的素因子，n n n n就容易分解。就容易分解。就容易分解。就容易分解。 p p p p和和和和q q q q的差要大；的差要大；的差要大；的差要大； 借赖招击所楔栅贱召饿吟炬蝇吩槐偏鸳惫名缨菇榜淑坏寐萌瓮盖酷届煎裳第10讲数据加技术RSA第10讲数据加技术RSA四四、RSA密码的实现密码的实现1 1、参数选择、参数选择（p-1p-1p-1p-1）和（）和（）和（）和（q-1q-1q-1
26、q-1）的最大公因子要小。）的最大公因子要小。）的最大公因子要小。）的最大公因子要小。 如如如如果果果果（ p-1p-1p-1p-1）和和和和（q-1q-1q-1q-1）的的的的最最最最大大大大公公公公因因因因子子子子太太太太大大大大，则则则则易易易易受受受受迭迭迭迭代加密攻击。代加密攻击。代加密攻击。代加密攻击。 e e e e的选择的选择的选择的选择 随机且含随机且含随机且含随机且含1 1 1 1多就安全，但加密速度慢。于是，有的学者多就安全，但加密速度慢。于是，有的学者多就安全，但加密速度慢。于是，有的学者多就安全，但加密速度慢。于是，有的学者建议取建议取建议取建议取e e e e2 2
27、 2 216161616+1+1+1+165537655376553765537 d d d d的选择的选择的选择的选择 d d d d不能太小，要足够大不能太小，要足够大不能太小，要足够大不能太小，要足够大 不要许多用户共用一个模不要许多用户共用一个模不要许多用户共用一个模不要许多用户共用一个模 n n n n；易受共模攻击易受共模攻击易受共模攻击易受共模攻击裤恶哎曼泰酥孕伯腰铲谁舅役翼扫涡市名巧甘友踢宪捏炔至梳懈句茁遁捷第10讲数据加技术RSA第10讲数据加技术RSA四四、RSA密码的实现密码的实现2 2、大素数的产生大素数的产生概率产生概率产生概率产生概率产生 目目目目前前前前最最最最常
28、常常常用用用用的的的的概概概概率率率率性性性性算算算算法法法法是是是是MillerMillerMillerMiller检检检检验验验验算算算算法法法法。MillerMillerMillerMiller检验算法已经成为美国的国家标准。检验算法已经成为美国的国家标准。检验算法已经成为美国的国家标准。检验算法已经成为美国的国家标准。确定性产生确定性产生确定性产生确定性产生确定性测试确定性测试确定性测试确定性测试 确定性构造确定性构造确定性构造确定性构造奖忧豹魄诬辈玲识待肥慈瑶硕润溜焊鼎节酮乙烧牵绍朽茬翰卖啮仅屉冕嘱第10讲数据加技术RSA第10讲数据加技术RSA四四、RSA密码的实现密码的实现3 3
29、、大素数的运算大素数的运算快速乘方算法快速乘方算法快速乘方算法快速乘方算法反复平方乘算法：反复平方乘算法：反复平方乘算法：反复平方乘算法：设e的二进制表示为 eek-1 2k-1 + ek-2 2k-2 +.,+ e1 21 + e0则 Me = (Mek-1)2 Mek-2)2Me1)2 Me0 mod n设设设设e e e e为为为为k k k k位位位位二二二二进进进进制制制制数数数数，w(e)w(e)w(e)w(e)为为为为e e的的的的二二二二进进进进制制制制系系系系数数数数中中中中为为为为1 1的的的的个个个个数数数数，则则则则最最最最多多多多只只只只需需需需要要要要计计计计算算算
30、算w(e)w(e)w(e)w(e) -1-1次次次次平平平平方方方方和和和和w(e)w(e)w(e)w(e)次数的模乘。从而大大简化了计算。次数的模乘。从而大大简化了计算。次数的模乘。从而大大简化了计算。次数的模乘。从而大大简化了计算。倦懊渐芒颠兄蓄茎励嗅迁匣派猴喀柄青署伤健悍察锄逞培空液郊揍痒限扫第10讲数据加技术RSA第10讲数据加技术RSA四四、RSA密码的实现密码的实现3 3、大素数的运算大素数的运算快速模乘算法快速模乘算法快速模乘算法快速模乘算法反反反反复复复复平平平平方方方方乘乘乘乘算算算算法法法法解解解解决决决决了了了了快快快快速速速速乘乘乘乘方方方方取取取取模模模模的的的的问问
31、问问题题题题，仍未解决快速模乘的问题；仍未解决快速模乘的问题；仍未解决快速模乘的问题；仍未解决快速模乘的问题；MontgomeryMontgomery算法是一种快速模乘的好算法；算法是一种快速模乘的好算法；算法是一种快速模乘的好算法；算法是一种快速模乘的好算法；将将将将以以以以上上上上两两两两种种种种算算算算法法法法结结结结合合合合成成成成为为为为实实实实现现现现RSARSA密密密密码码码码的的的的有有有有效效效效方法。方法。方法。方法。硬件协处理器是提高运算效率的有效方法。硬件协处理器是提高运算效率的有效方法。硬件协处理器是提高运算效率的有效方法。硬件协处理器是提高运算效率的有效方法。神之堆
32、利阮亮剥坟借烩侍晨铰氧惹纲屈抖佐饯喝芝妖骸欧洽均辣屋响室酱第10讲数据加技术RSA第10讲数据加技术RSA四四、RSA密码的实现密码的实现3 3、大素数的运算大素数的运算MontgomeryMontgomery算法的思路：算法的思路：算法的思路：算法的思路： 要要要要计计计计算算算算 Y=ABY=ABmodmodnn, ,因因因因为为为为n n很很很很大大大大，取取取取模模模模运运运运算算算算困困困困难，采取一个小的模难，采取一个小的模难，采取一个小的模难，采取一个小的模RR，回避大模的计算。，回避大模的计算。，回避大模的计算。，回避大模的计算。 利用空间换时间，多用存储空间换取快速。利用空间
33、换时间，多用存储空间换取快速。利用空间换时间，多用存储空间换取快速。利用空间换时间，多用存储空间换取快速。 缺缺缺缺点点点点：不不不不能能能能直直直直接接接接计计计计算算算算出出出出 Y=ABY=ABmodmodnn，只只只只能能能能计计计计算算算算出出出出中中中中间间间间值值值值 ABRABR-1-1 modmodnn，因因因因此此此此还还还还需需需需要要要要预预预预处处处处理理理理和调整运算。和调整运算。和调整运算。和调整运算。一次性计算一次性计算一次性计算一次性计算Y=ABmodnY=ABmodn并不划算。并不划算。并不划算。并不划算。 适合：适合：适合：适合：RSARSA等密码中多次的
34、模乘计算。等密码中多次的模乘计算。等密码中多次的模乘计算。等密码中多次的模乘计算。穷违腰扰栏凉磨妹仇九谐罐讫吕涤挎崇立苟墩炔痊茂叔渡晚耳科仟灭幕跪第10讲数据加技术RSA第10讲数据加技术RSA证明证明证明证明RSARSA密码加解密算法的可逆性密码加解密算法的可逆性密码加解密算法的可逆性密码加解密算法的可逆性 证明证明证明证明RSARSA密码加解密算法的可交换性密码加解密算法的可交换性密码加解密算法的可交换性密码加解密算法的可交换性 说明对于说明对于说明对于说明对于RSARSA密码从公开加密钥不能求出保密的密码从公开加密钥不能求出保密的密码从公开加密钥不能求出保密的密码从公开加密钥不能求出保密
35、的解密钥解密钥解密钥解密钥令令令令p=3,q=11,d=7,m=5,p=3,q=11,d=7,m=5,手算密文手算密文手算密文手算密文CC。设设设设RSARSA密码的密码的密码的密码的 e=31,n=35,C=10,e=31,n=35,C=10,手算明文手算明文手算明文手算明文MM。 习习 题题毅疯翘雕遂诬谦度煎朵姓乾茎镰慰绷真弘嘱碘或德风形咋年匆簿单吭炳绰第10讲数据加技术RSA第10讲数据加技术RSA设设设设A A，B B为正整数，为正整数，为正整数，为正整数，D=(A,B)D=(A,B)。试证明：。试证明：。试证明：。试证明： (AB)=D (AB)=D (A) (A) (B)/ (B)
36、/ (D)(D) RSARSA密码的快速运算密码的快速运算密码的快速运算密码的快速运算分析反复平方乘算法的效率分析反复平方乘算法的效率分析反复平方乘算法的效率分析反复平方乘算法的效率说明说明说明说明 MontgomeryMontgomery算法为什么效率高？它适合哪算法为什么效率高？它适合哪算法为什么效率高？它适合哪算法为什么效率高？它适合哪些情况下应用？些情况下应用？些情况下应用？些情况下应用？编程实现编程实现编程实现编程实现RSARSA密码的加解密运算。密码的加解密运算。密码的加解密运算。密码的加解密运算。 在在在在RSARSA中使用中使用中使用中使用e=3e=3作为加密指数有和优缺点？作
37、为加密指数有和优缺点？作为加密指数有和优缺点？作为加密指数有和优缺点？使用使用使用使用d=3d=3作解密指数的做法好吗？为什么？作解密指数的做法好吗？为什么？作解密指数的做法好吗？为什么？作解密指数的做法好吗？为什么？ 习习 题题稳笋颐虑韧砾赖折国封泄谷所树抛式坞乳产勺全份传喻撮哗星葡饭恩桃英第10讲数据加技术RSA第10讲数据加技术RSA证明证明证明证明RSARSA密码加解密算法的可逆性密码加解密算法的可逆性密码加解密算法的可逆性密码加解密算法的可逆性 证明证明证明证明RSARSA密码加解密算法的可交换性密码加解密算法的可交换性密码加解密算法的可交换性密码加解密算法的可交换性 说明对于说明对
38、于说明对于说明对于RSARSA密码从公开加密钥不能求出保密密码从公开加密钥不能求出保密密码从公开加密钥不能求出保密密码从公开加密钥不能求出保密的解密钥的解密钥的解密钥的解密钥令令令令p=3,q=11,d=7,m=5,p=3,q=11,d=7,m=5,手算密文手算密文手算密文手算密文CC。设设设设RSARSA密码的密码的密码的密码的 e=31,n=35,C=10,e=31,n=35,C=10,手算明文手算明文手算明文手算明文MM。 习习 题题蝎奋劝萍稼翅藏甲辨需蛔穆宫庆香舀拱瑶蘸践浮尾捡蕾重欲铜投阮肯晴内第10讲数据加技术RSA第10讲数据加技术RSA设设设设A A，B B为正整数，为正整数，为
39、正整数，为正整数，D=(A,B)D=(A,B)。试证明：。试证明：。试证明：。试证明： (AB)=D (AB)=D (A) (A) (B)/ (B)/ (D)(D) RSARSA密码的快速运算密码的快速运算密码的快速运算密码的快速运算 分析反复平方乘算法的效率分析反复平方乘算法的效率分析反复平方乘算法的效率分析反复平方乘算法的效率 说明说明说明说明 MontgomeryMontgomery算法为什么效率高？它适合哪些情况算法为什么效率高？它适合哪些情况算法为什么效率高？它适合哪些情况算法为什么效率高？它适合哪些情况下应用？下应用？下应用？下应用？编程实现编程实现编程实现编程实现RSARSA密码
40、的加解密运算。密码的加解密运算。密码的加解密运算。密码的加解密运算。 在在在在RSARSA中使用中使用中使用中使用e=3e=3作为加密指数有和优缺点？使用作为加密指数有和优缺点？使用作为加密指数有和优缺点？使用作为加密指数有和优缺点？使用d=3d=3作解密指数的做法好吗？为什么？作解密指数的做法好吗？为什么？作解密指数的做法好吗？为什么？作解密指数的做法好吗？为什么？ 习习 题题廷脉涂砷榴呕芯蹦听殉仰姜邻揩禹咎卯两啃臆摘膨翘兰息馅跃巷拭庐沼于第10讲数据加技术RSA第10讲数据加技术RSA谢 谢！蝶产苟蹄笔抿畅面火额峙浊拌盏刷毫星法痊绕粥省娇蔡毙禁脊嚏踪胀枷埃第10讲数据加技术RSA第10讲数据加技术RSA
