RSA的安全性
对RSA算法的攻击可能有如下四种方式： 穷举攻击：这种方法试图穷举所有可能的 私钥； 数学攻击：有多种数学攻击方法，它们的 实质都是试图分解两个素数的乘积； 计时攻击：这类方法依赖于解密算法的运 行时间； 选择密文攻击：这种攻击利用了RSA算法的 性质。
因子分解问题
由Euler定理有 mφ(q) ≡1 mod q 于是 （mφ(q)）kφ(p)≡1 mod q 写成 mkφ(n) ≡1 mod q 或 m kφ(n) =1+jq 这里j是正整数 由（2）式有 D[C] ≡m.(mφ(n))k(mod n) ≡m(1+jq) ≡m+mjq≡m+spjq=m+sjn≡m(mod n) 即D[C]=m
用数学方法攻击RSA的途径有以下三种： 分解n为两个素因子。这样就可以计算出φ(n)= （p-1）（q-1），从而可以确定 d≡e-1(mod φ(n))。 直接确定φ(n)而不先确定p和q。 直接确定d，而不先确定φ(n)。 对RSA的密码分析的讨论大都集中于第一种攻击 方法，即分解n。在选择RSA的n时，密钥大小在 1024至2048位范围内是合适的。


单向陷门函数的定义：一个函数，若计 算函数值很容易，并且在缺少一些附加 信息时计算函数的逆是不可行的，但是 已知这些附加信息时，可在多项式时间 内计算函数的逆，那么我们称这样的函 数为单向陷门函数。即单向陷门函数是 满足下列条件的一类不可逆函数fk 若k和X已知，则容易计算Y=fk(X)。 若k和Y已知，则容易计算X=fk-1(Y) 若Y已知但k未知，则计算X=fk-1(Y)是不可 行的 。
模[m1,m2,…，mk]有惟一解， x≡M1M1-1b1 + M2M2-1b2 +…+ MkMk-1bk mod m m=m1m2…mk Mi=m/mi，MiMi-1≡1 mod mi
例： 今有物不知其数，三三数之剩二，五五数之剩三， 七七数之剩二，问物几何？ 解： 问题归结为解
X≡2 mod 3 X≡3 mod 5 X≡2 mod 7
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）之间的整数值。
9.1公钥密码体制的基本原理
9.1.1公钥密码体制 公钥密码体制的特点： 仅根据密码算法和加密密钥来确定解密密钥 在计算上是不可行的。 有些公钥密体制还有如下特点： 两个密钥中的任何一个都可用来加密，另一 个用来解密。
9.1.2公钥密码体制的应用
Βιβλιοθήκη 加密/解密: 发送方用接收方的公钥对消息 加密。 数字签名：发送方用其私钥对消息“签 名”。签名可以通过对整条消息加密或者 对消息的一个小的数据块加密来产生。其 中该小数据块是整条消息的函数。 密钥交换：通信双方交换会话密钥。
①若（m，n）=1，由Euler定理有 mφ(n) ≡1（mod n），即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
加密: C≡me mod n 这里，m是明文，C是密文 解密: m≡Cd mod n. 使用RSA算法要满足：m〈n
举例： （1）构造用户A的参数： p=5 q=11 n=p╳q=55 φ (n)=（p-1）╳(q-1)= 4╳10=40 选择一个整数e，使e与φ(n)互素。现选择e=17 公钥为（e，n），即（17，55） 从ed≡1 mod φ(n)即17d≡1 mod 40 中求得d，解得d=33。 私钥（d，n）即为（33，55）。 （2）假如B想把明文m=25发给A，那么他就利用公式 C=me mod n把明文m加密成密文C，即 C=me mod n=2517 mod 55=20 并把C=20发送给A。 （3）A收到密文C后，利用公式m=Cd mod n把密文C恢复 成明文m。即 m=Cd mod n=2033 mod 55=25 A把B发给他的密文C=20恢复为明文m=25。


但Diffie-Hellman的开创性论文却引起了美国麻 省理工学院（MIT）的年青教授Ron Rivest对公 钥加密技术的极大兴趣，他下决心要开发一个 最终的公钥加密技术。于是他邀请两位同事Adi Shamirt和 Len Adleman一起来解决这个问题。 1977年，三人开发出了一个能够真正加密数据 的公钥加密算法，并于1978年在一篇题为“A Method for Obtaining Digital Signatures and Public Key Cryptosystems(获取数字签名和公钥 加密系统的方法)”中公开了这个算法，这就是 著名的RSA算法（以三位发明者名字的首字母 缩写命名）。 RSA先后被ISO、ITU、SWIFT等国际化标准组 织采用作为标准。

