古典密码学

简单学习一下古典密码体制与对应的密码分析方法

移位密码

Shift Cipher

移位密码算是古典密码学中最为简单的一种密码,其基础是数论中的模运算

密码体制


移位密码体制:


此处的 $K$ 满足 $0<=K<=25$ ,特殊的当 $K=3$ 时就是凯撒密码(Caesar Cipher)

分析方法

移位密码的分析方法及其简单,因为其密钥空间不是很大,完全可以利用密钥穷尽搜索方法来破译,下面给出一个例子

1
xbjhihpnpldgspqdjiutpg

编写爆破 $K=0,1,…,25$ 的脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
from string import ascii_letters
ctoi = lambda x: ascii_letters.index(x)
itoc = lambda x: ascii_letters[x]

secret = 'xbjhihpnpldgspqdjiutpg'

for k in range(0, 26):
plain = ''
for i in range(len(secret)):
y = ctoi(secret[i])
x = itoc((y - k) % 26)
plain += x
print(plain)

在结果中可以看到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
xbjhihpnpldgspqdjiutpg
waighgomokcfropcihtsof
vzhfgfnlnjbeqnobhgsrne
uygefemkmiadpmnagfrqmd
txfdedljlhzcolmzfeqplc
swecdckikgybnklyedpokb
rvdbcbjhjfxamjkxdconja
qucabaigiewzlijwcbnmiz
ptbzazhfhdvykhivbamlhy
osayzygegcuxjghuazlkgx
nrzxyxfdfbtwifgtzykjfw
mqywxweceasvhefsyxjiev
lpxvwvdbdzrugderxwihdu
kowuvucacyqtfcdqwvhgct
jnvtutbzbxpsebcpvugfbs
imustsayawordaboutfear <--
hltrsrzxzvnqczantsedzq
gksqrqywyumpbyzmsrdcyp
fjrpqpxvxtloaxylrqcbxo
eiqopowuwsknzwxkqpbawn
dhpnonvtvrjmyvwjpoazvm
cgomnmusuqilxuvionzyul
bfnlmltrtphkwtuhnmyxtk
aemklksqsogjvstgmlxwsj
zdljkjrprnfiursflkwvri
yckijiqoqmehtqrekjvuqh

第16行出现了明文字符串,对应的$K=15$

当然这是针对有意义的文本,可以观察出符合英文文本的特征,在下文维吉尼亚密码中将介绍卡方统计来找出密钥$K$的方法

仿射密码

Affine Cipher

仿射密码和移位密码很像

密码体制


仿射密码体制:


这里的 $a$ 是有要求的,$gcd(a,26)=1$,在 $Z_{26}$内有 $a=1,3,5,7,9,11,15,17,19,21,23,25$

而且必须注意 $a$ 与其乘法逆 $a^{-1}$ 必须存在,其乘法逆定义如下

只有满足这个条件解才是唯一

一个简单实现的脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
tab = 'abcdefghijklmnopqrstuvwxyz'
ctoi = lambda x: tab.index(x)
itoc = lambda x: tab[x]
opposite = {
1: 1,
3: 9,
5: 21,
7: 15,
9: 3,
11: 19,
15: 7,
17: 23,
19: 11,
21: 5,
23: 17,
25: 25
}


def encode(plain, a, b):
code = ''
for i in plain:
code += itoc((a * ctoi(i) + b) % 26)
return code


def decode(code, a, b):
plain = ''
for i in code:
plain += itoc((opposite[a] * (ctoi(i) - b)) % 26)
return plain

分析方法

仿射密码因为其固定的乘法元,比较容易分析,这里用到部分词频分析的知识

首先有一个英文字母频率表

可以看到 E 出现此频率是最大的,接下来是 T,A等

我们把26个字母可以分为五组

1.E的概论大约为0.120

2.T,A,O,I,N,S,H,R等概率在0.06到0.09之间

3.D,L的概率大约为0.04

4.C,U,M,W,F,G,Y,P,B的概率在0.015到0.028之间

5.V,K,J,X,Q,Z的概率小于0.01

最常见的两字母组

th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,ea,ng,as,or,ti,is,et,it,ar,te,se,hi,of

最常见的三字母组

the,ing,and,her,ere,ent,tha,nth,was,eth,for,dth

接下来就要对密码文本进行分析,可以使用在线工具,这里写了一个简单的脚本

