《信息安全课件(2010)3-1RSA算法》由会员分享，可在线阅读，更多相关《信息安全课件(2010)3-1RSA算法（19页珍藏版）》请在金锄头文库上搜索。
1、1 RSA算法算法 主讲人：裴士辉主讲人：裴士辉 e_mail: shihui_pei 电话：电话：13694302598 公钥密码体制的基本概念公钥密码体制的基本概念 公钥密码体制的概念是在解决单钥密码体制中最难 解决的两个问题时提出的，这两个问题是密钥分配 和数字签字。 公钥密码体制的概念是在解决单钥密码体制中最难 解决的两个问题时提出的，这两个问题是密钥分配 和数字签字。 1976年年W.Diffie和和M.Hellman对解决上述两个问题 有了突破，从而提出了公钥密码体制 对解决上述两个问题 有了突破，从而提出了公钥密码体制。 2 公钥密码体制的原理公钥密码体制的原理 公钥密码算法的最
2、大特点是采用两个相关密钥将加 密和解密能力分开，其中一个密钥是公开的，称为 公开密钥，简称公开钥，用于加密；另一个密钥是 为用户专用，因而是保密的，称为秘密密钥，简称 秘密钥，用于解密。因此公钥密码体制也称为双钥 密码体制。 公钥密码算法的最大特点是采用两个相关密钥将加 密和解密能力分开，其中一个密钥是公开的，称为 公开密钥，简称公开钥，用于加密；另一个密钥是 为用户专用，因而是保密的，称为秘密密钥，简称 秘密钥，用于解密。因此公钥密码体制也称为双钥 密码体制。 公开密钥体制用于加密的原理公开密钥体制用于加密的原理 加密加密c=EPKBm 解密解密m=DSKBc 3 公钥密码体制用于认证的原理
3、公钥密码体制用于认证的原理 签名：签名：c=ESKAm 验证：验证：m=DPKAc 公钥密码算法应满足的要求公钥密码算法应满足的要求 公钥密码算法应满足以下要求公钥密码算法应满足以下要求: 接收方 接收方B产生密钥对（公开钥产生密钥对（公开钥PKB和秘密钥和秘密钥SKB） 在计算上是容易的。 发方 ） 在计算上是容易的。 发方A用收方的公开钥对消息用收方的公开钥对消息m加密以产生密文加密以产生密文c， 即 ， 即 c=EPKBm 在计算上是容易的。 收方 在计算上是容易的。 收方B用自己的秘密钥对用自己的秘密钥对c解密，即解密，即m=DSKBc在计 算上是容易的。 在计 算上是容易的。 4 公
4、钥密码算法应满足的要求公钥密码算法应满足的要求 敌手由 敌手由B的公开钥的公开钥PKB求秘密钥求秘密钥SKB在计算上是不 可行的。 敌手由密文 在计算上是不 可行的。 敌手由密文c和和B的公开钥的公开钥PKB恢复明文恢复明文m在计算上 是不可行的。 加、解密次序可换，即 在计算上 是不可行的。 加、解密次序可换，即 EPKBDSKB(m)=DSKBEPKB(m) 其中最后一条虽然非常有用，但不是对所有的算法都 作要求。 其中最后一条虽然非常有用，但不是对所有的算法都 作要求。 RSA算法算法 RSA算法是算法是1978年由年由R.Rivest, A.Shamir和和L.Adleman提出的 一
5、种用数论构造的公钥密码体制，该体制已得到广泛的应用。 提出的 一种用数论构造的公钥密码体制，该体制已得到广泛的应用。 RivestShamirAdleman 5 2002 Turing Award (June03) 因子因子、素数、互素数素数、互素数 1、因子 设 、因子 设a，b(b0)是两个整数，如果存在另一整数是两个整数，如果存在另一整数m，使得，使得a=mb， 则称 ， 则称b整除整除a，记为，记为b|a，且称，且称b是是a的因子。的因子。 2、素数 称整数 、素数 称整数p(p1)是素数，如果是素数，如果p的因子只有的因子只有1，p。 3、最大共因子 称 、最大共因子 称c是两个整数
6、是两个整数a、b的最大公因子，如果 的最大公因子，如果 c是是a的因子也是的因子也是b 的因子，即的因子，即c是是a、b的公因子。 的公因子。 a和和b的任一公因子，也是的任一公因子，也是c的因子。 表示为 的因子。 表示为c=gcd(a, b)。 4、互素数 如果 、互素数 如果gcd(a,b)=1，则称，则称a和和b互素。互素。 6 设设n是一正整数，是一正整数，a是整数，如果用是整数，如果用n除除a，得商为，得商为q，余数为，余数为 r，则，则 a=qn+r,0r1, 如果对于所有的正整数如果对于所有的正整数q, 1c。 Euclid（b, c） b = cq1 + r1 (1) c =
7、r1q2 + r2 (2) r1=r2q3 + r3 (3) - r(j-1)=r(j)q(j+1) (j+1) 例例4.2 求求gcd(1970, 1066) 1970=11066+904, 1066=1904+162, 904=5162+94, 162=194+68, 94=168+26, 68=226+16, 26=116+10, 16=110+6, 10=16+4, 6=14+2, 4=22+0, 因此因此gcd(1970, 1066)=2 11 练习练习 求求gcd (57,17) 求求gcd (231,7563） Euclid算法求乘法逆元算法求乘法逆元 乘逆：乘逆：ab 1 (
8、mod r) a,b对于对于r 互为乘逆 欧几里德算法 设 互为乘逆 欧几里德算法 设ab 1( mod r) 已知：已知：a, 求求b r = aq1 + c1 (1) a =c1q2+c2 (2) c1=c2q3+c3 (3) c(j-2)=c(j-1)q(j)+c(j) (j) c(j-1)=c(j)q(j+1)+1 (j+1) 递推公式：递推公式： b (-1)=0 b (0)=1 b (j)=(1)b（j1）q（j）+b(j2) 12 例题例题 已知已知a=550, r=1769 求求b, 满足满足ab 1( mod r) 练习练习 已知已知a=167, r=2760 求求b, 满足
9、满足ab 1( mod r) 13 RSA的数论基础的数论基础 费尔玛费尔玛(Fermat)定理 若 定理 若p是素数，是素数，a是正整数且是正整数且gcd(a, p)=1，则，则 ap-11 mod p。 RSA的数论基础的数论基础 欧拉函数 设 欧拉函数 设n是一正整数，小于是一正整数，小于n且与且与n互素的正整数的个数称 为 互素的正整数的个数称 为n的欧拉函数，记为的欧拉函数，记为(n)。 14 RSA的数论基础的数论基础 欧拉定理 若 欧拉定理 若a和和n互素，则互素，则a (n) 1 mod n。 算法描述算法描述密钥的产生密钥的产生 选两个保密的大素数 选两个保密的大素数p和和q
10、。 计算 。 计算n=pq，(n)=(p-1)(q-1),其中其中(n)是是n的欧 拉函数值。 选一整数 的欧 拉函数值。 选一整数e，满足，满足1e(n)，且，且gcd(n),e)=1。 计算 。 计算d，满足，满足de1 mod (n),即即d是是e在模在模(n)下 的乘法逆元，因 下 的乘法逆元，因e与与(n)互素，由模运算可知，它的 乘法逆元一定存在。 以 互素，由模运算可知，它的 乘法逆元一定存在。 以e,n为公开钥为公开钥,d,n为秘密钥。为秘密钥。 15 算法描述算法描述加密加密 加密时首先将明文比特串分组，使得每个分组对应 的十进制数小于 加密时首先将明文比特串分组，使得每个分
11、组对应 的十进制数小于n，即分组长度小于，即分组长度小于log2n。然后对 每个明文分组 。然后对 每个明文分组m，作加密运算：，作加密运算： cmemod n 算法描述算法描述解密解密 对密文分组的解密运算为：对密文分组的解密运算为： mcdmod n 16 因子分解问题因子分解问题 三种数学攻击方法三种数学攻击方法 分解分解 N=p.q, 因此可计算出因此可计算出 (N)，从而确定，从而确定d 直接确定直接确定(N)，然后找到，然后找到d 直接确定直接确定d 大家相信：由大家相信：由N确定确定(N)等价于因子分解等价于因子分解 举例举例 选选p=7，q=17。 求 。 求n=pq=119，
12、(n)=(p-1)(q-1)=96。 取 。 取e=5，满足，满足1e(n)，且，且gcd(n),e)=1。 确定满足 。 确定满足de=1 mod 96且小于且小于96的的d，因为，因为 775=385=496+1，所以，所以d为为77， 因此公开钥为 ， 因此公开钥为5，119，秘密钥为，秘密钥为77，119。 设明文 。 设明文m=19，则由加密过程得密文为，则由加密过程得密文为 c195mod 1192476099 mod 11966 解密为解密为 6677mod 11919 17 计算问题：加密与解密过程中的指数运算计算问题：加密与解密过程中的指数运算 计算计算551mod 97 5
13、1=32+16+2+1 51=5 mod 97 52=25 mod 97 54=43 mod 97 58=6 mod 97 516=36 mod 97 532=35 mod 97 551= 532+16+2+1 =35*36*25*5=69 mod 97 练习练习 求求7560mod 561。 18 例题例题 已知已知 RSA公钥加密方案中公钥加密方案中 p=29 q=67 n=1943 e=701 m=23 求密文求密文 C=memod n =23701mod 1943 701=512+128+32+16+8+4+1 231=23 mod 1943 232=529 mod 1943 234=
14、49 mod 1943 238=458 mod 1943 2316=1863 mod 1943 2332=571 mod 1943 2364=1560 mod 1943 23128=964 mod 1943 23256=542 mod 1943 23512=371 mod 1943 C=371*964*571*1863*458*49*23=458 mod 1943 例题例题 已知已知 RSA公钥加密方案中公钥加密方案中 p=29 q=67 n=1943 e=701 c=1926 求明文求明文 -10 1101-1 22120 1mod ( ) ( )(29 1)(67 1)1848 7011m
15、od1848 0 1 1848701 2446(2) 12 701446 1255(1) 13 446255 den n bb qbbqb qbbqb = = = += += = += += = 31231 41342 51453 61 1 191(1) 15 255191 1 64(1) 18 19164 263(2) 121 6463 1 1(1) 1 qbbqb qbbqb qbbqb qb += += = += += = += += = += 564 29 29 bqb d += = 19 RSA中参数的选择：密钥长度中参数的选择：密钥长度 估计在未来一段比较长的时期，密钥长度介于估计在未来一段比较长的时期，密钥长度介于1024 比
