<font color="blue">射虎培训班——第三周</font> - 辕门射虎


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

发表于 2005-3-24 11:57 资料文集短消息看全部作者

射虎培训班——第三周

第一部分《密码学》第二课总第三课

单字母替换密码

原创：金圭子
（关键字解释：明文:没加密过的要传递的原文。密文:经过加密的用于传递的文字）

上期（http://www.xycq.net/forum/index.php?showtopic=47744上次恺撒密码的题目可还没人做哦！）所讲的恺撒密码在今天看来已经是非常简单了，因为其中唯一不确定的就是增减的位数罢了。你只要从1到25都试一次，肯定能猜到答案了。其实在当时被使用的原因也是当时人普遍文化程度不高，很多人甚至不认识字，怎么点小小的谜团已经可以糊弄人了。

而在今天这种密码早就不足以使用了。我自己就编写过一段程序来尝试25种变幻，而且其实你只要有纸笔和5分钟就可以发现增减数字，而再花10到20分钟（视密文长短而定）就可以破译全文了。所以这种密码现在仅仅用于“就是让你破译出来”的情况下了吧（比如柯南迷之间发贺卡，哈哈）
而今天介绍的是与恺撒密码类似但是却复杂的多的：单字母替换密码
这个也是和恺撒密码一样是单个字母替换的。但只需重排密码表上二十六个字母的顺序，密钥就会增加到四千亿亿亿多种，那么就能有效的防止敌人用筛选的方法检验所有的密钥，如：
明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
密码表 Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
明文 F O R E S T
密文 Y G K T L Z

甚至可以自己定义一个密码字母图形而不采用拉丁字母。
以前在欧洲的石工中就采用过利用简单的符号花纹来代替26个字母的密文，看过福尔摩斯探案集中《跳舞的人》的读者应该记忆也比较深刻吧，还有就是柯南里面也出现过，用太阳月亮等等来代替日语的五十音。但是用这种方法所得到的密文还是相当容易被破解的，主要原因是往往这样的符号比较有规律（比如柯南的就非常有规律），当然也因为这种密码方式往往看重的不是密码的难破译性，而是密码的隐蔽性（比如在柯南的故事里面用来做信纸的边框花纹，又比如石工更堂而皇之的把密码刻在墙壁上永垂不朽）

单字母替换的加密方式还是被持续使用几个世纪，直到阿拉伯人发明了密码破解术......
至迟在公元九世纪，阿拉伯的密码破译专家就已经娴熟地掌握了用统计字母出现频率的方法来击破简单替换密码。破解的原理很简单：在每种拼音文字语言中，每个字母出现的频率并不相同，比如说在英语中，e出现的次数就要大大高于其他字母。所以如果取得了足够多的密文，通过统计每个字母出现的频率，我们就可以猜出密码中的一个字母对应于明码中哪个字母（当然还要通过揣摩上下文等基本密码破译手段）。比如柯南·道尔在他著名的福尔摩斯探案集中《跳舞的人》里就详细叙述了福尔摩斯使用频率统计法破译跳舞人形密码的过程。

除了概率法以外，如果文中保留了明文的空格（这种情况非常多，因为如果把英文的空格去掉，密密麻麻的排列，而可能能分出几种意思来吧），那还可以根据比较短的字母来判断，比如在英文中，单个字母的单词就只有：a和i，如果看到密文中出现，基本上就可以确定了（如果这个频率高一般就是a，频率低一点的一般就是i）。而两个字母的单词有（括号中为比较常用的简称）：
an as at(ad am ax)
be
(co)
do
go(gm)
he hi
if in is it(id)
(kg km)
my me(mg mm)
no
of (oh) ok on or ox
(pm)
to
us(um uh un)
(xo)

其实这种情况在比较短（千字母以内）或者在没有计算机帮助的情况下比概率法的效果还要大的多啊^_^（可以看下面和习题）

