密码学基础2

tology）作为数学的一个分支，是密码编
码学和密码分析学的统称。
使消息保密的技术和科学叫做密码编码学（cryptography) 破译密文的科学和技术就是密码分析学（cryptanalysis） – 明文：是作为加密输入的原始信息，即消息的原始形 式，通常用m或p表示。所有可能明文的有限集称为明 文空间，通常用M或P来表示。
– 在第一次世界大战期间，敌对双方都使用加密系统（Cipher System），主要用于战术通信，一些复杂的加密系统被用于高级 通信中，直到战争结束。而密码本系统（Code System）主要用于 高级命令和外交通信中。 – 到了20世纪20年代，随着机械和机电技术的成熟，以及电报和无 线电需求的出现，引起了密码设备方面的一场革命——发明了转 轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的 重要标志之一。美国人Edward Hebern认识到：通过硬件卷绕实 现从转轮机的一边到另一边的单字母代替，然后将多个这样的转 轮机连接起来，就可以实现几乎任何复杂度的多个字母代替。转 轮机由一个键盘和一系列转轮组成，每个转轮是26个字母的任意 组合。转轮被齿轮连接起来，这样就能实现当一个齿轮转动
• 近代密码（计算机阶段）
– 密码形成一门新的学科是在20世纪70年代，这是受计算机科学蓬 勃发展刺激和推动的结果。快速电子计算机和现代数学方法一方 面为加密技术提供了新的概念和工具，另一方面也给破译者提供 了有力武器。计算机和电子学时代的到来给密码设计者带来了前 所未有的自由，他们可以轻易地摆脱原先用铅笔和纸进行手工设 计时易犯的错误，也不用再面对用电子机械方式实现的密码机的 高额费用。总之，利用电子计算机可以设计出更为复杂的密码系
.
– 密文：是明文经加密变换后的结果，即消息被加密处 理后的形式，通常用c表示。所有可能密文的有限集称 为密文空间，通常用C来表示。 – 密钥：是参与密码变换的参数，通常用k表示。一切可 能的密钥构成的有限集称为密钥空间，通常用K表示。 – 加密算法：是将明文变换为密文的变换函数，相应的 变换过程称为加密，即编码的过程（通常用E表示，即 c=Ek(p)）。 – 解密算法：是将密文恢复为明文的变换函数，相应的 变换过程称为解密，即解码的过程（通常用D表示，即 p=Dk(c)）。

左28位Ci
右28位D
左右合并 换位选择2
48位密钥Ki
数据加密标准DES
DES的雪崩效应
在相同密钥加密时,明文的微小变化(如1位)会 引起密文的较大变化. 对相同明文,用两个差别很小(如1位)的密钥加 密,产生的密文差别较大.
DES具有很强的雪崩效应
数据加密标准DES
DES的雪崩效应
如下两个明文只差1位:
R i-1(32位) E
32 4 8 12 16 20 24 28
1 5 9 13 17 21 25 29
2 6 10 14 18 22 26 30
3 7 11 15 19 23 27 31
4 8 12 16 20 24 28 32
5 9 13 17 21 25 29 1
48位
⊕
S3 S4 P S5
0
0 1 2 3
1
2
3
4
5
6 7
8
9 10 11 12 13 14 15
14 4 13 0 15 7 4 1 14 15 12 8
1 2 15 4 14 2 8 13 6 2 4 9
11 8 3 10 6 12 5 9 0 7 13 1 10 6 12 11 9 5 3 8 2 1115 12 9 7 3 10 5 0 1 7 5 11 3 14 10 0 6 13
现代密码学
公开密钥算法 加密密钥(公钥) ≠ 解密密钥(私钥) 数学基础:单向函数,单向陷门函数 应用方面:加密/解密 数字签名 密钥交换 代表:RSA体制,Rabin体制等
密钥管理
密钥生成
1、密钥长度与密钥空间 2、好密钥与弱密钥 好密钥：自动处理设备产生的随机的位串 弱密钥：特定的密钥比其他密钥的安全性差。例如,用 户个人信息,简写字母,各种数据库单词及其不同变形

