当前位置: 代码迷 >> C语言 >> 破解凯撒密码
  详细解决方案

破解凯撒密码

热度:1135   发布时间:2007-07-31 02:53:03.0
破解凯撒密码

[凯撒介绍]

凯撒密码(caeser)是罗马扩张时期朱利斯•凯撒(Julius Caesar)创造的,用于加密通过信使传递的作战命令。它将字母表中的字母移动一定位置而实现加密。


[加密原理]

凯撒密码的加密算法极其简单。其加密过程如下:
在这里,我们做此约定:明文记为m,密文记为c,加密变换记为E(k1,m)(其中k1为密钥),解密变换记为D(k2,m)(k2为解密密钥)(在这里k1=k2,不妨记为k)。凯撒密码的加密过程可记为如下一个变换:
c≡m+k mod n (其中n为基本字符个数)
同样,解密过程可表示为:
m≡c+k mod n (其中n为基本字符个数)
对于计算机而言,n可取256或128,m、k、c均为一个8bit的二进制数。显然,这种加密算法极不安全,即使采用穷举法,最多也只要255次即可破译。当然,究其本身而言,仍然是一个单表置换,因此,频率分析法对其仍是有效的。


[加密算法]

我们预定义基本字符个数为 #define MAX 128
凯撒加密函数可以表示为

char encipher(char plain_char, int key)
{
return (plain_char + key) % MAX;
};

凯撒解密函数:

char decipher(char cipher_char, int key)
{
return (cipher_char - key + MAX) % MAX;
};

加密后,原所有的ASCII码偏移key位,解密则移回key位。
如果要对一个文本文件进行加密,则只要依次逐个字符逐个字符地读取文本文件,进行加密后,逐个字符逐个字符写入密文文本文件中,即可:

FILE *fp_plaintext;
FILE *fp_ciphertext;
char plain_char;
... ...
while((plain_char=fgetc(fp_plaintext))!=EOF)
{
fputc(encipher(plain_char,key),fp_ciphertext);
}

对文件的解密也同样方法。


[破解原理]

一篇包含字符的英文文章,其各ASCII码字符出现,都有一定的频率,下面是对Google上随意搜索到的英文文章进行分析的结果,见表:

QUOTE:
=================================================
FileName : 01.txt

[1] 32: times:204
[2] 101:e times:134
[3] 116:t times:91
[4] 105:i times:87
[5] 111:o times:77
[6] 108:l times:75
[7] 97:a times:75
[8] 110:n times:69
[9] 10:
times:67
[10] 115:s times:63

=================================================
FileName : php.si.source.txt

[1] 32: times:576
[2] 101:e times:162
[3] 115:s times:153
[4] 110:n times:141
[5] 114:r times:138
[6] 105:i times:135
[7] 10:
times:134
[8] 116:t times:129
[9] 42:* times:116
[10] 111:o times:103

=================================================
FileName : work.txt

[1] 32: times:51322
[2] 101:e times:30657
[3] 116:t times:23685
[4] 97:a times:19038
[5] 111:o times:17886
[6] 105:i times:16156
[7] 110:n times:15633
[8] 114:r times:15317
[9] 115:s times:15226
[10] 104:h times:12191

=================================================
FileName : 02.txt

[1] 32: times:299
[2] 101:e times:217
[3] 110:n times:136
[4] 105:i times:133
[5] 111:o times:124
[6] 116:t times:116
[7] 97:a times:110
[8] 115:s times:98
[9] 114:r times:92
[10] 108:l times:82

=================================================
FileName : 03.txt

[1] 45:- times:404
[2] 32: times:394
[3] 101:e times:237
[4] 116:t times:196
[5] 114:r times:173
[6] 97:a times:163
[7] 105:i times:161
[8] 110:n times:153
[9] 111:o times:142
[10] 115:s times:129

=================================================
FileName : 04.txt

[1] 32: times:326
[2] 101:e times:179
[3] 116:t times:106
[4] 105:i times:101
[5] 111:o times:96
[6] 110:n times:94
[7] 97:a times:92
[8] 115:s times:78
[9] 100:d times:61
[10] 114:r times:60

=================================================
FileName : 05.txt

