信息安全认证课件 第二章 数学基础

第2章数学基础主要知识点：

--数论

--代数基础

--计算复杂性理论

--单向函数

Ch2-数学基础2023/6/81因子设Z表示全体整数所构成的集合。定义2.1设a,b∈Z，a≠0，c∈Z，使得b=ac，则称a整除b，并称a是b的因子或者约数，b是a的倍数，记为a|b。定理2.1（带余除法）设a,b∈Z，b≥1，则存在唯一的整数q和r，使得a=qb+r，0≤r<b。q称a除以b所得的商，r称为a除以b所得的最小非负剩余。。Ch2-数学基础2023/6/82最大公因子定义2.2设a,b∈Z，a，b不全为0，如果c|a且c|b，则称c为a和b的公因子。特别地，我们把a和b的所有公因子中最大的，称为a和b的最大公因子，记为gcd(a,b)或者(a,b).计算两个数的最大公因子的最容易的方法是用欧几里德(Euclid)算法(辗转相除法）。Ch2-数学基础定理2.3（欧几里德算法）给定整数a和b，且b>0，重复使用带余除法，即每次的余数为除数去除上一次的除数，直到余数为0，这样可以得到下面一组方程：

a=bq1+r1,0<r1<b,b=r1q2+r2,0<r2<r1,r1

=r2q3+r3,0<r3<r2,……rj-1

=rjqj+1+0

最后一个不为0的余数rj就是a和b的最大公因子Ch2-数学基础2023/6/84欧几里德算法欧几里德算法欧几里德算法例2.1求gcd(1970，1066)用欧几里德算法的计算过程如下：1970＝1×1066+9041066＝1×904+162904＝5×162+94162=1×94+6894＝1×68+2668＝2×26+1626＝1×16+1016＝1×10+610＝1×6+46=1×4+24＝2×2+0因此gcd(1970，1066)=2Ch2-数学基础2023/6/85素数定义2.4设p∈Z，p≥2，如果p的正因子只有1和p，则称p

为素数，否则为合数若正整数a有一因子b，而b又是素数，则称b为a的素因子如果整数a与整数b的最大公因子是1，即gcd(a,b)=1，则称a与b互为素数，简称互素设(m)为小于或等于m且与m互素的正整数个数，则称其为欧拉(Euler)函数。Ch2-数学基础2023/6/86同余定义2.8两个整数a,b分别被m除，如果所得的余数相同，则称a与b对模m是同余的，记为a≡b(modm)，正整数m称为模数同余具有下面的性质：(1)若a≡b(modm)，则则m|(b-a)。反过来，若m|(b-a)，则a≡b(modm)(2)如果a=km+b(k为整数)，则a≡b(modm)(3)每个整数恰与0,1,…，m-1这m个整数中的某一个对模m同余(4)a≡b(modm)当且仅当amodm=bmodmCh2-数学基础2023/6/87等价关系的性质

同余关系是一种等价关系，具有以下性质：自反性

a≡a(modm)(2)对称性若a≡b(modm),则b≡a(modm)传递性若a≡b(modm),b≡c(modm),则a≡c(modm)Ch2-数学基础定理2.8(乘法消去律)对于ab≡ac（modm）来说，若gcd(a,m)＝1则b≡c(modm)。定理2.9(加法消去律)如果a+b≡a+c（modm），则b≡c(modm)加法消去律是没有条件，但乘法消去律的条件是gcd(a,m)＝1，即a和m互素例如6×3≡6×7≡2mod8，但3≡7mod8不成立Gcd(5,8)=1,5*3≡5*11mod8,则3≡11mod8成立Ch2-数学基础2023/6/89模运算求余运算称为模运算,下面是模运算的一些性质。(1)(a+b)modm=((amodm)+(bmodm))modm(2)(a-b)modm=((amodm)-(bmodm))modm(3)(a×b)modm=((amodm)×(bmodm))modm(4)(a×(b+c))modm=((a×b)modm)+((a×c)modm))modmCh2-数学基础2023/6/810模运算举例例如11mod8=3;15mod8=7,那么(11mod8)+(15mod8)mod8=(3+7)mod8=2(11+15)mod8=26mod8=2

在模运算中，加法单位元是0，(0+a)modm=amodm乘法单位元是1，(1×a)modm=amodmCh2-数学基础定义2.13对a∈Zm，存在b∈Zm，使得a+b≡0(modm)，则b是a的加法逆元，记b=-a。定义2.14对a∈Zm，存在b∈Zm，使得a×b≡1(modm)，则称b为a的乘法逆元。加法一定存在逆元，乘法不一定存在逆元。Ch2-数学基础2023/6/812加法逆元和乘法逆元定义乘法逆元在密码学特别是非对称密码体制中，常常需要求模逆元，求模逆元就是求乘法逆元。即寻找一个x，使得a×x≡1modm成立求模逆元问题很困难，有时有结果，有时没有结果利用扩展欧几里德算法能够计算出模逆元Ch2-数学基础模8运算的例子

