密码学教程课件：古典密码

密码学

古典密码

1．1置换密码与代替密码

1．2统计攻击

1．3一次一密和乘积密码1．4相关数学概念和算法

密码技术源远流长:

1．1置换密码与代替密码自从有了战争，就有了密码；烽火台、、、在不安全的信道传递保密信息。例题：(置换密码)栅栏密码（美国南北战争时期）：1234567891011atcaegtoorwtaktihtmro3597682111410ceotgotawarkirthmat*to竖写横读atcaegtoorwtaktihtmroceotgotawarkirthmat*to

attackateighttomorrow还可以写出多行的形式：123456acetmwtkitotagorathmo古希腊的斯巴达密码棒：acetmwtkitotagorathmo置换（Permutation）：一个有限集合S上的一一对应映射。

逆置换：输出变输入，按列调整第一行为自然顺序：

30个元素的置换表：

为了安全，置换表一般需要很大；另一方面为了方便记忆和存储，置换表都有一些规律；还可以构造多个置换表：置换1置换2置换1置换2置换1置换2希腊时代的恺撒密码，将英文字母移位一个固定的值。

明文字母a

b

c

d

e

f

g

h

i

j

k

l

m密文字母DE

F

G

H

I

J

K

LM

N

O

P明文字母n

o

p

q

r

s

t

u

v

w

x

y

z密文字母Q

R

S

T

U

VW

X

Y

Z

A

B

C例题：（代替密码）

attackateighttomorrow

DWWDFNDWHLJKWWRPRUURZ明文字母a

b

c

d

e

f

g

h

i

j

k

l

m01

2

3

4

5

6

7

89101112明文字母n

o

p

q

r

s

t

u

v

w

x

y

z13141516171819202122232425

加法密码：从运算上代替密码可分为（等）：乘法密码：仿射密码：

置换（换位）密码：打乱明文各字母的顺序。代替（换元）密码：将明文字母用密文字母代替；单表古典密码：始终采用同一个明密对照表的加密；多表古典密码：

变化使用多个明密对照表的加密。例题：Viginere密码（多表代替，1523-1596）明文：vigenerecipher密钥：camelcamelcame--密文：XISIYGRQGTRHQY（见下页表。把所有移位都列出来。）

杰弗逊“轮子密码”：

美国总统托马斯.杰弗逊于1790年左右发明的一个器

械密码。这种设备是后来的机械和机电密码机的基础。机电式密码：电报和加解密做在一起，即密码电报；多表代替汉字密码：每个汉字编写为一串十进制数字（密码本）恩格尼玛密码机

1．2

统计攻击英文单个字母的统计特性单表代替不能掩盖统计特性：

还有字母串的分布：2字母串分布、3字母串分布

attackateighttomorrow

DWWDFNDWHLJKWWRPRUURZ针对单表代替的攻击：（1）截获一定数量密文，统计各个字母出现频次；（2）将出现频次高的密文字母，猜测为明文字母

d、t、a等；（3）猜测其他字母；

（4）反复验证。

例题：

任选两个字母，相同的概率。

粗糙度假设-检验攻击方（Adversary）防守方（Defender）

防守强度攻击强度

密码学（Cryptology）包括：

密码编码学（Cryptography）----设计

密码分析学（Cryptanalysis）----破译

1．3一次一密和迭代密码Vernam密码：

尽可能增加表的长度（很长的密钥流），

而加密就是简单加法，解密就是减法。（1）将明文转为二进制串；

（2）产生与明文一样长的随机二进制串（密钥）；

（3）明文与密钥逐比特异或（模2加）；

（4）解密时密文再与同样的密钥逐比特异或。序列密码的萌芽乘积密码：

将置换与代替结合使用，并进行多轮。

S盒：代替(substitute);

P盒：置换(Permutation)分组密码的萌芽公开1949年，香农发表：

“CommunicationTheoryofSecrecySystems”，

定义理论安全性，提出扩散和混淆的乘积方法。

信源信道信宿干扰通信的任务是把信息有效地、可靠地传递到信宿。

手段是编码（coding）。