1
2
3
4
5
6
7
8
str = ''
result = {}
for i in str:
result[i] = str.count(i)
result = sorted(result.items(), key=lambda d: d[1], reverse=True)
for i in result:
fmt = '{} {:0>2d} {:.3f}'
print(fmt.format(i[0], i[1], i[1] / len(str)))

可以给出str字符串中每个字符出现的频率

假如我们分析此仿射密码

1
FMXVEDKAPHFERBNDKRXRSREEMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH

首先分析其词频

R 08 0.140
D 07 0.123
E 06 0.105
K 05 0.088
H 05 0.088
V 04 0.070
F 03 0.053
S 03 0.053
M 02 0.035
X 02 0.035
A 02 0.035
P 02 0.035
U 02 0.035
L 02 0.035
B 01 0.018
N 01 0.018
O 01 0.018
Y 01 0.018

首先我们可以猜测R是e的加密,D是t的加密,从而得到下面的方程组

在 $Z_{26}$ 上有唯一解 $a\ =\ 6,b\ =\ 19$ ,可惜不满足 $gcd(a,16)=1$,这个解释是不正确的,再继续猜测,当R是e的加密,K是t的加密的时候,解得$a=3,b=5$,满足了$gcd(a)=1$,接着得继续判断在$K=(3,5)$的情况下是否得到正确的解

algorithmsarequitegenerrldefinitionsofarithmeticprocesses

显然可以

仿射密码的分析方法简单来说,就是通过密文出现的字符频率去猜测密钥的值,然后验证猜测的密钥值是否正确,在密钥空间不大的情况下,这显然是可解的

同时我们也可以尝试爆破$(a,b)$的值来得到密文,$a$的取值为上面提到的$1,3,5,···,25$中的一个,而$b$的取值是$0\to25$,遍历所有的组合,一共有311个(剔除了$a=1,b=0$),那么如何抉择解密出来的文本哪一个才是我们想要的,这里就需要判断每个解密文本的“适应性”

适应性特征描述了一个文本与英语的相似程度,它通过分析某些字母组合的频率来确定这个文本是否是一个有效的文本

这里使用来自Practical Cryptography的脚本来分析适应性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
'''
Allows scoring of text using n-gram probabilities
17/07/12
'''
from math import log10

class ngram_score(object):
def __init__(self,ngramfile,sep=' '):
''' load a file containing ngrams and counts, calculate log probabilities '''
self.ngrams = {}
for line in file(ngramfile):
key,count = line.split(sep)
self.ngrams[key] = int(count)
self.L = len(key)
self.N = sum(self.ngrams.itervalues())
#calculate log probabilities
for key in self.ngrams.keys():
self.ngrams[key] = log10(float(self.ngrams[key])/self.N)
self.floor = log10(0.01/self.N)

def score(self,text):
''' compute the score of text '''
score = 0
ngrams = self.ngrams.__getitem__
for i in xrange(len(text)-self.L+1):
if text[i:i+self.L] in self.ngrams: score += ngrams(text[i:i+self.L])
else: score += self.floor
return score

相应的攻击脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# this code cracks the affine cipher
import re
from ngram_score import ngram_score
fitness = ngram_score('quadgrams.txt') # load our quadgram statistics
from pycipher import Affine

def break_affine(ctext):
# make sure ciphertext has all spacing/punc removed and is uppercase
ctext = re.sub('[^A-Z]','',ctext.upper())
# try all posiible keys, return the one with the highest fitness
scores = []
for i in [1,3,5,7,9,11,15,17,19,21,23,25]:
scores.extend([(fitness.score(Affine(i,j).decipher(ctext)),(i,j)) for j in range(0,25)])
return max(scores)

# example ciphertext
ctext = 'FMXVEDKAPHFERBNDKRXRSREEMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH'
max_key = break_affine(ctext)

print 'best candidate with key (a,b) = '+str(max_key[1])+':'
print Affine(max_key[1][0],max_key[1][1]).decipher(ctext)

可以看到结果

1
2
3
➜  Crypto python break_affine.py
best candidate with key (a,b) = (3, 5):
ALGORITHMSAREQUITEGENERRLDEFINITIONSOFARITHMETICPROCESSES

代换密码

Substitution Cipher

代换密码实际上是一种单表替换密码,根据一个给定的表,使用特定的字符去替换特定的字符,且不一定存在顺序可言

密码体制


代换密码:


由于这里替换表 $\pi$ 是未知的,且如果想利用密钥穷尽搜索方法来分析的话,密钥空间为 $26!\approx4.03\times10^{26}$ 是一个十分大的数了,时间上难以接受

