对称密码 古典密码.docx

对称密码 古典密码.docx

《对称密码 古典密码.docx》由会员分享，可在线阅读，更多相关《对称密码 古典密码.docx（22页珍藏版）》请在冰点文库上搜索。

对称密码古典密码

第二讲对称密码----古典密码

一、内容提要

1.为什么需要密码

2.基本的概念和术语

3.密码学的历史

4.传统加密的古典技术

---代替密码

---置换密码

●为什么需要密码

1.信息的存储：

在公开的地方

2.信息的交换：

使用非隐秘介质

3.信息的传输：

通过不安全信道

●基本概念

1.密码学（Cryptology）：

是研究信息系统安全保密的科学。

2.密码编码学（Cryptography）：

主要研究对信息进行编码（压缩、保密和纠错），实现对信息的隐蔽。

3.密码分析学（Cryptanalytics）：

主要研究加密消息的破译或消息的伪造。

●基本术语

1.消息被称为明文（Plaintext）。

用某种方法伪装消息以隐藏它的内容的过程称为加密（Encryption），被加密的消息称为密文（Ciphertext），而把密文转变为明文的过程称为解密（Decryption）。

2.对明文进行加密操作的人员称作加密员或密码员（Cryptographer）。

3.密码算法（CryptographyAlgorithm）：

是用于加密和解密的数学函数。

4.密码员对明文进行加密操作时所采用的一组规则称作加密算法（EncryptionAlgorithm）。

5.所传送消息的预定对象称为接收者（Receiver）。

6.接收者对密文解密所采用的一组规则称为解密算法（DecryptionAlgorithm）.

二、传统密码体制

1、凯撒密表

•

2）加解密过程示意图

加密和解密算法的操作通常都是在一组密钥的控制下进行的，分别称为加

密密钥（EncryptionKey）和解密密钥（DecryptionKey）。

3）

加密通信的模型

密码学的目的：

Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。

4.密码体制

密码体制：

它是一个五元组（P,C,K,E,D）满足条件：

（1）P是可能明文的有限集；（明文空间）

（2）C是可能密文的有限集；（密文空间）

（3）K是一切可能密钥构成的有限集；（密钥空间）

*（4）任意k∈K,有一个加密算法eK∈E和相应的解密算法dK∈D，使得eK：

PC和dK：

CP分别为加密解密函数，满足dk（ek（x））=x,这里x∈P。

5.密码算法分类-i

按照保密的内容分：

1）受限制的（restricted）算法：

算法的保密性基于保持算法的秘密。

2）基于密钥（key-based）的算法：

算法的保密性基于对密钥的保密。

6.密码算法分类-ii

基于密钥的算法，按照密钥的特点分类：

对称密码算法（symmetriccipher）：

又称传统密码算法（conventionalcipher），就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。

又称秘密密钥算法或单密钥算法。

非对称密钥算法（asymmetriccipher）：

加密密钥和解密密钥不相同，从一个很难推出另一个。

又称公开密钥算法（public-keycipher）。

公开密钥算法用一个密钥进行加密，而用另一个进行解密。

其中的加密密钥可以公开，又称公开密钥（publickey），简称公钥。

解密密钥必须保密，又称私人密钥（privatekey）私钥，简称私钥。

7、密码算法分类-iii

1）按照明文的处理方法：

分组密码（blockcipher）：

将明文分成固定长度的组，每个分组都用相同的密钥进行加密产生相同、输出也是固定长度的密文。

⏹流密码（streamcipher）：

又称序列密码。

序列密码每次加密一位或一字节的明文，然后用相关但不同密钥加密产生相应的密文，相同的明文分组由于在明文序列中的位置不同对应的密文不同，也可以称为流密码。

序列密码是手工和机械密码时代的主流。

密码学的历史

●密码学的起源和发展

（1）

三个阶段：

1）1949年之前，密码学是一门艺术；

2）1949～1975年，密码学成为科学；

3）1976年以后，密码学的新方向——公钥密码学。

●密码学的起源和发展

（2）

1949年之前：

古典密码（classicalcryptography）

Ø密码学还不是科学，而是艺术。

Ø出现一些密码算法和加密设备。

Ø密码算法的基本手段（substitution&permutation）出现，针对的是字符。

Ø简单的密码分析手段出现。

●密码学的起源

隐写术（steganography）：

通过隐藏消息的存在来保护消息。

1）隐形墨水；

2）字符格式的变化；

3）图像

●Example-1

•（象形文字的修改）ModifiedHieroglyphics,c.1900B.C.

密码学的第一个例子是对标准书写符号的修改

例如：

古埃及法老坟墓上的文字

思想：

代替（substitution）

Example-2

•CaesarCipher,c.50B.C.

ABCDEFG……XYZ

DEFGHIJ……ABC

明文:

Caesarcipherisashiftsubstitution

密文:

FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQ

Example-3

用布或羊皮纸缠在竿上写字、奴隶的头剃光，将消息刺在头上，等头发长好后上路等等。

●密码学的起源和发展（3）

