网络信息安全课件第八章

2020/2/14现代密码学理论与实践-081网络信息安全Chapter8IntroductiontoNumberTheory2020/2/14现代密码学理论与实践-082/68第二部分公钥密码和散列函数第8章：数论入门第9章：公钥密码与RSA第10章：密钥管理和其他公钥密码体制第11章：消息认证和散列函数第12章：散列和MAC算法第13章：数字签名和认证协议2020/2/14现代密码学理论与实践-083/68本章要点素数是一种整数，在整除意义下，它只能被自身(正负)和1整除。素数在数论和密码学里扮演重要角色。在公钥密码里起重要作用的两个定理是费马定理和欧拉定理。许多密码算法的一个重要前提是能够选择一个大的素数。开发有效算法判定一个随机整数是否为素数是密码研究重要课题。离散对数是许多公钥算法的基础。离散对数和普通对数类似，但是在模算术上进行运算。2020/2/14现代密码学理论与实践-084/688.1素数PrimeNumbers素数的因子是1和其自身不能写作其他数的乘积形式1是素数，但是通常没有什么作用如，2,3,5,7是素数,4,6,8,9,10不是素数是数论的核心小于200的素数如下23571113171923293137414347535961677173798389971011031071091131271311371391491511571631671731791811911931971992020/2/14现代密码学理论与实践-085/68小于2000的素数2020/2/14现代密码学理论与实践-086/68合数的素因子分解分解一个数n就是把它写成其他数的乘积形式,如n=a×b×c比起用乘的方法把几个因子乘起来生成合数,分解合数通常要困难得多。任何整数a1,可以分解为a=p1a1p2a2…ptat,其中,p1p2…pt是素数,每一个ai是正整数,如91=7x13;11011=7x112x13素因子分解就是把一个合数写成若干素数的乘积形式，如3600=24x32x52PpapPa2020/2/14现代密码学理论与实践-087/68合数的素因子分解任一给定的正整数,可通过简单列出所有后面公式中非零指数分量来说明.Ex：12可以表示为{a2=2,a3=1},18可以表示为{a2=1,a3=2},91可以表示为{a7=1,a13=1}两个数的乘法等同于对应指数分量的加法k=mn→kp=mp+np对所有pEx：k=12x18=(22x3)x(2x32)=216,k2=2+1=3,k3=1+2=3,∴216=23x33如果任何以pk形式表示的整数仅能被对应素数分量小于或等于它的另一个整数pj整除,其中j≤k,因此有a|b→ap≤bp对所有p.Ex：a=12,b=36,12|36,12=22x31,36=22x32a2=2=b2,a3=1≤2=b32020/2/14现代密码学理论与实践-088/68互素和最大公约数GCDgcd(a,b)=c,即c是a和b的最大公约数,当1.c是a和b的因子2.任何a和b的因子也是c的因子下列关系总是成立的如果k=gcd(a,b),则kp=min(ap,bp),对于任意的p∊P两个整数a,b,如果除了1以外没有公共因子,则称它们互素(RelativelyPrime)8和15互素,因为8的因子是1,2,4,8,而15的因子是1,3,5,15,1是它们唯一的公共因子。如果将整数表示为素数之积,则容易确定两个正整数的最大公因子300=22x31x52,18=21x32,gcd(18,300)=21x31x50=62020/2/14现代密码学理论与实践-089/68One-wayFunctionandOne-wayTrapdoorFunction定义8.1单向函数(One-wayFunction)一函数f若满足下列条件,则称f为单向函数：(1)对于所有属于f域的任一x,容易计算y=f(x)(2)对于几乎所有属于f域的任一y,求得x,使y=f(x),在计算上不可行。定义8.2单向陷井门函数(One-wayTrapdoorFunction)一“可逆”函数F若满足下列二条件,则称F为单向陷井门函数:(1)对于所有属于F域的任一x,容易计算F(x)=y；(2)对于几乎所有属于F域的任一y,除非获得暗门信息(trapdoor),否则求出x,使得x=F-1(y)在计算上不可行,F-1为F之逆函数;如有额外信息(暗门),则容易求出x=F-1(y)。2020/2/14现代密码学理论与实践-0810/681.DiscreteLogarithmProblem(DLP)离散对数问题令质数p满足p-1含有另一大质数q(q整除p-1)及一整数g,1gp-1。若给定整数x,求y=gxmodp,最多需要Llog2x｣+w(x)-1次乘法,w(x)为x中所有1的个数。如x=15,即x=(1111)2,w(x)=4,则g15=((g2)g)2·g)2·gmodp,只需要3+4-1=6次乘法。但是若给定p,g及y,求x,则为DLP问题,最快方法需要L(p)=exp{(lnpln(lnp))½}次运算。当p=512位时,L(p)约为2256≈1077,计算上不可行,因为2100≈1030,计算要1016年。单向函数举例2020/2/14现代密码学理论与实践-0811/682.FactorizationProblem因数分解问题给定大素数p和q,求n=p×q,只要一次乘法给定n,求p和q,即为因数分解问题(FAC),最快方法需要T(n)=exp{c(lnnln(lnn))½}次运算,其中c为大于1的正整数。若p≈n,解离散对数比因数分解难。3.背包问题KnapsackProblem给定有限个自然数序列集合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)单向函数举例(续)2020/2/14现代密码学理论与实践-0812/68单向函数的交换性(commutativeproperty)单向函数本身对近代密码学领域用处不大，但若具有交换性，则作用大。定义8.3交换性令Z为一集合，F为将Z映射到Z本身的函数集合。令z∈Z,Fx(z)表示此函数集合之第x函数,若Fx(Fy(z))=Fy(Fx(z))，则称此函数集合具有交换性。例：D(E(m))=E(D(m))单向函数及其交换性2020/2/14现代密码学理论与实践-0813/68指数函数(ExponentiationFunction)定义8.4指数函数令G为有限乘法群,g∈G,则对于所有整数x,Ex(g)=gx∈G,是为指数函数。通常,令G={1,2,…,p-1},p为素数,则Ex(g)=gxmodp为指数函数。指数函数之特性1.周期性(Periodicity)令序列Ex(g)={g0,g1,g2,…}为g所产生之序列。因为G是有限群,Ex(g)不可能不重复,故Ex(g)产生之序列为周期序列。2020/2/14现代密码学理论与实践-0814/68当存在最小正整数T,使得ET(g)=gT=1=g0时,称T为g在G中的阶或序(order)。根据Fermat’sTheorem,对于所有g,T必定整除p-1.例：p=11,g=2,Ex(g)={20,21,22,…,210}={1,2,4,8,5,10,9,7,3,6,1}即：20=1mod1126=9mod1121=2mod1127=7mod1122=4mod1128=3mod1123=8mod1129=6mod1124=5mod11210=1mod1125=10mod11所以T=10=11-1=p-1指数函数之特性(1)2020/2/14现代密码学理论与实践-0815/682.本原元素(素根、原根)PrimitiveElement(Root)本原元：若g∈G的阶为T=p-1,则称g为模p的本原元。(1)当g为modp的本原元时,由g产生的序列Ex(g)具有最大周期(安全性较高)。(2)对于所有素数p,其本原元必定存在。(3)当g为模p的本原元且a与p-1互素时,即gcd(a,p-1)=1,则gamodp亦必为模p之本原元素。(4)模p的本原元素个数为φ(p-1),称为尤拉商数(EulerTotientFunction),表示不大于p-1,且与p-1互素的正整数之个数,即φ(p-1)。指数函数之特性(2)2020/2/14现代密码学理论与实践-0816/68指数函数之特性(3)本原元素举例：p=11,g=2,φ(p-1)=φ(10)=4,即1,3,7,9与p-1互素。若g=2为模p之本原元素,则21=2,23=8,27=7,29mod11=6均为模11之本原元素。找到一个本原元素后可以容易找到所有本原元素,问题是如何找到第一个本原元素。3.交换性指数函数满足交换性,因为:Ex(Ey(g))=Ex(gy)=(gy)x=gyxEy(Ex(g))=Ey(gx)=(gx)y=gxy∴Ex(Ey(g))=Ey(Ex(g))2020/2/14现代密码学理论与实践-0817/684.非对称性(AsymmetricProperty)∵Ex(-g)=(-g)x=(-1)xgx=(-1)xEx(g)∴若x为偶，则Ex(-g)=Ex(g)若x为奇，则Ex(-g)=-Ex(g)5.乘法性(MultiplicativeProperty)Ex(g1)Ex(g2)=g1xg2x=(g1g2)x=Ex(g1g2)指数函数之特性(4)2020/2/14现代密码学理论与实践-0818/688.2费马定理和欧拉定理定理8.1费马定理Fermat’sTheorem若p是素数,a是正整数且不能被p整除,则ap-1modp=1证明：因为{amodp,2amodp,...,(p-1)amodp}是{1,2,...,(p-1)}的置换形,所以,(aｘ2aｘ...ｘ(p-1)a)≡(1ｘ2ｘ...ｘ(p-1))(modp)≡(p-1)!modp.但是,aｘ2aｘ...ｘ(p-1)a=(p-1)!ap-1,因此(p-1)!ap-1≡(p-1)!modp,两边去掉(p-1)!,即得ap-1modp=1.例如：a=7,p=19,ap-1modp=718mod19=?72=49≡11mod1974=121≡7mod1978=49≡11mod19716=121≡7mod19ap-1=718=716x72≡7x11≡1mod192020/2/14现代密码学理论与实践-0819/688.2费马定理和欧拉定理用a乘以集合中所有元素并对p取模，则得到集合X={amodp,2amodp,…,(p-1)amodp}。因为p不能整除a，所以X的元素都不等于0，而且各元素互不相等。假设ja≡ka(modp),其中1≤jk≤p-1,因为a和p互素，所以两边可以把a消去，则推出j≡k(modp)，而这是不可能的。因此X的p-1个元素都是正整数且互不相等。所以说X和{1,2,…,p-1}构成相同，只是元素顺序不同。2020/2/14现代密码学理论与实践-0820/68费马定理的等价形式费马定理等价形式ap≡amodp,p是素数例如：p=5,a=3,35=243≡3mod5p=5,a=10,105=100000≡10mod5≡0mod521（1）计算610mod11；（2）计算312mod11。费马小定理(范例)22（1）计算610mod11若p是素数,a是正整数且不能被p整除,则ap-1modp=1解法：我们可得610mod11=1。这是p=11时，可以使用费马小定理的第一个版本直接计算得到。费马小定理（范例）23（2）计算312mod11ap≡amodp,p是素数解法：此处指数（12）和模数（11）是不同