数学准备 信息安全概论课件与复习提纲.pptVIP

输入：非负整数a，b，且a〉=b输出：d=gcd（a，b），满足ax+by=d的整数x与y 1 若b=0，则d?a,x ?1,y ?0,返回（d，x，y） 2 设x2 ?1，x1 ?0, y2 ?0，y1 ?1 3当b0, 3.1 q ? dow(a/b) ，r ?a-qb, x ?x2-qx1， y ?y2-qy1 3.2 a?b,b ?r，x2 ?x1, x1 ?x， y2 ?y1, y1 ?y 4则d?a,x ? x2,y ? y2,返回（d，x，y） * * 数学准备 * * AES 涉及有限域理论 RSA 涉及欧拉定理?欧拉函数，同余类，互素?数的因数分解 ECC 涉及群论，有限域理论 序列密码 特征多项式?有限域理论 * * 1 数的因数分解 因子 整数a,b,如果存在m，使a=mb，称为b整除a，记为b|a，称b是a的因子。 * * 素数 整数p(p1)为素数，如果p的因子只有±1,±p 整数分解的唯一性 任一整数a(a1)可唯一的分解为 其中p1p2…pt是素数，ai0 例：11011=7×112×13 1 数的因数分解 * * 最大公因子 c=gcd{a,b}=(a,b) c是a的因子也是b的因子 a和b的任一公因子也是c的因子 例如：12=gcd{12,60} 最小公倍数 c=lcm{a,b}=[a,b] 例如：60=lcm{15,20,30} 1 数的因数分解 * * 定理若d=gcd{a,b}，则存在整数p和q，使得d=pa+qb gcd(a,b)=1,称为a,b互素 若a和b互素，必存在整数p和q，使得1=pa+qb 1 数的因数分解 * * 若x+y ≡ 0 mod n, y为x的加法逆元。每一元素都有加法逆元 若对x，有xy ≡ 1 mod n，称y为x的乘法逆元。并非所有x都有乘法逆元。 1 数的因数分解 * * 模P乘法逆元 　　对于整数a、p，如果存在整数b，满足ab ≡ 1 mod p ，则说，b是a的模p乘法逆元。 　　定理：a存在模p的乘法逆元的充要条件是gcd(a，p) = 1  1数的因数分解 * * 例 求 5?1 mod 13 , 11?1 mod 13. 1数的因数分解 * * 2同余类 如果m|(a?b)，则称a和b模m同余，记为（称为同余式）a?b mod m * * 同余的性质 若n|(a-b)，则a≡b mod n (a mod n) ≡(b mod n),则a≡b mod n a≡b mod n，则b≡a mod n a≡b mod n， b≡c mod n，则a≡c mod n 例如： 13≡8 mod 5， 8≡23 mod 5，则13≡23mod 5 求余运算a mod n将a映射到集合{0,1,…,n-1} 2同余类 * * 定理 若a?b mod m，c?d mod m，则 (1) a ? c?b ? d mod m (2) ac?bd mod m 2同余类 * * 加法的可约律 (a+b)≡(a+c) mod n, 则b≡c mod n 例如：(1+11)≡(1+1) mod 5, 则11≡1 mod 5 对乘法不一定成立，但有定理 若ac?bc mod m, 且c与m互素，则a?b mod m  2同余类 * * 3欧几里德算法 求两个正整数的最大公因子 两个正整数互素，可以求一个数关于另一个数的乘法逆元 性质: 对任意非负整数a和正整数b,有 gcd(a,b)=gcd(b,a mod b)