18
古典密码
仿射密码 加密函数取形式为 y=e(x)=ax+b (mod 26), a,b,x,y∈Z/(26)， 要求唯一解的充要条件是gcd( a,26)=1 加密函数取形式为： x =dk(y)=a-1(y-b)(mod 26)
可能的密钥是26*12=311个
19
二、分组密码
20
密码的设计原则
•信息需要共享... •信息需要使用... •信息需要交换... •信息需要传输...
4
为什么需要密码
信息的存储: 在公开的地方 信息的交换: 使用非隐秘介质 信息的传输: 通过不安全信道
5
基本概念
密码学(Cryptology): 是研究信息系统 安全保密的科学. 密码编码学(Cryptography): 主要研究 对信息进行编码,实现对信息的隐蔽. 密码分析学(Cryptanalytics):主要研究 加密消的特点分类： 对称密码算法（symmetric cipher)：又称传统密 码算法（conventional cipher)，就是加密密钥和 解密密钥相同，或实质上等同，即从一个易于 推出另一个。又称秘密密钥算法或单密钥算 法。 非对称密钥算法（asymmetric cipher): 加密密钥 和解密密钥不相同。如果从一个很难推出另一 个。又称公开密钥算法（public-key cipher) 。 公开密钥算法用一个密钥进行加密, 而用另一 个进行解密.其中的加密密钥可以公开,又称公 开密钥（public key)，简称公钥.解密密钥必须
明文和密文在0~n-1之间,n是一个正整数
应用最广泛的公钥密码算法 只在美国申请专利，且已于2000年9月到期
43
RSA算法描述
分组大小为k, 2k < n ≤ 2k+1 加密: C = Me mod n 解密: M = Cd mod n = Med mod n 公钥: KP={e,n}, 私钥: KS={d,n} 上述算法需要满足以下条件:

中
所使用的方式，其中密钥k＝3，比如hello！就表示为khoor(忽略空格和符 号)，它的数学表达式为：
加密：c＝m＋k（mod26）
解密：m＝c－k（mod26） 加密步骤：1）先将26个英文字母编号:a,b,c,d……y,z;每个英文字母对应
的数字分别是0,1,2,3……24,25,注意这里的编号是从0开始的，与我们平时
12
Caesar密码
Caesar密码攻击
湖南公安高 等专科学校
如果在一篇用恺撒密码加密的密文中（假设它的字数很多，
而且字母随机性很好），我们就可以从中发现出现频率最多的 字母，假设它为e或者t或者a，将出现频率最低的字母假设为x 或者z或者q，然后玩填字游戏，找到加密所使用的k，攻破这个 加密体制。 求解k的表达式为：k＝c－m（mod26） 注意：如果k为负数时，则加上26，使得k始终是一正数
第二章 简单密码学（补充——古典密码学）
湖南公安高 等专科学校
候选明文 exxegoexsrgi dwwdfndwrqfh cvvcemcvqpeg buubdlbupodf attackatonce zsszbjzsnmbd yrryaiyrmlac … haahjrhavujl gzzgiqgzuti式为：
加密：c＝m＋k（mod26） 解密：m＝c－k（mod26） 其中k即密钥，也就是关键字（如cipher）的字母个数。还有一点与Caesar 密码不同，这里的字母表中字母顺序打乱了，不再是完全按英文字母顺序排列 的，关键字不同，密码表的次序就不相同，保证了安全性，比Caesar密码更加 健壮，单由于它仍然是单表替换密码，同样可用字母出现频率弱点进行攻击。
第二章 简单密码学（补充——古典密码学）