分析方法

代换密码较之仿射密码,更难破解,因为其变化不是线性的,表是无序的,词频分析仍是最有效的方法

hill-climbing算法可以有效找到正确的密钥,其也是如同上文仿射密码分析中,利用文本适应度来决策一个密钥解密出来的文本是否有效

hill-climbing算法流程如下

  1. 生成一个父密钥,随机的,使用此密钥来解密,并分析此密钥下的文本适应度,存储结果
  2. 略微改变密钥(随机交换两个字符)使用新的密钥来解密,分析文本适应度
  3. 如果新的文本适应度比已存的文本适应度更高,则更新父密钥,更新存储的文本适应度
  4. 重复2步骤,直到在最近的迭代中无法找到更好的密钥

这里不谈算法实现了,我也只是个脚本搬运工,XD

不过需要注意到是,文本适应度是利用文本中的四字组来和参考英文文本来比较的,如果明文构造的比较特殊,那么分析结果可能不是很好,并且当密文长度不足时,分析结果也是大打折扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from pycipher import SimpleSubstitution as SimpleSub
import random
import re
from ngram_score import ngram_score
fitness = ngram_score('quadgrams.txt') # load our quadgram statistics

ctext = 'YIFOFMZRWOFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR'
ctext = re.sub('[^A-Z]', '', ctext.upper())

maxkey = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
maxscore = -99e9
parentscore, parentkey = maxscore, maxkey[:]
print "Substitution Cipher solver, you may have to wait several iterations"
print "for the correct result. Press ctrl+c to exit program."
# keep going until we are killed by the user
i = 0
while 1:
i = i+1
random.shuffle(parentkey)
deciphered = SimpleSub(parentkey).decipher(ctext)
parentscore = fitness.score(deciphered)
count = 0
while count < 1000:
a = random.randint(0, 25)
b = random.randint(0, 25)
child = parentkey[:]
# swap two characters in the child
child[a], child[b] = child[b], child[a]
deciphered = SimpleSub(child).decipher(ctext)
score = fitness.score(deciphered)
# if the child was better, replace the parent with it
if score > parentscore:
parentscore = score
parentkey = child[:]
count = 0
count = count+1
# keep track of best score seen so far
if parentscore > maxscore:
maxscore, maxkey = parentscore, parentkey[:]
print '\nbest score so far:', maxscore, 'on iteration', i
ss = SimpleSub(maxkey)
print ' best key: '+''.join(maxkey)
print ' plaintext: '+ss.decipher(ctext)

有些挺快就能分析出来了

1
2
3
4
5
6
7
8
9
10
Substitution Cipher solver, you may have to wait several iterations
for the correct result. Press ctrl+c to exit program.

best score so far: -900.382755643 on iteration 1
best key: MVNHCIYUJKTFSXWQARDZEGPLOB
plaintext: GFLYLATROYLGBUELASTWEBARTOCASTBUIZKNESSHAICSFLULASTESAPTJEUGLEIAGRCEOIEMTRUNEDTHCANTCTHESRINGGMARKAUGFLTOSGBTBGLTHARTEROCTSTIINTOVEDMARCASDCEALPEDTIANITOFUIGHELOSICTSFR

best score so far: -714.033088457 on iteration 2
best key: CGHWZOTNMKSXVRYELFDJIQUPBA
plaintext: OURFRIENDFROMPARISEXAMINEDHISEMPTYGLASSWITHSURPRISEASIVEJAPORATIONHADTAKENPLACEWHILEHEWASNTLOOKINGIPOUREDSOMEMOREWINEANDHESETTLEDBACKINHISCHAIRVACETILTEDUPTOWARDSTHESUN

维吉尼亚密码

Vigenere Cipher

在前面提到的代换密码中,一旦替换表被确定,同样的字符是会被替换成唯一的字符,也就是单表替换。而维吉尼亚密码却可以让相同的字符被替换成不一样的字符,是一种多表替换密码。

密码体制


维吉尼亚密码体制:


这里与 $m$ 有关,这里的意义为密钥长度,每次使用相同的移位序列去加密m个字符,重复

此处给出一个示例脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
tab = 'abcdefghijklmnopqrstuvwxyz'
ctoi = lambda x: tab.index(x)
itoc = lambda x: tab[x]