1976年9月，一篇题为“New Directions in Cryptography(密码术的新方向)”的文章， 打破了几千年来对称密码技术的垄断局 面，开辟了现代密码技术的新领域——公 钥密码技术。这篇文章是一个名叫 Whitfield Diffie的自学成才的的密码学专 家和一个与他兴趣相投的斯坦福大学学 生Hellman共同发表的。其中阐述了一种 实用的密钥交换技术，解决了在对称密 码技术中一直困扰人们的密钥传递问题， 这就是著名的Diffie-Hellman(简称DH)密 码技术（以后再介绍）。
课后习题： 1.韩信点兵的故事。今有兵员不知其数，每五个数 之，剩下1人；每六个数之，剩下5人；每七人数 之，剩下4人；每十一人数之，剩下10人，问兵 员多少？ *编写中国剩余定理算法程序。 2.什么是单向陷门函数？ 3.P201 9.2 a, b 9.3
计时攻击 攻击者可以通过记录计算机解密消息所用的 时间来确定私钥。 解决方法： 不变的幂运算时间 随机延时 隐蔽
*选择密文攻击和最佳非对称加密填充
基本的RSA算法易受选择密文攻击（在此不深入讲解）， 可以采用最佳非对称加密填充（OAEP）来解决： 第一步，待加密的消息M被填充。可选参数集P作为散列 函数H的输入，输出用0加以填充以获得期望的长度， 从而可以放入整体数据块（DB）内。 第二步，随机选择一个种子，并作为一个散列函数的输 入，该散列函数称为掩码生成函数（MGF）。输出散 列值和DB进行按位异或运算产生掩码DB （maskedDB）。 第三步，该maskedDB反过来又作为MGF的输入产生一个 散列值，该散列值和种子进行异或运算产生掩码种子。 掩码种子和掩码DB连接起来构成加密后的消息EM。注 意，EM包含填充过的消息，该消息由种子进行隐蔽， 而种子又由maskedDB进行隐蔽。最后用RSA对整个EM 进行加密。
m = m1 m2 m3 =3*5*7=105 M1= m / m1=105/3=35 M2=m/m2=105/5=21 M3=m/ m3=105/7=15 M1M1-1≡1 mod m1 M2M2-1≡1 mod m2 M3M3-1≡1 mod m3
即：35M1-1≡1 mod 3 21M2-1≡1 mod 5 15M3-1≡1 mod 7 得：M1-1≡2 M2-1≡1 M3-1≡1
(2) me mod n是将明文以指数形式表示出来，或 者说以指数形式将明文隐藏起来。 (3)如果攻击者设法得到了一个明、密文对 （m,c）,他想得到解密密钥d，则必须在 Zn={1,2,…，n-1}中求解（离散）对数问题： d=logcm,这是一个困难问题。 (4)加密、解密过程中的主要运算是Zn中的幂运算。 由于n可能非常大，所以模n的幂运算的效率就 成为算法效率的关键。 （5）在找到一个可用的数，即与φ(n)互素的数之 前，要测试多少个随机数呢？可以很容易地证 明，两个随机数互素的概率约为0.6。
8.4中国剩余定理
8.4中国剩余定理
定理1-10中国剩余定理 (CRT：Chinese Remainder Theorem) 设m1,m2,…，mk是两两互素的正整数，即： (mi,mj)=1，i≠j，i, j=1,2,…，k，则同余方 程组：
X≡b1 mod m1 X≡b2 mod m2 …… X≡bk mod mk
除了要指定n的大小外，研究者还提出了其他一些限 制条件： p和q的长度应仅相差几位。这样对1024位（309 个十进制位）的密钥而言，p和q都应约在1075到 10100之间。 （p-1）和（q-1）都应有一个大的素因子。 （p-1，q-1）应该较小。 1/4，则d很容易被 另外，已经证明，若e<n且d<n 确定。
x≡M1M1-1b1 + M2M2-1b2 + M3M3-1b3 ≡70 b1 +21 b2+15 b3 mod 105 ≡70*2+21*3+15*2 mod 105 ≡23 mod 105
答案是： 三人同行七十稀 五树梅花廿一枝 七子团圆月正半 除百零五便得知
第9章公钥密码学与RSA

公钥密码学与以前的密码学完全不同。首 先，公钥算法是基于数学函数而不是基于 替换、置换等运算，更重要的是，与只使 用一个密钥的对称传统密码不同，公钥密 码是非对称的，它使用两个独立的密钥 （公钥和私钥）。
*计算方面的问题
运用中国剩余定理可以加快运算速度。 先计算一些中间结果： Vp≡Cd mod p Vq≡Cd mod q Xp≡qq-1mod p Xq≡pp-1mod q M≡(Vp Xp+ Vq Xq) mod n 进一步，可以用费马定理来简化计算 Vp≡Cd mod p≡Cd mod (p-1) mod p Vq≡Cd mod q≡Cd mod (q-1) mod q