疯狂的ENIGMA，难以破解的密码系统

疯狂的ENIGMA，难以破解的密码系统

 ENIGMA，二战的一代名机，古典密码的巅峰之作。但它早已是昨日黄花。当年，那位布莱奇利庄园六号棚屋的负责人，亲自参与了破译ENIGMA并直接改进了Bombe的威尔士曼，应该是最有资格对ENIGMA的错误做个评价的了；而他，是这样说的：
        德国人的错误……从头至尾，完全不是ENIGMA密码机的理论错误，而是机器操作程序、报文处理程序、无线电发送程序的弱点。总之，由一点失误演变成所有程序上的错误。
    威尔士曼还说了一句话，更加意味深长：  ENIGMA密码机，就其本身而言，如果被正确使用，将会是坚不可摧的。
   " '坚不可摧'的ENIGMA密码体制，最终还是遭到惨败"。错了，遭到惨败的是ENIGMA密码机，而不是ENIGMA的密码体制。

ENIGMA密码机最终被破译，技术上的原因是，当时只使用了3个转轮，而这3个轮早已泄入敌手。而充当密钥的是三个轮的排列、初始位置和插线板。这都是比较容易搞到或猜到的。更重要的是，不管加密的途径如何曲折，最终结果是一个二维表：C=T(M,pos);这里，M是明文字符，pos是字符在电文的位置，C是密文字符。T是表函数。序列周期长度17576，这个表函数只有26×17576大小，像今天的数独游戏（图灵的破译机是否在解这个数独游戏？），填满这个表，这个密钥就算破解了。

ENIGMA密码体制至今仍在被使用，早期的UNIX的makekey加密软件就是ENIGMA，vi -x 产生的密文也是ENIGMA，一些软件注册机也是ENIGMA。但这个ENIGMA已经与当年那个ENIGMA密码机有很大不同。它只有一个编码转轮，256个点位。反射板也有256个点位，可以转，所以也称反射轮（还有一个编码轮的逆轮）。它的序列周期是64K，比ENIGMA密码机大。它的表函数有256×64K，比ENIGMA密码机大了不少。最重要的，是密码轮和反射轮是根据密钥生成的，它们的组合理论上最多可以有256！×255×253×251××××3那么多，这可是个天文数字，远远比现代密码学的宠儿DES之类的64bit，128bit大得多得多，如果想蛮力攻击转轮是不可能的，这是ENIGMA体制的根本安全性所在。但是这个软件ENIGMA在学术上仍被认为是不安全的，原因何在？

原因之一是转轮生成的环节只使用了56bit的fast crypt，加上salt最终也只有70bit，它远远没有发挥ENIGMA的能力。我们可以改进转轮发生器，使之达到152bit以上并非难事。其二就是那个表函数，还是不够大。如果我们能够扰乱转轮的运转，使之失去周期性，最终完全破坏表函数，这样无疑ENIGMA将成为史上最安全的密码体制。

这里是原始的ENIGMA转轮机程序：

#define ROTORSZ 256

#define MASK 255

typedef char ENIGMA[3][ROTORSZ];//事先由密钥生成了这个转轮。

void enigma(ENIGMA t,char *string,int len)

{

register int i, n1, n2,k=0;

char *t1,*t2,*t3;

t1=t[0];

t2=t[1];

t3=t[2];

        n1 = 0; //初始位置是固定的

        n2 = 0;

        for(k=0;k

                i=string[k];

         i = t2[(t3[(t1[(i+n1)&MASK]+n2)&MASK]-n2)&MASK]-n1;

                string[k]=i;

                n1++;

                if(n1==ROTORSZ) {

                        n1 = 0;

                        n2++;

                        if(n2==ROTORSZ) n2 = 0;

                }

        }

}

