第二章密码编码学基础

授课老师：袁曼丽授课地点：福建师范大学第二章密码编码学基础2.1术语和背景解密明文信息安全原理与应用密文原始明文加密加密解密明文密文原始明文对称密码体制加密密钥

信息安全原理与应用解密明文密文原始明文非对称密码体制加密加密密钥

KE信息安全原理与应用解密密钥

KD·密码编码学（cryptography）·密码破译者（cryptanalyst）·密码学（cryptology）信息安全原理与应用2.2

替换密码信息安全原理与应用·把原始信息中的字母用另一个字母或符号代替，这种技术称为单一字母替换密码（monoalphabetic cipher）或简单替换法(simple

substitution)。Caesar

Cipher-恺撒密码信息安全原理与应用·2千年前，Julius

Ceasar使用了一种简单的替换密码-——后被人称为恺撒密码（Caesar

cipher

）·首先被应用于军事上(cf

Gallic

Wars)·替换方法，每个字母用其后的第三个字母替换eg. L

FDPH

LVDZ

LFRQTXHUHG->

I

CAME

I

SAW

I

CONQUERED·Caesar

cipher可以描述如下：Plain:

ABCDEFGHIJKLMNOPQRSTUVWXYZCipher:

DEFGHIJKLMNOPQRSTUVWXYZABC·练习 解密

"RPQLD

JDOOLD

HVW

GLYLVD

LQ

SDUWHV

WUHV"恺撒密码的一般形式信息安全原理与应用·一般形式，可以把Caesar

cipher中字母移动的位数由3变为1-25中的任何一个·可以指定一个密钥字母作为字母A的密文。·例如：密钥字母F表示：·A F,

B

—

G,

...

Y

—

D,

Z

—E·即每个字母移动5位·共有26种可能的密码算法（25种可用）恺撒密码的分析破译·密文：wklv

phvvdjh

lv

qrw

wrr

kdug

wr

euhdn·明文：T OT

TOO

TO信息安全原理与应用混合单码替换密码信息安全原理与应用·不仅仅是移位变换·每个字母可以用其它任何一个字母替换（不能重复）·每个字母可以随机的映射到其它一个·因此密钥长度是26个字母·单字母替换密码（

Monoalphabetic

Substitution

Cipher

）·例如：·明文:ABCDEFGHIJKLMNOPQRSTUVWXYZ·密文:DKVQFIBJWPESCXHTMYAUOLRGZN·Plaintext:

IFWEWISHTOREPLACELETTERS·Ciphertext:

WIRFRWAJUHYFTSDVFSFUUFYA简单的单码替换密码信息安全原理与应用·the

Mixed

Monoalphabetic

Cipher

has

a

26letter

key·需要一种简单方法指定密钥·有多种方法，一种简单方法是写没有重复字母的“密钥字”，其它字母按顺序写在密钥字最后字母后面·例如，给定密钥字“word"·Plain:

ABCDEFGHIJKLMNOPQRSTUVWXYZ·Cipher:

wordabcefghijklmnpqstuvxyz密钥加长信息安全原理与应用·Plain:

ABCDEFGHIJKLMNOPQRSTUVWXYZ·密钥：professional·Cipher:

profsinalbcdghjkmqyuvwxyz无规律排列字母信息安全原理与应用·Plain:

ABCDEFGHIJKLMNOPQRSTUVWXYZ·规律：偏移量每次增加2的n倍(n从0开始)·Cipher:

adgjmpsvybehknqtwzcfilorux一次一密乱码本信息安全原理与应用·Blaise

de

Vigenère发明了多字母替换密码（polyalphabetic

substitution

cipher）·使用多个单字母替换表·因此一个字母可以被多个字母替换·方法，用一个密钥选择对每个字母使用哪个字母表弗纳姆密码信息安全原理与应用弗纳姆密码举例信息安全原理与应用·报文：VERNAMCIP

H E

R·等价的数字：214171301228157417·+随机数：

764816824403581160054888·=和：

9752339544156019751252105·=mod

26190717181581923

12

01·密文：tahrspItx

m