让我们具体看看这两种方法是怎么起作用的：
下面先说说各字母在英语文章中出现的频率
（百分比）
A:8.2 N:6.7
B:1.5 O:7.5
C:2.8 P:1.9
D:4.3 Q:0.1
E:12.7 R:6.0
F:2.2 S:6.3
G:2.0 T:9.1
H:6.1 U:2.8
I:7.0 V:1.0
J:0.2 W:2.4
K:0.8 X:0.2
L:4.0 Y:2.0
M:2.4 Z:0.1
当然，这只是个概数，不会与每篇文章的字母出现频率完全一样，通常越短的信
息的字母频率与上面的相比就越不相符，越短的信息也就越难破解了。如：
John,a jazzist,will go to Japan in June to join a jazz party.
其中，J的百分比是12.8，而E的百分比是0，对其进行频率分析就毫无意义。
又如：UOCT XH.若
明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
密码表 Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
则它被翻译为GIVE UP.
但若
明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
密码表 Q W U E T R Y I X P A S C H O M D F G J K L Z V B N
则它被翻译为COME IN.
究竟那个是真的，不得而知。但当它放进一篇文章里，就可从前后推知它应怎样
翻译了。

让我们来看一篇比较长的文章中，单字母替换密码是怎么被频率法破解的。（现实运用中，大密文的情况还是比较多的）
再来看看下面的密文：
......YSZX E NATRXZR GZEXM EDY LT 1640 CNZ NZER YB CNZ KEMOZXSLUUZ
BEHLUG FEM MLX NADY KEMOZXSLUUZ NZ FEM E FLUR ETR ZSLU HET NZ FEM PXAZU
ETR ZTVYGZR NATCLTD WZYWUZ MLX NADY BZUU LT UYSZ FLCN CNZ READNCZX YB
E BEXHZX FNY FEM E TZLDNKYAX YB NLM CNZ GYATD FYHET FEM EBXELR YB CNZ
ZSLU NADY ETR ESYLRZR NLH YTZ REG NADY NZEXR CNEC NZX BECNZX ETR
KXYCNZXM FZXZ EFEG NZ OTZF CNEC MNZ FYAUR KZ EUYTZ MY NZ XYRZ CY CNZ
BEXH FLCN BLSZ YX MLI YB NLM ZSLU BXLZTRM CNZG HERZ CNZ DLXU DY KEPO CY
KEMOZXSLUUZ NEUU FLCN CNZH ETR UYPOZR NZX LT E XYYH AWMCELXM CNZT CNZG
MEC RYFT LT CNZ DXZEC RLTLTD NEUU CY RXLTO EM AMAEU CNZG RXETO KYCCUZ
EBCZX KYCCUZ ETR MYYT CNZG KZDET CY MLTD ETR UEADN ETR MNYAC ZSLU
FYXRM......（约550个字母）
先对它进行频率分析（出现次数/百分比）
A:16/2.9 N:46/8.4
B:14/2.5 O: 8/1.5
C:38/6.9 P: 3/0.5
D:16/2.9 Q: 0/0.0
E:54/9.8 R:29/5.3
F:17/3.1 S:11/2.0
G:10/1.8 T:35/6.4
H: 9/1.6 U:29/5.3
I: 1/0.2 V: 1/0.2
J: 0/0.0 W: 3/0.5
K:10/1.8 X:34/6.2
L:34/6.2 Y:41/7.5
M:27/4.9 Z:65/11.8
可发现E，Z出现的频率很高，那么我们可假设Z＝E，E＝A或Z＝A，E＝E。看看原来的文章，其中E以单字母单词出现，那么基本上Z＝E，E＝A。
（还有些辨别E和A的方法，如一般文章中EE出现的频率比AA高）
再来看看，CNZ，ETR作为三字母单词出现多次，那么他们有可能分别是THE和AND。那么C＝T，N＝H，T＝N，R＝D。再说，文章中C，N，T，R出现的频率分别是：
6.9，8.4，6.4，5.3，除了C有一点偏差以外，其余的和标准频率都差不多，不妨继续下去。
又看看，文章中出现过LT 1640。若T＝N的话，L就应该是I了，原文中LT CNZ就是IN THE了，上面的推理应该无误。
又看文中，出现了CNZ NZER YB CNZ KEMOZXSLUUZ，YB也出现过几次，而我们知道CNZ＝THE，那么这是不是THE XXXX OF THE XXXXXXXXXXX呢，YB＝OF？Y，B出现的频率是7.5，2.5，标准频率中O，F出现的频率是7.5，2.2，好像是吧？而后面出现过几个CY，就是TO了，英文中TO出现的频率也颇高，就又证实了自己的推理。

