密码学 | Golowper’s blog

type

Post

status

Published

date

May 10, 2022

slug

summary

大二下密码学学习笔记

1.3 密码学的起源现状和发展趋势及密码战线上的斗争

手工或简单机械密码时期：密码棒

1977 年DES加密 2^26 & RSA 大质数分解

1.4数学基础知识介绍

初等数学基本概念：

整除和因子（约数）整除：-3|18

剩余和模运算

模运算性质：

最小公倍数lcm

最大公约数gcd

辗转相除法求最大公约数

互素

素数

合数

唯一分解定理：任意整数a都能拆解为质数的平方和

同余

a同余

模n剩余类：n=3时

{,-3,0,3,6,,} , {,-2,1,4,,} , {,-1,2,5,,,}

模n完全剩余系：

模运算满足封闭性：mod运算结果不在Zn之外

加法逆元

乘法逆元

乘法可约律

扩展的欧几里得算法

互素剩余系 / 既约剩余系

欧拉函数

素数n 的

欧拉定理

费马定理

二.抽象代数的基本概念

定义

群：

封闭性，结合律，存在单位元 a*e=e*a=a ，任意元素都有逆元

eg：

环：

域：

具有两种代数运算的结构，（F，＋，×）是非零元都有乘法逆的交换环。

满足以下条件： ◆ 关于加法构成Abel群， ◆ 非零元素全体对乘法构成Abel群， ◆ 加法和乘法之间满足分配律。

第二章古典密码

置换的概念：加密函数或变换应该是双射

替代密码如：凯撒密码

换位密码

乘积密码

单表古典密码

加法密码 q是密钥空间

乘法密码。 k与q互素加密：解密：

仿射密码

置换密码

多表密码

简单加法密码

简单乘法密码

简单仿射密码

简单置换密码

换位密码

广义置换密码

广义仿射密码

Playfair密码体制

Vigenere 密码体制

古典密码的统计分析

第三章分组密码

4.1 分组密码的设计原理与结构

4-分组密码.pdf

5328.8KB

香农安全理论的主要结论

完善保密的密码系统的充要条件是明文和密文是相互独立的。一次一密体制是完善保密体制，要求：（1）密钥的长度至少和明文相同；（2）每次加密使用不同的密钥；（3）密钥是随机性的。为了克服统计分析，可以采用扩散和混淆两种基本方式。

扩散：就是使明文的每一位影响密文中的许多位，也就是密文的每一位受明文的许多位的影响。这样可以隐蔽明文的统计特性。

混淆：使用复杂的非线性替代变换可以达到比较好的混淆效果。

置换 P：扩散 替代 S：混淆

分组密码的总体结构有两种类型：

Feistel 结构：每轮处理一半数据，加解密相似。

SP 结构（替代－置换网络）：每轮处理整个分组数据，加解密不相似。

4.2 数据加密标准 DES与多重DES

DES结构

4.3 高级加密标准 AES

AES：

分组长度128bit 密钥长128bit ，192bit ，256bit

AES中的运算

1、有限域GF()中的运算（字节运算）

对于域的加法就是多项式对应项相加，系数模二加


加法可以理解为对应位的异或运算，如：
57⊕83 ---------------------------16进制
=01010111⊕10000011-------2进制
异或运算具体步骤（对应位相同则为0，不相同则为1）
0 1 0 1 0 1 1 1
1 0 0 0 0 0 1 1
————————
1 1 0 1 0 1 0 0

=11010100-----------------------2进制
=D4---------------------------------16进制

对于域的乘法


乘法类似多项式乘法，再结合类似mod m(x)方式计算。
之所以说类似，是因为运用多项式乘法后，需要消去系数为偶数的项，系数为奇数的项则将系数设置为1。因为2进制计算，系数只能为0和1。mod m(x)同样不是一般的除法取余，而是要使用异或运算。
m(x)=x8+x4+x3+x+1
至于为什么是这个表达式，我也不清楚，希望有数学大咖解释一下~
具体步骤可以参考下列例题：

xtime 运算