ab维吉尼亚表信息安全原理与应用替换法小结信息安全原理与应用·替换的目的是混乱，这种加密方法试图使密码破译者或入侵者难以确定报文和密钥是如何转换成密文的。2.3

置换密码信息安全原理与应用·置换（transposition）是将报文中的字母重新排序。运用置换，其目的就是扩散，并利用密文，广泛地传播报文或密钥中的信息。·置换试图打破已确定的模式。·置换是对报文符号的重新排序，所以也称为排列（permutation）。2.3.1

列置换·明文:THIS

IS

A

MESSAGE

TO

SHOW

HOW

A

COLUMNARTRANSPOSITION

WORKS.T

H

I

S

IS

A

M

E

SS

A

G

E

TO

S

H

O

WH

O

W

A

CO

L

U

M

NA

R

T

R

AN

S

P

O

SI

T

I

O

NW

O

R

K

S·密文：tssoh

oaniw

haaso

lrsto

imghwutpir

seeoa

mrook

istwc

nasns信息安全原理与应用双字母组、三字母组以及其他结构信息安全原理与应用·就像有常用字母一样，成对出现的字母也有一些特有的结构，称为双字母组。双字母组三字母组ENENTREIONEHANDNTINGTHIVEONTIOINFORTFOURANTHIORONE双字母的分析和破译法信息安全原理与应用·

tssohoaniwhaasolrsto

imghwtssohoaniwhaasolrsto

imghwtssohoaniwhaasolrsto

imghwtssohoaniwhaasolrsto

imghw·是一种替换与变换合用的密码·一般情况下，手工破译是非常困难信息安全原理与应用2.3.2乘积密码S

U

N

D

A

YW

h

e

r

e

I

s

/

4

5

6

/

a

I

r

b

o

r

n

e08329069799

98

3

4

3

1

0

93

44

45

46

93

6

1

4

80

7

4 2

3BCEFGH80843919498IJKLMO1858892957PQRTVW8186459699XZ./82878993·优质密码特征(Claude

Shannon

1949提出)·加密、解密的工作量应该由所要求的安全程度决定。·密钥集合和加密算法不应该过于复杂。·执行过程应该尽量简单。·密码中的差错不应该具有传播性，也不应该影响报文中的其他信息。·加密后的文本大小不应该比原始报文大。信息安全原理与应用·流密码本章讨论的大多数都是流流密码。明文密文密钥（可选）信息安全原理与应用流加密·块密码XN

OI

TP

YRPO

BA

QC

KD密钥（可选）信息安全原理与应用流加密·流算法和块算法比较信息安全原理与应用流加密算法块加密算法优点转换速度快低错误扩散率高扩散性无法插入符号缺点低扩散性易被恶意插入和篡改加密较慢错误扩散·混乱性和扩散性混乱性：当明文中的字符变化时，截取者不能预知密文会有何变化。扩散性：密码应该把明文的信息扩展到整个密文中去，明文的变化就可以影响到密文的很多部分。信息安全原理与应用·密码分析学：破译加密体制密文全部明文部分明文算法信息安全原理与应用美国数据加密标准—DES（Data

Encryption

Standard）信息安全原理与应用美国制定数据加密标准简况信息安全原理与应用·目的通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于90年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。只有标准化，才能真正实现网的安全，才能推广使用加密手段，以便于训练、生产和降低成本。美国制定数据加密标准简况信息安全原理与应用·美国NBS在1973年5月15公布了征求建议。