平均每个符号的信息量

X是信源;

Y是信宿

含义：损失熵等于明文熵，

信宿端从密文得不到明文的任何信息；

明文信息“皆损失在信道中”；

（皆被加密过程所掩盖。）

含义：密钥熵（不确定性）大于等于明文熵，

密钥信息要能够掩盖住明文信息；

熵越大，用于表示信息的符号长度越长，

即密钥长度要大于等于明文长度。密码体制(模型)：明文空间M：所有明文构成的集合密文空间C：所有密文构成的集合密钥空间K：所有密钥构成的集合加密算法Ek：由k确定的加密算法解密算法Dk：由k确定的解密算法

从空间中随机选取OneTimePad:一次一密（1）密钥与明文一样长；（2）密钥必须是真随机的；（3）密钥只能对一个密文进行加密。

可证明了这一体制是无条件安全的。但只具有理论价值，实际中：（1）难以做到密钥与明文一样长；

（3）真随机的密钥难以实现；

（4）每次更换密钥，效率太低。发展为现代序列密码可通过以下手段达到计算安全性：扩散(diffusion)：明文与密文的关系尽量混乱；混淆(confusion)：密钥与密文之间的关系尽量混乱。理论安全：不泄漏任何信息，不依赖敌手的计算能力。计算安全：计算上困难的，依赖于敌手的计算能力。实际中：置换（P盒）实现扩散；代替（S盒）实现混淆。

二者乘积并多次迭代可达到足够的安全性。发展为现代分组密码攻击=计算困难问题1977年，数据加密标准DES算法被公布；

DES----DataEncryptionStandard

乘积密码的典范；现代分组密码的第一标准。加解密算法公开保密的只有密钥处理二进制数据1976年，Diffe和Hellman提出公钥密码思想；

解决对称密码中建立和管理密钥的问题；

加密用公钥，解密用私钥。私钥还可以数字签名。箱子变邮筒密码学新方向!密码学加密：实现保密性认证：实现认证性1978年，出现第一个公钥加密算法：RSA。因此：加密算法分为对称加密、非对称加密；对称加密又分序列密码和分组密码两种类型；认证技术主要有：数字签名、Hash函数和认证协议。构成密码学的主要(基本)内容!计算机内部处理的是二进制串：

二进制串（0和1组成的串）不仅可以表示数，

还可以表示各种符号等其他数据。

比特（bit：binarydigit）：

每位二进制串中的符号称为1比特（bit）；

不论是1还是0，都算1比特。（信息的单位）

ASCII码（American

Standard

CodeofInformationInterchange）：

128个常用符号编码为128个整数（对应二进制串），

扩展的ASCII码表示另外附加128个符号。将键盘符号转变为二进制码

编码译码加密解密认证认证信源信道信宿噪声网络（安全）信息处理系统：从功能上看：

从内容上看：

保密性

认证性

安全多方计算

对称密码

公钥密码杂凑函数

密码协议安全性定义、设计（编码）、实现和分析（攻击）(含身份认证)可视为三个发展阶段模运算的性质：

同余运算的性质：

1．4相关数学概念和算法加法群：（additivegroup）集合上定义一种运算（+），有单位元，都有逆元。

二种运算！

＋0100111001000101

＋01234001234112340223401334012440123×123411234224133314244321都有加法逆元即负元

＋012345001234511234502234501334501244501235501234×12345112345224024330303442042554321整数集合模素数p构成剩余类域Zp；整数集合模合数n构成剩余类环Zn。有限域有限环无限的代数结构：Z：整数环；Q：有理数域；

R：实数域；C：复数域。

两种运算都构成群（并有分配律）的就是域例题：

商辗转剩余361241221200结论：公因子是每个余数的因子；

每个余数都可以写成输入二数的线性组合。商辗转剩余268321211剩余表示为36和24的和36的系数24的系数1236-1*241-1024-2*12=24-2*（36-1*24）=（-2）*36+3*24-23剩余表示为26和3的和26的系数3的系数226-8*31-813-1*2=3-1*（26-8*3）=（-1）*26+9*3-19