RSA公钥密码体制简介.ppt

公钥密码技术
1
整理课件
RSA公钥密码算法
主要内容：RSA公钥密码算法，RSA公钥密码的实现。
重点： RSA算法，脱密的快速实现，素数生成算法。
难点：素数生成算法。
2
整理课件
RSA体制
由Rivest、Shamir、Adleman于1978年首次发表；
最容易理解和实现的公钥算法;
经受住了多年深入的攻击;
其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；
RSA既可用于加密，又可用于数字签名，已得到广泛采用；
RSA已被许多标准化组织(如ISO、ITU、IETF和SWIFT等)接纳；
目前许多国家标准仍采用RSA或它的变型
3
整理课件
假设m为要传送的报文。
1、任产生两个素数p与q，使得n=pq>m
2、随机选择数e：e与(p-1)(q-1) 互素
3、用辗转相除法求d：ed=1 mod(p-1)(q-1)
4、公开：（e，n），保密：d 
加密过程：c=me mod n
解密过程：m=cd mod n
一、RSA算法
1、RSA算法描述
4
整理课件
定义：任给一个正整数m，如果用m去除任意两个整数a、b所得的余数相同，称a、b对模m同余。记为： ，若余数不同，则a、b对模m不同余。记为： 。
定理： ，当且仅当m|(a-b)。
定理：欧拉定理，对任意 有
推论:费尔马定理，若p为素数，则
其中
2、工作原理
5
整理课件
RSA算法论证
① E和D的可逆性
要证明：D(E(M))=M
M＝Cd ＝(Me)d＝Med mod n
因为ed＝1 modφ(n)，这说明ed＝tφ(n)+1,其中
t为某整数。所以,
Med ＝Mtφ(n)+1 mod n 。
因此要证明Med ＝M mod n ，只需证明
M tφ(n)+1 ＝M mod n 。
6
整理课件
RSA算法论证
在（M，n）＝1的情况下，根据数论(Euler定理)，
M tφ(n) ＝1 mod n ，
于是有，
M tφ(n)+1 ＝M mod n 。
7
整理课件
RSA算法论证
在（M，n）≠1的情况下，分两种情况：
第一种情况：M∈{1,2,3,…,n-1}
因为n=pq，p和q为素数，
M∈{1,2,3,…,n-1}，且（M，n）≠1 。
这说明M必含p或q之一为其因子，而且不能同
时包含两者， 否则将有M≥n ， 与
M∈{1,2,3,…,n-1}矛盾。
8
整理课件
RSA算法论证
9
整理课件
RSA算法论证
不妨设M＝ap 。
又因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
整理课件