可以看出，转轮的初始位置是固定的，每次转一步也很规律，这直接导致系统有明显的周期性，从而存在一个256×64K的表。t1是编码轮，t3是反射轮，t2是t1的逆，用于反查t1。这个方案的设计很英明，更多的编码轮并不增加安全性，只能增加运行时间。
   现在来改进这个程序，首先让n1,n2两个轮的初值与消息长度len和t相关，每次旋转的步距（旋转因子）也与len和t相关；

void enigma1(ENIGMA t,char *string,int len)

{

register char *p;

register int  n1,n2, k, x;      //x旋转因子

char *t1,*t2,*t3;

        if(!t || !string || len <= 0) return;

        t1=t[0];

        t2=t[1];

        t3=t[2];

//初始位置和旋转因子与len和T有关，不知道T就不知道它们，也无法通过明文、密文的关系推断T。

        n2=t[len&1][(len>>9)&MASK]&MASK;

        n1=t3[(len>>1)&MASK]&MASK;

        x=((t3[((len>>17)+n1)&MASK]&3)<<1)+1;   //x=1,3,5,7

        p=string;

        for(k=0;k

                *p = t2[(t3[(t1[(*p+n1)&MASK]+n2)&MASK]-n2)&MASK]-n1;

                ++p;

                n1 += x;

                if (n1 >= ROTORSZ) {

                        n1 &= MASK;

                        if(++n2==ROTORSZ) n2 = 0;

                }

        }

}

结果，原来的二维表变成了三维表C=T(M,pos,len)，对于每一个消息长度都有一个二维表，这大大增加了破译难度。它的序列周期仍为64K。enigma1的运行结果：

Input：aaaaa

enigma1 encode:FB CF 49 53 15 

enigma1 decode: aaaaa

Input：aaaaaa

enigma1 encode:51 4F ED E4 26 C8 

enigma1 decode:aaaaaa

为了彻底消除序列周期，对上述程序做进一步的改进，它的旋转步距由明文字符决定，转轮疯狂旋转——疯狂的ENIGMA。这里，每一个字符都是其后所有字符的子密钥：

void frenz_encode(ENIGMA t,char *string,int len)

