【第三章】密码算法

基本概念

• 明文M

• 密文C

• 加密E（M）=C

• 解密D（C）=M

• 明文转化密文方式，替换、换位

• 密钥

密码学

• 密码编辑学
• 设计密码算法保证安全

• 密码分析学
• 加密信息破译或伪造
• 前提是知道加密算法
• 密码攻击
• 唯密码攻击
• 已知明文攻击（密文-明文对）
• 选择明文攻击（可得到需要的任何明文对应的密文）
• 选择密文攻击（可得到需要的任命密文对应的明文）

• 密码体制
• 大体上可分为对称密码算法和公钥密码算法

• 计算安全
• 破解成本高于加密信息本身
• 破解时间超出加密信息有效期

对称密码

• 也称单钥、传统、私钥

分类

• 按照密文处理方式
• 序列密码（流密码）
• 分组密码

• 按照是否对称
• 对称密码
• 非对称密码

• 明文转密文操作类型
• 替换
• 移位

古典密码

单表代换密码

• 加密
先乘再加

• 解密
先减再除

• 密钥
• 必须满足

• 破解
• 明文、密文字母出现的次数统计规律
• 移位密码知道一密文明文对应关系位即可破解
• 放射密码知道两位密文明文对应关系即可破解

多表代换密码

• 加密
• d为代换周期，是密钥的长度
• 密钥循环与明文长度对齐，每位相加
• 加和超出N则modN
• 是密钥的第个

• 解密
 

多字符代换密码

• 加密
• c为长度为L的字符，T为L*L的矩阵

• 解密

分组密码

• 长度为L，的数依次处理

DES

• 密钥
• 64bit，8个校验位，有效位56位，轮密钥长度K_i=48
• 编排：
• LS_i()1、2、9、16轮左移位1位其他2位
• PC_2另一种置换

• 加密
• 分组长度64位
• k从1到16
• 或者直接按照表格对应
• f()
• 先将32位扩展成48位
• 和k_i异或
• 8个S盒，每个6位输入，4位输出

• 解密
• k从16到1

• 填充
• 如果分割后不足64位，即8bit，缺少n个字节，就填充n个n
• 不缺也填充，填充k个k
• 解密的时候最后一位是几，就删除几个字节

S盒

• 输入6位，中间四位为输入，两边两位是选择

• 有00 01 10 11四个选择的结果

• 根据表格，输入和选择对应结果

电码本模式ECB

• 直接使用分组密码

密码分组链接CBC

• 上一个的结果要异或得到本组的输入，加密不能并行

• 相同明文对应的密文不一定相同

• 需要共同的初始化向量

• 初始化向量IV可以改变第一块

• 密文快损坏，影响两明文块

AES

• 长度
• 密钥128/192/256bit
• 分组长度128bit

SM4

• 长度
• 分组128bit
• 密钥128bit

序列密码

非对称密码

• 也称公钥，双钥

• 如何产生密钥对

• 如何加解密

概率加密

单向函数

陷门单项函数

RSA

• 密钥生成
• 生成两个大的奇的互为素数的p、q
• n=pq且f(n)=(p-1)(q-1)
• 分清n和f(n)
• 任选b，1<b<f(n)，使g（b,f(x)）=1即b,f(x)互素
• a=b^{-1}modf(n)
• 补充知识，逆元定义
• ab 三 1(mod m)称m可逆，b是a的逆元，m和a互质,a^{-1}mod m
• 逆元是指b，即
算法学习笔记(9)：逆元
在数论中，如果 ab\equiv1\pmod{p} ，我们就说 a 和 b 在模 p 意义下互为乘法逆元，记作 a=\text{inv}(b) 。逆元有什么用呢？我们常常遇到一些题目要求结果对一个大质数 p 取模，这是因为答案很大，出题人为了不麻…

https://zhuanlan.zhihu.com/p/100587745

• 补充知识，欧几里得算法（辗转相除法）求逆元
• 上一次的除数数以上次的余数
• 之后再往回带，得到m和a两个数字直接的关系式
【密码学笔记】辗转相除法求模的逆元
问题：求 A 关于模 N 的逆元 B ，即要找出整数 B ，使得 A \times B = 1 (\bmod N) ，其中 A 和 N 互素。方法：辗转相除法（欧几里德算法） 解题思路：首先对 A 和 N 进行辗转相除： \begin{align*} N &amp; = A \…

https://zhuanlan.zhihu.com/p/477151965
• 补充知识，最大公因数
• 带余数除法
• 公钥为(n,b)私钥为(p,q,a)或(n,a)

• 加密
• y=x^b mod n
• x=y^a mod n

• 解密
• 费马定理

• 安全效率
• 适合加密少量数据

• DPKC确定性公钥系统
• 任一明文的密文都是（由公钥）唯一确定的

• EIGarmal非确定公钥系统
• 加密算法是非确定的.即使加密相同的明文，得到的密文也是不相同的，因此又称为概率加密体制。

对称非对称密码体制比较

• 对称
• 加解密快
• 密钥分发快云南
• 管理复杂
• 不能实现数字签名

• 非对称
• 相对

数字信封（混合加密）

杂凑函数和消息认证码

• 哈希算法、杂凑函数、单向散列函数、数字指纹法表示同一个含义

• 单向性：对于给定的hash值h，要找到x，使得H（x）= h在计算上是不可行的，即求hash的逆很困难；

• 弱抗碰撞性：对于给定的消息x，要发现另一个消息y，满足H（x）=H（y）在计算上是不可行的；

• 强抗碰撞性：对于任意不同的消息x和y，使得H（x）=H（y）在计算上也是不可行的。

数字签名