密码学与网络安全第四章 密码数学基础(B).ppt

第四章第四章 密码学基础密码学基础(B)代数结构代数结构 —— 群、环、域群、环、域 §1 代数结构代数结构 一、一、 群群(group) 定义定义 2.1 设设G为一非空集合为一非空集合,  为定义在为定义在G上的二元运算上的二元运算. 如果下述条件成立如果下述条件成立, 则称代数系统则称代数系统 G,    为一个为一个群群. (1) 运算封闭性运算封闭性:  a, b G, a b G; (2) 结合律结合律:  a, b, c G, a (b c)=(a b) c; (3) 存在单位元存在单位元 e G: 使得对使得对 a G, a e=e a=a; (4)  a G, 存在存在a的逆元的逆元 a 1 G: 使得使得 a a 1= a 1 a=e. (5) 交换律：交换律： a，，b  G, a b= b a.交换群交换群 例例1 G =   Zn, +   （模（模 n +) 为一个群为一个群, 且是交换群。

且是交换群 单位元为单位元为 0 mod n a 的逆元是的逆元是 – a mod n= n-a 例例2 G =   Z*n, ×   （模（模 n ×) 为一个群为一个群, 且是交换群且是交换群 单位元为单位元为 1 mod n a 的逆元是的逆元是 a -1 mod n 例例3 A={a, b, c, d}, G =  A , ·   是交换群是交换群 运算表：运算表： ·abcdaabcdbbcdaccdabddabc 单位元单位元: a 逆元对逆元对: (a,a) , (b,d), (c,c)  例例4 置换群（置换群（permutation group）） 设设 (1,2,3) 的所有置换构成集合的所有置换构成集合 T={(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2),(3,2,1)} 在在T上规定二元运算上规定二元运算 ⊙ ⊙ 为两个置换的复合：为两个置换的复合： (2,1,3)⊙⊙(2,3,1) =(1,3,2)⊙⊙(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1)(1,2,3)(1,2,3)(1,3,2)(1,2,3)(2,1,3)(1,2,3)(3,2,1)(2,3,1)(1,3,2)(1,2,3)(3,1,2)(1,2,3)(3,2,1)(1,2,3) 则则G =   T, ⊙⊙   为一个群为一个群, 但不是交换群。

但不是交换群 单位元为恒等置换单位元为恒等置换 e ={ 1,2,3} a 的逆元是的逆元是 a 的逆置换的逆置换 1 2 31 2 31 2 31 2 31 2 31 2 3（（2 1 3 ））（（2 3 1 ））（（1 3 2 ））定义定义 设设  G,     是一群是一群, H是是G的一非空子集的一非空子集. 如果如果  H,     也是群也是群, 则称则称  H,     是是  G,     的一个子群的一个子群. 定义定义 设设  G,     是一群是一群, 若若G的元素个数有限，的元素个数有限， 则称则称  G,     是是有限群有限群(finite group). |G| 表示表示G的元素个数，称为的元素个数，称为G的阶在模在模 n 加法运算下，加法运算下，Zn 是是n阶有限群。

阶有限群 定义定义 设设  G,     是一群是一群, 若若G的元素可以由一个元素及其的元素可以由一个元素及其幂组成，则称幂组成，则称  G,     是是循环群（循环群（cyclic group). 在在 n 阶阶循环群中，生成元素为循环群中，生成元素为 g , G={e, g, g2, … gn-1 } , gn = e循环群的生成循环群的生成元素可能不只一个！元素可能不只一个！例例6 在在 G=  Z*10 , *   中中, Z*10 ={1,3,7,9}, 有循环子群：有循环子群：H1=  {1}, ×  , 生成元是生成元是 1H2=  {1，，9}, ×  ，生成元是，生成元是9H3= G, 生成元是生成元是3, 或或 7 例例5 在在 G=  Z6 , +   中中, 有循环子群：有循环子群：H1=  {0}, +  , 生成元是生成元是0H2=  {0,2,4}, +  ，生成元是，生成元是2或或4H3=  {0,3}, +  , 生成元是生成元是3H4=  Z6, +  ，， 生成元是生成元是1例例7 在在 G=  Z17 , +   中中, 仅有两个可能的子群仅有两个可能的子群: 阶数为阶数为1的子群：的子群：   {0} , +   阶数为阶数为17的子群的子群: G   Zp , +   子群结构很简单！子群结构很简单！Lagernge 定理定理 设设H 是是 G 的的子群，则子群，则|H| | |G|。