{

register char *p;

register int x,n1;       //x旋转因子

char *t1,*t2,*t3;

int  n2, k;

        if(!t || !string || len <= 0) return;

        t1=t[0];

        t2=t[1];

        t3=t[2];

        

        n2=t[len&1][(len>>9)&MASK]&MASK;

        n1=t3[(len>>1)&MASK]&MASK;

        

        p=string;

        for(k=0;k

                x=t3[(*p+k)&MASK];//旋转步距，解码时与下一句对调位置。

                *p = t2[(t3[(t1[(*p+n1)&MASK]+n2)&MASK]-n2)&MASK]-n1;

                ++p;

                n1 += x;

                if(n1<0) {

                        n1&=MASK;

                        continue;

                }

                if (n1 >= ROTORSZ) {

                        n1 &= MASK;

                        if(++n2==ROTORSZ) n2 = 0;

        }

}

至此，ENIGMA的周期性完全被打破，表函数也完全不存在了。它成了无限序列。理论上，一个无限序列的密码系统是不可破解的。这就是说，如果一个密钥只使用1次，它就是安全的。如果使用多次，比如，如果有两个相似的明文，它们只差1个bit，在密文中这个差别被扩散到那个差别字符之后的所有字符。这个表现是与3DES差不多的，当然3DES要影响到一个密文组及其以后的密文组。差别字符没有影响到它前边的密文，看来这是一个缺陷。需要对其进一步的改进，ENIGMA2：

1.对明文进行frenz_encode变换。

2.对一次密文反序；

3.用一字符异或下一字符，从头到尾。

4.对扰乱后的密文再次用enigma1加密。

最后的密文已经能够达到：明文只要改变1bit，密文满盘皆改。想从密文对照明文获取转轮内容已经极其困难，几乎是不可能的了。请看如下测试结果：

明文1：aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

enigma1加密1：

E0 DC F9 7E 2C BC 9C 51 BB EC 4F EE 8A 99 1E DF 4A 6F B1 35 91 4B 96 AC CA 65 07 A9 2B 68 EA 86  

frenz_enigma加密1：

E0 15 90 23 40 81 6F E5 BD E3 55 47 9F 45 01 B9 2C 9A BA CA 7D 7C 57 86 E6 74 CA 10 C1 49 3D 52

Engima2加密1：

31 F5 F6 D6 9F AC 11 64 D3 DF F9 52 68 20 8B 59 39 33 34 74 C3 51 CF 5A 88 2C 2B EC 8F CD 02 8B 

明文2：aaaaaaaaaaaaaaacaaaaaaaaaaaaaaaa 与明文1只差1bit。

enigma1加密2：

E0 DC F9 7E 2C BC 9C 51 BB EC 4F EE 8A 99 1E DF D6 6F B1 35 91 4B 96 AC CA 65 07 A9 2B 68 EA 86

frenz_enigma加密2：

E0 15 90 23 40 81 6F E5 BD E3 55 47 9F 45 01 B9 F7 BE 08 B6 1F CB 82 44 5D 53 CF 85 4A 15 4D 6E  

engima2加密2：

09 52 6F 51 ED 28 18 1A BA 95 8C 6F BD 25 35 C6 A2 E0 A5 39 9D 4D C6 03 6E 29 89 79 49 D4 EF 14

可以看到，enigma1只有1个字节不同，franz_enigma有一半相同。enigma2则完全不同。enigma1的周期长度为64K，enigma2和frenz_enigma没有周期。

速度测试，enigma1的耗费为1个时间单位，frenz_enigma为2, enigma2为4 , DES_ede3_cbcm_encrypt是27, DES_xcbc_encrypt（这个不是3DES）是7。而这两个DES的密文表现与frenz_enigma差不多，如果明文改变一个bit，密文前半部分是不变的。在1.6G主频的机器上，enigma1的加密速度为5mS/MByte,这样的速度能够胜任音视频流的加密。

如果在网络通信过程使用ENIGMA，建议每次连接都变更密钥。如果广域的私有网，建议使用enigma1，如果在公网，有vpn的信道加密，frenz_enigma也够用了。如果在无线网，移动通信使用，应该使用enigma2。

由于一般的密码分析术是针对3DES这类分组密钥，内部是异或运算的密码体制。这样的分析术对ENIGMA是无效的。但愿密码学界能对这个ENIGMA算法的安全性作出分析和评估。根据前面分析，破译转轮是复杂问题，破译密钥的难度提高到152比特以上，密文与明文没有对应关系，密文和明文与密钥也没有关系，因此，在找到破解方法之前，它是安全的。假如原来的系统使用3DES，现在增加一层ENIGMA，开销增加不多，就足以使你的对手陷入无限的迷茫中。

ENIGMA的使用也是非常便捷，操作过程也没有特殊要求，程序如下：

#include 

Func(char *buf,int len)

{

ENIGMA t;

enigma1_init(t,"key string");

enigma1(t,buf,len); //加密。

..........

enigma1(t,buf,len); //解密

...........

frenz_encode(t,buf,len);

..........

frenz_decode(t,buf,len);

...........

}

相比3DES，非常简洁。

从转轮的生成和使用评估ENIGMA的安全性

转轮生成程序：

/* 生成密码轮 */

#define RAN_LEN 17

void enigma1_init(ENIGMA t,char *pw)

{

int ic, i, k, temp;

int random,seed;

char *buf,buf1[RAN_LEN+1];

char    *t1,*t2,*t3,salt[3];

int len;

int32_t crc,*ip;

char *h;

int hlen;

        if(!t || !pw || !*pw) return;

        t1=t[0];

        t2=t[1];

        t3=t[2];

        len=strlen(pw);

        crc=(int32_t)ssh_crc32((const unsigned char *)pw,len);//open ssh里的。

        ip=(int *)buf1;

        *ip=htonl(crc);//CRC在不同系统上具有相同的值，作为随机串的使用，必须保证在所有系统上相同的字节次序

        seed=0xFFFF&gencrc((unsigned char *)pw,len);//CCITT-CRC16，你也可以用别的CRC16

        salt[0]=seed&127;

        if(!salt[0]) salt[0]=0X41;

        seed >>= 7;

        salt[1]=seed&127;

        if(!salt[1]) salt[1]=0X41;

        salt[2]=0;

        if(seed==0) seed=pw[len-1];

// 设置ic，初始化的自旋

        ic=len;

        for(i=0;i

        ic &= 127;

        ic|=(seed & 128);

        if(len>13) {

                hlen=13;

                h=pw+len-13;

        } else {

                hlen=len;

                h=pw;

        }

/* 你可以在buf1里添加任何散列数据  如MD5等 */

        buf=des_fcrypt(pw,salt,buf1+sizeof(int32_t));

        for (i=0; i<13; i++) {

//随机串由原来的6-7bit提升到8bit，并与密钥的最后13位直接相关

                buf[i] = (buf[i] << 1) ^ h[i % hlen];

                seed = seed*buf[i] + i;

        }

// ic，初始化的自旋

        for(i=0;i

                t1[i] = (i+ic) & MASK;

                t3[i] = 0;

        }

        for(i=0;i开始制造转轮

                seed = len*seed + buf1[i%RAN_LEN];//这里用到长度啦！

                random = (seed&0X7FFFFFFF) % 65529;     //random(key);

// 以上生成尽可能随机的random，你有充分的自由度选择你的算法

/* 生成主编码轮 t1 */

                k = ROTORSZ-1 - i;

                ic = random % (k+1);

                temp = t1[k];

                t1[k] = t1[ic];

                t1[ic] = temp;

/************************************************************************

 * 生成反射板 反射板只要不重不漏的把各点两两连接起来?

 ************************************************************************/

                if(t3[k]!=0) continue;

                ic = (random>>8) % k;

                while(t3[ic]!=0) ic = (ic+1) % k;

                t3[k] = ic;

                t3[ic] = k;

        }

/* t2为t1的逆 */

        for(i=0;i

                t2[t1[i]&MASK] = i;

}

算法分析：生成转轮利用了密钥的CRC16、CRC32、fast crypt，采集到144bit的伪随机串，利用8bit校验和设定转轮的初态，并利用密钥长度信息生成转轮（有感于王小云破解MD5，她的破解是要改变消息长度的）。可能的转轮数量超过了2^152,即超过152bit的安全性，这是内在的本源安全性。外在的密钥安全性：密钥长度不受限制，不存在弱密钥，如果说弱密钥，就是不要使用人们容易猜测的字串。建议的密钥长度不短于21字节。因为前8字节被直接用于fcrypt，后13字节直接用于随机值修正，其余字节都通过CRC参与转轮。每个字节都可以是1-255的值，尾0结束。不建议用汉字，因为不同系统字符集可能有不同解释。但可以使用如下形式的密钥串："\003\217\045\316\xFB\t\x07\n\b\r\077"。这样就达到168bit，与3DES同级别，而且不限长的密钥更难攻击。

程序中有很多涉及散列的代码和作用点，都是可以变更的，所有的变更都将产生独一无二的密钥系列，所有的系列都是互不兼容的，这给ENIGMA预留了巨大的安全储备空间。

由于构建转轮采用了大量不可逆的散列算法，因此从转轮反推密钥是不可能的，由于明文与密文间的关系只与转轮有关，与密钥无关，这就意味着，从明文与密文间的关系推导密钥是不可能的。在改进的ENIGMA，疯狂的ENIGMA和加强的ENIGMA中，转轮的转动受到被加密/解密信息的严重干扰，导致从密文与明文间的关系推断转轮是极其困难的，可以说是几乎不可能的，因此，在找到这几乎不可能的方法之前，ENIGMA是安全的。