1、密码学的数学基础密码学的数学基础初等数论初等数论素数的产生素数的产生有限域内的离散对数有限域内的离散对数单向哈希函数单向哈希函数 初等数论初等数论1. 模运算模运算2. 素数素数3. 最大公因数最大公因数4. 乘法逆元素乘法逆元素5. Fermat小定理及欧拉函数小定理及欧拉函数6. 中国剩余定理中国剩余定理7. 二次剩余二次剩余8. Legendre（勒让得）符号勒让得）符号9. Jacobi（雅各比）符号雅各比）符号10. 生成元生成元11. 有限域中的计算有限域中的计算1 模运算模运算同余：如果同余：如果a = b + kn，k为整数，则为整数，则a b（mod n）a mod n ：a
2、模模n操作操作，表示表示a除以除以n的余数，的余数，为为 0到到n 1之间的整数。之间的整数。例如：例如：(79) mod 12 = 16 mod 12 = 4 模运算（模运算（+、 ）满足交换律、结合律和）满足交换律、结合律和分配律。分配律。按模计算原理：对中间结果作模运算与做完了按模计算原理：对中间结果作模运算与做完了全部运算后再做模运算结果相同。全部运算后再做模运算结果相同。按模指数运算：按模指数运算：am mod n将指数运算作为一系列乘法运算，每次做一次模运将指数运算作为一系列乘法运算，每次做一次模运算。算。例：例：a8 mod n = (a2 mod n)2 mod n)2 mod
3、 n当当m不是不是2的乘方时，将的乘方时，将m表示成表示成2的乘方和的形式。的乘方和的形式。例如：例如：25=(11001)2，即，即25=24+23+20 a25 mod n = (a16 a8 a) mod n = (a2)2)2)2 (a2)2)2 a) mod n = (a2 a)2)2)2 a) mod n适当存储中间结果，则只需适当存储中间结果，则只需6次乘法：次乘法：(a2mod n) a)mod n)2mod n)2mod n)2mod n) a)mod n定理：若定理：若a b mod m，c d mod m，则则1. a c b d mod m2. ac bd mod m证
4、：证：a=km+b；c=hm+d定理：若定理：若ac bc mod m，且且gcd（c,m）=1，则则a b mod m 证明：因为证明：因为 ac bc mod m所以所以 ac=km+bc所以所以 c（a-b）=km又因为又因为 gcd（c,m）=1所以所以 c|k所以所以 k=hc所以所以 a-b=hm所以所以 a b mod m定理：若定理：若ac bc mod m，d=gcd（c,m），），则：则：a b mod m/d 因为因为 ac bcmod m所以所以 ac=km+bc所以所以 c（a-b）=km又因为又因为 d=gcd（c,m）所以所以 c=c1d，m=c2d，gcd（c1
5、,c2）=1所以所以 c1d（a-b）=kc1d所以所以 c1（a-b）=kc2又因为又因为 gcd（c1,c2）=1所以所以 c1|k所以所以k=hc1所以所以 a-b=khc2所以所以 a b mod c2 所以所以 a b mod （m/d） 2 素数素数素数（质数）：大于素数（质数）：大于1的整数，只能被的整数，只能被1和本身整除。和本身整除。有无穷多个素数。有无穷多个素数。如：如：2，73，2521，2365347734339，2756839-1整数的表示法整数的表示法1987的的10进制表示：进制表示：110391028107定理：设定理：设m是大于是大于1的正整数，则每个正整数的
6、正整数，则每个正整数n可可唯一的表示为：唯一的表示为： n=CkmkCk-1mk-1C1mC0 m为基（为基（radix）设设n0=n，则则n1= n0/m C0=n0 mod m所以所以 Ci=ni mod m ni1= ni /m 例：例：n=389；m=5n0=389 ；C0=389 mod m=4n1=389/5=77；C1=n1 mod 5=2n2=77/5=15；C2= n2 mod 5=0n3=15/5=3；C3= n3 mod 5=3所以所以 389=353254=（3024）5 3 最大公因数最大公因数公因数：两个整数公因数：两个整数a，b的公因数定义为能同时的公因数定义为能
7、同时整除整除a，b的所有整数。的所有整数。 3为为6的因子，记为的因子，记为3|6，3除尽除尽6 任意的任意的a|b，a|c，称称a为为b，c的公因子的公因子 最大公因数：最大公因数：a与与b的公因数中能被所有的公因数中能被所有a，b的公因数整除的正整数，记为的公因数整除的正整数，记为gcd(a，b)。互素（互质）：两个整数称为互素的，如果它互素（互质）：两个整数称为互素的，如果它们除了们除了1以外没有其他的公因数，即以外没有其他的公因数，即 gcd(a,b)=1。定理：若定理：若a=bq+r，则则gcd（a,b）= gcd（b,r） 证明：证明：d=（a,b），），d=（b,r）d| a b
8、q d | r，d为为b,r的公因数；的公因数； d|d d=hdd|bq+r d|a，d为为a,b的公因数；的公因数；d|d d=kd所以所以 kh=1 k=h= 1； 最大公因数的求法：辗转相除法最大公因数的求法：辗转相除法例如：求例如：求gcd(15,36)36= 2+= 2+= 2+0因此，因此，gcd(15,36)=3原理：若原理：若a b (mod c)，则则 gcd(a,c) = gcd(b,c)这里，这里，gcd(15,36) = gcd(15,6) = gcd(6,3) = 3求最大公因数的求最大公因数的Euclid算法算法4 乘法逆元素乘法逆元素求求x，满足满足 (a x)
9、 mod n = 1, 即即 x a-1(mod n)当当a与与n互素时互素时, 方程方程 x a-1(mod n) 有唯一解；有唯一解；当当a与与n不互素时不互素时, 此方程无此方程无解。解。如果如果n为素数，则从为素数，则从1到到n-1的任意整数都与的任意整数都与n互素，互素，即在即在1到到n-1之间都恰好有一个关于模之间都恰好有一个关于模n的乘法逆元。的乘法逆元。求乘法逆元：扩展求乘法逆元：扩展的的Euclid算法算法例：求例：求5关于模关于模14的乘法逆元的乘法逆元辗转相除：辗转相除： = 2 + = + 1逆推：逆推：1 = - = - （ - 2）= 5 3 - 14 因此，因此，
10、5关于模关于模14的乘法逆元为的乘法逆元为3。5 Fermat小定理及欧拉函数小定理及欧拉函数Fermat小定理：如果小定理：如果m为素数，为素数，a不能被不能被m整整除，则除，则 am-1 1 (mod m)模模n的简化剩余集：模的简化剩余集：模n的的完全剩余集的一个完全剩余集的一个子集，其中每个元素与子集，其中每个元素与n互素。互素。欧拉函数：记为欧拉函数：记为 (n)，为模为模n的简化剩余集中的简化剩余集中元素的个数。元素的个数。如果如果n是素数，则是素数，则 (n) = n-1设设n = p1r1 p2r2 pmrm, 其中其中p1, p2, ,pm是是n的素数因子的素数因子, 则则
11、(n) = n (1-1/p1) (1-1/p2) (1-1/pm)欧拉扩展的欧拉扩展的Fermat小定理：如果小定理：如果gcd(a,n) = 1，则则 a (n) mod n = 1。6 中国剩余定理中国剩余定理定理：如果定理：如果n的素数因子分解式为的素数因子分解式为p1 p2 pt，则一组方程则一组方程 (x mod pi）= ai，其中其中i = 1,2,t，有唯一解有唯一解x，其中其中x小于小于n（其中某其中某些些pi可能相等）可能相等）。例：今有物不知其数，三三数之剩二，五五数例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？之剩三，七七数之剩二，问物几何？
12、x mod 3 = 2x mod 5 = 3x mod 7 = 2定理：令定理：令d1，d2，,dt为两两互素，并令为两两互素，并令n=d1d2dt，则则 x mod di xi (i=1, t)在在0，n-1范围内有公共解范围内有公共解x：x= mod n其中：其中：mi=n/di，yi=mi-1 mod di解法：解法：令令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1 p2 p3=105，M1=n/p1=35, M2=n/p2=21, M3=n/p3=15求解求解 35 x1 mod 3=1, 得得x1=2求解求解 21 x2 mod 5=1, 得得x2=1求解求解
13、 15 x3 mod 3=1, 得得x3=1则则 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (35 2 2+21 1 3+15 1 2) mod 105 = 233 mod 105 = 23孙子定理的应用：孙子定理的应用：3x mod10=1解：解：10=2 5， 3x1 mod2=1 and 3x2 mod 5=1x1=3 (2)-1mod2=1, m1=5, m1-1=5 (2)-1mod2=1x2=3 (5)-1mod5=2, m2=2, m2-1=2 (5)-1mod5=3所以所以 x=（151223）mod10=7 7 二次剩余二次剩余定义：
14、设定义：设p为为素数，素数，a0且且ap，如果存如果存在某个在某个x，满足满足x2 a (mod p)，则称则称a为模为模p的二次剩余；否则称的二次剩余；否则称a为模为模p的非的非二次剩余。二次剩余。8 Legendre（勒让得）符号勒让得）符号记为记为L(a,p)，其中其中a为任意整数，为任意整数，p为大为大于于2的素数。的素数。定义：定义：L(a,p) = 0，如果如果a能被能被p整除；整除；L(a,p) = 1，如果如果a是模是模p的二次剩余；的二次剩余；L(a,p) = -1，如果如果a是模是模p的非二次剩余；的非二次剩余；计算：计算：L(a,p) = a(p-1)/2 mod p计算
15、法则（略）计算法则（略）9 Jacobi（雅各比）符号雅各比）符号记为记为J(a,n)，是是Legendre符号的扩展，其中符号的扩展，其中a为任意整数，而为任意整数，而n为任意奇数。为任意奇数。定义：定义：J(a,n)只对只对n为奇数时有意义为奇数时有意义J(0,n)=0如果如果n为素数，且为素数，且n|a，则则J(a,n)=0如果如果n为素数，且为素数，且a是模是模n的二次剩余，则的二次剩余，则J(a,n) = 1如果如果n为素数，且为素数，且a是模是模n的非二次剩余的非二次剩余，则，则J(a,n) = -1如果如果n是合数，则是合数，则J(a,n)=J(a,p1)J(a,p2)J(a,p
16、m)，其中将其中将n因数分解为因数分解为p1p2pmJacobi符号的计算（略）符号的计算（略）Blum整数：整数：若若p和和q为两个素数，且都与为两个素数，且都与3模模4同余，则同余，则n = pq称为称为Blum整数。若整数。若n为为Blum整数，整数，则每个模则每个模n的二次剩余恰好有的二次剩余恰好有4个平方根，个平方根，其中一个也是一个二次剩余，称为原平方根。其中一个也是一个二次剩余，称为原平方根。例如，例如，139的模的模437的原平方根为的原平方根为24，另三，另三个平方根为个平方根为185，252和和413。10 生成元生成元定义：如果定义：如果p为为素数，素数，gp，如果对每个
17、如果对每个b从从1到到p-1，存在存在a，使使ga b (mod p)，则则g为模为模p的生成元。的生成元。例：例：p=11，2为模为模11的生成元的生成元生成元的测试生成元的测试 素数素数q,q| p-1, s.t g(p-1)/q mod p=1, 则则g不为不为p的生成元的生成元 11 有限域中的计算有限域中的计算有限域：元素个数有限的域，也叫伽罗瓦有限域：元素个数有限的域，也叫伽罗瓦（Galois）域。域。在有限域中，非在有限域中，非0数的加、减、乘、除都有定数的加、减、乘、除都有定义。加法单位元是义。加法单位元是0，乘法单位元是，乘法单位元是1，每个非，每个非0元素都有一个唯一的乘法
18、逆元。元素都有一个唯一的乘法逆元。有限域中运算满足交换律、结合律和分配律。有限域中运算满足交换律、结合律和分配律。有限域中元素个数为素数或素数的乘方：设有限域中元素个数为素数或素数的乘方：设p为素数，则有限域可记为为素数，则有限域可记为GF(p)或或GF(pn)。不可约多项式：一个多项式如果除了不可约多项式：一个多项式如果除了1和和本身外，不能分解成其他多项式的乘积形本身外，不能分解成其他多项式的乘积形式，则成为不可约多项式。式，则成为不可约多项式。本原多项式：一个有限域内的生成元多项本原多项式：一个有限域内的生成元多项式，其系数是互素的。式，其系数是互素的。在在GF(qn)中，所有运算都是模
19、中，所有运算都是模p(x)的运的运算，其中算，其中p(x)是是n阶不可约多项式。阶不可约多项式。GF（pn）表示形式如：表示形式如：a=an-1xn-1+a1x+a0,其中其中ai是是mod p的整数。的整数。也表示：也表示：an-1an-2a1a0一般研究一般研究GF（2n），），如如GF（25）：）：a(x)=x4+x3+1表示表示11001。若若p（x）不能为次数小于不能为次数小于n的多项式之的多项式之积，则积，则p（x）称既约多项式。称既约多项式。 二元多项式系数的运算：二元多项式系数的运算：（U +V）mod 2 =UV=0 or 1 UV = UV UV = UV例 ：例 ： G
20、F （ 25） ：） ： a ( x ) = x4+x2+1,b(x)= x3+ x2ab=10101+01100=11001 例：例：a=101，p（x）=x+x+1，GF（2），），求（求（a a）mod p（x） a a=10001，p（x）= x+x+1=1011如果如果 p（x）为为GF（2n）的既约多项式，则的既约多项式，则 （p（x）=2n1。 例：例：a=100，p=1011，GF（2），），求求a-1 练习：练习：a=011，p（x）=1011，GF（2），），求求a-1 素数的产生素数的产生因数分解：对一个数进行因数分解，是指找出这因数分解：对一个数进行因数分解，是指找出这
21、个数的素数因子。个数的素数因子。素数的产生素数的产生:1. Solovay-Strassen方法方法2. Lehmann法法3. Rabin-Miller法法4. 实际应用实际应用5. 强素数强素数1 Solovay-Strassen方法方法用用Jacobi符号来测试符号来测试p是否为素数：是否为素数：（1）选择一个随机数）选择一个随机数a，a0，且且Z=1，则则p不是素数；不是素数；（5）令）令i=i+1，如果如果ib且且Z p-1，令令Z=Z2 mod p，返回第（返回第（4）步。如果）步。如果Z =p-1，则则p通过检测，可能通过检测，可能是素数；是素数；（6）如果）如果i=b且且Z p
22、-1，则则p不是素数。不是素数。一个奇合数通过一个奇合数通过t次测试的概率小于次测试的概率小于1/4t。4 实际应用实际应用（1）产生一个）产生一个n位随机数位随机数p（n位二进制）；位二进制）；（2）将最高位和最低位置为）将最高位和最低位置为1；（3）检查）检查p是否能被小素数整除：是否能被小素数整除：3，5，7，11，等等。许多实际应用中都用小于，等等。许多实际应用中都用小于256地所地所有素数去除有素数去除p；（4）对于随机数对于随机数a，进行进行Rabin-Miller测试，测试，如果如果p通过了，则产生另一个随机数通过了，则产生另一个随机数a，再进行再进行测试。选择值小一些的测试。选
23、择值小一些的a可以令计算更快。做可以令计算更快。做5次测试，如果次测试，如果p没没通过其中的一次，则产生另通过其中的一次，则产生另一个一个p再测试。再测试。5 强素数强素数强强素数素数p,q：能令乘积能令乘积n难以用特定的因难以用特定的因数分解算法进行因数分解的素数。数分解算法进行因数分解的素数。性质：性质：p-1和和q1的最大公因数很小的最大公因数很小p-1和和q-1都有大素数因子，记为都有大素数因子，记为p，q；p -1和和q-1都有大素数因子；都有大素数因子；p +1和和q+1应该都有大素数因子；应该都有大素数因子；(p-1)/2和和(q-1)/2都是素数。都是素数。有限域内的离散对数有
24、限域内的离散对数求求x，使使ax b (mod n)当当n很大时，这是一个困难的问题很大时，这是一个困难的问题并非所有的离散对数问题都有解并非所有的离散对数问题都有解密码学中常用的离散对数：密码学中常用的离散对数：GF(p)的乘法群的乘法群GF(2n)的乘法群的乘法群EC(F)单向哈希函数单向哈希函数定义：一个单向哈希函数定义：一个单向哈希函数H(M)，操作一操作一个任意长度的消息个任意长度的消息M，返回一个固定长返回一个固定长度的值度的值h。h = H(M) 。性质：性质：给定给定M，很容易计算很容易计算h；给定给定h，很难计算很难计算M，使使H(M)=h；给定给定M，很难找到另一个消息很难找到另一个消息M，使使H(M)=H(M)。
