分类:
2010-01-28 16:53:06
疯狂的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是安全的。
chinaunix网友2010-02-03 11:52:10
有的系统设计多达8个转轮,本人认为这并不能提高安全性。它只提高了序列周期,绝大多数通信过程没有那么大消息长度,只要破解前N字节的常用字符就可以满足大多数需要。另外,一个转轮可以保证任何明文字符加密后都不是自己,多于一个的转轮就没这个保证了。