[1] 32: times:441
[2] 101:e times:191
[3] 111:o times:151
[4] 116:t times:120
[5] 97:a times:112
[6] 110:n times:108
[7] 105:i times:91
[8] 114:r times:84
[9] 117:u times:79
[10] 115:s times:79

有此分析可知,一篇英文文章中,出现较高频率的两个字符是 ' ' (空格) 和 'e',而且它们的ASCII码分别是32和101,差值是69。
既然凯撒密码利用的是单表替换的一种简单加密算法,所以,我们的主角, ' ' 和 'e' ,在解密后,依然会保持相同的ASCII码差值,69。

|c1 - c2| = |'e' - ' '| = |101 - 32| = 69
|m1 - m2| = | ((c1 + k) mod 256)-((c2 + k) mod 256)| = |c1 - c2| = |'e' - ' '| = 69

现在可以得到破解凯撒密码的原理了,我们统计一片经过凯撒加密的密文字符信息,在出现频率较高的字符里面寻找差值是69的2个字符,这两个必定是 ' ' 和 'e' 字符的加密字符,计算偏移量(既密钥key),通过解密运算,还原出明文。


[破解算法]

任何一片英文加密后的密文,我们统计出所有字符的个数:

#define MAX 128

... ...

FILE *fp_ciphertext;
char cipher_char;
int i; //密文文件长度,包含多少字符
unsigned int size_file=0; //申明num数组,存储各个ASCII字符在密文中出现的个数
num[MAX];

... ...

for(i = 0;i < MAX; i++) //初始化num数组中的值
num[i] = 0;

... ...

while((cipher_char=fgetc(fp_ciphertext))!=EOF)
{
num[cipher_char]++;
size_file++;
}

统计出现最多次数的字符,定义#define GETTOP 10,统计最多的前10位字符:

//统计前10位
#define GETTOP 10

... ...

int temp,i,j;
int maxascii[GETNUM]; //申明maxascii数组,存储统计出的概率前10位的字符ascii码
int maxtimes[GETNUM]; //申明maxtimes数组,存储统计出的概率前10位的字符的出现次数

... ...

for(i=0;i<GETTOP;i++)
{
temp=0; //临时变量temp里面来存储出现最多次数的字符的ascii码
for(j=1;j<MAX;j++) //依次比较所有的字符次数,获得最多字符的ascii码
{
if(num[j]>=num[temp])
temp=j;
}
maxascii[i]=temp; //把出现最多次数字符的ascii存储到相应的maxascii数组中
maxtimes[i]=num[temp]; //把最多次数字符的出现次数存储到相应的maxtimes数组中
num[temp]=0; //把最多次数字符的次数赋值成0,
//进行循环运算,同样的算法,第二次循环得到的值,肯定是出现第二多的字符
//避免了对256或128个字符进行排序的复杂运算
//当年我用汇编编写成绩排序的程序时,也用这套排序算法:-)

}

找出出现最多字符中,ASCII码差别是69的两个字符,计算出密钥key的长度:

for(i=0;i<GETTOP;i++)
{
for(j=0;j<GETTOP;j++)
{
if((max[i]-max[j])==69)
{
key=(max[j] - 32 + MAX ) % MAX;
printf("Key : %d\n",key);
break;
}
}
}
[程序演示]

原文章是一篇关于 花生壳域名邦定软件 本地溢出漏洞的文章,全部内容为:

QUOTE:
PeanutHull Local Privilege Escalation Vulnerability

by Sowhat

Last Update:2005.09.24

EN: http://secway.org/advisory/AD20050720EN.txt
CN: http://secway.org/advisory/AD20050720CN.txt

CVE:CAN-2005-2382
BID:14330

Product Affected:

PeanutHull <= 3.0.1.0


Overview:

Oray Inc. is the world's biggest DDNS (Dynamic Domain Name Service)
Provider (According to their WEBSITE). PeanutHull is the DDNS client
For more information ,see http://www.oray.net

Details:

The vulnerability is caused due to SYSTEM privileges are not
dropped when accessing the PeanutHull from the System Tray icon.

A local non-privileged user can access the application via the
system tray and can execute commands with Local System privileges.

