密码学中常用数学知识综述

1、公钥密码 密码学中常用的数学知识 公钥密码体制的基本概念 RSA算法4.1.1 群、环、域群、环、域群群G, 的定义的定义: u 一些数字组成的集合一些数字组成的集合 u 一个二元运算，运算结果属于此集合（封闭性）一个二元运算，运算结果属于此集合（封闭性）u 服从结合律。有单位元，逆元服从结合律。有单位元，逆元 。u 如果是可交换的，则成为如果是可交换的，则成为Abel群群*为乘法时，称为乘法群为乘法时，称为乘法群 逆元（逆元（a-1）*为加法时，称为加法群为加法时，称为加法群 逆元（逆元（-a）环环的定义的定义: u Abel 群，及一个乘法运算：群，及一个乘法运算：u 满足结合律与满足结合

2、律与加法的分配律加法的分配律 u 如果加法满足交换律如果加法满足交换律, 则称交换环则称交换环u 例：整数例：整数 mod N （for any N ）域域的定义：的定义： u是是Abel加群加群 u环环 u是是Abel 乘群乘群 u例：例： 整数整数 mod P （ P 为素数）为素数）Galois 域：域：u 如果如果 n是素数是素数 p ，则模运算，则模运算modulo p 形成形成 Galois Field modulo p u 记为：记为： GF(p) 4.1.2 素数和互素数素数和互素数因子：因子： 对整数对整数 b!=0b!=0 及及 a , 如果存在整数如果存在整数 mm 使得

3、使得 a=mb,a=mb,称称 b b 整除整除 a, a, 也称也称b b是是a a的因子。的因子。 记作记作 b|ab|a 例例 1,2,3,4,6,8,12,241,2,3,4,6,8,12,24 整除整除 2424素数：素数： 素数素数: : 只有因子只有因子 1 1 和自身和自身 1 1 是一个平凡素数是一个平凡素数 例例 2,3,5,7 2,3,5,7 是素数是素数, 4,6,8,9,10 , 4,6,8,9,10 不是不是200200以内的素数：以内的素数： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79

4、 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199素数分解：素数分解： 把整数把整数n n写成素数的乘积写成素数的乘积 分解整数要比乘法困难分解整数要比乘法困难 整数整数 n n的素数分解是把它写素数的乘积的素数分解是把它写素数的乘积 eg. 91 = 7 eg. 91 = 7 13 ; 3600 = 2 13 ; 3600 = 24 4 3 32 2 5 52 2 互素数：互素数： 整数整数 a, ba, b 互素是指互素是指 它们没有除它们没有除1之外的其

5、它因子之外的其它因子。8 与与15 互素互素 8的因子的因子1,2,4,8 15的因子的因子 1,3,5,15 1 是唯一的公因子是唯一的公因子 记为：记为：gcd(8,15)=14.1.3 模运算模运算 设设n n是一正整数是一正整数,a ,a是整数是整数, ,若若 a=qn+r, 0rn, a=qn+r, 0rd1. Xf;Yd;2. If Y=0 then return X=gcd(f,d)3. R=X mod Y4. X=Y;5. Y=R6. Goto 2假定输入是两个正整数假定输入是两个正整数Euclid算法：算法：ngcd(55,22)=gcd(22,11)=gcd(11,0)=1

6、1ngcd(11,10)=gcd(10,1)=1 欧几里德算法欧几里德算法-求乘法逆元求乘法逆元 若若gcd(a,b)=1, bgcd(a,b)=1, b在模在模a a下有乘法逆元下有乘法逆元( (设设ba)ba)。 即存在即存在xa,bx1 mod axd)1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d);2. If Y3=0, then return X3=gcd(f,d);停止，没有逆元停止，没有逆元;3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f;4. Q=X3 div Y3（整数除）（整数除）;5. (T1 T

7、2 T3)(X1-QY1,X2-QY2,X3-QY3);6. (X1 X2 X3)(Y1Y2 Y3);7. (Y1Y2 Y3)(T1 T2 T3);8.Goto 2扩展欧几里德算法：扩展欧几里德算法：求求d模模f的逆元的逆元例：求解例：求解 11d (mod51) = 1的步骤。的步骤。 即求即求11-1mod51=？循循环环次次数数QX1X2X3Y1Y2Y3初初值值-1051 0111Extended Euclid(f,d) (fd)1.（X1 X2 X3)(1,0,f); (Y1Y2 Y3)(0,1,d);2. If Y3=0, then return X3=gcd(f,d); 停止，没有逆元停止，没有逆元;3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f;4. Q=X3 div Y3（整数除）（整数除）;5. (T1 T2 T3) (X1-QY1,X2-QY2,X3-QY3);6. (X1 X2 X3)(Y1Y2 Y3);7. (Y1Y2 Y3)(T1 T2 T3);8.Goto 21411-1mod51=14Q=X3 div Y3 = 5