H的阶数必能整除的阶数必能整除G的阶数！的阶数！ 子群子群H的阶数一定是的阶数一定是|G|的因子！的因子！定义定义 设设  G,     是一群是一群, a 是是G的一个元素的一个元素满足满足 a n = e 的的 最小整数，称为最小整数，称为 元素元素 a 的阶的阶，，记为记为 ord (a) ord (a) 等于由等于由 a 生成的循环子群的阶数生成的循环子群的阶数例例9 G=  Z*10 , *   , Z*10 ={1,3,7,9}, H1=  {1}, ×  , ord(1)= 1H2=  {1，，9}, ×  ，，ord(9)=2H3= G, ord(3)=ord(7)=4 例例8 在在 G=  Z6 , +   中中, 有循环子群：有循环子群：H1=  {0}, +  , ord(0)=1H2=  {0,2,4}, +  ，， ord(2)=ord(4)=3H3=  {0,3}, +  , ord(3)=2H4= G ord(1)= ord (5)=6他们都是他们都是|G| 的因子！的因子！他们也都是他们也都是|G| 的因子！的因子！ 二、二、 环环 ( ring ) 定义定义 设设G为一非空集合为一非空集合, G上定义了两种二元运算上定义了两种二元运算 +：： 构成构成 加法交换群加法交换群  ：： 满足封闭性满足封闭性+结合律（结合律（+交换律）交换律） 而且而且 * 对对+ 有分配律有分配律 则称代数系统则称代数系统 R=  G, +,    为一个为一个环或交换环。