•1976年以后：

Ø1976年Diffie&Hellman提出了不对称密钥密码

Ø1977年Rivest，Shamir&Adleman提出了RSA公钥算法

Ø90年代逐步出现椭圆曲线等其他公钥算法，公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！

●密码分析

假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。

这个假设称为Kerckhoff原则。

最常见的破解类型如下：

1）唯密文攻击：

Oscar具有密文串y。

2）已知明文攻击：

Oscar具有明文串X和相应的密文Y。

3）选择明文攻击：

Oscar可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。

4）选择密文攻击：

Oscar可暂时接近密码机，可选择密文串y，并构造出相应的明文x。

这一切的目的在于破译出密钥或密文。

●密码破译

•密码破译的原则：

遵循观察与经验；

•方法：

采用归纳与演绎；

•步骤：

分析、假设、推测和证实；

•三大要素：

–语言的频率特征：

e

–连接特征：

q…u,Iex,

–重复特征：

th,tion,tious

●密码算法的安全性

1）无条件安全（Unconditionallysecure）

无论破译者有多少密文，他也无法解出对应的明文，即使他解出了，他也无法验证结果的正确性。

2）计算上安全（Computationallysecure）

Ø破译的代价超出信息本身的价值；

Ø破译的时间超出了信息的有效期；

●对称密码分析的两个基本方法

1）穷举法（ExhaustiveAttackmethod），又称为强力法（Brute-forcemethod）.。

完全试凑法（completetrial-and–errormethod）；

–这是对截获的密文依次用各种可能的密钥破译。

–对所有可能的明文加密直到与截获的密文一致为止。

2）分析法

–系统分析法（统计分析法）：

利用明文的统计规律

–确定性分析法

●对称密码的两个基本运算

1）代替（Substitution）

古埃及的原始密码（左方是密文，右方是相应的明文）

2）置换（Permutation）

●古典密码

基于字符的密码

1）代替密码（substitutioncipher）：

就是明文中的每一个字符被替换成密文中的另一个字符。

接收者对密文做反向替换就可以恢复出明文。

（代替规则、密文所用字符、明文中被代替的基本单位）

2）置换密码（permutationcipher），又称换位密码（transpositioncipher）：

明文的字母保持相同，但顺序被打乱了。

●代替密码

•简单代替密码（simplesubstitutioncipher），又称单字母密码（monoalphabeticcipher）：

明文的一个字符用相应的一个密文字符代替，而且密文所用的字符与一般的明文所用字符属同一语言系统。

•多字母密码（ployalphabeticcipher）：

明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置。

●多字母代换密码

可以用矩阵变换方便地描述多字母代换密码，有时又称起为矩阵变换密码。

单字母密码

●单表代换密码

–移位（shift）密码

–密钥短语（KeyWord）密码

–任意的单表代替密码

1、移位密码算法

●设P=C=K=Z/（26），对k∈K，定义ek（x）=x+k（mod26）=y∈C

同时dk（y）=y-k（mod26）

实际算法为：

∀x∈P有e3（x）=x+3（mod26）=y

同时有，d3（y）=y-3（mod26）

移位密码分析

给定加密的消息：

PHHWPHDIWHUWKHWRJDSDUWB

1）加解密算法已知

2）可能尝试的密钥只有25个（不包括0）

通过强力攻击得到明文：

meetmeafterthetogaparty.

移位密码很容易受到唯密文攻击。

2、任意的单表代替密码算法

例：

置换π的对应关系为：

ABCDEFGHIJKLMNOPQRSTUVWXYZ

IDMEFZOAPHXBSCQRLTUYJVNWGK

试用单表代换密码以π为密钥对明文消息UNIVERSITY加密，然后对密文解密。

加密：

π（u）π（n）π（i）π（v）π（e）π（r）π（s）π（i）π（t）π（y）=JCPVFTUPYG

π-1的对应关系：

ABCDEFGHIJKLMNOPQRSTUVWXYZ

HLNBDEYJAUZQCWGIOPMRSVXKTF

构造方法：

以西文单词为密钥的换字表

–例如：

取atmosphere为密钥，首先找出其中发生重复的字母，去掉重复字母e，成为atmospher.

–其次，字母一共10个，从第11个字母开始，用atmosphere按顺序进行代替配置。

–然后把其余17个字母按自然顺序接在后面。

以atmosphere为密钥的换字表

密码破译

●密码设计是利用数学来构造密码；

●密码分析除了依靠数学、工程背景、语言学知识外，还要靠经验、统计、测试、眼力、直觉判断力…有时还要靠点运气；

●密码破译的原则：

遵循观察与经验；

●方法:

采用归纳与演绎；

●步骤:

分析、假设、推测和证实；

1、单表替换密码的破译

语言的统计特性：

–语言的频率特征

–连接特征

–重复特征

1）频率特征

•在各种语言中，各个字母的使用次数是不一样的，有的偏高，有的偏低，这种现象叫偏用现象。

