【安全课件】第12讲--分组密码小节.ppt

1 分组密码小结 王滨2005 03 25 2 主要内容 欧几里德算法求最大公约数求模n的逆元 3 欧几里得算法 辗转相除法 引理1记gcd a b 是非负整数a和b的最大公因子 则gcd a b 1等价于存在整数x y 使得ax by 1其中的x和y可由辗转相除法求出 4 辗转相除法 引理2 带余除法 设a是整数 b是自然数 则存在整数q和非负整数r 使得a bq r 且0 r b 并记amodb r 引理3设a b r为不全为零的整数 且a bq r 则gcd a b gcd b r 证明 设d gcd a b 由于d a bq r 且d b 则一定有d r 则d gcd b r 下证d gcd b r 由于gcd a d b d 1 一定有gcd r d b d 1 故d gcd b r 证毕 5 辗转相除法 计算gcd a b Step1A a B bStep2计算带余除法 求出满足A qB r和00时 执行A B B r后返回执行Step2 6 例1计算gcd 63 100 解63 0 100 63 100 1 63 37 63 1 37 2637 1 26 11 26 2 11 4 11 2 4 3 4 1 3 1 3 3 1 0故gcd 63 100 1 7 系数的计算 倒推进行 将余数代入 1 4 1 3 4 1 11 2 4 1 11 1 2 4 1 11 3 4 1 11 3 26 2 11 7 11 3 26 7 37 26 3 26 7 37 7 3 26 7 37 10 26 7 37 10 63 37 10 63 17 37 10 63 17 100 63 17 100 27 63 8 输出使得ax by gcd a b 的gcd a b 和x y的推理过程 记a0 a a1 b 则求ax by gcd a b 的过程可写为 即 9 欧几里得算法 计算gcd a b 和使ax by gcd a b 成立的x y Step1A a B b s 1 t 0 x 0 y 1 Step2计算带余除法 求出满足A qB r和00时 执行A B B rw x x s qx s w w y y t qy t w 后返回执行Step2 10 欧几里得算法 计算gcd a x b x 和使z x a x y x b x gcd a x b x 成立的z x y x Step1A x a x B x b x s x 1 t x 0 z x 0 y x 1 Step2计算带余除法 求出满足A x q x B x r x 和deg r deg B 的q x 和r x Step3当r x 0时 输出B x gcd a x b x 和z x m x 当r x 0时 执行A x B x B x r x w x z x z x s x q x z x s x w x w x y x y x t x q x v x t x w x 后返回执行Step2 11 辗转相除法的C语言算法intinverse a inta registerintn1 n2 q r b1 b2 t if a b2 0 else n1 n n2 a b2 1 b1 0 do r n1 n2 q n1 r n2 if r if b2 0 b2 n b2 else n1 n2 n2 r t b2 b2 b1 q b2 b1 t while r return b2 12 例子 求10110110在modb x 中的逆 10110110 a x x7 x5 x4 x2 x b x x8 x4 x3 x 1 100011011 求z x 满足z x a x y x b x 1 解 step1 A x a x B x b x s x 1 z x 0 t x 0 y x 1 step2 A x 0 B x r x r x a x 由于r x 0 则A x B x B x r x w x z x 0 z x s x q x z x s x 1 s x w x 0执行step2 100011011 x 10110110 r故q x x r x 01110111 A x 10110110 B x r x w x 1 z x x s x 1 执行step2 10110110 x 01110111 rq x x r x 01011000 w x x z x x2 1 s x x 13 w x z x z x s x q x z x s x w x 执行step2 01110111 1 01011000 rq x 1 r x 00101111 w x x2 1 z x x2 x 1 s x x2 1 执行step2 01011000 x 00101111 rq x x r x 00000110 w x x2 x 1 z x x3 x 1 s x x2 x 1执行step2 00101111 x3 x2 1 110 rq x x3 x2 1 r x 1 w x x3 1 z x x6 x5 x4 x3 s x x3 1执行step2 110 x2 x 1 rr x 0故z x x6 x5 x4 x3即 10110110 01111000 14 15个候选算法 RijndaelRC6MarsSerpentTwofish 前5个算法是第二轮筛选出的5个决赛算法 CASt 256 CRYPTON DEAL DFC E2 FROG HPC MAGENTA Safer LOKI97 15 先进对称分组加密算法的特点 可变的密钥长度 RC5混合的运算IDEA数据相关的圈数RC5密钥相关的圈数CAST 128密钥相关的S盒 Blowfish冗长密钥调度算法 Blowfish可变的F CAST 128可变长明文 密文块长度可变圈数每圈操作作用于全部数据 16 分组密码的一般设计原理 针对安全性的一般原则 混乱扩散重要的设计原理 必须能抵抗现有的攻击方法针对实现的原则软件硬件 17 分组密码的整体结构 Feistel网络 DESSP网络 AES其它密码结构 Frog 18 S盒的设计准则 S 盒首次出现在Lucifer算法中 因DES的使用而流行 S 盒是许多密码算法的唯一非线性部件 因此 它的密码强度决定了整个算法的安全强度 提供了密码算法所必须的混乱作用 如何全面准确地度量S 盒的密码强度和设计有效的S