模8的加法和乘法运算与普通运算一样,只是将所得的值是去模8后的余数

Ch2-数学基础2023/6/814Ch2-数学基础2023/6/815模8乘法运算的例子

模8的加法逆元和乘法逆元

对每一个x都有一个对应的y，使得x+y≡0mod8，则y是x的加法逆元。如对2，有6，使得2+6≡0mod8，那么6是2的加法逆元如果对x，存在y，使得x×y≡1mod8，则y为x的乘法逆元。如3×3≡1mod8，因此3的乘法逆元是3。Ch2-数学基础2023/6/816扩展的欧几里德算法求a=97,m=1001,求a在模1001时的乘法逆元。1001=97*10+3197=31*3+431=4*7+34=3*1+13=3*1+0

gcd(97,1001)=1逐项回代即得到1=sa+tms即为a的模1001时的乘法逆元Ch2-数学基础1=4-3*1=4-(31-4*7)回代=4*8-31=(97-31*3)*8-31回代=97*8-31*25=97*8-(1001-97*10)*25回代=97*258+1001*(-25)

则258是97在模1001下的乘法逆元。Ch2-数学基础快速指数模运算在非对称密码体制（公钥密码体制）中常常涉及指数模运算，如计算73327mod37一种方法是利用前面介绍的模运算性质(a×b)modm=((amodm)×(bmodm))modm，将指数模运算可以看做是多次重复乘法，并且在计算中间结果时就取模Ch2-数学基础2023/6/819指数模运算举例例如：计算117mod13，可以按照下面的思路：112=121≡4mod13114=(112)2≡42mod13≡3mod13117=11×112×114≡11×4×3mod13≡132mod13≡2mod13Ch2-数学基础快速求memodn算法一(1)ae,bm,c1,其中a,b,c为三大整数寄存器。

(2)如果a=0，则输出结果c即为所求的模n的大整数次幂。(3)如果a是奇数，转第(5)步。(4)a(a÷2),b(b×b)modn,转第(3)步。(5)a(a-1),c(c×b)modn,转第(2)步。Ch2-数学基础2023/6/821计算3037mod77Ch2-数学基础2023/6/822费马定理费马定理和欧拉定理在公钥密码体制中占非常重要的地位定理2.13(费马定理Format)若p是素数,且a是正整数，且gcd(a,p)=1，则：ap-1

1(modp)

举例：a=7,p=19,gcd(7,19)=1