1974年8月27日NBS再次出公告征求建议，对建议方案提出如下要求：·算法必须完全确定而无含糊之处；·算法必须有足够高的保护水准，即可以检测到威胁，恢复密钥所必须的运算时间或运算次数足够大；·保护方法必须只依赖于密钥的保密；·对任何用户或产品供应者必须是不加区分的。美国制定数据加密标准简况信息安全原理与应用·IBM公司在1971年完成的LUCIFER密码(64

bit分组，代

换-置换，128

bit密钥)的基础上，改进成为建议的DES体制·1975年3月17日NBS公布了这个算法，并说明要以它作为联邦信息处理标准，征求各方意见。·1977年1月15日建议被批准为联邦标准[FIPS

PUB

46]，并设计推出DES芯片。·1981年美国ANSI将其作为标准，称之为DEA[ANSIX3.92]·1983年国际标准化组织(ISO)采用它作为标准，称作DEA-1美国制定数据加密标准简况信息安全原理与应用·NSA宣布每隔5年重新审议DES是否继续作为联邦标准，1988年（FIPS46-1）、1993年（FIPS46-2），1998年不再重新批准DES为联邦标准。·虽然DES已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。·1993年4月，Clinton政府公布了一项建议的加密技术标准，称作密钥托管加密技术标准EES(EscrowedEncryption

Standard)。算法属美国政府SECRET密级。美国制定数据加密标准简况信息安全原理与应用·DES发展史确定了发展公用标准算法模式，而EES的制定路线与DES的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。·1995年5月AT&T

Bell

Lab的M.Blaze博士在PC机上用45分钟时间使SKIPJACK的LEAF协议失败，

伪造ID码获得成功。1995年7月美国政府宣布放弃用EES来加密数据，只将它用于语音通信。·1997年1月美国NIST着手进行AES（AdvancedEncryption

Standard）的研究，成立了标准工作室。2001年Rijndael被批准为AES标准。DES算法信息安全原理与应用·分组长度为64

bits(8

bytes)·密文分组长度也是64

bits。·密钥长度为64

bits，有8

bits奇偶校验，有效密钥长度为56

bits。·算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。DES算法框图输入

64

bit明文数据初始置换IP乘积变换（16轮迭代）逆初始置换IP-164

bit密文数据输出标准数据加密算法信息安全原理与应用初始置换IP·将64

bit明文的位置进行置换，得到一个乱序的64

bit明文组，而后分成左右两段，每段为

32

bit，以L0和R0表示，IP中各列元素位置号数相差为8，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成置换输出。·逆初始置换IP-1。将16轮迭代后给出的64

bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。·IP和IP-1在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系，,x64变成为IP输信息安全原理与应用并将原来明文的校验位x8,x16,出的一个字节。初始置换IP信息安全原理与应用最终置换（逆初始置换IP-1）信息安全原理与应用乘积变换信息安全原理与应用·它是DES算法的核心部分。将经过IP置换后的数据分成32

bit的左右两组，在迭代过程中彼此左右交换位置。·每次迭代时只对右边的32

bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32

bit与右边得到的32

bit逐位模2相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左

边的寄存器中作为下一轮迭代时左边的段。·在每一轮迭代时，右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算。Li-1(32bit)Ri-1(32bit)选择扩展运算E48

bit寄存器按bit模2加密48

bit寄存器选择压缩运算S32

bit寄存器置换运算P按bit模2和Li

(32bit)Ri

(32bit)乘积变换框图密钥产生器信息安全原理与应用选择扩展运算E信息安全原理与应用将输入的32

bit

Ri-1扩展成48

bit的输出，令s表示E原输入数据比特的原下标，则E的输出是将原下标s

0或1(mod

4)的各比特重复一次得到的，即对原第1,4,5,8,9,12,13,16,17,20,21,24,25,28,29，32各位都重复一次,实现数据扩展。将表中数据按行读出得到48

bit输出。位12345678移到的位置2，48345，76，891011，13位910111213141516移到的位置12，14151617，1918，20212223，25位1718192021222324移到的位置24，26272829，3130，32333435，37位2526272828303132移到的位置36，38394041，4342，44454647，1选择压缩运算S将前面送来的48

bit数据自左至右分成8组，每组为6

bit。而后并行送入8个S一盒，每个S盒为一非线性代换网络，有4个输出。48

bit寄存器S1

S2

S3

S4

S5

S6

S7

S832

bit寄存器信息安全原理与应用S盒运算信息安全原理与应用将前面送来的48比特数据从左至右分成8组，每组为6比特，然后并行送入8个S盒。8个S盒的工作原理都是一样，为一个非线性替换运算。每个S盒都是一个4行、

