中国剩余定理和RSA算法

中国剩余定理和RSA算法第1页，共27页。模[m1,m2,…，mk]有惟一解，x≡M1M1-1b1+M2M2-1b2+…+MkMk-1bkmodmm=m1m2…mkMi=m/mi，MiMi-1≡1modmi例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？X≡2mod3X≡3mod5X≡2mod7解：问题归结为解第2页，共27页。m=m1m2m3=3*5*7=105M1=m/m1=105/3=35M2=m/m2=105/5=21M3=m/m3=105/7=15M1M1-1≡1modm1M2M2-1≡1modm2M3M3-1≡1modm3即：35M1-1≡1mod3得：M1-1≡221M2-1≡1mod5M2-1≡115M3-1≡1mod7M3-1≡1第3页，共27页。答案是：三人同行七十稀五树梅花廿一枝七子团圆月正半除百零五便得知x≡M1M1-1b1+M2M2-1b2+M3M3-1b3

≡70b1+21b2+15b3mod105≡70*2+21*3+15*2mod105≡23mod105第4页，共27页。第9章公钥密码学与RSA公钥密码学与以前的密码学完全不同。首先，公钥算法是基于数学函数而不是基于替换、置换等运算，更重要的是，与只使用一个密钥的对称传统密码不同，公钥密码是非对称的，它使用两个独立的密钥（公钥和私钥）。第5页，共27页。9.1公钥密码体制的基本原理公钥密码体制公钥密码体制的特点：仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的。有些公钥密体制还有如下特点：两个密钥中的任何一个都可用来加密，另一个用来解密。第6页，共27页。第7页，共27页。第8页，共27页。第9页，共27页。第10页，共27页。公钥密码体制的应用

加密/解密:

发送方用接收方的公钥对消息加密。数字签名：发送方用其私钥对消息“签名”。签名可以通过对整条消息加密或者对消息的一个小的数据块加密来产生。其中该小数据块是整条消息的函数。密钥交换：通信双方交换会话密钥。第11页，共27页。单向陷门函数的定义：一个函数，若计算函数值很容易，并且在缺少一些附加信息时计算函数的逆是不可行的，但是已知这些附加信息时，可在多项式时间内计算函数的逆，那么我们称这样的函数为单向陷门函数。即单向陷门函数是满足下列条件的一类不可逆函数fk若k和X已知，则容易计算Y=fk(X)。若k和Y已知，则容易计算X=fk-1(Y)若Y已知但k未知，则计算X=fk-1(Y)是不可行的。第12页，共27页。1976年9月，一篇题为“NewDirectionsinCryptography(密码术的新方向)”的文章，打破了几千年来对称密码技术的垄断局面，开辟了现代密码技术的新领域——公钥密码技术。这篇文章是一个名叫WhitfieldDiffie的自学成才的的密码学专家和一个与他兴趣相投的斯坦福大学学生Hellman共同发表的。其中阐述了一种实用的密钥交换技术，解决了在对称密码技术中一直困扰人们的密钥传递问题，这就是著名的Diffie-Hellman(简称DH)密码技术（以后再介绍）。第13页，共27页。但Diffie-Hellman的开创性论文却引起了美国麻省理工学院（MIT）的年青教授RonRivest对公钥加密技术的极大兴趣，他下决心要开发一个最终的公钥加密技术。于是他邀请两位同事AdiShamirt和LenAdleman一起来解决这个问题。1977年，三人开发出了一个能够真正加密数据的公钥加密算法，并于1978年在一篇题为“AMethodforObtainingDigitalSignaturesandPublicKeyCryptosystems(获取数字签名和公钥加密系统的方法)”中公开了这个算法，这就是著名的RSA算法（以三位发明者名字的首字母缩写命名）。