当我们解密的时候，除了大胆假设，还要不时运用其他证据来证实自己的推理，否则很容易到了最后才发现自己的错误，那又要花大量时间重头做起了。

现在找找和Y有关的单词，可发现文中有一个MY，有可能是NO和SO，假设是NO，那与后面的NZ（HE）就组成NO HE，好像不大通顺，如果是SO HE就比较通顺了，M应该就是S了。接着，由NLH和HET推出H＝M，又推出FYHET和FNY中F＝W，从1640知道文章使用过去时态，那么FEM代表WAS应是正确的。
现在概括一下：
明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
密码表 E R Z B N L H T Y M C F

将其代入原文，得：
......oSeX a hAndXed GeaXs aDo in 1640 the head of the KasOeXSiUUe
famiUG was siX hADo KasOeXSiUUe he was a wiUd and eSiU man he was PXAeU
and enVoGed hAntinD WeoWUe siX hADo feUU in UoSe with the daADhteX of
a faXmeX who was a neiDhKoAX of his the GoAnD woman was afXaid of the
eSiU hADo and aSoided him one daG hADo heaXd that heX fatheX and
KXotheXs weXe awaG he Onew that she woAUd Ke aUone so he Xode to the
faXm with fiSe oX siI of his eSiU fXiends theG made the DiXU Do KaPO to
KasOeXSiUUe haUU with them and UoPOed heX in a Xoom AWstaiXs then theG
sat down in the DXeat dininD haUU to dXinO as AsAaU theG dXanO KottUe
afteX KottUe and soon theG KeDan to sinD and UaADh and shoAt eSiU
woXds......（小写的是替换后的，大家可不看后面自己推推）

那就好看多了，文中有句......that heX BatheX and KXotheXs weXe......，可推出X＝R，又由oSeX a hAndXed GeaXs aDo等提示可推出A＝U，S＝V，G＝Y，D＝G。注意到文中有单词haUU，查字典易知符合条件的只有HALL，所以U＝L。
又有fiSe oX siI，即five or siI，那么I＝X。由......the DiXU Do KaPO to......推出K＝B。由......he Onew that......推出O＝K。由.....enVoGed hAntinD WeoWUe......推出V＝J，W＝P。由......he was PXAeU.....和结合上下文可知P＝C。那么就有：

明码表 A B C D E F G H I J K L M N O P R S T U V W X Y
密码表 E K P R Z B D N L V O U H T Y W X M C A S F I G
最后整篇文章就出来了：
......Over a hundred years ago,in 1640,the head of the Baskerville
family was Sir Hugo Baskerville.He was a wild and evil man he was cruel
and enjoyed hunting people.Sir Hugo fell in love with the daughter of a
farmer who was a neighbour of his.The young woman was afraid of the
evil Hugo,and avoided him.One day,Hugo heard that her father and
brothers were away.He knew that she would be alone.So he rode to the
farm with five or six of his evil friends.They made the girl go back to
Baskerville Hall with them and locked her in a room upstairs.Then they
sat down in the great dining hall to drink.As usual they drank bottle
after bottle and soon they began to sing and laugh and shout evil
words......
总结一下吧，解单字母替换密码，首先要进行频率分析，确认几个频率较高和较低的几个字母，再根据英文本身的特点进行分析，并寻找一定的证据证明自己的结论，假设的同时要和标准频率对照一下，特别要注意上下文的连贯性，那就可以了。大家不妨拿后面的题目做一下，稍难但出得不错哦。

课后题目：