def encode(text, key):
ans = ''
j = 0
for i in text.lower():
ans += itoc((ctoi(i) + ctoi(key[j % len(key)])) % 26)
# print(ctoi(i), ctoi(key[j % len(key)]))
j += 1
return ans

def decode(text, key):
ans = ''
j = 0
for i in text.lower():
ans += itoc((ctoi(i) - ctoi(key[j % len(key)])) % 26)
# print(ctoi(i), ctoi(key[j % len(key)]))
j += 1
return ans

分析方法

维吉尼亚密码又被称为”Unbreakable Cipher”,曾被认为是百年内不可破解的,但实际上,当密文足够长,或者使用了较短的密钥,我们还是有办法破解的

维吉尼亚密码分析方法有两个步骤:

确定密钥长度

由于维吉尼亚密码实际上是多组凯撒密码的作用,在密钥长度的重复序列里,对应位置上的字符都是移相同位数的,比如密钥是ASD,则密文中从第一个字符开始,每隔三个字符,都是移动A位。因此我们收集对应位置1,4,7,···,字符序列,就得到了一组由相同移位运算得到的密文,同理收集另外的字符序列,当然这里的周期取决于密钥长度

巧合指数是用来统计字母频率的一种技术

该指数不会被替换影响,简单的替换密码不会修改字母频率。如果文本与英语相似,$I.C.$约为0.06,如果字符分布均匀,则$I.C.$接近0.03-0.04

为了确定密钥的周期,假设密钥长度为2,从密文中提取出1,3,5,7,···和2,4,6,···两个序列,计算序列的$I.C.$值,求均值;同时不断增加密钥长度,求各长度下的$I.C.$均值

简单写了一个脚本分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# encoding:utf-8
code = 'CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBOMQEQERBWRVXUOAKXAOSXXWEAHBWGUMMOMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTULADNGMGPSRELXNJELXVRVPRTULHDNOWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSUIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHROHAEYEVTAOEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE'


def calFrequency(code):
result = {}
for i in code:
result[i] = code.count(i)
return result


def cal_IC(text):
tab = calFrequency(text)
char_sum = 0
for i in tab.keys():
char_sum += tab[i] * (tab[i] - 1)
return char_sum / (len(text) * (len(text) - 1))


def cal_IC_Avg(str_list):
IC_sum = 0
for i in str_list:
IC_sum += cal_IC(i)
return IC_sum / len(str_list)


ans = dict()

# 密钥最大长度这里设为26,实际分析可以大到长度的一半,不过会有倍数问题
for i in range(2, 26):
str_list = list()
for j in range(i):
temp = ''
for k in range(int(len(code) / i)):
temp += code[i * k + j]
str_list.append(temp)
ans[i] = cal_IC_Avg(str_list)

ans = sorted(ans.items(), key=lambda d: d[1], reverse=True)
print(ans)

在结果中可以发现一些比较接近0.06的$I.C.$值对应的长度

1
(25, 0.06666666666666664), (5, 0.06641988365943945), (15, 0.06596491228070175), (10, 0.06516129032258064), (20, 0.05714285714285714), (23, 0.04682274247491638), (3, 0.04636544685088375), (9, 0.04634581105169341), (11, 0.04449254449254449), (6, 0.04399195575666164), (21, 0.043432757718472007), (18, 0.043300653594771234), (2, 0.04317617866004963), (17, 0.04306036139946174), (19, 0.04298245614035088), (13, 0.042363433667781496), (12, 0.0423076923076923), (7, 0.042283298097251586), (8, 0.04183535762483131), (4, 0.041625041625041624), (24, 0.04059829059829059), (22, 0.040459540459540456), (16, 0.03983918128654971), (14, 0.03896103896103897)]

可以发现5的倍数的对应$I.C.$值都很接近0.06,可以考虑密钥为5的倍数

确定正确密钥

假设密钥是5,那么这个密文文本就可以分为五个序列,每一个序列都是一个移位密码,我们只需分别求出对应序列的移位密钥$K_i$,由于这是从文本中抽出的字符序列,没有英文逻辑,直接采用移位密码分析的爆破算法无法直接观察出密钥的正确性,还需要加入卡方统计来判断

意思是爆破$K_i$并将结果的频率分布与每个密钥的英文频率分布进行比较,正确的密钥应具有最小的卡方统计量(理论上,实际应该考虑最小的几个)

