密码学-加密演算法 第3章 基础数论.ppt

《密码学-加密演算法 第3章 基础数论.ppt》由会员分享，可在线阅读，更多相关《密码学-加密演算法 第3章 基础数论.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 返回总目录返回总目录返回总目录返回总目录 第第3章章基础数论基础数论1.2 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论教学目的教学目的了解模运算及辗转相除法了解模运算及辗转相除法了解模运算及辗转相除法了解模运算及辗转相除法了解中国余式子定律了解中国余式子定律了解中国余式子定律了解中国余式子定律了解了解了解了解LagrangeLagrange定理与费马小定理定理与费马小定理定理与费马小定理定理与费马小定理了解原根、二次剩余、了解原根、二次剩余、了解原根、二次剩余、了解原根、二次剩余、GaloisGalois域等概念域等概念域等概念域等概念了解质数理论和连分数了解质数理论和

2、连分数了解质数理论和连分数了解质数理论和连分数了解密码安全伪随机数字生成器了解密码安全伪随机数字生成器了解密码安全伪随机数字生成器了解密码安全伪随机数字生成器 1.3 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论 模运算与辗转相除法模运算与辗转相除法本章内容本章内容本章内容本章内容 中国余式子定律中国余式子定律 LagrangeLagrange定理与费马小定理定理与费马小定理定理与费马小定理定理与费马小定理 原根原根 二次剩余二次剩余 GaloisGalois域域 连分数连分数 质数理论质数理论 密码安全伪随机数字生成器密码安全伪随机数字生成器密码安全伪随机数字生成器密码安

3、全伪随机数字生成器 1.4 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论模运算与辗转相除法模运算与辗转相除法3.1 模运算与辗转相除法假设今天是星期五，请问10000天后是星期几？（即5+10000除以7的余数）即：10000天后是星期二 1.5 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论同余同余定义（同余，（同余，CongruenceCongruence）：令）：令 。令。令 为两整数，称为两整数，称a a同余同余b b模模n n，记为，记为 ，当，当n n整整除除b-ab-a。而所有与。而所有与a a同余的整数所组成的集合，即同余的整数所组成的集合

4、，即称为称为a a的同余类。所有同余类所形成的集合的同余类。所有同余类所形成的集合 1.6 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论同余类同余类同余类满足的性质：同余类满足的性质：（1）（反身性，Reflexivity）（2）（对称性，Symmetry）若若 则则（3）（迁移性，Transitivity）若若 则则例：令令 则则1.7 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论模运算模运算加法：加法：（1 1）封闭性：若同余类）封闭性：若同余类 则则 （2 2）交换律：若同余类）交换律：若同余类 则则 （3 3）结合律：若同余类）结合律：若同余类

5、则则 （4 4）存在加法单位素：存在）存在加法单位素：存在 ，使得，使得 （5 5）存在加法反元素：对任一）存在加法反元素：对任一 存在存在 使得使得 减法：减法：乘法：乘法：1.8 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论交换群交换群定义（交换群）（交换群）考虑考虑 ，其中，其中G G为集合，而为集合，而*为运算。令公理：为运算。令公理：（1 1）封闭性：）封闭性：则；则；（2 2）交换律：）交换律：则；则；（3 3）结合律：）结合律：则；则；（4 4）存在单位素：）存在单位素：，使得，使得（5 5）存在反元素：）存在反元素：，使得，使得若公理若公理1 1、3 3、4

6、 4、5 5成立，称为成立，称为群群(Group)(Group)；若以上公理若以上公理1 15 5都成立，称为都成立，称为交换群交换群。1.9 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论交换环交换环此时除了此时除了 为交换群以外，另外针对乘法为交换群以外，另外针对乘法运算也满足封闭性、交换律、结合律以及存在乘法单运算也满足封闭性、交换律、结合律以及存在乘法单位素（即位素（即 ）等性质，但并）等性质，但并非所有非零元素都有乘法反元素，另外乘法对加法有非所有非零元素都有乘法反元素，另外乘法对加法有分配律，即：分配律，即：若若 则则此时，以代数的术语，称此时，以代数的术语，称

7、为为交换环交换环（Commutative RingCommutative Ring）。）。考虑考虑1.10 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论辗转相除法辗转相除法例：求7812及6084的最大公因子 被除数被除数=商商 除数除数+余数，余数，gcdgcd（被除数，除数）（被除数，除数）=gcdgcd（除数，余数）（除数，余数）辗转相除法辗转相除法就是利用此性质，反复以就是利用此性质，反复以（除数（除数/余数）取代（被除数余数）取代（被除数/除数）除数）k01234567rk78126048172890082872360qk1311112其中：其中：所以gcd(78

8、12,6084)=36 1.11 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论辗转相除法辗转相除法定理3.1 整数线性方程整数线性方程有整数解有整数解 证明：证明：若若 则：则：为一整数解为一整数解若若有整数解有整数解因：因：且且所以所以借助广义辗转相除法，存在整数 ，使得 1.12 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论对模乘法对模乘法例：令令n n为自然数，则为自然数，则对模乘法为交换群对模乘法为交换群 证明：证明：根据交换群封闭性根据交换群封闭性则则因因 ，故存在乘法反元素，故存在乘法反元素 、使得使得且且 ，而而故故 为为 的乘法反元素。的