ap-1=a18mod19≡1mod19(可验证）Ch2-数学基础2023/6/823费马定理应用举例求3201mod11P=11为素数，gcd(3,11)=1互素则根据费马定理310≡1mod113201=310*310*310*

….*310*313201mod11≡1*1*1*….*1*3(mod11)≡3(mod11)Ch2-数学基础欧拉定理定理2.14(欧拉定理)对于任何互素的两个整数a和n，有aφ(n)≡1modnCh2-数学基础欧拉函数性质求(41)

，(27)，(440)(1)(41)=41-1=40(2)(27)=(33)=33-32=18(3)(440)=(5*8*11)=(5)*(8)*(11)

=4*10*(23-22)=160Ch2-数学基础2023/6/8欧拉函数的求法：（1）如果n是素数，则ϕ(n)=n-1

（2）n＝pq，其中p，q为素数，则ϕ(n)=(p-1)(q-1)

（3）1.定义（欧拉函数）欧拉函数ϕ(n)是一个定义在正整数上的函数，ϕ(n)的值等于序列0，1，2，…，n－1中与n互素的数的个数。费马小定理和欧拉定理2023/6/8(2)欧拉定理设m>1，如果gcd(a,n)=1,则:aϕ(n)

≡1modn.

eg:

求7803的后三位数字解：7803（mod1000）的结果

ϕ(1000)=1000(1-1/2)(1-1/5)=400，有7803

≡(7400)273

≡343(mod1000)费马小定理和欧拉定理（续）2023/6/8推论（Fermat小定理）:p素数,a是整数且不能被p整除,则:ap-1≡1modp.

费马小定理和欧拉定理（续）例如：求253(mod11)=?

由Fermat小定理:

210=1024≡1(mod11)253=(210)523≡1523≡8(mod11)

2023/6/8解： （1）由费尔马定理2100（mod101）＝1（mod101） （2）243210

≡(2100)

432210

≡210

≡1024(mod101)=14eg:

计算243210

（mod101）欧拉定理的应用2023/6/87.一次同余式

(1)定义:设m∈Z+,a,b∈Z,a≠0,我们把

ax+b≡0(modm)

称为模数m的一次同余式.如果x0∈Z满足:ax0+b≡0(modm)

则称x≡x0(modm)是同余式的解.eg

:

同余式2x+1≡0(mod3)有解x0=1.

同余式2x+1≡0(mod4)无解.

同余式2x+1≡0(mod5)有解x0=2.一次同余式2023/6/8(2)一次同余式的解

定理1:

设m∈Z+,a,b∈Z,a≠0,(a,m)=1,则同余式

ax≡b(modm)恰有一个解x≡baϕ(m)-1(modm).eg:同余式2x+1≡0(mod5)有解:x0=(-1)×2ϕ(5)-1≡4×23≡32≡2(mod5)

一次同余式（续）2023/6/8

定理2:

设m∈Z+,a,b∈Z,a≠0,(a,m)=d,则同余式ax≡b(modm)有解的充要条件是d|b.在d|b的条件下,同余式有d个解.eg:

同余式2x≡3(mod4)无解⇐d=(2,4)=2ł3.

同余式2x≡4(mod6)d=(2,6)=2|4有2个解:x=2,5.

一次同余式的解2023/6/8《孙子算经》中记载着一道世界闻名的“孙子问题”：“今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”孙子问题等同于下面这样一个问题：已知x=2mod3，x=3mod5且x=2mod7，求整数x。中国剩余定理2023/6/8中国剩余定理（续）2023/6/8中国剩余定理(孙子:SunZe,公元前450年,孙子定理)：设自然数m1,m2,…mr两两互素，并记M=m1m2…mr，则同余方程组:x≡b1(modm1)x≡b2(modm2)..............x≡br(modmr)

有唯一解：

x≡b1*M1*y1+b2*M2*y2+…+br*Mr*yr(modM)Mi=M/mi,yi=Mi-1(modmi)(1ir)

中国剩余定理（续）2023/6/8例如:求以下同余方程组的解：

x≡5mod7x≡3mod11x≡10mod13中国剩余定理解同余方程组解：r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10;

模M=m1

m2

m3=1001,M1=M/m1=m2

m3=143,M2=91,M3=77.y1=M1-1(modm1)=143-1(mod7)=5,y2=4,y3=12.

解为:x=b1

M1

y1+b2

M2

y2+b3

M3

y3(modM)=5143

5+391

4+1077

12(mod1001)=13907(mod1001)=894验证:x=894=1277+5=5(mod7)素性测试很多密码算法需要随机选择一个或者多个非常大的素数一般做法是先生成大的随机整数，然后确定该大数是否是素数目前没有还没有简单有效的方法确定一个大数是否是素数定理2.15:如果p为大于2的素数，则方程x2≡1(modp)的解只有x=1和x=-1。定理2.15的逆否命题是：如果方程x

2≡1(modp)有一解，那么p不是素数Ch2-数学基础2023/6/838Miller-Rabin素性概率检验算法WITNESS(a,n)(1)将(n-1)表示为二进制形式bkbk-1…b0(2)d1fori=kdownto0do{xd；

d(d

d)modn；

if(d=1&x

1&x

n-1)thenreturnTRUE；

ifbi=1thend(d

a)modn}ifd1thenreturnTRUE；

elsereturnFALSE.Ch2-数学基础2023/6/839算法有两个输入，n是待检验的数，a是小于n的整数。如果算法的返回值为TRUE，则n肯定不是素数，如果返回值为FALSE，则n有可能是素数。

for循环后，有d=an-1modn，由费马定理可知，若n为素数，则d为1，因此若d1，则n不是素数，所以返回TRUE。因为n-1≡-1modn，所以x1，x

n-1，表示x

2≡1(modp)有不在{-1，1}中的根，因此n不为素数，返回TRUECh2-数学基础2023/6/840离散对数离散对数是许多公钥算法的基础本原根这一个重要概念假设gcd(a,n)=1,如果m是使am

≡1modn成立的最小正整数，则称它是a对模n的指数，记为Ordna

若Ordna=φ(n)，则称a是模n的本原根(primitiveroot)，也称生成元Ch2-数学基础2023/6/841求模7和模15的本原根对于模7而言，满足gcd(a,n)=1的a是{1,2,3,4,5,6}，将