简单实现了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from string import ascii_letters
ctoi = lambda x: ascii_letters.index(x)
itoc = lambda x: ascii_letters[x]
stand = {'e': 0.1311, 't': 0.1047, 'a': 0.0815, 'o': 0.08, 'n': 0.0710, 'r': 0.0683, 'i': 0.0635, 's': 0.0610, 'h': 0.0526, 'd': 0.0379, 'l': 0.0339, 'f': 0.0292, 'c': 0.0276,
'm': 0.0254, 'u': 0.0246, 'g': 0.0199, 'y': 0.0198, 'p': 0.0198, 'w': 0.0154, 'b': 0.0144, 'v': 0.0092, 'k': 0.0042, 'x': 0.0017, 'j': 0.0013, 'q': 0.0012, 'z': 0.008}


def shift(text, n):
plain = ''
for i in range(len(text)):
y = ctoi(text[i])
x = itoc((y - n) % 26)
plain += x
return plain

def cal_kri_squa(text):
text = text.lower()
result = {}
kri_squa = 0
for i in text:
result[i] = text.count(i)
for i in result.keys():
E=stand[i]*len(text)
kri_squa += (result[i] - E) ** 2 / E
return kri_squa

code='EMTXBHMRXXXBMGXXLKMGXAGLLPHTGTHFLBKKRGXHBTLMXGWHVBEAAXHKZLWWGF'

for i in range(26):
plain = shift(code, i)
print (i, plain[0:20], int(cal_kri_squa(plain)))

可以发现当前密钥是19

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(0, 'emtxbhmrxxxbmgxxlkmg', 1058)
(1, 'dlswaglqwwwalfwwkjlf', 520)
(2, 'ckrvzfkpvvvzkevvjike', 747)
(3, 'bjquyejouuuyjduuihjd', 663)
(4, 'aiptxdintttxictthgic', 278)
(5, 'zhoswchmssswhbssgfhb', 133)
(6, 'ygnrvbglrrrvgarrfega', 232)
(7, 'xfmquafkqqqufzqqedfz', 1486)
(8, 'welptzejpppteyppdcey', 251)
(9, 'vdkosydiooosdxoocbdx', 571)
(10, 'ucjnrxchnnnrcwnnbacw', 723)
(11, 'tbimqwbgmmmqbvmmazbv', 532)
(12, 'sahlpvaflllpaullzyau', 227)
(13, 'rzgkouzekkkoztkkyxzt', 702)
(14, 'qyfjntydjjjnysjjxwys', 1631)
(15, 'pxeimsxciiimxriiwvxr', 352)
(16, 'owdhlrwbhhhlwqhhvuwq', 783)
(17, 'nvcgkqvagggkvpggutvp', 819)
(18, 'mubfjpuzfffjuofftsuo', 394)
(19, 'ltaeiotyeeeitneesrtn', 5) <----
(20, 'kszdhnsxdddhsmddrqsm', 327)
(21, 'jrycgmrwcccgrlccqprl', 634)
(22, 'iqxbflqvbbbfqkbbpoqk', 829)
(23, 'hpwaekpuaaaepjaaonpj', 764)
(24, 'govzdjotzzzdoizznmoi', 664)
(25, 'fnuycinsyyycnhyymlnh', 193)

那么针对维吉尼亚密码解密,密钥长度确定了,就把密文分割成几个序列,再对每个序列进行密钥分析,得到每个序列对应的密钥,即可得到完整密钥,继而恢复明文

比如上面我们分析得到密钥长度大概是5的倍数,从5开始,分割密文得到

1
2
3
4
5
CVABWEBQBUAWWORWWXANTBDPXXRDWBFAXCWMNJJFAIACNRNCATBWKDMCDCQQXW
HOEITESEWOOEGMFTIFUDSTNSNVTNDPASNHESBGSEGEMRDRSHEAIEORTHNHOANO
RARANOBQRASAUNVRAPTCXUGRJRUOTHLVGRLUHNGYNQRRGINRYOPVEEBRVRHIRI
EHAXXPOEVKXHMKGZKSEMMLMEEVLWYXJBLZEIWMLPRJVELMROEEEKWMHTRCPIMI
EMTXBHMRXXXBMGXXLKMGXAGLLPHTGTHFLBKKRGXHBTLMXGWHVBEAAXHKZLWWGF

对每一个序列进行密钥分析得到密钥

9,0,13,4,19 (janet)

使用此密钥对密文解码得到明文