素数
如何判断一个数是否为素数？
本章授课提纲
（1）整除
（2）素数
（3）最大公约数 （4）欧几里德算法
最大公约数
最大公约数的定义 a和b的最大公约数（Greatest Common Divisor ） 是能够同时整除a和b的最大正整数，记为gcd(a,b) 或者(a,b)。 例如：gcd(6,4)=2，gcd(5,7)=1，gcd(24,60)=12 互素的定义 如果gcd(a,b)=1，就称a和b互素
证明：记a-b=nk，b-c=nl，那么两式相减得ac=n(k-l)，所以a≡c(mod n)。
模运算和同余
模运算和同余的性质 性质五：如果m|(a-b)，则a≡b(mod m) 证明：由已知条件可得a-b=km，k为某一整数； 进而可得a=b+km，故a(mod m)=(b+km)除以m的余 数=b除以m的余数=b(mod m)，由同余的第二个定 义可以得证。
[11(mod 8)-15(mod 8)](mod 8)=(3-7)(mod 8)=4
=(11-15)(mod 8)=-4(mod 8)=4
模运算和同余
模运算的乘法的结合律 [a(mod n)〓b(mod n)](mod n)=(a〓b)(mod n) 举例： [11(mod 8)〓15(mod 8)](mod 8)=(3〓7)(mod 8)=21(mod 8)=5 =(11〓15)(mod 8)=165(mod 8)=5
欧几里德算法
欧几里德算法的精确描述 两个整数用a,b表示，商用q表示，余数用r表示 Step1 取a,b较大者为a，较小者为b Step2 做除法，计算并保留余数r=mod(a,b) Step3 将原来的除数改做被除数，余数作为除数 a=b,b=r 重复Step1和Step2直到r=0，返回b

版权所有，盗版必纠
13.1.1 密码学发展历史
• 古典密码算法有:替代加密、置换加密； • 对称加密算法包括DES和AES； • 非对称加密算法包括RSA、背包密码、Rabin、 椭圆曲线等。 • 目前在数据通信中使用最普遍的算法有DES算法 和RSA算法等。 • 除了以上这些密码技术以外，一些新的密码技 术如辫子密码、量子密码、混沌密码、DNA密码 等近年来也发展起来，但是它们距离真正的实用 还有一段距离。
版权所有，盗版必纠
13.1 密码学概述
• 小小的密码还可以导致一场战争的胜负。例如，计算机时 代的到来使得美国在1942年制造出了世界上第一台计算 机。二战期间，日本采用的最高级别的加密手段是采用 M-209转轮机械加密改进型—紫密，在手工计算的情况下 不可能在有限的时间破解，美国利用计算机轻松地破译了 日本的紫密密码，使日本在中途岛海战中一败涂地，日本 海军的主力损失殆尽。1943年，在解密后获悉日本山本 五十六将于4月18日乘中型轰炸机，由6架战斗机护航， 到中途岛视察时，罗斯福总统亲自做出决定截击山本，山 本乘坐的飞机在去往中途岛的路上被美军击毁，山本坠机 身亡，日本海军从此一蹶不振。密码学的发展直接影响了 二战的战局！
版权所有，盗版必纠
13.1.1 密码学发展历史
• 经典密码学(Classical Cryptography)。其两大类别
分别为：
• (1).
• • 经典加密法的资讯很易受统计的攻破，资料越多，解破就 更容易，使用分析频率就是好办法。经典密码学现在仍未 消失，常被用于考古学上，还经常出现在智力游戏之中。 在20世纪早期,包括转轮机的一些机械设备被发明出来用 于加密,其中最著名的是用于第二次世界大战的密码机 “迷”(Enigma)，如图13.2所示。 这些机器产生的密码 相当大地增加了密码分析的难度。比如针对Enigma的各 种各样的攻击，在付出了相当大的努力后才得以成功。

➢ 密码表多个——不固定
一条明文加密和解密同时使用多个密码表 明文中两个相同的字母可能被加密成不同的密文字母
11 软件网络 网络与信息安全
提纲
概述
单表代换算法
➢ 单符号代换算法
• 凯撒密码
• 移位密码 • 单表密码 • 短语密码 • 仿射密码
攻击方法
小结
12 软件网络
网络与信息安全
凯撒密码
基本型凯撒密码等于如下变换
明文字母表 密文字母表
➢ 明文表和密文表共同构成密钥 加密
解密
14 软件网络 网络与信息安全
凯撒密码
让每个字母对应一个数值
则基本型凯撒密码可以表示为
加密： 解密：
Ci = E(pi) = (pi+3) mod 26 pi = D(Ci) = (Ci3) mod 26
23 软件网络
网络与信息安全
9 软件网络 网络与信息安全
代替密码
单表密码算法（ Monoalphabetic Cipher)
➢ 密码表仅 1 个——固定
任何明文加密、密文解密均使用同一个密码表加密 明文中相同的字母必然被加密成相同的密文字母
10 软件网络 网络与信息安全
代替密码
多表密码算法（Polyalphabetic Cipher)
➢ 典型的密码系统
5 软件网络 网络与信息安全
对密码算法的基本要求
对密码算法的基本要求 ➢ 加密能力强
当密文或明文－密文对被截获时，破解密钥或明文在 计算上是不可行的
➢ 安全性不依赖于密码算法本身的保密，而依赖于 密钥
➢ 易于实现，使用方便
6 软件网络 网络与信息安全
古典密码
古典密码（Classical Cryptography）

