信息安全数学基础

null信息安全数学基础信息安全数学基础 信息科学与工程学院 null网络信息的安全威胁 网上犯罪形势不容乐观； 有害信息污染严重； 网络病毒的蔓延和破坏； 网上黑客无孔不入； 机要信息流失与信息间谍潜入； 网络安全产品的自控权； 信息战的阴影不可忽视。引 言null网络通信的困境引 言null我们要保护什么呢？引 言null网络安全体系的五类服务引 言null网络安全体系的五类服务访问控制服务：根据实体身份决定其访问权限； 身份鉴别服务：消息来源确认、防假冒、证明你 是否就是你所声明的你； 保密性服务：利用加密技术将消息加密，非授权 人无法识别信息； 数据完整性服务：防止消息被篡改，证明消息与 过程的正确性； 防抵赖服务：阻止你或其他主体对所作所为的进 行否认的服务，可确认、无法抵赖。引 言null引 言解决 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ：加密如何实现保密性？密码分析AliceBobEvenull引 言解决方法：数字摘要如何实现完整性？消息篡改公共网络AliceBobm,zm,zz=hk(m)y=hk(m)Evenull引 言解决方法：数字签名如何实现不可否认性？否认公共网络AliceBobTrent谁是正确的？举报null引 言解决方法：密码技术 身份鉴别：就是确认实体是它所声明的，身份鉴别服务提供关于某个实体身份的保证，以对抗假冒攻击。如何鉴别通信对象的身份？null本课程的相关知识点简单的密码学基础： 密码技术是信息安全的核心技术； 需要掌握一些密码学基础知识。 相关的数学知识： 密码技术的实现依赖于数学知识； 掌握密码技术涉及的相应数学基础知识点。 参考教材： (1) 密码学导引,机械工业出版社,Paul Garrett 著,吴世忠等译； (2) 信息安全数学基础,武汉大学出版社,李继国等 主编。引 言null什么是密码技术？窃听公共网络AliceBobEve篡改伪造密文 密码学是一门古老而深奥的学科,包括密码编码学和密码分析学; 通信双方按照某种约定将消息的原形隐藏。 密码系统:明文,密文,加解密算法,密钥。引 言null密码学的起源与发展 三个阶段： 1949年之前：密码学是一门艺术； 1949～1975年：密码学成为科学； 1976年以后：密码学的新方向－－公钥密码学。 1949年之前(手工阶段的初级形式) 隐写术：隐形墨水、字符格式的变化、图像； 举例： 芦花丛中一扁舟，俊杰俄从此地游； 义士若能知此理，反躬难逃可无忧。 258 71539 258 314697 314697 15358 24862 17893 引 言null1949~1975年(机械阶段)：现代密码出现 1949年香农Shannon提出“保密系统信息理论”； 提出：数据的安全基于密钥而不是密码算法。 1976年以后(计算机阶段)：公钥密码诞生 1976年Diffie&Hellman的“New Directions in Cryptography”提出了不对称密钥密码； 1977年Rivest, Shamir & Adleman提出了RSA公钥算法； 90年代出现椭圆曲线ECC等其他公钥算法。引 言null对称密钥密码算法进一步发展 1977年DES正式成为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ； 80年代出现“过渡性”的“post DES”算法，如IDEA、RCx、CAST等； 90年代对称密钥密码进一步成熟，Rijndael、RC6、MARS、Twofish、Serpent等出现； 2001年Rijndael成为DES的替代者AES。 2004年6月美国NIST提出最新信息加密技术----量子密码。 2004年山东大学王小云教授成功破解处理电子签名的MD5。引 言null密码算法的分类 按照保密的内容分 受限制的算法：保密性基于保持算法的秘密。 基于密钥的算法：保密性基于密钥的保密。 Kerchoffs原则 1883年Kerchoffs第一次明确提出了编码的原则：保密性完全依赖于密钥，算法应该公开。 这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为古典密码和现代密码的分界线。引 言null基于密钥的算法，按照密钥的特点分类： 对称密码算法：又称秘密密钥算法或单密钥算法，加密密钥和解密密钥相同，或可以容易地从一个推出另一个。特点：加密速度快；密钥管理复杂，主要用于加密信息。 非对称密钥算法：又称公开密钥算法，加密密钥和解密密钥不相同，而且很难从一个推出另一个。特点：密钥管理简单，但加密速度慢，用于加密会话密钥和用于数字签名。 实际网络应用中，常采用非对称密码来交换对称密码算法的密钥。引 言null经典的古典密码算法主要有： 代替密码：将明文字符用另外的字符代替，典型的有恺撒密码、仿射密码、维吉尼亚密码等； 换位密码：明文的字母保持相同，但顺序打乱。经典的现代密码算法有很多种，最通用的有： DES：数据加密标准，对称密码算法，用于加密； AES: 高级加密标准，对称密码算法，用于加密；引 言null RSA：最流行的公钥密码算法，加密和数字签名； ECC：椭圆曲线密码，采用ElGamal算法，公钥密码算法，安全性高，密钥量小，灵活性好； DSA：数字签名算法，是数字签名的一部分，公钥密码算法，数字签名。 MD5(SHA-1)：数字摘要算法，数字签名，保证消息的完整性。引 言null密码系统的安全 理论安全：攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。Shannon用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密密码本，不实用。 实际安全：如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行。引 言null密码系统的攻击 四种基本攻击类型： 唯密文攻击：攻击者只有一些密文； 已知明文攻击：攻击者知道一些明文密文对； 选择明文攻击：攻击者可以选择明文密文对； 针对密钥的攻击：主要是针对公钥密码系统。 穷举攻击：攻击者采用尝试方法穷举可能的密钥。 当密钥空间较小时很有效。字典攻击是 利用一些常用的单词进行组合。 基本要求：任何一种加密系统都必须能够对抗唯 密文攻击。 目前的标准是：一个密码系统应当能够对抗选择 明文攻击。引 言null第一章 简单密码经典的简单密码： 移位密码、一次一密乱码本、仿射密码。 1.1 移位密码 1.Caesar密码：最简单的移位密码。 原理：将消息中的每个字母前移3位或者后 移3位。 举例： all of gaul is devided into three parts DOO RI JDXO LU GLYLGHG LQWR WKUHH SDUWU 2.移位密码： 改进Caesar密码：发送方和接收方协商一个密钥k，1≤k≤25，代表移动位数。null3.攻击： 穷举攻击：25种可能的密钥(密钥空间)； 4.特点： 对称密码：加密密钥和解密密钥相同； 单表代替密码：所有的明文字母用同一种方法 加密，即子密钥相同。 1.2 约简/整除算法 1.n模m的约简： n除以m的余数r，0≤r<|m| 记作：r=n%m 或者 r=n mod m，m称为模数。 计算：设a=|n|%|m|，则 当n<0时，n%m=|m|-a； 当m<0时，n%m=n%|m|。第一章 简单密码null举例： -10%7： 10%(-7)： -10%(-7)：4，因为 -10=7×(-2)+43，因为 10=-7×(-1)+34，因为 -10=-7×2+4注意： 任何整数模m的约简都是非负数。 2.乘法逆 n模m的乘法逆t满足：n×t%m=1 记作：t=n-1%m 举例： 2-1%5的值为： 3-1%100的值为：3，因为 3×2%5=167，因为 67×3%100=1第一章 简单密码null4.乘法逆元的计算 (1)穷举法：寻找满足条件的数。 技巧：若t×n%m=-1，则n-1%m=m-t。 33×3%100=-1，所以3-1%100的值为67。第一章 简单密码 3.命题 设m≠0,±1为整数，x与m互素，则x有模m的 乘法逆元。特别地，满足表达式ax+bm=1的任意 整数a就是一个x模m的乘法逆元。 假如y是x模m的乘法逆元，对于y’，若m|y-y’， 那么y’也是x模m的乘法逆元；反之亦然。 null (2)欧几里德算法： 举例： 23-1%100 方法：100-4×23=8 23-2×8=7 8-1×7=1 7-7×1=0所以： 1=3×100-13×23 1=-13×23%100 23-1%100 = -13 = 87 1=3×100%23 100-1%23=8-1%23 = 3 算法：1 =8-1×7 =8-1×(23-2×8) =3×8-1×23 =3×(100-4×23)-1×23 =3×100-13×231 -1 -1 3 3 -13 所以：3×100-13×23 = 1第一章 简单密码null1.3 欧几里得算法 用以寻找两个整数m和n的最大公因子d。 使用该算法将x和y的最大公因子表示为： ax+by=gcd(x,y)的形式。 1.举例描述 两个整数513和614 614-1·513=101 513-5·101=8 101-12·8=5 8-1·5=3 5-1·3=2 3-1·2=12.寻找整数a,b 1=3-1·2=3-1·(5-1·3) =-1·5+2·3=-1·5+2·(8-1·5) =2·8-3·5=2·8-3·(101-12·8) =-3·101+38·8 =-3·101+38·(513-5·101) =38·513-193·101 =38·513-193·(614-1·513) =-193·614+231·513最大公因子为1第一章 简单密码null2.乘法逆元的计算结论：当x和y互素时，gcd(x,y)为1，即可得到x-1%y为a，y-1%x为b。第一章 简单密码null3.举例 所以：21-1%25的结果为6。 例2：求1234-1%4321 例1：求21-1%25 解：25-1·21=4 21-5·4=1 4-1·4=0 第一章 简单密码null3.命题： (1)给定一非零整数m和任意整数n，存在唯一的 整数q和r，使得0≤r<|m|且n=q×m+r (2)设n和N为两个整数，对某个整数k有N=kn， 则对任意整数x有：(x%N)%n=x%n1.3 一次一密乱码本OTP 1.思想：密钥与消息一样长，且只能使用一次。 2. 工作原理 数字放映机工作原理变压器基本工作原理叉车的结构和工作原理袋收尘器工作原理主动脉球囊反搏护理 ： 消息长度为n， x=(x1,x2,…,xn)； 随机密钥： k=(k1,k2,…,kn)； 加密：Ek(x)=((x1+k1)%26,…,(xn+kn)%26) 解密：Dk(y)=((y1-k1)%26,…,(yn-kn)%26)第一章 简单密码null3. 举例： 消息：n e v e r m o r e 密钥：e x c e l s i o r 密文：R B X I C E W F VR(17)=(n(13)+e(4))%26 F(5)=(r(17)+o(14))%264. 特点： 密钥的产生与分发管理复杂； 对称密码； 多表代替密码：明文中不同位置的字母采用的加 密密钥不同。第一章 简单密码null1.4 仿射密码 1.思想：对移位密码进行改进，扩大密钥空间。 2.原理： 加密：Ea,b(x)=(ax+b)%26 0≤a,b≤ 25 解密：Da,b(y)= 3.特点： (1)当a=1时为移位密码； (2)加密密钥为(a,b)；解密密钥为(a-1,-a-1b)； (3)单表代替密码； (4)对称密码：由加密密钥可以推导出解密密钥；第一章 简单密码null (5)密钥空间：由于a-1必须存在，所以可能的密钥数 为12×26-1=311个。第一章 简单密码null4.攻击方法： 穷举攻击：尝试311个可能的密钥。 选择明文攻击： Ea,b(0)=(a0+b)%26 Ea,b(1)=(a1+b)%26 已知明文攻击： Ea,b(x)=(ax+b)%26 Ea,b(y)=(ay+b)%26 唯密文攻击：字母频率攻击。a=(x-y)-1(Ea,b(x)-Ea,b(y))%26 b=(Ea,b(x)-ax)%26b=Ea,b(0) a=(Ea,b(1)-b)%26第一章 简单密码null 举例： 已知明文：meet me at midnight 假设密文：HNNS HN DS HXEQXFOS (1)选择明文攻击 攻击者选择：a(0) D(3) d(3) E(4)第一章 简单密码null第一章 简单密码null第一章 简单密码1.5 Vigenere密码 1.特点： 具有相对较大的密钥空间； 对称密码；多表代替密码； 有周期性的弱点：若两个字符出现的间隔是密钥长度的倍数，则它们将以同样的方法加密。 2.加密和解密的原理： (1)密钥是一个字符序列：k=(k0,k1,…,km-1)； 明文x=(x0,x1,…,xN)被分成长度为m的段。 (2)加密函数：Ek(x0,x1,…,xN)=(y0,y1,…, yN) yi=(xi+ki%m)%26 解密函数：Dk(y0,y1,…, yN)=(x0,x1,…,xN) xi=(yi-ki%m)%26null第一章 简单密码3.多轮加密 若一个明文使用密钥长度为m的维吉尼亚密码加密，得到的密文再用长度为n的密钥加密，其结果与用长度为lcm(m,n)的维吉尼亚密码加密的结果一样。 若m,n互素，则lcm(m,n)=mxn，密钥长度很大。null第一章 简单密码1.6最小公倍数lcm和最大公约数gcd 1.定义 对于两个整数d,n，若d整除n，或者说d是n的一个因子，记作：d|n 设m,n是两个非0的整数，则最大公约数d为最 大的正整数，使得d|m和d|n，记作d=gcd(m,n)； 最小公倍数N为最小的正整数，使得m|N和n|N， 记作N=lcm(m,n)。 2.定理 m,n的最大公约数gcd(m,n)具有这样的特性：对于m,n的每一个公因子e满足e|gcd(m,n)； m,n的最小公倍数lcm(m,n)具有这样的特性：对于m,n的每一个公倍数N满足lcm(m,n)|N； null第一章 简单密码3.素数 素数p是那些不存在因子d的整数1ln2 第一章 简单密码null作业： (1)为移位密码加密的消息解密： YRQ QEFP BUXJMIB FP IBPP BXPV (2)求-1000模88的约简。 (3)求29模100的乘法逆。 (4)已知明文攻击： Ea,b(3)=5且Ea,b(6)=7，求解密密钥。 (5)求gcd(1112,1544)，并将其表示成如下形式： 1112x+1544y (6)求1001模1234的乘法逆。第一章 简单密码null 古典密码的两大机制： 代替密码：字母表范围内替换； 换位密码：在消息内变换字母的位置。 2.1代替密码 1.描述 密钥是字母表的任意组合，有一个明密对应表； 密钥空间巨大：26!； 单表代替密码的两个特例：移位密码和仿射密码。 2.举例 首先选加密表；为了便于记忆，协商一个密钥： DO YOU LIKE THIS BOOK 去掉重复字母，再进行补充，形成加密表： abcdefghijklmnopqrstuvwxyz DOYULIKETHSBACFGJMNPQRVWXZ第二章 代替与换位null第二章 代替与换位2.2 换位密码 1.机制：单个字符不变而位置改变。 如将文本翻转：明文 computersystems 密文 SMETSYSRETUPMOC 2.特点： (1)密文长度与明文长度相同； (2)唯密文攻击可能得到多种不同的破译结果； 如 keep－peek；live－evil－vile 3.分组换位密码 针对固定大小的分组进行操作。 举例：明文 can you understand (1)列换位法 设密钥k=4，将明文进行分组排列null密文： CODTAUEANURNYNSD明文： canyouunderstand明文：canyouunderstand1 2 3 41 2 3 4第二章 代替与换位null按列 读出t y p e密文： YNSDNURNCODTAUEA明文： canyouunderstand明文：canyouunderstand1 2 3 43 4 2 1 YNSD NURN CODT AUEA(2)密钥为字符串type第二章 代替与换位null(3)矩阵换位法：置换矩阵作为密钥明文：canyouunderstandc a n y o u u n d e r s t a n dn c y a u o n u r d s e n t d a密文：NCYAUONURDSENTDA按置换矩阵的阶4分组c a n y o u u n d e r s t a n dN C Y A U O N U R D S E N T D A明文：canyouunderstand解密置换矩阵：说明：第二章 代替与换位null第二章 代替与换位2.3 频率攻击1.原理：利用自然语言的频率攻击 字母出现的频率有规律： e:11.67 t:9.53 o:7.81 a:7.73 … the:4.65 to:3.02 of:2.61 and:1.85 … 2.应用：对古典密码进行唯密文攻击。 3.举例：对仿射密码的攻击 密文：JFFGJFDMGFSJHYQHTAGHQGAFDCCFP 统计字母出现的次数： F－6 G－4 H－3 J－3 …… 猜测：e(4)－F(5) t(19)－G(6) 则有：Ea,b(e)=F Ea,b(t)=G null第二章 代替与换位Ea,b(x)=(7x+3)%26解密函数为：E15,7(x)=(15x+7)%26解密后的明文为： meet me after midnight in the alleynull第二章 代替与换位4.举例：对代替密码的攻击 KOS BMKKBS ISS YFSJ NFK BMES KOSIDY IFP KF JSS MK.eeeeeeetttttooooniiilkbbssddbay 分析：由ESROL得到er,s,o,l或re,s,o,lloser 或 sorel 那么：由VIERD得到drive或irevd 所以比较合理的明文是： loser drive5.举例：对换位密码的攻击 ESROL VIERDnull第二章 代替与换位作业：(1)解密由仿射密码加密的密文： VCLLCP BKLC LJKX XCHCP (2)解密用简单换位密码加密的密文： EAGGAR DAIREPnull3.1 群 1.二元运算 定义：设s为集合，函数f:sss称为s上的二 元运算或代数运算。满足： 可计算性：s中任何元素都可以进行这种运算； 单值性：运算结果唯一； 封闭性：s中任何两个元素运算结果都属于s。 2.群的定义 定义：设是代数系统，为G上的二元运算，如果运算是可结合的，则称半群。 若为半群，并且二元运算存在单位元eG，则称为幺半群； 若为半群，并且二元运算存在单位元eG，G中的任何元素x都有逆元x-1G，称 为群，简记为G。第三章 置 换null 举例： (1)是群，其中Z为整数集合，+是普通 的加法，单位元是0，整数x的逆元是-x。 (2)是群，Z6={0,1,2,3,4,5}，为模6 加法。显然满足结合律，单位元是0；由于15=0， 24=0，33=0，所以1和5互为逆元，2和4互为逆元，3和0的逆元仍然是3和0。 3.群中元素的阶 定义：设是群，aG，nZ，则a的n次幂为 e n=0 an= an-1a n>0 (a-1)m n<0,n=-m 举例：在群中，30=0，35=15，3-5=-15 在群中，20=0，23=0，2-3=0第三章 置 换null 阶的定义： (1)设是群，aG，使得等式ak=e成立的 最小正整数k称为a的阶，记做|a|=k，a称为k阶元，若不存在这样的整数k，则a称为无限阶元。 例如： 在中，2和4是3阶元，3是2阶元， 1和5是6阶元，0是1阶元。 在中，0是1阶元，其他都是无限阶元。 (2)设为群，aG，且|a|=r。设k是整数，则ak=e当且仅当r|k。 (3)设为群，则群中任何元素a与其逆元a-1 具有相同的阶。第三章 置 换null 4.循环群和置换群 定义1：设为群，如果存在一个元素aG， 使得G={ak|kZ}，则称G为循环群，记做G=， 称a为生成元。若|a|=n，则G称为n阶循环群。 例如： 是循环群，其中Z6={0,1,2,3,4,5,}， 为模6加法，生成元为1或5。 是循环群，生成元为1或-1。 是循环群，Zn={0,1,…,n-1,}，生成 元为1。第三章 置 换null 定义3：设s={1,2,…,n}，s上的n!个置换构成集合 sn，则称sn与置换的复合运算◦构成的群为s上 的n元对称群，的任意子群称为s上的n元置换群。第三章 置 换 定义2：设s={1,2,…,n}，s上的任何双射映射函数 :ss称为s上的n元置换，记为：null3.2置换概念 1.置换 一个集合X的置换f定义为X到自身的一个双射 函数f。对应有n个元素的集合X，共有n!个置换。 问题：对于集合X，给定某个状态，经过多少次 置换返回初始状态？ Sn={1,2,3,…,n-1,n}表示n个元素的置换群 置换g为满足g(k)=ik的一个置换：平凡置换e：没有移动任何元素的置换。 即对于所有的i，有e(i)=i。置换与集合内容无关第三章 置 换null2. 置换的合成或乘积 设g和h是两个置换，先应用h，再应用g， 记为：g◦h或gh 注意： g◦h ≠h◦g 置换的合成满足结合律： (g◦h)◦k=g◦(h◦k) 3. 逆置换 对于任意置换g，存在一个逆置换g-1，满足： g◦g-1=g-1◦g=e 4. 图表记法 用来计算两个置换的乘积。如：第三章 置 换null5. 循环 最简单的置换是不同长度的循环。 一个k循环满足： f(i1)=i2, f(i2)=i3 ,…, f(ik-1)=ik, f(ik)=i1，对于任意j(i1,i2,…,ik)，有f(j)=j。 举例：则：可见：g◦h ≠h◦g，具有不可交换性。记作：(i1,i2,…,ik)(1 2)(1 3)第三章 置 换null6. 结论 (1)如果g是一个k循环，那么gk=e。注意：一个k循环有k种表示法。 比较： (1 2 3)与(1 3 2)(1 2 3)= (2 3 1)= (3 1 2)如：则：即：对某个集合应用g操作k次，不会对集合产生 任何影响。第三章 置 换null(2)置换的阶 是置换被多次应用后却不产生任何实际影响所需要的重复次数。 若置换g是一个k循环，则有gk=e，g的阶为k。(3)不相交的循环 若g=(i1,…,ik)和h=(j1,…,jl)分别为k循环和l循环，且{i1,i2,…,ik}和{j1,j2,…,jl}是不相交的列表，则有： gh=hg 这样的循环g和h称为不相交的循环。第三章 置 换null 一个置换g的阶k=不相交循环分解中各循环长度的最小公倍数。如：思考：如果一副50张的牌洗得好，重复洗8次后所 有的牌将返回初始位置。阶为4(4) 置换的不相交循环分解 任何置换都可以表示为不相交循环的乘积，并且本质上只有这一种表示方法。=(1 4 5 7)(2 3)(6)第三章 置 换null3.3 切牌 最简单的切牌：选择一个随机点把一副牌一分为二，然后交换两部分。 n张牌：0,1,…,n-1 i+1,…,n-1,0,1,…,i 切牌过程为：fi(x)=(x+n-i-1)%n 如：n=6,i=1 0,1,2,3,4,5 2,3,4,5,0,1 置换过程为：f1(x)=(x+4)%6第三章 置 换null若n张牌的位置编号为： 1,2,…,n-1,n i+1,…,n-1,n,1,…,i 则切牌过程为：fi(x)=(x+n-i-1)%n+1第三章 置 换如：n=6,i=2 1,2,3,4,5,6 3,4,5,6,1,2 置换过程为：f1(x)=(x+3)%6+1null2n张牌： 1,2,…,n,n+1,…,2n-1,2n 两半交错：n+1,1,n+2,2,…,2n-1,n-1,2n,n 1,n+1,2,n+2,…,n-1,2n-1,n,2n 命题：对一副有2n张牌1,2,…,2n-1,2n的完美快速 洗牌过程为：f(x)=(2x)%(2n+1) 推论：若e为2模2n+1的阶，即e是满足2e=1 mod 2n+1的最小正整数。那么对一副有2n张牌经 过e次洗牌后，所有的牌都第一次返回到它们 的起始位置。不好的洗牌完美洗牌第三章 置 换3.4洗牌null然后按列读取这些数： 0,n,2n,…,mn-n,1,n+1,2n+1,…,mn-n+1,…,mn-1 对于数x，行：x/n 列：x%n3.5 分组交错 给定正整数m和n，针对mn个元素，一个mn分组交换的置换定义为： 按行将mm个数据写成mn的矩阵的形式第三章 置 换null然后按列读取这些数： 0,4,8,1,5,9,2,6,10,3,7,11 对应的置换过程为：例：12个数据 0,1,2,3,4,5,6,7,8,9,10,11， 进行34分组交错。 对应的循环分解为：数据置换位置阶为5按4行3列写出第三章 置 换null命题：忽略两个不动点0和mn-1，mn分组交错 对集合{1,2,3,…,mn-2}的作用是： x (mx)%(mn-1) 举例：36分组交错3x%173x%17 分析：快速洗牌，去掉两个不动点 完美的快速洗牌： x (2x)%(2n+1)第三章 置 换null作业： (1)计算乘积第三章 置 换 用不相交循环的乘积表示上述的结果，并确定阶。 (2)S5中任意元素的最大阶是多少？S14呢？ (3)确定对一副20张牌的完美快速洗牌的循环分解。 (4)找出35的分组交错置换的循环分解。null第四章 现代对称密码 香农提出的现代密码设计准则： Kerchhoff原则：系统的安全性不依赖于对密文或 加密算法的保密，而依赖于密钥。 惟一需要保密的是密钥； －－决定了古典密码学与现代密码学。 一个好的密码将融合混淆和扩散 混淆：混淆明文的不同部分； 扩散：对攻击者隐藏一些语言的局部特征； 现代密码将结合换位和代替： 代替密码在混淆上是有效的； 换位密码扩散性较好。null4.1 数据加密标准DES(Data Encryption Standard) 1976年被采纳作为联邦标准，并授权在非密级 的政府通信中使用，应用广泛。 DES是一个分组加密算法，对称密码，64位分 组，密钥长度为64位(实际长度为56位)。第四章 现代对称密码现代密码算法的特点： 只要保证密钥安全，就能保证加密信息的安全。 对称密码算法：很好地融合了混淆和扩散； DES、AES、IEDA、RC6等 非对称密码算法：基于数学难题； RSA、ECC、ElGamal等null DES的整个算法是公开的，系统的安全性靠 密钥保证。算法包括三个步骤：初始置换IP、16轮 迭代的乘积变换、逆初始变换IP-1。 1.初始置换IP 初始置换IP可将64位明文M=m1m2…m64的位置进 行置换，得到乱序的64位明文组M0=m58m50…m7。 2. 逆初始置换IP-1 逆初始置换IP-1将16轮迭代后的64比特数据的各 字节按列写出，将前四列插到后四列中，再对各列进行 逆序，然后将元素按行读出即可得到输出的密文组。 IP和IP-1的作用主要是打乱输入的ASCII码字划分关系，并将明文校验码变成IP输出的一个字节。第四章 现代对称密码null第四章 现代对称密码null第四章 现代对称密码null第四章 现代对称密码null【举例】设64位明文M为： 00000000 11111111 01010101 00010001 10001000 11001100 00110011 10101010 则经过IP置换后的M0为： 00100110 01001110 00100110 01001110 10110010 11000010 10110010 11000010 转换过程如下：第四章 现代对称密码null 3. 乘积变换 乘积变换是DES算法的核心部分。将经过IP置 换后的数据分成32位的左右两组，在迭代过程中彼此 左右交换位置。每次迭代时只对右边的32位进行一系列 的加密变换，然后把左边的32位与右边得到的32位逐 位进行异或操作，作为下一轮迭代时左边的段。迭代 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 为： Li=Ri-1，Ri=Li-1f(Ri-1,ki) ：按位异或操作运算符，即按位作模2相加运算。 运算规则为：10=1，01=1，00=0，11=0 f的功能是将32比特的数据经过选择扩展运算 E、密钥加密运算、选择压缩运算S和置换运算P转换为32比特的输出。 第四章 现代对称密码null第四章 现代对称密码null (1)选择扩展运算E 选择扩展运算下可将输入的32比特Ri-1扩展成 48位的输出。令s表示E原输入数据比特的下标，则 E的输出是将原下标s为0或1(模4)的各比特重复一次 得到的，实现数据扩展。第四章 现代对称密码null (2) 密钥加密运算 密钥加密运算将48比特的子密钥ki与选择扩展 运算E输出的48比特数据进行按位异或运算。 【举例】设32比特数据Ri-1为 00000000 11111111 00000000 11111111，48比特子密钥ki为 00000000 11111111 01010101 10101010 11001100 10001000，求 Ri-1经过选择扩展运算E后与子密钥ki异或后的结果。第四章 现代对称密码null 16个子密钥ki的产生： 64比特初始密钥k经过换位函数PC-1将位置号 为8,16,24,32,40,48,56和64的8位奇偶位去掉并 换位；换位后的数据分为2组，经过循环左移位LSi和 换位函数PC-2变换后得到每次迭代加密用的子密钥ki。第四章 现代对称密码null第四章 现代对称密码null LSi表示求子密钥ki时将Ci-1和Di-1进行循环左 移，其移位位数为： (3)选择压缩运算 选择压缩运算可将密钥加密运算后的48比特数 据从左至右分成8组，每组为6比特，并行迭入8个S 盒后压缩成32比特输出。每个S盒的输入为6比特， 输出为4比特，以完成压缩变换。 对于某个S盒Si，假设其输入为b1b2b3b4b5b6， 在Si表中找到b1b6行，b2b3b4b5 列的整数，转换 为4位二进制就是输出的4比特数据。第四章 现代对称密码null第四章 现代对称密码null第四章 现代对称密码null【举例】设S5的输入为b1b2b3b4b5b6=110110。 则(b1b6)2=(10)2=2，(b2b3b4b5)2=(1011)2=11 在S5中找到行为2，列为11的数据5转换为4位二 进制为0101，所以S5的输出为0101。 (4)置换运算P S1~S8盒的输出合成32比特数据后，用换位表p 进行置换，得到的32比特数据就是f(Ri-1,ki)的输出。第四章 现代对称密码nullnull DES的解密算法和加密算法相同，只是在解密 过程中将子密钥的顺序颠倒。 DES的出现在密码史上是个创举。以前任何设 计者对于密码体制细节都是严加保密的。自公布以 来，它一直活跃在国际保密通信的舞台上，成为商用 保密通信和计算机通信的最常用的加密算法。由于 DES的安全性完全依赖于密钥，而其64位的密钥太 短，因而出现了许多DES的改进算法，如三重DES、 分组反馈连接式DES以及密码反馈模式DES等。随着 新的攻击手段和改进的加密算法的不断出现，DES 也许将完成它的历史使命。 高级加密标准AES评选于2000年10月结束，Rijdael算法为AES的唯一算法。第四章 现代对称密码null 4. DES的安全性 (1)差分分析 1990年Biham和Shamir提出差分密码分析。 是一种比穷举攻击有效的选择明文的攻击方法。 差分分析的攻击方法是针对DES和其他类似的有 固定S盒的算法。DES的S盒恰好最适宜于抗差分分 析。最佳差分分析的总结表明对16轮DES的攻击需 选择明文247，分析的复杂性为237。 (2)线性密码分析 Mitsuru Matsui提出了线形密码分析。使用线性 近似值来逼近分组密码的操作。攻击完整的16轮DES，当已知明文的平均数为243时，可得到密钥，是最有效的攻击DES的方法。 第四章 现代对称密码null第四章 现代对称密码4.2 序列密码 1.随机数生成器 (1)任意由确定过程生成的随机数序列，从实 际意义上讲都不是随机的。 (2)pRNG(pseudo-random number generators): 伪随机数发生器，其典型应用是一次一密乱码本。 (3)一个pRNG要求：在不知道密钥的情况下， 由随机数序列中已知部分推测下一个数是“困难”的。 (4)伪随机数序列的周期：要求尽可能大 对于序列s0,s1,s2,…若存在p，使得si+p=si 则称它为周期为p的周期序列。null第四章 现代对称密码 2.线性同余发生器 最为广泛使用的伪随机数产生器。 (1)产生方式 sn+1=(a·sn+b) mod m ∈Zm 其中0