网络信息安全crypto-8数论入门课件.ppt
2023/3/18,现代密码学理论与实践-08,1,网络信息安全Chapter 8 Introduction to Number Theory,2023/3/18,现代密码学理论与实践-08,2/68,第二部分 公钥密码和散列函数,第8章：数论入门第9章：公钥密码与RSA第10章：密钥管理和其他公钥密码体制第11章：消息认证和散列函数第12章：散列和MAC算法第13章：数字签名和认证协议,2023/3/18,现代密码学理论与实践-08,3/68,本章要点,素数是一种整数，在整除意义下，它只能被自身(正负)和1整除。素数在数论和密码学里扮演重要角色。在公钥密码里起重要作用的两个定理是费马定理和欧拉定理。许多密码算法的一个重要前提是能够选择一个大的素数。开发有效算法判定一个随机整数是否为素数是密码研究重要课题。离散对数是许多公钥算法的基础。离散对数和普通对数类似，但是在模算术上进行运算。,2023/3/18,现代密码学理论与实践-08,4/68,8.1 素数Prime Numbers,素数的因子是1和其自身 不能写作其他数的乘积形式 1是素数，但是通常没有什么作用 如，2,3,5,7是素数,4,6,8,9,10不是素数是数论的核心小于200的素数如下 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199,2023/3/18,现代密码学理论与实践-08,5/68,小于2000的素数,2023/3/18,现代密码学理论与实践-08,6/68,One-way Function and One-way Trapdoor Function,定义8.1 单向函数(One-way Function)一函数f 若满足下列条件,则称f 为单向函数：(1)对于所有属于f 域的任一x,容易计算y=f(x)(2)对于几乎所有属于f 域的任一y,求得x,使y=f(x),在计算上不可行。定义8.2 单向陷井门函数(One-way Trapdoor Function)一“可逆”函数F若满足下列二条件,则称F为单向陷井门函数:(1)对于所有属于F域的任一x,容易计算F(x)=y；(2)对于几乎所有属于F域的任一y,除非获得暗门信息(trapdoor),否则求出x,使得 x=F-1(y)在计算上不可行,F-1为F之逆函数;如有额外信息(暗门),则容易求出 x=F-1(y)。,2023/3/18,现代密码学理论与实践-08,7/68,1.Discrete Logarithm Problem(DLP)离散对数问题令质数p满足p-1含有另一大质数q(q整除p-1)及一整数g,1g p-1。若给定整数x,求y=gx mod p,最多需要Llog2x+w(x)-1次乘法,w(x)为x中所有1的个数。如x=15,即 x=(1111)2,w(x)=4,则g15=(g2)g)2g)2g mod p,只需要3+4-1=6次乘法。但是若给定p,g及y,求x,则为DLP问题,最快方法需要L(p)=exp(lnpln(lnp)次运算。当p=512位时,L(p)约为22561077,计算上不可行,因为21001030,计算要1016年。,单向函数举例,2023/3/18,现代密码学理论与实践-08,8/68,2.Factorization Problem 因数分解问题给定大素数 p和q,求n=pq,只要一次乘法给定n,求p和q,即为因数分解问题(FAC),最快方法需要 T(n)=exp c(ln n ln(ln n)次运算,其中c为大于1的正整数。若pn,解离散对数比因数分解难。3.背包问题Knapsack Problem给定有限个自然数序列集合B=(b1,b2,bn)及二进制序列x=(x1,x2,xn),xi(0,1),求S=xibi最多只需n-1次加法；但若给定B和S,求x则非常困难。穷举时有2n种可能,当n很大时为计算上不可行。Garey和Johnson证明,背包问题是NP问题(Non-Polynomial),单向函数举例(续),2023/3/18,现代密码学理论与实践-08,9/68,单向函数的交换性(commutative property)单向函数本身对近代密码学领域用处不大，但若具有交换性，则作用大。定义8.3 交换性令Z为一集合，F为将Z映射到Z本身的函数集合。令zZ,Fx(z)表示此函数集合之第x函数,若Fx(Fy(z)=Fy(Fx(z)，则称此函数集合具有交换性。例：D(E(m)=E(D(m),单向函数及其交换性,2023/3/18,现代密码学理论与实践-08,10/68,8.2 费马定理和欧拉定理,定理8.1 费马定理 Fermats Theorem若p是素数,a是正整数且不能被p整除,则ap-1 mod p=1证明：因为a mod p,2a mod p,.,(p-1)a mod p是1,2,.,(p-1)的置换形,所以,(a2a.(p-1)a)(12.(p-1)(mod p)(p-1)!mod p.但是,a2a.(p-1)a=(p-1)!ap-1,因此(p-1)!ap-1(p-1)!mod p,两边去掉(p-1)!,即得ap-1mod p=1.例如：a=7,p=19,ap-1mod p=718 mod 19=?72=4911 mod 19 74=1217 mod 19 78=4911 mod 19 716=1217 mod 19 ap-1=718=716x727x111 mod 19,2023/3/18,现代密码学理论与实践-08,11/68,8.2 费马定理和欧拉定理,用a乘以集合中所有元素并对p取模，则得到集合X=a mod p,2a mod p,(p-1)a mod p。因为p不能整除a，所以X的元素都不等于0，而且各元素互不相等。假设ja ka(mod p),其中1jkp-1,因为a和p互素，所以两边可以把a消去，则推出j k(mod p)，而这是不可能的。因此X的p-1个元素都是正整数且互不相等。所以说X和1,2,p-1构成相同，只是元素顺序不同。,2023/3/18,现代密码学理论与实践-08,12/68,费马定理的等价形式,费马定理等价形式 apa mod p,p是素数例如：p=5,a=3,35=2433 mod 5 p=5,a=10,105=10000010 mod 50 mod 5,13,（1）计算610 mod 11；（2）计算312 mod 11。,费马小定理(范例),14,（1）计算610 mod 11若p是素数,a是正整数且不能被p整除,则ap-1 mod p=1解法：我们可得610 mod 11=1。这是p=11 时，可以使用费马小定理的第一个版本直接计算得到。,费马小定理（范例）,15,（2）计算312 mod 11apa mod p,p是素数解法：此处指数（12）和模数（11）是不同的。,费马小定理（范例）,2023/3/18,现代密码学理论与实践-08,16/68,费马大定理（费马最后定理）,将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。关于此，我确信已发现了一种美妙的证法，可惜这里空白的地方太小，写不下,17,欧拉（Euler，Lonard，1707年4月15日1783年9月18日）是瑞士数学家和物理学家。,欧拉定理,2023/3/18,现代密码学理论与实践-08,18/68,欧拉函数：Eulers Totient Function(n),(n)是比n小且与n互素的正整数的个数，即模n的缩剩余系中元素之个数。,2023/3/18,现代密码学理论与实践-08,19/68,欧拉函数(n)的证明,定理8.2 p和q是素数,n=p*q,(n)=(p)(q)=(p-1)(q-1)显然，对于素数p，(p)=p-1证明：考虑余数集合0,1,(pq-1)中不与n互素的余数集合是p,2p,(q-1)p,q,2q,(p-1)q和0,所以(n)=pq-(q-1)+(p-1)+1=pq-(p+q)+1=(p-1)(q-1)=(p)(q),20,欧拉定理,对任意互质的a和n有：,21,（1）若 n 是素数，根据 和费马小定理，則上式成立；若p是素数,a是正整数且不能被p整除,则ap-1 mod p=1（2）所有小于 n，且与 n 互质的正整数的集合,欧拉定理（证明）,22,欧拉定理（证明）,即每一个元素都有gcd(xi,n)=1。用a与R中的每个元素模n相乘：S是R的一个排列，因为(1)a与n互素，且xi与n互素，所以axi必与n互素，这样S中所有元素均小于n且与n互素。(2)S中没有重复元素，所以集合S是集合R的一个置换。,23,欧拉定理（证明）,2023/3/18,现代密码学理论与实践-08,24/68,8.4 Chinese Remainder Theorem,中国余数定理CRT说明某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构Z10(0,1,9)中的10个整数可通过它们对2和5(10的素因子)取模所得的两个余数来重构.假设数x的余数r2=0 且r5=3,即x mod 2=0,x mod 5=3,则x是Z10中的偶数且被5除余3,唯一解x=8.一种CRT的表示形式令M=mi,其中mi两两互素,1=i,j=k,ij,gcd(mi,mj)=1将Zm中的任一整数对应一个k元组,该k元组的元素均在Zmi中,对应关系为A(a1,a2,ak),其中AZm,对1=i=k,aiZmi,且ai=A mod mi,2023/3/18,现代密码学理论与实践-08,25/68,8.4 Chinese Remainder Theorem,断言一对任何A，0AM，有唯一的k元组(a1,a2,ak)与之对应，其中0aimi，并且对任何这样的k元组(a1,a2,ak)，ZM中有唯一的A与之对应。,2023/3/18,现代密码学理论与实践-08,26/68,8.4 Chinese Remainder Theorem,由A到(a1,a2,ak)的转换显然是唯一确定的。即只需取ai=A mod mi。对给定的(a1,a2,ak)，可如下计算A。,2023/3/18,现代密码学理论与实践-08,27/68,8.4 Chinese Remainder Theorem,第二个断言与算术运算有关，可从模算术规则推出,2023/3/18,现代密码学理论与实践-08,28/68,Chinese Remainder Theorem,定理8.7 中国余数定理,Chinese Remainder Theorem令d1,dt两两互素,n=d1d2dt,则x mod di=xi,i=1,t 在0,n-1中有一个公共解x.证明：对每一个I,i=1,t,gcd(di,)=1,存在yi,使得()yi mod di=1;进一步地,()yi mod dj=0,ji,(因为dj是()的一个因数)令x=()yi xi mod n.x mod di=()yixi mod di=xi,()yi mod di=1)x是x mod di=xi(1it)的公共解。,2023/3/18,现代密码学理论与实践-08,29/68,孙子定理(孙子算经,3-5世纪),今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何。x mod 3=2n=3*5*7=105x mod 5=3d1=3,d2=5,d3=7x mod 7=2x1=2,x2=3,x3=2,2023/3/18,现代密码学理论与实践-08,30/68,孙子定理(孙子算经,3-5世纪),今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何。x mod 3=2n=3*5*7=105x mod 5=3d1=3,d2=5,d3=7x mod 7=2x1=2,x2=3,x3=2(1)求yi，()yi mod di=1()y1 mod 3=1()y2 mod 5=1()y3 mod 7=1得：35 y1 mod 3=1y1=221 y2 mod 5=1y2=115 y3 mod 7=1y3=1(2)x=(352221131512)mod 105=23,2023/3/18,现代密码学理论与实践-08,31/68,8.5 离散对数(discrete logarithm),幂运算是相对容易的,求解离散对数通常是难解问题离散对数是包括Diffie-Hellman密钥交换和数字签名(DSA)在内的许多公钥算法的基础。,2023/3/18,现代密码学理论与实践-08,32/68,Discrete Logarithms,模n的整数幂根据欧拉定理(定理8.3),a(n)mod n=1.考虑欧拉定理更一般的形式：am mod n=1,gcd(a,n)=1,至少有一个整数m满足am mod n=1,即m=(n),使其成立的最小正幂m为下列之一：a(模n)的阶a所属的模n的指数a所产生的周期长度7模19的各次幂71=7 mod 19;72=49=2x19+11=11 mod 1973=343=18x19+1=1 mod 19;74=2401=126x19+7=7 mod 1975=16807=884x19+11=11 mod 19因为73=1 mod 19,可得73j=737J=7J mod 19,这说明若7的两个指数相差3或3的倍数，则以它们为指数的7的模19幂是相同的，即该序列是周期性的，且其周期长是使7m=1 mod 19成立的最小正幂m。,2023/3/18,现代密码学理论与实践-08,33/68,Discrete Logarithms,更一般地,(n)是一个数所属的模n的可能的最高指数,如果一个数的阶是(n),则称之为n的本原根。若a是n的本原根,则其幂a,a2,a(n)是模n各不相同的,且均与n互素;若a是素数p的本原根,则a,a2,ap-1是模p各不相同的。素数19的本原根为2,3,10,13,14和15。不是所有的整数都有本原根，只有形为2,4,p和2p的整数才有本原根，这里p是任何奇素数，是正整数。,2023/3/18,现代密码学理论与实践-08,34/68,模19的整数幂,总结,素数，合数，单项函数，单项陷门函数费马定理欧拉函数，欧拉定理中国剩余定理离散对数问题,2023/3/18,现代密码学理论与实践-08,35/68,
