ch-1-数论基础及对称加密算法.ppt

上传人:99****p 文档编号:1516038 上传时间:2019-03-04 格式:PPT 页数:35 大小:575.50KB
下载 相关 举报
ch-1-数论基础及对称加密算法.ppt_第1页
第1页 / 共35页
ch-1-数论基础及对称加密算法.ppt_第2页
第2页 / 共35页
ch-1-数论基础及对称加密算法.ppt_第3页
第3页 / 共35页
ch-1-数论基础及对称加密算法.ppt_第4页
第4页 / 共35页
ch-1-数论基础及对称加密算法.ppt_第5页
第5页 / 共35页
点击查看更多>>
资源描述

1、数论基础及对称加密算法1提纲n数论基础v加密系统中常用的数论知识v复杂性理论简介n对称加密算法v对称密码体制模型v流密码v分组密码vDESvRijndael密码体制( AES加密算法)vKASUMI分组密码 2数论基础3加密系统中常用数论知识n模 q运算v定义:给定任一正整数 q和任一整数 a,如果用q除 a,得到商 s和余数 r,则有 a=sq+r,记 ra mod q;v运算操作:加法 : (a mod q)+(b mod q)=(a+b) mod q乘法: (a mod q)(b mod q)=(ab) mod q4加密系统中常用数论知识n模 q运算v运算性质:Zn定义为集合 0,1,q

2、-1 ,也称为模 q的剩余类集合,以下为 Zn上的模运算的性质;交换律: (a+b) mod q=(b+a) mod q(ab) mod q=(ba) mod q结合律: (a+b)+c mod q= a+(b+c) mod q(ab)c mod q= a(bc) mod q分配律: a(b+c) mod q=ab+ac mod q恒等律 : (0+a) mod q=a mod q(1a) mod q=a mod q加法逆元:若存在 a,b Zn,使得 (a b) mod q=0,则 b是 a模 q的加法逆元。乘法逆元:若存在 a,b Zn,使得 ab=1 mod q,则 b是 a模 q的乘法

3、逆元。5加密系统中常用数论知识n模 q运算v求模逆运算 : (辗转相除法 ) 定理:设 r1=b1u mod q, r2=b2u mod q, r1=mr2+r3,则 r3=(b1-mb2)u mod q。 求逆元: u,q已知,求 x, (0r3 rkrk+10,以上操作必终止于有限步,不妨设 rk+1=0,那么必有1=rk=(rk,rk-1)=(r 3,r2)=(r2,r1)=(u,q)所以 rk=bku mod q,得 bku1 mod q,于是 u-1bk mod q 6加密系统中常用数论知识n 环v群是一种 代数结构 ,由一个 集合 以及一个 二元运算 所组成。 v群是一个 集合 G

4、,连同一个 运算 “,它结合了任何两个 元素 a 和 b 而形成另一个元素指示,记为 a b。符号 “ 是对具体给出的运算,比如上面加法的一般的占位符。要具备成为群的资格,这个集合和运算 (G, ) 必须满足叫做群公理的四个要求 :1.闭合。对于所有 G 中 a, b,运算 a b 的结果也在 G 中。2.结合律。对于所有 G 中的 a, b 和 c,等式 (a b) c = a (b c) 成立。3.单位元。存在 G 中的一个元素 e,使得对于所有 G 中的元素 a,等式 e a = a e = a 成立。4.逆元。对于每个 G 中的 a,存在 G 中的一个元素 b 使得 a b = b a

5、 = e,这里的 e 是单位元。v使等式 a b = b a 总是成立的群叫做 阿贝尔群 (以 尼尔斯 阿贝尔 命名)。 v例子: 整数 配备上 加法 运算就形成一个群。 7加密系统中常用数论知识n环v集合 R和定义于其上的二元运算 + 和 , (R, +, )构成一个环,若它们满足:(R, +)形成一个 交换群 ,其幺元称为零元素,记作 0。即: (a + b) = (b + a) (a + b) + c = a + (b + c) 0 + a = a + 0 = a a (a) 满足 a + a = a + a = 0 (R, )形成一个 半群 ,即: (ab)c = a(bc) 乘法关于

6、加法满足分配律: a(b + c) = (ab) + (ac) (a + b)c = (ac) + (bc) 其中,乘法运算符 常被省略,所以 ab 可简写为 ab。 此外,乘法是比加法优先的运算,所以 a + bc 其实是 a + (bc)。v交换环 :若环 R中, (R, )还满足交换律,从而构成 交换半群 ,即: a, b R,有 ab=ba,则 R称为交换环。 8加密系统中常用数论知识n域v集合 R和定义于其上的二元运算 + 和 , (R, +, )构成一个环,若它们满足:(R, +)形成一个 交换群 ,其幺元称为零元素,记作 0。即: (a + b) = (b + a) (a + b

7、) + c = a + (b + c) 0 + a = a + 0 = a a (a) 满足 a + a = a + a = 0 (R, )形成一个 半群 ,即: (ab)c = a(bc) 乘法关于加法满足分配律: a(b + c) = (ab) + (ac) (a + b)c = (ac) + (bc) 其中,乘法运算符 常被省略,所以 ab 可简写为 ab。 此外,乘法是比加法优先的运算,所以 a + bc 其实是 a + (bc)。v交换环 :若环 R中, (R, )还满足交换律,从而构成 交换半群 ,即: a, b R,有 ab=ba,则 R称为交换环。 9加密系统中常用数论知识n

8、域:是一种可进行加、减、乘和除(除了除以零之外)运算的代数结构,是数域以及四则运算的推广;n 域分为两种:v 无限域,元素个数无限,特征为0;v 有限域,元素个数有限,特征为p;v 特征:假设 p是最小的正整数, 使得 p个 1相加等于 0, 那么 p就称为域的特征;v 有限域元素个数为 q=pn;n 有限域 GF(q)同构于 GF(p)x/f(x),其中 f(x)为 GF(p)上的不可约多项式;n 多项式在 GF(p)上不可约:有限域GF(p)的任一元素都不是多项式方程的解。域无限域 有限域特征 0 特征 p,含有q = pn个元素GF(q)同构于 GF(p)x/f(x)其中 f(x)为 GF(p)上不可约多项式10

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 课件讲义

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。