9、乘法反元素。1.13 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论模运算与辗转相除法模运算与辗转相除法3.2 中国余式子定理（Chinese Remainder Theorem）定理：定理：令为令为 两两互质的正整数，令两两互质的正整数，令 则同余联立方程组则同余联立方程组在集合在集合 有惟一解，其解为有惟一解，其解为其中其中 ，而，而1.14 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论余式定理应用余式定理应用其中，其中，为为n n的质因数，的质因数，性质性质1 1：存在群同构（存在群同构（Group IsomorphismGroup Isomorph

10、ism）定义：定义：当为正整数时，定义当为正整数时，定义 Euler-Phi Euler-Phi 函数为函数为 性质性质2 2：1.15 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论LagrangeLagrangeLagrangeLagrange定理与费马小定理定理与费马小定理定理与费马小定理定理与费马小定理 3.3 Lagrange定理与费马小定理 令令 为群，若为群，若 为子集，且在相同的运为子集，且在相同的运算算*形成群则称形成群则称 （或（或H H）为）为G G的子群的子群（SubgroupSubgroup）。）。子群(Subgroup)1.16 2006第第第第3

11、 3章章章章 基础数论基础数论基础数论基础数论LagrangeLagrangeLagrangeLagrange定理定理定理定理定理（LagrangeLagrange定理）定理）若若G G为有限群，为有限群，H H为为G G中之子群，则中之子群，则 证明：证明：H H为为G G的子群，为方便起见，假设为乘法群。的子群，为方便起见，假设为乘法群。可定等价关系如下：可定等价关系如下：若若 如此定义出的等价关系可将分割成若干个等价类，如此定义出的等价关系可将分割成若干个等价类，即即 每个等价类都有每个等价类都有#H#H个元素（考虑个元素（考虑 为为1 11 1对对应）。因此应）。因此#H#H整除整除#

12、G#G1.17 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论费马小定理费马小定理定理（费马小定理）（费马小定理）令为令为p p质数、质数、a a为与为与p p互质的整数，则互质的整数，则证明：证明：考虑乘法群考虑乘法群 ，为其子群，为其子群，根据根据LagrangeLagrange定理定理 所以所以其中其中因此因此：1.18 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论原根原根考虑2的次方（mod 11）：3.4 原根可以发现乘法群 中的同余类均可表示为中的同余类均可表示为22的若干次方的若干次方 此时称此时称2 2为乘法群为乘法群 的的原根原根（Pri

13、mitive RootPrimitive Root）当当 时，则时，则1010必整除必整除x x；此时称；此时称1010为为2 2在（在（mod mod 1111）（或在乘法群）（或在乘法群 ）的）的秩秩（OrderOrder）1.19 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论秩秩定义：令令G G为乘法群，而为乘法群，而g gG G为其中一元素，则元素为其中一元素，则元素g g的秩的秩（OrderOrder）定义为）定义为 也可能不存在也可能不存在x x N N使得使得 ，此时定义，此时定义 。若若G G为有限群，则为有限群，则 为为G G的子群，有的子群，有 ，根据，

14、根据LagrangeLagrange定理，子群的元素个数必整定理，子群的元素个数必整除母群除母群G G的元素个数，故的元素个数，故1.20 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论原根定理原根定理定理：令令g g为质数为质数p p上的原根，则上的原根，则 （1 1）若）若x x为整数，则为整数，则（2 2）若）若i i、j j为整数，则为整数，则证明：证明：（1 1）若）若欲证欲证假设不成立，可写假设不成立，可写 得：得：但：但：.所以：所以：有有r r个元素，这与个元素，这与p p为原根的假设矛盾。为原根的假设矛盾。（2 2）假设）假设ijij，将同余式，将同余式 两

15、边同乘以两边同乘以得：得：利用已证明的性质利用已证明的性质1 1，此等价于：，此等价于：1.21 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论子群与循环群子群与循环群令令G G为任一乘法群，为任一乘法群，为任一元素，则为任一元素，则 为为G G中的子群（封闭性与反元素的存在性自然成立）。此中的子群（封闭性与反元素的存在性自然成立）。此子群称子群称为由元素为由元素g g所生成的子群。所生成的子群。定义：子群子群定义：循环循环群（群（Cyclic GroupCyclic Group）若存在若存在 使得使得 ，则称，则称G G为循环群（为循环群（Cyclic Cyclic Gro

16、upGroup），而），而g g为原根或生成元（为原根或生成元（GeneratorGenerator）。）。1.22 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论二次剩余二次剩余3.5 二次剩余 Quadratic Residue 定义：定义：同余式同余式a a与与n n为互质整数为互质整数若有整数解，称若有整数解，称a a为（为（mod nmod n）的二次剩余）的二次剩余（Quadratic ResidueQuadratic Residue）若无解则称若无解则称a a为（为（mod nmod n）的非二次剩余（）的非二次剩余（Quadratic Quadratic No

