基于公开密钥的加密过程
图4.1 公钥密码体制的通信保密过程
基于公开密钥的鉴别过程
图4.2 公钥密码体制的数字签名和验证签名过程
公钥密钥的应用范围
加密/解密 数字签名(身份鉴别) 密钥交换
5.1.4 公钥密码系统基本思想和要求
1、涉及到各方：发送方、接收方、攻击者 2、涉及到数据：公钥、私钥、明文、密文 3、公钥算法的条件： – 产生一对密钥是计算可行的； – 已知公钥和明文，产生密文是计算可行的； – 接收方利用私钥来解密密文是计算可行的； – 对于攻击者，利用公钥来推断私钥是计算不可行的 – 已知公钥和密文，恢复明文是计算不可行的； – (可选)加密和解密的顺序可交换。
5.1.2 公钥密码体制的起源


公钥密码又称为双钥密码和非对称密码，是1976年 由Diffie和Hellman在其“密码学新方向”一文中提 出的，见划时代的文献：W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976,PP.644-654 RSA公钥算法是由Rivest,Shamir和Adleman在 1978年提出来的, 见Communitions of the ACM. Vol.21.No.2. Feb.1978, PP.120-126

Euler定理: 若a与n为互素的正整数,则: aφ (n)≡1modn，推论: 若n=pq, p≠q都是素数, k是任意整数,mkφ (n）+1≡m k(p-1)(q-1)+1 ≡m mod n, 对任意0≤m≤n 证明φ (n)= (p-1)(q-1)

离散对数的计算:
y≡gx mod p 已知g,x,p,计算y是容易的 已知y,g,p,计算x是困难的。
至今没有有效的求解方法。
指数函数及其性质 指数函数y=ax mod p，已知x求y 是一个可解问题，但其逆过程：已知y求 x称为离散对数问题，所以指数函数被认 为是一个单向函数。 Fermat定理：p素数，a是整数且不能被 p整除，则:ap-1≡1modp


乘法逆元：n是整数 当ax=1modn，x是a的乘法逆元。a的逆元记作 a-1，根据Fermat定理，p是素数，若gcb(a,p)=1， ap-2modp是a的乘法逆元。 Euclid计算公因数gcd(a，b)=gcd（b，a mod b）;可以通过扩展的Euclid算法可以 算 :ed=kφ (n)+1 知道e，d，φ (n)其中两个求另 一个。因此：aed ≡amodn
Diffie-Hellman密钥交换方案
算法：通信方A和B
① ② ③ ④ ⑤ ⑥ ⑦
双方选择素数p以及p的一个原根a 用户A选择一个随机数Xa < p，计算Ya=aXa mod p 用户B选择一个随机数Xb < p，计算Yb=aXb mod p 每一方保密X值，而将Y值交换给对方 用户A计算出K=YbXa mod p 用户B计算出K=YaXb mod p 双方获得一个共享密钥(aXaXbmod p)


有限域的乘法群上的离散对数问题(The Discrete Logarithm Problem,ElGamal体制） 椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem,类比的ElGamal体 制）
大整数分解问题和离散对数是构造RSA算法的重
5.1.3 公开密钥密码加密: X→Y: Y = EKU(X) 解密: Y→X: X = DKR(Y) = DKR(EKU(X)) 知道加密算法,从加密密钥得到解密密钥在计算上是不 可行的。（单向函数的性质） 两个密钥中任何一个都可以用作加密而另一个用作解 密(单向函数的交换性，不是必须的) X = DKR(EKU(X)) = EKU(DKR(X))
5.1 公钥密码体制的基本原理
公钥密码体制采用了两个不同的密 钥，这对在公开的网络上进行保密通信、 密钥分配、数字签名和认证有着深远的 影响。
5.1.1 对称算法的不足
密钥管理量的困难：两两分别用一个密钥时， 则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户 量增大时，密钥空间急剧增大。如:n=100 时， 共4,995个；n=5000时增加到12,497,500个。 密钥建立问题：对协商密钥的信道的安全性的 要求比正常的传送消息的信道的安全性要高。 数字签名的问题：传统加密算法无法实现抗抵 赖的需求。
要基础
整数因子分解问题 许多密码系统的安全性都依赖于整数 因子分解的困难性。如RSA加密方案， RSA签名方案和Rabin公钥加密方案。
定义：给定一个正整数n，找到它的素因子，即 n=p1e1p2e2…pkek,这里pi是不同的素数，并且ei≥1。如： 91=7×13 ; 3600=24×32×52

1. 2. 3.
密码学中常用的主要有三个群的离散对数
有限域GF（p）的乘法群 有限域GF（2n）上的乘法群 有限域F上的椭圆曲线群
5.1.7
设计公钥密码体制
利用指数函数设计一个公钥密码体 制用于密钥协商：通信双方根据对方公 开的信息，通过协商获得一对密钥（对 称密钥），用来对以后的信息数据进行 加密。
5.1.5 部分数学基础
涉及计算复杂性、近世代数等内容。 严格单向函数
一个单射函数f: 如果下述条件成立： 存在一个有效的方法，对所有的x∈X可计算f （x），但不存在一个有效的办法由y= f（x）计 算x,所有的y∈Y。 则称X→Y称为是严格单向函数。


陷门单向函数
单向陷门函数是满足下列条件的函数f： (1)给定x，计算y=fk(x)是容易的；
(2)给定y, 计算x使x=fk-1(y)是不可行的。
(3)存在k，已知k时,对给定的任何y，若相应的x存 在，则计算x使fk-1(x)是容易的。
5.1.6 公钥密码基于的数学难题



背包问题 大整数分解问题（The Integer Factorization Problem,RSA 体制） 离散对数问题：