Exploit:
1. Double click on the PeanutHull icon in the Taskbar to open
the PeanutHull window.
2. Click Help, click BBS
3. Type C:\ in the poped up IE Address BAR
4. Navagate to %WINDIR%\System32\
5. click CMD.exe
6. A new command shell will open with SYSTEM privileges

Exploitng this vulnerability allows local non-privileged user
to obtain SYSTEM privilege.

Vendor Response:

2005.07.13 Vendor notified via email
2005.07.14 Vendor responsed that this problem will be fixed
in the 3.0 Final Version.
2005.07.20 PeanutHull 3.0 Released
2005.07.20 So I released this advisory


Updated:

According to Secunia's verification, the 3.0.1.0 is still vulnerable.
Non-privileged user can invoke the PeanutHull window by sending a SW_SHOW
message.

2005.07.21 new Proof of Concept code released.

Exploit:
http://secway.org/exploit/PeanutHull_Local.rar

Solution:
No workaroud this time.
Plz grant only trusted users access to the affected systems.

现在我们对该文章进行加密,注意,我使用的密钥是17:

QUOTE:
D:\studio\kaiser>kaiser
=======================================================
---- Kaiser Cipher by dorainm dorainm@gmail.com ----
=======================================================
Usage : kaiser -k key [-e|-d] -f PlainText_FileName CipherText_FileName
kaiser -k key [-e|-d] -s PlainText

D:\studio\kaiser>kaiser -k 17 -e -f blog.txt cipher.txt
=======================================================
---- Kaiser Cipher by dorainm dorainm@gmail.com ----
=======================================================

The command completed successfully

加密成功,我们看看密文:

QUOTE:
avr Y }}1] tr}1a zz}vxv1V tr}r z 1g }v rsz}z
s
1d yr ]r 1f ur vKCAAF?AJ?CE V_K1y K@@ vt r
? x@ruz
@RUCAAFAHCAV_? T_K1y K@@ vt r
? x@ruz
@RUCAAFAHCAT_? TgVKTR_>CAAF>CDIC SZUKBEDDA a u t 1Rwwvt vuK avr Y }}1MN1D?A?B?A `v zv K ` r
1Zt?1z 1 yv1 }u8 1szxxv 1UU_d19U
r~zt1U ~rz1_r~v1dv ztv: 1a zuv 19Rtt uzx1 1 yvz 1hVSdZeV:?1avr Y }}1z 1 yv1UU_d1t}zv W 1~ v1zw ~r z 1= vv1y

K@@ ? r
?v 1 Uv rz} K eyv1 }v rsz}z
1z 1tr vu1u v1 1djdeV^1 zz}vxv 1r v1 1 u vu1 yv1rttv zx1 yv1avr Y }}1w ~1 yv1d
v~1e r
1zt ? R1} tr}1 > zz}vxvu1 v 1tr1rttv 1 yv1r }ztr z 1zr1 yv1
v~1 r
1ru1tr1v vt v1t ~~ru 1 z y1] tr}1d
v~1 zz}vxv ? V } z K B?1U s}v1t}zt|1 1 yv1avr Y }}1zt 1z1 yv1er |sr 1 1 v1 111 yv1avr Y }}1 zu ?

C?1T}zt|1Yv} =1t}zt|1SSd D?1e
v1TKm1z1 yv1 vu1 1ZV1Ruu v 1SRc E?1_rrxr v1 16hZ_UZc6md
v~DCm F?1t}zt|1T^U?v v1 G?1R1v 1t ~~ru1 yv}}1 z}}1 v1 z y1djdeV^1 zz}vxv V } z x1 yz 1 }v rsz}z
1r}} 1} tr}1 > zz}vxvu1 v 1 s rz1djdeV^1 zz}vxv? gvu 1cv  vK CAAF?AH?BD1gvu 1 zwzvu1zr1v~rz}1