单表替换：
（提示：留意重复出现的连续多个字母，如I L D I。这种方法在解维尔纳斯密码
时很有用哦～～～）
下面再说说一些常用技巧：
1.辨认出E后，能轻易的标出H，因为H常常出现在E前，却很少位于其后；
2.Q的后面多是U；
3.当一个单词知道其中大部分字母后，不妨查查英文字典（当然，很懂E文的就不
用了～～～），如果字典里只有一个单词符合条件时，就会很快的知道其他字母。
上面的只是抛砖引玉，希望大家有什么好方法也告诉一下～～～
解密或许是个沉闷的过程，但当你找到解法后，又会很兴奋，大家ENJOY一下吧！

课后习题：
1.MQPUOZ WOLN DNLWZOUVNG MWFNPND EMQE EMN YXATWSY YEWWG HWD SNEENDY QOG
MQPUOZ QIISUNG EMN DCSNY FMULM ZCUGN CY UO QSS HWDAY WH YNLDNE FDUEUOZY
EMN YWSCEUWO FQY NQYX NOWCZM EMN HUDYE ANYYQZN YCTAUEENG EW AN FQY YW
YMWDE EMQE UE FQY UAIWYYUTSN HWD AN EW GW AWDN EMQO EW YQX FUEM YWAN
LWOHUGNOLN EMQE EMN YXATWS WH EMN YEULBAQO FUEM TWEM QDAY NKENOGNG CI
UO EMN QUD YEWWG HWD N QY XWC QDN QFQDN N UY EMN AWYE LWAAWO SNEEND UO
EMN NOZSUYM QSIMQTNE QOG UE IDNGWAUOQENY EW YW AQDBNG QO NKENOE EMQE
NPNO UO Q YMWDE YNOENOLN WON FWCSG NKINLE EW HUOG UE AWYE WHENO WCE WH
HUHENNO YXATWSY UO EMN HUDYE ANYYQZN HWCD FNDN EMN YQAN YW UE FQY
DNQYWOQTSN EW YNE EMUY GWFO QY N UE UY EDCN EMQE UO YWAN LQYNY EMN
HUZCDN FQY TNQDUOZ Q HSQZ QOG UO YWAN LQYNY OWE TCE UE FQY IDWTQTSN
HDWA EMN FQX UO FMULM EMN HSQZY FNDN GUYEDUTCENG EMQE EMNX FNDN CYNG EW
TDNQB EMN YNOENOLN CI UOEW FWDGY U QLLNIENG EMUY QY Q MXIWEMNYUY QOG
OWENG EMQE N FQY DNIDNYNOENG TX EMN YEULBAQO FUEM TWEM QDAY NKENOGNG CI
UO EMN QUD
2.U B H X P P R A I L A F X K A E L U F L U L D G A A N V C D U M A K R
D U K L X C M A R H X P E U C C B U M K I L D I U I R U M V C H M A D M
R F X M A L A O A D I X M F A U E D R F X M G U M F A K I L D I U I E D
R D M U M G U I D I U X M E L U F L L A E X P C K M X I O A B P R A R U
M F A L A F X P C K M A G A O U M D Y U M A I L D I U I F X P C K F X M
A B O X M D M H X M A W P I I L A C D K H D M K R X M H K A D O E D I R
X M E A L D G A A M K A K W H I P O M U M Y I L A K D M F U M Y M A M I
X Y X X K E L A M I L A H L D G A R X X B I A M W A A M I L A D Y A M I
R X B A G U C D M K U I L U M S I L D I U L D G A B P C B U C C A K M H
V O X M U R A X B Y U G U M Y H X P R X M A I L U M Y P M P R P D C B X
O H X P O M X I A W X X S I L O A A B X O I H U R X P O I O D U M D M K
U B D M F H E A R L X P C K W A W D F S U M W D S A O R I O A A I B X O
K U M M A O

3.来追忆一下有名的电影吧（提示：为什么要用大小写的字母呢？）：

ULC GSOV SX ULC OKDZ RMI XKZLUKDZ MZMKDIU ULC FMUOKE SD UKUMDKB.

b-dtf voss dttz zit rqvf gy zit rtqr zvtfzn-touiz rqnl qyztk.

IAKVCOFMD UMHCI AMOU KD NMUUGC OSWMGC MDV VCBKVCI US HKGG NKGG.

lxhtkdqf ygxfr ygkktlz uxdh of dgxsof kgxut.