17、nresidueNonresidue）。）。1.23 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论二次剩余的性质二次剩余的性质 性质令令p p为奇质数，可定义函数为奇质数，可定义函数 则：则：a a 为二次剩余为二次剩余 其中：其中：为二次剩余 为非二次剩余 1.24 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论LegendreLegendreLegendreLegendre符号符号符号符号 定义：令令p p为质数，定义为质数，定义LegendreLegendre符号如下：符号如下：定理（EulerEuler判别）判别）令令p p为质数，为质数，a a与

18、与p p互质。则：互质。则：1.25 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论LegendreLegendreLegendreLegendre符号符号符号符号 性质 令令p p为奇质数，为奇质数，a a、b b为与为与p p互质的整数，则互质的整数，则 （1 1）若）若则则（2 2）（3 3）（4 4）（5 5）定理Quadratic Reciprocity Quadratic Reciprocity 令令p p、q q为奇质数，则为奇质数，则 1.26 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论JacobiJacobiJacobiJacobi 符

19、号符号符号符号定义：令令a a为整数，为整数，n0n0为奇整数，其质因数分解为为奇整数，其质因数分解为 定义定义JacobiJacobi符号：符号：性质：当当n0n0为奇整数，为奇整数，JacobiJacobi符号才可能有意义符号才可能有意义 （5 5）（3 3）（4 4）（2 2）（6 6）注：注：a a、b b为整数，为整数，mm、n n为奇整数为奇整数1.27 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论GaloisGalois域域3.6 Galois域 定义域（域（FieldField）：令）：令K K为一集合，并含有两个运算为一集合，并含有两个运算“”“”及及“*

20、”“*”，则（，则（K K，*）为域）为域 公理：（K K，*）为交换群，即）为交换群，即（1 1）（）（-封闭性）封闭性）（2 2）（）（-单位素）单位素）（3 3）（）（-反元素）反元素）（4 4）（）（-结合律）结合律）（5 5）（）（-交换性）交换性）x xy yx xx xx xx xx=x=（x xy y）z z=x=x（y yz z）x xx xy y1.28 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论GaloisGalois域域公理：为交换群为交换群 即：即：（1 1）（）（*-封闭性）封闭性）（2 2）（）（*-单位素）单位素）（3 3）（）（*-反元素

21、）反元素）（4 4）（）（*-结合律）结合律）（5 5）（）（*-交换性）交换性）公理：*对有对有 分配律分配律 1.29 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论质数理论质数理论3.7 质数理论 定义令令p p为不为为不为1 1的正整数，的正整数，p p为质数（为质数（PrimePrime）若某正整数若某正整数d d整除整除p p（记为（记为 ），则），则d=1d=1或或d=pd=p。EratosthenesEratosthenes筛法筛法 1.30 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论质数定理质数定理质数定理uRiemannRiemann

22、猜想猜想uHardy-Hardy-LittlewoodLittlewood猜想猜想 与与同时为质数同时为质数 1.31 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论连分数连分数3.8 连分数定义任何以下形式的数均称为连分数任何以下形式的数均称为连分数 其中其中，q1q1、q2q2、为整数为整数1.32 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论连分数连分数 性质令令 为一实数，其连分数表达式为为一实数，其连分数表达式为 其中，其中，而其各项连分数的收敛值为：当中当中 满足递推关系及初始条件满足递推关系及初始条件1.33 2006第第第第3 3章章章章

23、基础数论基础数论基础数论基础数论连分数连分数 定理：令令 （且（且 ）为实数）为实数x x的某项连分数的收敛值的某项连分数的收敛值 1.34 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论密码安全伪随机数生成器密码安全伪随机数生成器3.9 密码安全伪随机数生成器BlumBlumShub()dop=RandomPrime();while(p%4!=3);doq=RandomPrime();while(p%4!=3);/p,q为随机质数且=3 mod 4n=p*q;dos=RandomInteger(1,n);while(gcd(s,n)!=1);/gcd(s,n)=1且s为随机

24、数种子x0=s;for(i=1;i=k;i+)xi=xi-1*xi-1%n;bi=xi&1;/取最末位;return(b1,b2,.,bk);算法Blum-Blum-Shub伪随机数字生成器 1.35 2006第第第第3 3章章章章 基础数论基础数论基础数论基础数论密码安全伪随机数生成器密码安全伪随机数生成器 算法RSA伪随机数字生成器 RSA_PseudomBitGen()p=RandomPrime();q=RandomPrime();n=p*q;phi=(p-1)*(q-1);doe=RandomInteger(2,phi-1);while(gcd(e,phi)!=1);/gcd(e,phi)=1x0=RandomInteger(1,n-1);/x0为随机数种子for(i=1;i=k;i+)xi=PowerMod(xi-1,e,n);/xi=xi-1e%nbi=xi&1;/取最末位;return(b1,b2,.,bk);