“不可破译”的密码
密码在当今社会生活中的作用可以说十分巨大,除了众所周知的军事国防方面的应用外,现代金融、贸易、生产等无不在大规模使用密码.计算机网络的广泛应用,使人们对密码的依赖达到了新的高度,在千百万台计算机联结成的因特网上,用户的识别基本上是靠密码.密码被破译就会产生危及安全的极严重的后果.计算机“黑客”的作为,即为密码破译的一例,连美国国防部的计算机都未能幸免,可见密码编制的难度了.
由大整数因数分解的困难,人们研制成功一种“不可破译”的密码:RSA体制密码(见本刊2000年第6期《大整数的因数分解问题》一文).RSA密码是一种公开密钥密码,说它“不可破译”是形容破译之难,不过的确至今尚没找到破译的理论工具.
一般密码编制理论中,称要传递的原文为“明文”,经加密后实际传递的是密码构成的“密文”,收信方则将其解密,恢复为明文使其可理解,就完成了通信任务.这其中加密和解密要用通信双方约定的方法,这一方法就称为密钥.更一般地,人们首先给定一个加密算法,不太严格地说,可把这一算法视为函数,函数的值就是密钥,而解密算法可以说是加密算法的一个反函数,使用同一个密钥(原函数的值)可将密文惟一地译成明文.
密码的关键就在于通信双方约定密钥而不被外界所知,外界对密码的破译也就指向密钥了.而且为了防止外界可能的破译,就应尽力使外人不可能积累在同一密钥下的许多密文,否则可用统计分析法等确定出密钥,世界战争史、外交史上有许多破译成功的例子.这样就经常变换密钥,重要的通信要每天一换甚至通一次信换一次.
这么频繁换的密钥怎样送给对方?如果随其他信息(用无线电或网络)易于失密,每次派专人送又不可能,怎样解决这一问题呢?这就是RSA密码的长处了,它把密钥分成加密钥和解密钥.如A和B通信,A把加密钥公开送达B(可用明码电报或与上次通信同时),不怕外人知道,所以叫公开密钥,而解密钥留在自己处不送达B,B收到公开密钥后,用它加密要给A的信息,然后送回A(这也无须特别秘密),则A可用手中的解密密钥解密.
外人没有解密密钥,就无从破译密码了,那么加密钥和解密钥就没有关系了吗?当然不是,否则就无法解密了.不过这种关系正是建立在大整数因数分解困难的基础上.换句话说,由公开密钥得出解密钥要进行一个充分大的整数的因数分解,你无法分解也就无法破译.
具体的编码过程是,先找出两个不同的大素数p和q,再给定一个数r(一般是用计算机产生一个随机数或至少一个伪随机数,也可每次一换),使r与数(p-1)(p-1)互素,这三个数p、q、r就是解密密钥.
再求一个数m,使(rm-1)能被(p-1)(q-1)整除.严格表述为:求m,使
rm≡1(mod(p-1)(q-1)).
由于r与(p-1)(q-1)互素,所以m是一定可求出来的(有数论定理保证).再求出数n=pq.m、n为加密密钥,即公开密钥.
具体的加密方法为,设明文为x,可把x视为(或变为)一个大整数,设x<n,若x≥n,则将x表示为s进位的形式(s≤n,常用s=2t形式)的数,使其每一个数位上的数都小于n,再分数位进行编码.求一个数y(0≤y<n)使
y≡xm(modn)(可理解为,使(y-xm)能被n整除),y就是用m、n密钥加密后的密文.
解密过程为,求
z=yr(modn)(0≤z<n),
在限定的条件(0≤y<n,0≤z<n)下有(可严格证明)
δ=x,
即得出明文.
外人要想破译密码,就必须由m、n求出数r来.
由此可见,要找到r必须由n得出p和q,即对n进行因数分解,如p、q取得相当大,即n相当大,由于分解困难,无法破译这一密码.
由于运用现代计算机已可分解100位左右数的因数,因此n要取得相当大,从而p、q也要取得相当大,比如每个数80位以上,再求积,这在技术上是可能的.
是否还应考虑相应计算的复杂性和计算所需要的时间呢?当然有这方面的问题,现在通常用复合编码法解决,即用其他计算比较简单、耗时少的编码方法编码,而每次编码所采用的密钥用RSA密码来传递,这既加强了安全性,又加快了速度.