MAASGGS ULKOUCCD RKGG UMHC M CYOSUOKA ULC VMW MXUCO USFSOOSR.

cqf itslofu vql yofrofu ftdg of lgsqkol.

ILOCH XSYDV M AKMDKIU KD ULC KBC MZC.

这些题目都有点点难度，大家如果一次作不出，可以试着写出过程，我们一起来分析才是上课哟！
其中1、2题我没有自己做过，只有答案。可第3题我当时可是自己一个人用了3、4个小时就做出来的哦^_^

听了这么多课，有没有跃跃欲试自己也想写个密码呢？有时候把你想说的话，用密码写下，让对方绞尽脑汁但是终能想到，也能带来欣慰的笑容吧^_^

[广告] 《精忠报国岳飞传完整版》火热发布


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

发表于 2005-3-24 12:43 资料文集短消息看全部作者

QUOTE:

原帖由叶落秋寒于2005-03-24, 12:09:44发表
解密的程序我写过，不过像密码学的这么多知识，着实不太懂的说。

我只准备出三期题目了，因为之后的双表替换、转子的那种、甚至md5的那种多对一等等都不是凡人可以通过纸笔可以算出的。甚至用计算机也要算老久。不适合出题。

当然如果大家感兴趣我可以写一点。

另外让大家猜一个吧：我既然说“三期”，大家觉得我下一期可能会出什么密码？？请详细描述一下（因为我不很了解这种密码的标准称呼）。
我就以私人名义悬赏500给第一个猜到的吧（限期2周）

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

发表于 2005-3-25 09:25 资料文集短消息看全部作者

QUOTE:

原帖由叶落秋寒于2005-03-24, 19:01:48发表
RSA密码
用户选两个大素数 p,q 计算 n=p*q;
用户再选整数e 满足 gcd(e,(p-1)(q-1)=1, 然后计算整数d 使得ed=1 mod((p-1)(q-1))
公开密钥： e,n; 保密密钥： p,q,d
加密：c=m**e(mod n) 解密：c**d=m(mod n)

我觉得这个很难出题目………………

[广告] 《精忠报国岳飞传完整版》火热发布


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

发表于 2005-3-29 11:19 资料文集短消息看全部作者

QUOTE:

原帖由han6于2005-03-29, 9:38:03发表
挑两个刺：

26的阶乘是四百亿亿亿，不是四千亿亿亿。

QUOTE:

John,a jazzist,will go to Japan in June to join a jazz party.
其中，J的百分比是12.8，而E的百分比是0，对其进行频率分析就毫无意义。

在June这个单词中，e不是出现了一次么，怎么能说百分比是0。

作业
1.
明码表 Q T L G N H Z M U B S A O W I D Y E C P F K X V
密码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

having once recognized however that the symbols stood for letters and having applied the rules which guide us in all forms of secret writings the solution was easy enough the first message submitted to me was so short that it was impossible for me to do more than to say with some confidence that the symbol of the stickman with both arms extended up in the air stood for e as you are aware e is the most common letter in the english alphabet and it predominates to so marked an extent that even in a short sentence one would expect to find it most often out of fifteen symbols in the first message four were the same so it was reasonable to set this down as e it is true that in some cases the figure was bearing a flag and in some cases not but it was probable from the way in which the flags were distributed that they were used to break the sentence up into words i accepted this as a hypothesis and noted that e was represented by the stickman with both arms extended up in the air

耶…………神仙啊！！！
你太神奇了………………

不但题目全对，而且认认真真的看完还挑了两个刺…………

而且还会在字体里面选择Fixedsys……赞叹啊………………

不过……好像我觉得“明码表”应该是明文的表，而“密码表”应该是密文的表吧？？
那既然明文是having，密文是MQPUOZ，就应该是明码表是A...，密码表是Q...啊？？你是不是反了？？

[广告] 《精忠报国岳飞传完整版》火热发布


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

发表于 2005-3-31 10:10 资料文集短消息看全部作者

没什么啦，也是你先提出多个我的错误么^_^

[广告] 《精忠报国岳飞传完整版》火热发布