xtime()算法可用于面向字节的乘法运算，在程序开发中应用广泛，各种语言的实现代码在网上都可以查到，就不再赘述。仅在此详述算法的推导以及笔算解题时的使用方法。
根据定义，xtime()运算是最高项指数不大于7的多项式b(x)乘以多项式x的乘法运算。
因为是面向字符的运算，根据上述乘法原理，可以推出下列bi(i=0,1,…7)为0或1。
即：
b(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0
xtime(b(x))=x·b(x)=(b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x )mod m(x)
=(b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x )mod (x8+x4+x3+x+1)
接下来要分类讨论


当b7=0（左移一位，末位补0）


当b7=1（左移一位，末位补0，异或1B）

xtime计算举例


# 以下数字都是16进制
57·01=57=01010111
57·02=xtime(57)=xtime(01010111)=10101110=AE---------------------------------------------（b7=0，左移一位，末位补0）
57·03=57·(01+02)=57⊕xtime(57)=01010111⊕10101110=11111001=F9
57·04=57·02·02=AE·02=xtime(AE)=xtime(10101110)=01000111=47---------------------（b7=1，左移一位，末位补0，异或1B）
57·08=57·04·02=47·02=xtime(47)=xtime(01000111)=10001110=8E----------------------（b7=0，左移一位，末位补0）
57·10=57·08·02=8E·02=xtime(8E)=xtime(10001110)=00000111=07----------------------（b7=1，左移一位，末位补0，异或1B）
所以

57·13
=57·(10+02+01)
=57·10⊕57·02⊕57·01
=00000111⊕10101110⊕01010111
=11111110
=FE

2、系数在GF()的多项式运算（字运算）

字加法

字乘法

4.4 分组密码的应用模式

ECB

CBC

CFB模式

OFB模式

第四章公钥密码

6-公钥密码.pdf

2429.6KB

公钥密码基本原理

RSA 公钥密码(需要背下来)

RSA密码体制

选择一对不同的大素数p和q，将p和q保密。

令 n＝pq，用户公布n。计算并保密。

选取正整数 e ，使其满足 e是公钥

计算 d，满足 ,d是私钥

加密过程为：

解密过程为：

模幂算法

模逆算法

ElGamal 公钥密码（懂）

一. 离散对数问题

群的阶：有限群中元素的个数。

群元素的阶：乘法群中满足 =1 的最小正整数m。称为g在群中的阶

循环群：群G的每一个元都是G的某一个固定元g的乘方。g称为G的生成元。

本原元：循环群 中的生成元称为域 的本原元。是域，3和5是它的本原元。

离散对数问题：给定一个素数 p 和 Zp 的一个本原元 α，对于β ∈Zp* 找一个唯一整数 n ,0 ≤ n ≤ p − 2 使得

通常记为

二. ElGamal密码体制

（1）选择大素数p，α是一个本原元，p和α是公开的；

（2）随机选择整数 d ，，计算，β 是公钥，d 是私钥；

（3）明文空间为，密文空间为 x

加密变换：对于任意明文，秘密随机选取一个整数 k ，密文为

椭圆曲线上的M-V公钥密码ECC（不考）

椭圆曲线定义式：

有限域定义：

椭圆曲线加法

C=2A

C=3A

加密过程

对称密码和公钥密码体制的比较

对称密码系统

公钥密码系统

作业：

序列密码

5-序列密码.pdf

4424.5KB

5.1 序列密码的基本原理

如果每隔固定的r个字符或比特，以后密钥重复使用，则为周期序列密码；密钥不重复的为非周期序列密码。同步方式（synchronous）；自同步方式（self-synchronous）自同步密钥流与明文有关，一般需要密文反馈。实际应用中不可能存储大量的同步序列密码的密钥流，因此加密解密装置均需包含密钥生成器(KG)，其中密钥流的初始状态由短的种子密钥I触发

分组密码与序列密码的比较：

（1）序列密码：处理速度快，实时性好，适用于军事、外交等保密系统。但是适应性差，需要密钥同步。

（2）分组密码：不需密钥同步，较强的适应性，适宜作为加密标准。但是加密速度慢，错误易扩散和传播。(但比公钥密码快得多)

5.2 线性反馈移位寄存器

反馈移位寄存器

序列密码通过反馈移位寄存器产生密钥。移位寄存器可以通过一个反馈循环，从前面n项计算下一项，成为一个伪随机序列发生器。

例：

非退化的移位寄存器

退化和非退化的寄存器

x1(输出序列)	x2	x3	x4=f()=x1+x2+x3
1	0	0	0
0	0	0	1
0	0	1	1
0	1	1	0
1	1	0	1
1	0	1	0
0	1	0	0
1	0	0	0

m序列：

由例子可得出以下结论

（1）n-LFSR的结构由其结构常数唯一确定；

（2）n-LFSR的结构常数与反馈函数互相唯一确定；

（3）n-LFSR输出序列由其结构常数和初态唯一确定；

（4）一个n-LFSR可以产生个不同序列。（不考虑平移等价的话。）

平移等价：一个序列向左移若干位后，和另一序列相同。

（5）一个n-LFSR的序列的最大周期是

（6）m序列→由结构常态决定

LFSR

m序列的伪随机性

伪随机周期序列应满足三个性质

0游程和1游程

m序列的伪随机性

5.4 B—M算法

B—M算法

5.5 线性移位寄存器的非线性组合

解决线性反馈的不安全性的两种方式：

非线性反馈移位寄存器

布尔函数：

M序列：

线性反馈的非线性组合

第七章数字签名

1 . 数字签名的基本原理

💡

在密码学中利用数字签名和认证技术来实现信息 完整性、认证性和不可否认性等

利用对称钥加密可以实现签名，但需要一个可信第三方（TTP－Trusted Third Party）

💡

利用私钥签名；利用公钥验证

利用私钥加密可实现签名：

条件：当解密和加密变换可以交换顺序时；

通常数字签名方案包括三个部分：

（1）密钥生成：生成签名者所需的密钥；

（2）签名过程：签名者选择 m∈M，利用密钥进行签名

s=S(m)，输出(m,s)；

（3）验证过程：验证者获得验证函数（方程），验证签名，如果验证方程成立，则承认该签名；否则拒绝。

2 . RSA 数字签名（必会）

例题：

RSA签名的安全性：

hash + RSA签名

3 . ELGamal 数字签名（理解，不考）

生成密钥

签名算法

签名验证

例题：

4 . 数字签名标准DSS

第八章 Hash函数

8-Hash函数.pdf

1822.6KB

1、消息认证和数据完整性

认证（authentication）：采取一些措施保证实体（entity）是他们所宣称那些人，或消息不被非法者修改。认证是所有信息安全目标中最重要的内容之一。

身份认证：双方在线、实时性的验证，可以采用挑战－应答方式实现；例如电话

消息认证：挑战－应答不方便，常是单向的、可以有延时。例如 email（不是双方直接通信）

数据安全一般要求两项内容：

数据确实来自于所称的源（数据源认证）。

数据的状态是未被改变的（数据完整性）。

2、Hash函数的定义、性质和分类

2.1 Hash函数的定义

定义：

一个将任意有限长度的数据，映射到固定长度的函数，这个确定长度的输出叫hash值。用数学形式表述为：对定义域 D 和值域 R，有

函数是多对一的，意味着存在碰撞（因为 |D| > |R| ：D的值域大于R的值域，即多对一）是不可避免的。但是可以使产生碰撞的概率很小，即所谓计算安全的。

Hash函数的基本思想： 作为输入串的简明表示（代表），可以用作确认输入串的唯一凭证。所以hash函数也被叫做压缩函数、消息摘要、指纹等。也叫杂凑函数。一般的Hash函数至少有以下两个性质：（1）压缩。映射一个任意有限长的输入，为一个固定长的输出；（2）容易计算。给出h和输入x，计算h（x）是容易的。不同的Hash函数还要添加其他性质：（1）单向性：由 h(x) 计算 x 是计算困难的；（2）无碰撞性：不同的输入产生相同输出是计算困难的；

弱碰撞自由