第6章 公钥密码体系

猜想：攻破RSA与分解n是多项式等价 的。然而，这个猜想至今没有给出可信的 证明！！！
（１）素因子p,q应当是强素数， p是强素数：存在大素数p1，p1|p-1,同时r1 , r2是 大素数， r1 | p1 -1 ,r2| p1 -1. 选择强素数的目的是因为选择的p,q如果p-1,q-1 的素因子都很小，则n=pq存在p-1或p+1分 解法
公钥密码体制的要求：
1. 产生一对密钥是计算可行的
2.
3. 4. 5. 6.
已知公钥和明文，产生密文是计算可行的
接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢复明文是计算不可行的 (可选)加密和解密的顺序可交换


公钥密码的安全性依赖于从已知的公钥， 加密算法和密文中无法求出明文或秘钥。 Diffie和Hellman提出了一种陷门单向函 数概念，为建立公钥密码体制找到了一 种途径。
e2 2
p
em m
em em e2 pm ) ( p1e1 ) ( p2 ) ( pm ) e2 1 2
p
e1 1 1
( p1 1) p
( p2 1)
p
em 1 m
( pm 1)
欧拉函数
练习： (300) ?
(300) (22 52 3) (22 ) (52 ) (3)
欧拉函数 (n)
1、p为素数，(p)＝p 1 2、p为素数,(p k ) p k 1 ( p 1)
计数： [1, pk ]中与pk 互素的数的个数
除去[1, p k ]中p的倍数，剩下的都与p k 互素 p,2p, , p k 1 p是[1, p k ]中所有p的倍数，共有 p k 1个。 所以与p k 互素的数的个数有p k－p k 1个
模幂运算－平方和乘算法
m mod N , c (ck 2 ci 2i
i 0
k 1
z 1 for i=k-1 downto 0 { z=z2 mod N if ci 1 then z=z*m mod N } return (z)
平方和乘算法的复杂度：执行次数至少要k次模乘，最多 需要２ｋ次模乘
单向函数

函数f 若满足下列条件 １）对任意给定的x，容易计算f(X)=y ２）对任意给定的y，求出x使得f(x)=y是 困难的。
求离散对数问题 y=gx mod p 若给出p,g,y求x称为求离散对数问题 因子分解问题 n=pq 若给定n,求p,q称为因子分解问题 背包问题 给定一个有限个自然数序列集合B=(b1,b2,……,bn)及二进制数序列 x=(x1,x2,……,xn)，S= x1 b1 + x2 b2 +…… + xn bn 给定B，S，求x序列，称为求背包问题
(2)因子p,q的差必须足够大。 如果p,q比较接近，则由p,q的平均值可得
Q pq 2
2
pq n
再利用
pq pq 2 n Q n 2 2
2
可得
pq Q 2 p q Q2 n 2
进而求出p,q
例如p 101, q 103, n 10403 则 n 101.995 取Q 102, 而102 10403 1 ，因此
2
pq 102 2 p q 1 2
（３）ＲＳＡ的加解密密钥不能太小，存在低指数 攻击
已经证明了当d的二进制长度小于模数n长度的1/4时， 可以利用连分数法在多项式时间内求解n。
解密：为从c中恢复明文m，A利用解密密钥d，计算
m=cd mod n
例如在上面的例子中，假设m=19，则 c=195 =19 ×(192)2=19 × 3612=19 × 42 mod 119 =304=66 mod 119 因此密文为c=66
对于密文c=66,其解密过程如下 m=6677=(662)38 × 66 mod 119 =7238 × 66 mod 119 =4738 × 66 mod 119 =6719 × 66 mod 119 =(672)9 × 67 × 66 mod 119 =869 × 19 mod 119 =(862)4 × 86 × 19 mod 119 =184 × 87 mod 119 =18 × 87 mod 119 =19 mod 119
模幂运算
1513 mod 53, c (c3c2 c1c0 ) (1101) 2 23 2 2 1 Step1 z 1 Step 2 z z 2 m c3 mod N z 12 151 mod 53 15 Step3 z z 2 m c2 mod N z 152 151 mod 53 36 Step 4 z z 2 m c1 mod N z 36 2 150 mod 53 24 Step5 z z 2 m c0 mod N z 242 151 mod 53 1 1513 mod 53 1
RSA公钥密码体制
1 、1977年由Rivest、Shamir和 Adleman发明 并于1978年公布。 2 、明文和密文在0~n-1之间,n是一个正整数 3 、应用最广泛的公钥密码算法 4 、只在美国申请专利，且已于2000年9月到期
欧拉函数 (n)
在[1, n]中，不大于n而且与n互素的正整数 的个数，记作(n)

单向陷门函数：
单向陷门函数是满足下列条件的函数f： 1. 给定x，计算y=f(x)是容易的； 2. 给定y, 计算x使x=f-1(y)是不可行的； 3. 存在陷门t，已知t时，对给定的任何y，若相应 的原象x存在，则计算x是容易的。
通过陷门单向函数建立公钥密码

f(x)是单向陷门函数，陷门为t。 那 么设计公钥密码系统时f(x)作为公钥，陷 门t作为私钥，任何人都可将明文m利用 公钥f(x)加密得到密文y=f(m)，而任何人 不知道私钥即陷门，由密文y都无法求出 m，因为f(x)是单向的，但拥有私钥，便 可容易求出m
如果解密指数d被泄露，则就可以分解出n， 因此就必须重新选取n，而不能只是重新 选取e,d.
RSA的实现

可供选择的大素数是否多 随机选择大素数是否容易 模幂运算能否快速实现
模幂运算
m c mod N , c (c3c2 c1c0 ) 2 c3 23 c2 2 2 c1 2 c0 m m
n 1, (n) ?
欧拉函数
1、p为素数，(p)＝p 1 2、p为素数,(p k ) p k 1 ( p 1)
3、若(m1, m2 ) 1 ，则 (m1m2 ) (m1 ) (m2 )
n 1, (n) ? n p p
e1 1 e2 (n) ( p1e1 p2
计算机安全与保密
公钥密码体系
杭州电子科技大学
对称算法的不足

密钥必须通过某一信道协商，对这个信 道的安全性的要求比正常的传送消息的 信道的安全性要高
1. 公钥密码背景
密码分析 用户A 明文M 加密
k1
密文C E (M , k1 )
解密
k2
M D(C , k2 )
用户B
公钥空间
私钥空间
公钥密码体制的特点： 1. 加密密钥与解密密钥在本质上是不同的，即已知一个密钥并不 能轻易地求出另一个密钥。 2. 不需要增加分发密钥的额外信道。
256 255
由此可见，大素数的分布是相当多的
素数判定

确定性素数判定：判定结果一定正确
概率性素数判定：判定结果在某个概率 上是正确的。 概率性素数判定算法内部使用了一个随 机数，在复杂度理论中也称此类算法为 随机算法


Miller-Rabin素数判定算法
定义 设n 2是一个奇数，设n 1 2 s m，其中s是非负整数， m 0是奇数，设0 b n, 如果 b m 1mod n 或者存在一个r , 0 r s，使得b 2 则称n是以b为基的强伪素数 例：n 91,91 1 2 45 945 1mod 91 91是以9为基的强伪素数
r
m
1mod n
c c3 23 c2 22 c1 2 c0
m
c3 23
m
c2 22
m c1 2 m c0 mod N
(m
c3 22
m
c2 21
m c1 ) 2 m c0 mod N
((m c3 2 m c2 ) 2 m c1 ) 2 m c0 mod N (((12 m c3 ) 2 m c2 ) 2 m c1 ) 2 m c0 mod N Step1 z 1 Step 2 z z 2 m c3 mod N Step3 z z 2 m c2 mod N Step 4 z z 2 m c1 mod N Step5 z z 2 m c0 mod N
解密的正确性：
费马小定理： 若(a,n)=1,则a(n)=1 mod n 2. 推论1：若n=pq，p≠q都是素数，k是任意整数，则 m(n)+1=m(p-1)(q-1)+1=m mod n 3. 推论２： mk(p-1)(q-1)+1=m mod n 由于ed=1 mod(n)，则存在整数k,满足 ed=1+k(n)=1+k(p-1)(q-1) 因此 cd=med=mk(p-1)(q-1)+1=m mod n 所以解密成功。
①
例如取p=7,q=17,则
n=pq=7×17=119 (n)=(7-1)(17-1)=6 × 16=96
任取e=5，则d=77.注意5 × 77=385=1 mod96
2.