密码学基础讲义.ppt

* 2.4.1 公开密钥理论基础 公开密钥密码是1976年由Whitfield Diffie和Martin Hellman在其“密码学新方向”一文中提出的。 单向陷门函数f(x)，必须满足以下三个条件。 ① 给定x，计算y=f(x)是容易的； ② 给定y, 计算x使y=f(x)是困难的（所谓计算x=f-1(y)困难是指计算上相当复杂已无实际意义）； ③ 存在δ，已知δ时对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。 公开密钥密码的核心思想 公开密钥的应用：加密模型 公开密钥的应用：认证模型 2.4.2 Diffie-Hellman密钥交换算法 数学知识 原根 素数p的原根（primitive root）的定义：如果a是素数p的原根，则数a mod p, a2 mod p,…, ap-1 mod p是不同的并且包含从1到p-1之间的所有整数的某种排列。对任意的整数b，可以找到唯一的幂i，满足b≡ai mod p，且1≤i≤p-1。 注：“b≡a mod p”等价于“b mod p = a mod p”，称为“b与a模p同余”。 离散对数 若a是素数p的一个原根，则相对于任意整数b（b mod p≠0），必然存在唯一的整数i（1≤i≤p-1），使得b≡ai mod p，i称为b的以a为基数且模p的幂指数，即离散对数。 对于函数y≡gx mod p，其中，g为素数p的原根，y与x均为正整数，已知g、x、p，计算y是容易的；而已知y、g、p，计算x是困难的，即求解y的离散对数x。 注：离散对数的求解为数学界公认的困难问题。 Diffie-Hellman密钥交换算法 Alice和Bob协商好一个大素数p，和大的整数g，1gp，g是p的原根。p和g无须必威体育官网网址，可为网络上的所有用户共享。当Alice和Bob要进行必威体育官网网址通信时，他们可以按如下步骤来做： ① Alice选取大的随机数xp，并计算Y=gx(mod P)； ② Bob选取大的随机数x?p，并计算Y?=gx ? (mod P)； ③ Alice将Y传送给Bob，Bob将Y?传送给Alice； ④ Alice计算K=(Y ?)X(mod P)，Bob计算K ?＝(Y) X ?(mod P) 显而易见K=K?=gxx ?(mod P)，即Alice和Bob已获得了相同的秘密值K。 2.4.3 RSA公开密钥算法 欧拉定理? 欧拉函数是欧拉定理的核心概念，其表述：对于一个正整数n，由小于n且和n互素的正整数构成的集合为Zn，这个集合被称为n的完全余数集合。Zn包含的元素个数记做φ(n)，称为欧拉函数，其中φ(1)被定义为1，但是并没有任何实质的意义。 如果两个素数p和q，且n = p×q ，则φ(n) =(p-1)(q-1)； 欧拉定理的具体表述：正整数a与n互素，则a φ(n) ≡ 1 mod n。 推论： 给定两个素数p和q，以及两个整数m、n，使得n = p×q，且0mn，对于任意整数k下列关系成立，m k φ(n)+1 = m k(p-1)(q-1)+1 ≡ m mod n。 大整数因子分解 大整数因子分解问题： 已知p、q为两个大素数，则求N=p×q是容易的，只需要一次乘法运算；但已知N是两个大素数的乘积，要求将N分解，则在计算上是困难的，其运行时间复杂程度接近于不可行。 算法时间复杂性： 如果输入规模为n时，一个算法的运行时间复杂度为O(n)，称此算法为线性的； 运行时间复杂度为O(nk)，其中k为常量，称此算法为多项式的； 若有某常量t和多项式h(n)，使算法的运行时间复杂度为O(th(n))，则称此算法为指数的。 一般说来， 在线性时间和多项式时间内被认为是可解决的，比多项式时间更坏的，尤其是指数时间被认为是不可解决的。 注：如果输入规模太小，即使很复杂的算法也会变得可行的。 RSA密码算法 RSA密码体制： 是一种分组密码，明文和密文均是0到n之间的整数，n通常为 1024位二进制数或309位十进制数， 明文空间P=密文空间C={x∈Z|0x n,Z为整数集合}。 RSA密码的密钥生成具体步骤如下： ① 选择互异的素数p和q，计算n=pq，?(n) = (p - 1)(q - 1)； ② 选择整数e，使gcd(?(n),e) = 1，且1 e ?(n)； ③ 计算d，d ? e-1 mod ?(n)，即d为模?(n)下e的乘法逆元； 公钥Pk = { e, n }，私钥Sk = { d, n, p, q } 加密：c = me mod n；解密：m = cd mod n。 RSA例 p=101，q＝113，n=11413，?(n)=100×112＝11200。 e = 3533，求得d ? e-1 mod 11200 ? 6597 mod 11