CAAF?AH?BE1gvu 1 v  vu1 yr 1 yz 1 s}v~1 z}}1sv1wz vu1 11111111111z1 yv1D?A1Wzr}1gv z ? CAAF?AH?CA1avr Y

}}1D?A1cv}vr vu CAAF?AH?CA1d 1Z1 v}vr vu1 yz 1ruz
f ur vuK1 Rtt uzx1 1dvt zr8 1v zwztr z =1 yv1D?A?B?A1z 1 z}}1 }v rs}v? _ > zz}vxvu1 v 1tr1z |v1 yv1avr Y

}}1 zu 1s
1 vuzx1r1dhpdY`h ~v rxv? CAAF?AH?CB11v 1a w1 w1T tv 1t uv1 v}vr vu? V } z K y K@@ vt r
? x@v } z @avr Y }}p] tr}? r d } z K _ 1 |r u1 yz 1 z~v? a}
1x r 1 }
1 vu1 v 1rttv 1 1 yv1rwwvt vu1
v~ ?

现在,我们要对密文进行破解(注意,是破解,不是解密!我们假设这篇密文是我们通过某种渠道获得的,并不知道加密者使用的密钥),运行破解程序brake:

QUOTE:
D:\studio\kaiser>brake
=======================================================
---- Kaiser Braker by dorainm dorainm@gmail.com ----
=======================================================

usage : brake cipher_filename plain_filename


D:\studio\kaiser>brake cipher.txt plain.txt
=======================================================
---- Kaiser Braker by dorainm dorainm@gmail.com ----
=======================================================
[+] Input ciphertext text file : cipher.txt
[+] Open the ciphertext file okay.
[+] Get the size of the ciphertext file : 1687 .
[+] Computing the key of the kaiser is 17 .
[+] Output plaintext text file : plain.txt
[+] create the plaintext text file successfully
[+] All Finished.

The command completed successfully

破解完成,我们可以看到,破解程序计算出,密文长度是1687,密钥是17,然后进行解密,现在看看解密后的文章内容:

QUOTE:
PeanutHull Local Privilege Escalation Vulnerability

by Sowhat

Last Update:2005.09.24

EN: http://secway.org/advisory/AD20050720EN.txt
CN: http://secway.org/advisory/AD20050720CN.txt

CVE:CAN-2005-2382
BID:14330

Product Affected:

PeanutHull <= 3.0.1.0


Overview:

Oray Inc. is the world's biggest DDNS (Dynamic Domain Name Service)
Provider (According to their WEBSITE). PeanutHull is the DDNS client
For more information ,see http://www.oray.net

Details:

The vulnerability is caused due to SYSTEM privileges are not
dropped when accessing the PeanutHull from the System Tray icon.

A local non-privileged user can access the application via the
system tray and can execute commands with Local System privileges.

Exploit:
1. Double click on the PeanutHull icon in the Taskbar to open
the PeanutHull window.
2. Click Help, click BBS
3. Type C:\ in the poped up IE Address BAR
4. Navagate to %WINDIR%\System32\
5. click CMD.exe
6. A new command shell will open with SYSTEM privileges

Exploitng this vulnerability allows local non-privileged user
to obtain SYSTEM privilege.

Vendor Response:

2005.07.13 Vendor notified via email
2005.07.14 Vendor responsed that this problem will be fixed
in the 3.0 Final Version.
2005.07.20 PeanutHull 3.0 Released
2005.07.20 So I released this advisory


Updated:

According to Secunia's verification, the 3.0.1.0 is still vulnerable.
Non-privileged user can invoke the PeanutHull window by sending a SW_SHOW
message.

2005.07.21 new Proof of Concept code released.

Exploit:
http://secway.org/exploit/PeanutHull_Local.rar

Solution:
No workaroud this time.
Plz grant only trusted users access to the affected systems.

密文已经在不知道密钥长度的情况下,被破解、解密成可以正确阅读的明文了,而且与原文完全一致!


[最后小结]

凯撒密码是密码学中,一种最简单的加密算法,本文没有很高的技术含量,介绍了凯撒密码的原理、算法、代码实现,破解凯撒密码

程序的原理、算法、代码实现,以及程序的演示!

dorainm
dorainm@gmail.com



<全文完>


既然得到了密钥长度,算完成了对凯撒密码的破解了,那就进行解密吧,大功告成!

ps: 今天看了一下,凯撒拼写都是错误的,汗...
搜索更多相关的解决方案: 凯撒  密码  破解  

----------------解决方案--------------------------------------------------------
  相关解决方案