RSA先后被ISO、ITU、SWIFT等国际化标准组织采用作为标准。第14页，共27页。RSA密码体制描述参数的构成:（1）选取两个不同的大素数p、q。（2）计算n：n=pq和φ(n)=（p-1）(q-1)（3）随机选取e，使e满足1<e<φ(n)，且（e,φ(n)）=1那么公钥就是(e，n)(4)计算d：满足ed≡1(modφ(n))那么私钥就是(d，n)(5)销毁p、q、φ(n)；自己保存好私钥(d，n)；公开公钥(e,n).明文和密文空间就是0到（n-1）之间的整数值。第15页，共27页。加密:C≡memodn这里，m是明文，C是密文解密:m≡Cdmodn.使用RSA算法要满足：m〈n第16页，共27页。举例：（1）构造用户A的参数：p=5q=11n=p╳q=55φ(n)=（p-1）╳(q-1)=4╳10=40选择一个整数e，使e与φ(n)互素。现选择e=17公钥为（e，n），即（17，55）从ed≡1modφ(n)即17d≡1mod40中求得d，解得d=33。私钥（d，n）即为（33，55）。（2）假如B想把明文m=25发给A，那么他就利用公式C=memodn把明文m加密成密文C，即C=memodn=2517mod55=20并把C=20发送给A。（3）A收到密文C后，利用公式m=Cdmodn把密文C恢复成明文m。即m=Cdmodn=2033mod55=25A把B发给他的密文C=20恢复为明文m=25。第17页，共27页。课堂练习：p=11,q=7,e=13，问私钥是什么，若加密明文m=10，则对应的密文是什么？第18页，共27页。（1）RSA算法原理基于Euler定理及大数分解的困难性下面证明RSA解密过程的正确性：D[C]≡Cd≡med(modn)（1）∵ed≡1modφ(n)∴ed=1+kφ(n)这里k是整常数，代入（1）有D[C]≡med(modn)≡m1+kφ(n)（modn）=m.(mφ(n))k(modn)（2）RSA算法分析第19页，共27页。①若（m，n）=1，由Euler定理有mφ(n)≡1（modn），即D[C]≡m。②若（m，n）≠1，又n=pq，由素数性质得（m,n）=p或q。假设（m，n）=p,有m=sp,这里s是正整数∵1<m<n，∴1≤s<q(p,q)=1,(s,q)=1,又p、q都是素数，故从而

(sp,q)=1,即（m，q）=1第20页，共27页。由Euler定理有mφ(q)≡1modq于是（mφ(q)）kφ(p)≡1modq写成mkφ(n)≡1modq或mkφ(n)=1+jq这里j是正整数由（2）式有D[C]≡m.(mφ(n))k(modn)≡m(1+jq)≡m+mjq≡m+spjq=m+sjn≡m(modn)即D[C]=m第21页，共27页。(2)memodn是将明文以指数形式表示出来，或者说以指数形式将明文隐藏起来。

(3)如果攻击者设法得到了一个明、密文对（m,c）,他想得到解密密钥d，则必须在Zn={1,2,…，n-1}中求解（离散）对数问题：d=logcm,这是一个困难问题。(4)加密、解密过程中的主要运算是Zn中的幂运算。由于n可能非常大，所以模n的幂运算的效率就成为算法效率的关键。（5）在找到一个可用的数，即与φ(n)互素的数之前，要测试多少个随机数呢？可以很容易地证明，两个随机数互素的概率约为0.6。第22页，共27页。*计算方面的问题运用中国剩余定理可以加快运算速度。先计算一些中间结果：Vp≡CdmodpVq≡CdmodqXp≡qq-1modpXq≡pp-1modqM≡(VpXp+VqXq)modn进一步，可以用费马定理来简化计算Vp≡Cdmodp≡Cd

mod(p-1)modpVq≡Cdmodq≡Cd

mod(q-1)modq第23页，共27页。RSA的安全性

对RSA算法的攻击可能有如下四种方式：穷举攻击：这种方法试图穷举所有可能的私钥；数学攻击：有多种数学攻击方法，它们的实质都是试图分解两个素数的乘积；计时攻击：这类方法依赖于解密算法的运行时间；选择密文攻击：这种攻击利用了RSA算法的性质。第24页，共27页。因子分解问题

用数学方法攻击RSA的途径有以下三种：分解n为两个素因子。这样就可以计算出φ(n)=（p-1）（q-1），从而可以确定

d≡e-1(modφ(n))。直接确定φ(n)而不先确定p和q。直接确定d，而不先确定φ(n)。对RSA的密码分析的讨论大都集中于第一种攻击方法，即分解n。在选择RSA的n时，密钥大小在1024至2048