2 RSA算法
RSA算法是一种常用的公钥加密算法，基于数论的难题，广泛应用于数字签名和密钥交换 等场景。
3 椭圆曲线算法
椭圆曲线算法是一种新兴的公钥加密算法，具有更短的密钥长度和更高的安全性。
消息认证码
消息认证码用于验证消息的完整性和真实性，常用于数据完整性校验和身份认证。
1 消息认证码概述
2 常用的消息认证码
总结
通过此课件，我们回顾了现代密码学的基础知识，并推荐了后续学习的方向。
《现代密码学基础》PPT 课件
现代密码学基础课程的PPT课件，包括密码学概述、对称加密算法、公钥加密 算法、消息认证码、密码学协议、密码学安全等内容。
密码学概述
密码学是研究信息安全和通信安全的一门学科，主要包括加密与解密技术、密钥管和认证协议 等内容。
1 密码学定义
密码学是研究信息安全和通信安全的一门学科，涉及加密与解密技术、密钥管理和认证 协议等内容。
消息认证码用于验证消息的完整性和真实性， 通常包括消息摘要和密钥。
• HMAC算法 • CMAC算法 • GMAC算法
密码学协议
密码学协议用于实现安全的通信和身份认证，常用于保护网络通信和数据传输的安全性。
1 密码学协议定义
2 常用的密码学协议
密码学协议用于实现安全的通信和身份认证， 通常包括密钥协商、身份认证和数据加密等 功能。
对称加密算法使用相同的密钥对信息进行加 密和解密，加密和解密过程效率高，但密钥 管理复杂。
2 常用的对称加密算法
• DES算法 • 3DES算法 • AES算法
公钥加密算法
公钥加密算法使用不同的密钥对信息进行加密和解密，具有更高的安全性。
1 公钥加密算法概述
公钥加密算法使用不同的密钥对信息进行加密和解密，提供更高的安全性和密钥管理的 便利。

相应的密文串将是: VPXZGIAXIVWPUBTTMJPWIZITWZT
解密过程与加密过程类似,不同的只是进行模26减,而不是模26 加。
使用Vigenère表可以方便地进行加密和解密。
@
基本概念
• 密码学(Cryptology): 是研究信息系统安全保密 的科学.
➢ 密码编码学(Cryptography): 主要研究对信息 进行编码,实现对信息的隐蔽.
➢ 密码分析学(Cryptanalytics):主要研究加密消 息的破译或消息的伪造.
密码新技术
• 量子密码(单量子不可复制定理) • DNA密码 • 化学密码 • ……
• 消息被称为明文(Plaintext)。用某种方法伪装消息以 隐藏它的内容的过程称为加密(Encrtption)，被加密 的消息称为密文(Ciphertext)，而把密文转变为明文 的过程称为解密(Decryption)。
• 对明文进行加密操作的人员称作加密员或密码员 (Cryptographer).
• 例如：明文INTELLIGENT用密钥PLAY加密为： M＝INTE LLIG ENT K＝PLAY PLAY PLA
Ek(M)＝XYTC AMIE TYT
• 例 设m＝6，且密钥字是CIPHER,这相应于密钥。假定明文串 是 this cryptosystem is not secure 首先将明文串转化为数字串，按6个一组分段，然后模26“加”上 密钥字得：
密码算法分类-iii
• 按照明文的处理方法： ➢ 分组密码（block cipher):将明文分成固定长度
的组，用同一密钥和算法对每一块加密，输出 也是固定长度的密文。 ➢ 流密码（stream cipher):又称序列密码.序列密 码每次加密一位或一字节的明文，也可以称为 流密码。