通信安全密码学.ppt

陷门单向函数 定义：对fz:Az?Bz，z∈Z，Z是陷门信息集 （1）对所有z∈Z，在给定z下容易找到一对算法Ez和Dz使对所有x∈A,易于计算fz及其逆，即 fz(x)=Ez(x) Dz(fz(x))=x 而且当给定z后容易找到一种算法Fz，称Fz为可用消息集鉴别函数，对所有x∈A，易于检验是否x∈Az（Az属于A）, Az是可用的明文集。 陷门单向函数 （2）对几乎所有z∈Z，当只给定Ez和Fz时，对几乎所有x∈Az，很难或实际上不可能从y=Fz(x)算出x。 （3）对任一z，集Az必须是必威体育官网网址系统中明文集中的一个方便集。即便于实现明文到它的映射。 陷门单向函数 如果我们要构造一个公钥密码体制，仅给出一个单向的单射函数是不够的。从Alice的观点来看，并不需要E是单向的，因为它需要用有效的方式解密所收到的信息。因此，Alice应该拥有一个陷门，其中包含容易求出E的逆函数的秘密信息。也就是说，Alice可以有效解密，因为它有额外的秘密知识，即SK，能够提供给你解密函数D。 因此，我们称一个函数为一个陷门单向函数，如果它是一个单向函数，并在具有特定陷门的知识后容易求出其逆。 公钥系统 在一个公钥系统中，所有用户共同选定一个陷门单向函数，加密运算E及可用消息集鉴别函数F。用户i从陷门集中选定zi，并公开Ezi和Fzi。任一要向用户i送机密消息者，可用Fzi检验消息x是否在许用明文之中，而后送y=Ezi(x)给用户x即可。 在仅知y，Ezi和Fzi下，任一用户不能得到x,但用户i利用陷门信息zi，易于得到Dzi(y)=x。 构造双钥密码的单向函数 多项式求根 给定a0,a1,…,an-1,p和x最多通过n次乘法和n-1次加法，求y 反之，已知y,a0,a1,…,an-1，求解x需要对高次方程求根。至少要 次乘法。 构造双钥密码的单向函数 离散对数 已知x，求 容易，但已知y,g,p求 为离散对数问题。最快求解法运算次数渐近值为 构造双钥密码的单向函数 大整数分解 判断一个大奇数n是否为素数的有效算法，大约需要计算量 ，当n为256或512位二元数时，用当前计算机可在10分钟内完成。 已知二大素数p和q，求n=pq只需要一次乘法。但若由n求p和q，则是几千年来数论专家的攻关对象！ RSA算法 当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。 它是一个基于数论的非对称(公开钥)密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。 它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。 RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。 RSA原理 1)??任意选取两个不同的大质数p和q，计算乘积r=p*q； 2)??任意选取一个大整数e，e与(p-1)*(q-1)互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的质数都可用。 3)??确定解密密钥d： d * e = 1 mod（p - 1）*（q - 1） 根据e、p和q可以容易地计算出d。 RSA原理 4)??公开整数r和e，但是不公开d； 5)??将明文P (假设P是一个小于r的整数)加密为密文C，计算方法为：  C = Pe mod r 6)??将密文C解密为明文P，计算方法为：  P = Cd mod r 然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。 RSA原理 证明 欧拉函数值Φ(r)=(p-1)(q-1) Cd=(Pe)d, de=1 mod Φ(r), ? de=sΦ(r)+1 欧拉定理? (C,r)=1, Cr=1 mod r 　Cd=Cde=Csr+1=C·Csr=C ·1=C mod r 简单示例 选取p=7,q=9,?r=63, (p-1)(q-1)=48, 选取加