1
thealmondtreewasintentativeblossokthedayswerelongeroftenendinghitfmagnificenteveningsofcorrugatedpinkskiesthhhuntingseasonwasoverwithhounbsandgunsputawayforsixmonthsthevineyardsherebusyagainasthewellorganizedfarmerstreatedtheirvinesandthekorelackabaisicalneighborshurriedtodothepruningtheyshouldhavedoneinnovember

在《密码学原理与实践》一书中确定密钥的方法是用到类似重合指数的方法,对于每个可能的密钥$K_i$,利用如下指标进行判断

期望值是$M_g\approx0.065$,这里就不写脚本分析了

希尔密码

Hill Cipher

希尔密码也是一种多表替换密码,主要利用了线性代数中矩阵乘法的知识,只不过是$Z_{26}$下的,例如

可以用如下的矩阵式代表

以上运算都是在$Z_{26}$下进行的,密钥$K$一般取一个$m \times m$的矩阵,$y=xK$

从上面的加密变换可以看出,密文是通过对明文做线性变换得到的,下面考虑解密过程,也就是使用加密矩阵的逆矩阵进行解密 $x=yK^{-1}$,这就涉及到矩阵求逆的知识了。

这里也类似于仿射密码中的$a$值一样有要求,矩阵$K$在$Z_{26}$下可逆,即要求$gcd(det(K),26)=1$

矩阵求逆的方法,也有很多,这里不列举了

密码体制


希尔密码密码体制:


分析方法

希尔密码唯密文攻击是非常困难的,但是如果我们知道部分明文和密文的对应关系,则很容易通过线性方程组的形式解出加密矩阵

假设密钥$K$是$m\times m$的矩阵,那么我们至少需要m个明文密文对

假设明文是 friday,利用$m=2$的密钥$K$进行希尔加密,得到密文为 pqcfku

于是我们有以下方程

利用前两组,可以得到矩阵方程

则尝试求密钥$K$

可以使用剩余的方程进行检验

如果密钥$K$的$m$值未知,可以爆破$m$值,即从1,2,······进行尝试,从而找到正确的$m$值

置换密码

Permutation Cipher

前面提到的几种加密方式,都是实现了字符与字符的映射,明文字符被不同的密文字符替换,而置换密码与之不同,加密后字符并没有改变,只是利用置换打乱了字母的排序,也就是乱序的一个过程

置换是一个双射函数$\pi:X \to X$,满足双射函数的要求,因此有逆置换$\pi^{-1}:X \to X$,使得 $\pi^{-1}(x)=x^,当且仅当\pi(x^,)=x$ 成立

密码体制


置换密码体制:


给出一个简单的例子,假设置换与逆置换如下

加密明文为

shesellsseashellsbytheseashore

分为6个一组

shesel lsseas hellsb ythese ashore

置换得

eeslsh salses lshble hsyeet hraeos

于是最终密文为

eeslshsalseslshblehsyeethraeos

实际上置换密码是希尔密码的一种,只不过加密矩阵为每行每列只有一个1,其他都是0的矩阵,即有单位矩阵进行行列变换得来的矩阵

分析方法

由于希尔密码可以看作密钥$K$由单位矩阵进行行列变换得到的矩阵,所以也可以使用希尔密码中的分析方法来进行密码分析

流密码

Stream Cipher

上述提到的所有加密方式,都有一个固定的密钥$K$,这种类型的密码叫做分组密码(Block Cipher),而流密码与之不同,它有一个密钥流$z=z_1z2···$,然后利用这个密钥流来加密明文

最简单的流密码是其密钥流直接通过初始密钥使用某种特定算法运算得来,密钥流与明文流是独立的,这种流密码也叫做同步流密码,例如维吉尼亚密码中的密钥在模运算下不断重复,以此来对明文进行移位,密钥流形如这个样子

这种也叫周期流密码,在一定长度内重复,当流密码以二元字符来表示时,可以看作是模2的运算,这也方便计算机硬件实现,一个例子如下

这里每一个$z_i$都由m个值共同决定,当然要避免产生的密钥流都是0,这样密文和明文就是一致的了

这种密钥流的产生可以使用线性反馈移位寄存器(LFSR)以硬件的方式来实现

另外一种密钥流产生会与明文或密文相关,称为异步流密码,他会使用已有的明文或者密文来参与密钥的产生,自动密钥密码来源于维吉尼亚密码,其使用明文来构造密码流


自动密钥密码体制:

参考

  1. 《密码学原理与实践》

  2. http://practicalcryptography.com/

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×