16列的矩阵，每行都是0到16个数字，但每行的数字排列都不同。每个S盒有6位输入，4位输出，6位输入中的第1位和第6位数字组成的二进制数值决定置换矩阵的行数，其余4位数字所组成的二进制数值决定置换矩阵的列数，行数和列数交点的数字便是S盒的输出。■例：假设S1盒的输入110010,

因第1位和第6位数字组成的二进制数为10=(2)10，他对应S1行号为2的那一行，其余4位数字所组成的二进制数为1001=(9)10，对应S1列号为9的那一列，交点处的数是12，则S1的输出为1100。S盒的置换矩阵如表2.2-5所示。信息安全原理与应用S-盒1信息安全原理与应用S-盒2S-盒3S-盒4S-盒8S-盒7S-盒6S-盒5置换运算P对S1至S8盒输出的32

bit数据进行坐标置换，置换P输出的32

bit数据与左边32

bit即Ri-1逐位模2相加，所得到的32

bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。位移到的位置1～8917233113282189~162416306262010117~24814253429信1息1安全1原9理与应用DES加密算法--密钥的产生信息安全原理与应用·DES的乘积变换部分含有16轮非线性变换，每一轮变换都用一个48比特的子密钥，共需16个不同的48比特的子密钥。·一个64比特的外部密钥经过密钥产生器产生48比特的16个子密钥。密钥产生框图信息安全原理与应用密钥的产生置换1：置换1的作用是将56比特密钥K’各位上的数按规定方式进行换位。置换后的56比特分别存到两个28比特的寄存器中。如图2.2.5所示。C0的各位依次为原密钥中的57,49,41,…,36位，D0的各位依次为原密钥中的63,55,…,4位。信息安全原理与应用密钥的产生·

循环左移寄存器：每个循环左移寄存器都有28比特，加密时，循环寄存器对 的内容是将循环寄存器对

位·的比特数如的表内所容示分。别左移1至2位得到的。各级寄存器移在表2.2.1中,

当i=4时，左移位数是2，即寄存器对的内容是寄存器的 内容循环左移两位得到的。信息安全原理与应用密钥的产生压缩置换：是从56位内容中选出48位，产生16轮加密的16子密钥。压缩置换表如表2.2-2所示。的比特序号，的第14,17,11,…压缩置换表中的数字表示循环寄存器对他的读取顺序是从左到右，从上到下，即位分别置换成 的第1,2,3,…位。信息安全原理与应用DES的安全性·互补性。DES算法具有下述性质。若明文组x逐位取补，密钥k逐位取补，即y=DESk(x),则有这种互补性会使DES在选择明文破译下所需的工作量减半。·弱密钥和半弱密钥。DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k，各轮的子密钥都相同，即有k1=k2=…=k16就称给定密钥k为弱密钥(Weak

key)。信息安全原理与应用DES的安全性信息安全原理与应用若k为弱密钥，则有DESk(DESk(x))=xDES

-1(DES

-1(x))=xk

k即以k对x加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。弱密钥下使DES在选择明文攻击下的搜索量减半。如果随机地选择密钥，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及DES的安全性。DES的安全性信息安全原理与应用密文与明文、密文与密钥的相关性。Meyer[1978]详细研究了DES的输入明文与密

文及密钥与密文之间的相关性。表明每个密文比特都是所有明文比特和所有密钥比特的复合函数，并且指出达到这一要求所需的迭代次数至少为5。Konheim[1981]用

2检验证明，迭代8次后输出和输入就可认为是不相关的了。DES的安全性信息安全原理与应用S盒设计。DES靠S盒实现非线性变换。密钥搜索机。对DES安全性批评意见中，较为一致的看法是DES的密钥短了些。IBM最初向NBS提交的建议方案采用112bits密钥，但公布的DES标准采用64

bits密钥。有人认为NSA故意限制DES的密钥长度。采用穷搜索对已经对DES构成了威胁．二重DES信息安全原理与应用用DES进行两次加密，但这是否就意味着两重DES加密的强度等价于112

bit密钥的密码的强度？答案是否定的。中途相遇攻击法