•对英文的任何一篇文章，一个字母在该文章中出现的次数称作这个字母（在这篇文章中）的频数。

•一个字母的频数除以文章的字母总数，就得到字母的使用频率。

●英文字母的普遍使用频率

美国密码学家W.F.Friedman在调查了大量英文资料后，得出英文字母的普遍使用规律。

英文单字母的相对频率表

字母频率

字母频率

字母频率

R

0.0677

I

0.0627

Z

0.0008

Q

0.0012

H

0.0528

Y

0.0199

P

0.0199

G

0.0199

X

0.0017

O

0.0797

F

0.0289

W

0.0149

N

0.0707

E

0.1304

V

0.0092

M

0.0249

D

0.0378

U

0.0249

L

0.0339

C

0.0279

T

0.1045

K

0.0042

B

0.0139

S

0.0607

J

0.0013

A

0.0856

●特殊的特征

开头结尾特征：

有些文章的开头和结尾受到固定格式的限制；

有时文章中间的某些特定部位，某些字母也会出现较高的使用频率。

●频度最高的前30个双字母

•THHEINERANREEDONESST

•ENATTONTHANDOUEANGAS

•ORTIISETITARTESEHIOF

●频度最高的前20个三字母

•THEINGANDHEREREENTTHANTHWASETHFORDTHHATSHEIONINTHISSTHERSVER

●其它频率特征

①the的使用频率最高，是ING的三倍，若把the去掉，t在第II类中排在最后，h会降为第III类，th和he也不是常出现的字母组了；

②一半的单词以esdt结尾；

③一半的单词以tasw开头；

④Y的使用频率90%都集中在单词的结尾；

2）、连接特征

①后连接：

q…u

②前连接：

x的前面总是i,e很少是o和a

③间断连接：

在e和e之间，r的出现频率最高

3）、重复特征

•两个字符以上的字符串重复出现的现象，叫做语言的重复特征。

•thtiontious

●example

•UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

•VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

•EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

确定字母的相对频率

双字母频率

•UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

•VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

•EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

①最常见的双字母组合ZW，Z猜测其为T，W对应为H，P猜测其为E

三字母组合

•UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

•VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

•EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

①ZWPTHE

②ZWSZTHT

③SA

进一步分析-1

进一步分析-2

进一步分析-3

•Itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow.

单表密码破译小结

假定，推翻，再假定，再推翻，直至破译

①对密文字母的频数、使用频率和连接次数进行统计；

②根据了解到的密码编制人员的语言修养，以及手中掌握的密文的统计规律，多方比较，对明文的语种和密码种类作出假定；

③将假定语种的字母频率与密文字母频率进行比较；

④首先找出密文中频率最高的字母；

⑤根据字母的频率特征、连接特征、重复特征，从最明显的单词或字母开始，试探进行。

⑥总结

二、对抗频率分析的办法

●多名或同音代替密码

●多表代替密码

●多字母代替密码

1、多名代替密码

与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。

例如，A可能对应于5、13、25；B可能对应于7、9、31、42

当对字母的赋值个数与字母出现频率成比例时。

这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。

然而，若明文字母的其它统计信息在密文中仍很明显时，那么同音代替密码仍然是可破译的。

2、多表代替密码

多表代替密码：

是以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。

Ø非周期多表代替密码：

代换表是非周期的无限序列

一次一密密码（one-timepadding）：

对每个明文每次采用不同的代换表。

Ø周期多表代替密码：

代换表个数有限，重复使用。

维吉尼亚（Vigenere）密码Vigenérecipher（1858）

滚动密钥密码

对于周期代换密码，当密钥的长度d和明文一样长时，就成为滚动密钥密码。

Vigenére本人建议密钥与明文一样长

Vernam密码

•1918年，GillbertVernam建议密钥与明文一样长，并且没有统计关系的密钥内容，他采用的是二进制数据：

加密：

Ci=Pi⊕Ki

解密：

Pi=Ci⊕Ki

核心：

构造和消息一样长的随机密钥

转子机（图）

多字母代替密码

Playfair密码

1）Playfair举例

2）Playfair密码分析

•Playfair有26X26=676种字母对组合

•字符出现几率一定程度上被均匀化

•基于字母频率的攻击比较困难

•依然保留了相当的结构信息

置换密码

•换位密码把明文按行写入，按列读出

•密钥包含3方面信息：

行宽、列高、读出顺序

•完全保留字符的统计信息

•使用多轮加密可提高安全性

1）多次置换

•多次置换，减少结构性排列，不易于重构。

Reference

•WilliamStallings,Cryptographyandnetworksecurity:

principlesandpractice,SecondEdition.

•BruceShneier,Appliedcryptography:

protocols,algorithms,andsourcecodeinC,SecondEdition.

•ThomasH.Barr,InvitationtoCryptology,PrenticeHall,2002

•李克洪主编,实用密码学与计算机安全,东北大学出版社,1997,10

•王育民刘建伟编著,通信网的安全----理论与技术,2000,5

•

作业：

将明文变成密文的两个基本方法？