RSA公钥密码体制.ppt

RSA公钥密码体制 主讲人：赵永哲 e_mail: yongzhe @jlu.edu.cn 电话公钥密码体制的基本概念 公钥密码体制的概念是在解决对称密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。 对称密码体制在进行密钥分配时，要求通信双方已经有了一个共享的密钥，或者可籍助于一个密钥分配中心临时分配会话密钥。对第一个要求，常常可用人工方式事先传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。 第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。 1976年W.Diffie和M.Hellman对解决上述两个问题有了突破，从而提出了公钥密码体制。 公钥密码体制的原理 公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公钥，用于加密；另一个密钥是为用户专用，因而是必威体育官网网址的，称为秘密密钥，简称私钥，用于解密。因此公钥密码体制也称为双钥密码体制或非对称密码体制。 算法有以下重要特性： 已知密码算法和公钥，求解私钥在计算上不可行。 用公钥加密的消息只能用与之对应的私钥来解密。 加密和解密操作在计算上可快速执行。 公开密钥体制用于加密的原理 加密c=EPKB(m) 解密m=DSKB(c) 公钥密码体制用于认证的原理 签名：s=ESKA(m) 验证签名：m=DPKA(s) 公钥密码算法应满足的要求 公钥密码算法应满足以下要求: ① 接收方B产生密钥对(PKB,SKB)在计算上是容 易的。 ② 发方A用接收方B的公钥对消息m加密以产 生密文c，即c=EPKB(m)在计算上是容易的。 ③ 接收方B用自己的私钥对密文c进行解密，即 m=DSKB(c)在计算上是容易的。 公钥密码算法应满足的要求 ④ 敌手由B的公钥PKB求其私钥SKB在计算上 是不可行的。 ⑤ 敌手由密文c和B的公钥PKB恢复明文m在计 算上是不可行的。 ⑥ 加、解密次序可换，即 DSKB(EPKB(m)) =EPKB(DSKB(m)) 其中最后一条虽然非常有用，但不是对所 有的算法都作要求。 公钥密码算法应满足的要求 以上要求的本质之处在于要求一个单向陷门函数。 称一个函数是单向陷门函数，是指该函数是易于计算的，但求 它的逆是不可行的，除非再已知某些附加信息。当附加信息给 定后，求逆可在多项式时间完成。 总结为：单向陷门函数是一族可逆函数ft，满足： ① Y=ft(X)易于计算（当ft和X已知时）。 ② X=ft-1(Y)在计算上是不可行的（当Y、ft已知，但t未知时）。 ③ X=ft-1(Y)易于计算（当Y、ft 、t 均已知时）。 因此，实现公钥密码的核心就是寻找合适的单向陷门函数。 RSA算法 RSA算法是1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的公钥密码体制，该体制已得到广泛的应用。 2002 Turing Award (June’03) RSA的数论基础 算法描述—— 密钥的产生 ① 秘密选取两个大素数p和q。 ② 计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。 ③ 选一整数e，满足1eφ(n)，且gcd(φ(n),e)=1。 ④ 计算d，满足d·e≡1 mod φ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。 ⑤ 以{e,n}为公开钥,{d,n}为秘密钥。 算法描述—— 加密 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算： c≡me mod n 算法描述—— 解密 对密文分组的解密运算为： m≡cd mod n RSA 的单向陷门函数 参数: N=pq. N ?1024 bits. p,q ?512 bits. e –加密指数 gcd(e, ?(N) ) = 1 . 单向函数: RSA(M) = Me (mod N) 其中 M?ZN* 因子分解问题 三种数学攻击方法 分解 N=p.q, 因此可计算出 ?(N)，从而确定d 直接确定?(N)，然后找到d 直接确定d 大家相信：由N确定?(N)等价于因子分解 举例 选p=7，q=17。 求n=p×q=119，φ(n)=(p-1)(q-1)=96。 取e=5，满足1e