环或交换环运算运算* 运算运算 运算封闭性运算封闭性 运算封闭性运算封闭性 结合律结合律 结合律结合律 交换律交换律 交换律交换律* 单位元单位元(零元）零元） 逆元（负元）逆元（负元） *对对+ 分配律分配律 整数集整数集 Z 上的（上的（+, *）运算构成交换环）运算构成交换环 R=  Z, +,     不能进行不能进行“除法除法”运运算算 三、域三、域 ( field ) 定义定义 设设G为一非空集合为一非空集合, G上定义了两种二元运算上定义了两种二元运算 +：： 构成构成 加法交换群加法交换群  ：： 构成乘法交换群构成乘法交换群 而且而且 * 对对+ 有分配律有分配律 则称代数系统则称代数系统 F=  G, +,    为一个域为一个域运算运算* 运算运算 运算封闭性运算封闭性 运算封闭性运算封闭性 结合律结合律 结合律结合律 交换律交换律 交换律交换律 零元零元 单位元单位元 负元负元 逆元逆元 *对对+ 分配律分配律加减乘除加减乘除 畅通无阻！畅通无阻！域的例子：域的例子： 1、、 有理数域有理数域 2、、 实数域实数域 3、、 有限域有限域 ：： Zp Galois（伽罗华）指出：有限域的元素个数比为（伽罗华）指出：有限域的元素个数比为 p n 。

因此，有限域又称伽罗华域，记为因此，有限域又称伽罗华域，记为 GF( p n ) 例例1 GF(5) = Z5 , 在模在模5下可以定义四则运算下可以定义四则运算例例2 GF(2) = Z2 , 在模在模2下可以定义四则运算下可以定义四则运算 0+0=0；；0+1=1，，1+0=1，，1+1=0 （异或运算）（异或运算） 0*0=0；；0*1=0，，1*0=0，，1*1=1 （与运算）（与运算） 加法零元：加法零元：0，， -0=0；；-1=1 乘法单位元：乘法单位元：1，， 1-1 =1；；0 无逆元无逆元 加法就是减法加法就是减法乘法就是除法乘法就是除法 §2 伽罗华域伽罗华域 GF(2n) 一、背景一、背景 （（1）对应于计算机上的）对应于计算机上的n位二进制运算位二进制运算 （（2）不能简单地视为在）不能简单地视为在 Z2n = {0,1, 2, … 2n-1} 上的四则运上的四则运算由于有些元素没有乘法逆，不能进行除法运算算由于有些元素没有乘法逆，不能进行除法运算. （（3）通常把一个）通常把一个n位二进制数看成是一个以二进制为系数位二进制数看成是一个以二进制为系数的的n-1次多项式。

次多项式 0011 —— x+1 1011 —— x3+ x+ 1 1100 —— x3+ x2 0000 —— 0 0001 —— 1x3x2x1x000111011110000000001二、多项式加法二、多项式加法⊕ ⊕ 1、、 n位二进制数看成是二进制为系数的位二进制数看成是二进制为系数的n-1次多项式次多项式 系数域是系数域是GF( 2 ) 多项式域多项式域GF(2n ) (x+1) ⊕⊕(x3+ x+ 1)= x3 0011 ⊕⊕ 1011⊕⊕x3x2x1x00011⊕⊕10111000 2、加法运算、加法运算 （具有（具有运算封闭性）运算封闭性） 1000按位进行按位进行异或异或模模2加：异或加：异或模模2乘：布尔乘：布尔 00100110 + 00001100x7x6x5x4x3x2x1x000100110+0000110100101011 例例1、、 GF(28)中的加减法运算中的加减法运算 00101010x7x6x5x4x3x2x1x000100110-0000110100101011多项式的逆元多项式的逆元就是其自身！就是其自身！做减法就是做做减法就是做加法！加法！ 三、多项式乘法三、多项式乘法 1、多项式域、多项式域GF(2n )上两个多项相乘得到一个新多项式，上两个多项相乘得到一个新多项式，次数可能超过次数可能超过n-1。

运算封闭性面临挑战运算封闭性面临挑战 2、解决思路：多项式的模运算解决思路：多项式的模运算 3、模运算：设、模运算：设 p(x) 是是 n次素多项式（不可约）次素多项式（不可约） mod p(x) 模运算模运算: 求出除求出除p(x)所得的余式所得的余式 模运算能够保证乘法运算的封闭型！模运算能够保证乘法运算的封闭型！ 1、怎样进行模运算？、怎样进行模运算？ P1(x)=q(x)*P(x)+r(x) P1(x) mod P(x) = r(x) 含义：含义：P1(x) 与与 r(x) 同余同余 当当 P1(x) 也是也是 n 次多项式时：次多项式时： P1= P(x) + r(x) （商（商q(x) =1）） r(x) = P1(x) - P(x) = P1(x) +P(x) 模模P运算运算是加是加P(x) ! 当当 P1(x) 也是也是 n-1 低次多项式时：低次多项式时： P1= r(x) （商（商q(x) = 0）） r(x) = P1(x) 模模P运算运算是是P1(x) ! 例例1+X7x6x5x4x3x2x1x0100000011100011011000011000 解：解：最左边一位可最左边一位可以不考虑！以不考虑！ 00000011 +00011011 00011000  例例2不满不满8时不进位时不进位:只左移位只左移位满满8时进位：时进位：先左移位再先左移位再+00011011 例例3 模运算的二进制表示模运算的二进制表示 不进位时：不进位时：左移位左移位有进位时：有进位时：先左移位再先左移位再+00011011 x8: 100000000+100011011= 00011011 x9: 00110110 x10: 01101100 x11: 11011000 x12: 10110000+00011011= 10101011 x13: 01010110 +00011011= 01001101 x14: 10011010 x15: 00110100+00011011= 00101111 x16: 01011110 x17: 10111100 x18: 01111000+00011011= 01100011 2、模、模 P(x) 乘法运算乘法运算 例例4  例例5 二进制表示：二进制表示： 幂幂结果结果进位进位运算过程运算过程10011110○不运算不运算00100111●00111100+0001101101001110○左移位左移位10011100○左移位左移位00100011●00111000+0001101101000110○左移位左移位 = 00100110 = 10011110 = 100011011 幂幂结果结果进位进位运算过程运算过程10011110○不运算不运算00100111●00111100+0001101101001110○左移位左移位10011100○左移位左移位00100011●00111000+0001101101000110○左移位左移位 = 00100110* 10011110 mod 100011011 = 00100111+ 01001110 + 01000110 = 00101111 只进行了异或只进行了异或和左移位运算和左移位运算 3、怎样求逆元素？、怎样求逆元素？ 定理：定理： 如果如果p(x), q(x)互素互素, 则存在多项式则存在多项式s(x)和和t(x)使得使得 s(x) p(x)+t(x) q(x)=1 定理：定理： 如果如果 p(x) 是是n次不可约多项式，次不可约多项式， 则对任何则对任何 低于低于n次的多项式次的多项式 A(x) 必存在唯一的必存在唯一的A-1(x)，使得，使得 A(x)* A-1(x) =1 mod p(x) 求逆的方法求逆的方法 —— 扩展的欧几里得算法扩展的欧几里得算法 。

qr1r2rt1t2tx2+1x4+x+1x2+1x01x2+1xx2+1x11x2+1x3+x+1xx10x2+1x3+x+1010x3+x+10 在在GF(24)中，中， 求求 (x2+1) mod(x4+x+1) 的逆的逆. 例例6 (x2+1)*( x3+x+1) mod(x4+x+1)r =r1-q*r2t =t1-q*t2 验证：验证： = x2* ( x3+x+1) +1* ( x3+x+1)= ( x5+x3+x2) + ( x3+x+1)= ( x5+x2+x+1)= x*(x+1)+x2+x+1= x2+x+x2+x+1 = 1 4、、GF(23) 专题研究专题研究 GF(23) 有有8个元素：个元素：000，，001，，010，，011，，100，，101，，110，，111 GF(23) 上的加法上的加法 —— 按位异或按位异或+000001010011100101110111000000001010011100101110111001000011010101100111110010000001110111100101011000111110101100100000001010011101000011010110000001111000 GF(23) 上的加法上的加法 零元素零元素—— 000，负元素，负元素—— 自身自身 4、、GF(23) 专题研究专题研究 GF(23) 上的乘法上的乘法 （模（模 x3+x2+1））——左移位和异或左移位和异或 ×000001010011100101110111000000000000000000000000000001001010011100101110111010100110101111001011011101001010111100100001111011010110101110100001110001011101111001010 GF(23) 上的乘法上的乘法 单位元单位元—— 001，， 逆元对：逆元对：001~001；；011~100，，010~110，，101~111 逆元：非零元素都有逆！逆元：非零元素都有逆！ 5、、GF(24) 的生成元的生成元不可约多项式不可约多项式 x4+x+1x4 = x+1序号序号生成元生成元 模模 运运 算算结结 果果二进制表示二进制表示100000021100013x1x100104x2x201005x3x310006x4 x4 = x+1 x+100117x5x5 = x ( x+1)= x2 + x x2+x01108x6x6 = x (x2+x)= x3+ x2 x3+ x2 11009x7 x7 = x (x3+ x2)= x3+ x +1x3+ x +1101110x8x8 = x(x3+ x +1 )= x+1 +x2+ xx2+ 1010111x9x9 = x (x2+ 1)= x3+ x x3+ x101012x10x10 = x(x3+ x)= x+1 +x2x2 +x+1011113x11x11 = x (x2 +x+1)= x3+ x2 +xx3+ x2 +x111014x12x12 = x(x3+ x2 +x)= x+1+ x3+ x2 x3+ x2 +x+1111115x13x13 = x(x3+ x2 +x+1)= x+1 +x3+ x2 +xx3+ x2 +1110116x14 x14 = x(x3+ x2 +1)= x+1+x3+xx3+11001 6、利用生成元的四则运算、利用生成元的四则运算生成元生成元结结 果果二进制表二进制表示示000000110001x1x10010x2x20100x3x31000x4 x+10011x5x2+x0110x6x3+ x2 1100x7 x3+ x +11011x8x2+ 10101x9x3+ x1010x10x2 +x+10111x11x3+ x2 +x1110x12x3+ x2 +x+11111x13x3+ x2 +11101x14 x3+11001• 加法：按位异或（二进制加法：按位异或（二进制 +））• 减法：减法即加法减法：减法即加法• 乘法：乘法：• 乘法逆：乘法逆： GF(24) 所有非零元素都能表成所有非零元素都能表成 x p , p = 1,2, …… 2n-1 乘除法是指数上的加减法乘除法是指数上的加减法 mod (2n-1) • 除法：逆元素乘法除法：逆元素乘法 6、利用生成元的四则运算、利用生成元的四则运算生成元生成元结结 果果二进制表二进制表示示000000110001x1x10010x2x20100x3x31000x4 x+10011x5x2+x0110x6x3+ x2 1100x7 x3+ x +11011x8x2+ 10101x9x3+ x1010x10x2 +x+10111x11x3+ x2 +x1110x12x3+ x2 +x+11111x13x3+ x2 +11101x14 x3+11001 例：在例：在GF(24) 上计算以下各题：上计算以下各题：( 0010 ) -3 = 11111000 +1111+1011= 11001000 -1100= 01001010 *1110= 01101000 /0101= 0111 7、系数在、系数在GF(28)的多项式运算的多项式运算 系数在系数在GF(28) 上的多项式上的多项式 其中系数其中系数 ai 在在GF(28) 上，即上，即8位二进制数构成的字节。

位二进制数构成的字节 用用 4个字节个字节 可表示可表示GF(28) 上的三次多项式上的三次多项式 a(x)+b(x) 只要对同次幂的系数作普通加法只要对同次幂的系数作普通加法 (按位异或按位异或 ) a(x)×b(x) 则要对模一个则要对模一个4次多项式次多项式 M(x)，以保证结果，以保证结果 仍然是三次多项式仍然是三次多项式 例：取例：取 M(x) = x4+1 例：取例：取 M(x) = x4+1 设设 ，则，则可以用矩阵表示运算结果可以用矩阵表示运算结果GF(28)上的矩阵运算表示两个多项式的乘法上的矩阵运算表示两个多项式的乘法可表示为：可表示为：可表示为：可表示为：可表示为：可表示为： 习题习题4 （（p110）） 24，，25，，26，，31，，32，，33，，37*。