通信学报990416.htm

用des算法加密文件的小程序

size=3>C(s1)＝C(s)+A(s0)，　A(s1)＝A(s)－A(s0)。</FONT></P>
      <P align=right><FONT size=3>(2)</FONT></P>
      <P align=left><FONT 
      size=3>　　上述编码过程可以用一把不等距刻度尺来描述，该刻度尺在0，p(0｜s)和1处分别标上了刻度0.0，0.1和1.0。每个刻度之间又按类似的比例关系标上更精细的刻度，这个过程可以重复多次，直到所需精度已经标出，如图1所示。</FONT></P></TD></TR></TBODY></TABLE>
<P align=center><IMG alt="93-1.gif (2983 bytes)" height=79 
src="通信学报990416.files/93-1.gif" width=366></P>
<TABLE border=0 width="90%">
  <TBODY>
  <TR>
    <TD>
      <P align=center><FONT size=3>图1　算术编码所使用的刻度尺</FONT></P>
      <P align=left><FONT 
      size=3>　　当算术编码使用上述标尺进行工作时，只需简单地把二进制串s转化成二进制小数0.s，然后找出标尺上带有刻度0.s的那个点，该点在正常标尺下的值就是C(s).譬如二进制串为10111，则其编码区间就是位于图1中0.10111和0.11000之间的那个区间。</FONT></P>
      <P align=left><FONT size=4><STRONG>3　算术加密</STRONG></FONT></P>
      <P align=left><FONT 
      size=3>　　数据加密是一个由明文，密文，密钥，加密算法和解密算法组成的五元组。一个加密算法是否安全，取决于两个方面：其一是在不知密钥的情况下，已知密文很难得到明文；其二是已知密文和相应的明文很难导出密钥。<BR>　　假设二进制串s的位表示为s(0)s(1)…s(μ)，引进记号P<SUB>j</SUB>＝P(0｜s(0) 
      s(1)…s(j))，表示公式(1)和(2)中使用的概率，其中j＝0，1，…，μ。我们在文[7]中构造并证明了</FONT></P>
      <P align=center><IMG alt="94-1.gif (1112 bytes)" height=43 
      src="通信学报990416.files/94-1.gif" width=275></P>
      <P align=right><FONT size=3>(3)</FONT></P>
      <P align=left><FONT 
      size=3>　　不难发现，如果不知道P<SUB>j</SUB>，则从C(s)中解出s是不可能的。因此如果把P<SUB>j</SUB>作为密钥，则C(s)就可以做为s的密文。由此得到如下的加密算法：<BR>　　算法A：加密<BR>　　1)　初始化：c＝0，a＝1，输入P<SUB>0</SUB>，P<SUB>1</SUB>，…，P<SUB>u</SUB>。<BR>　　2)　编码符号：对j＝0到μ，执行<BR>　　<SUP><STRONG>.</STRONG></SUP> 
      如果s(j)＝0，a＝a×P<SUB>j</SUB>；否则a＝a×(1－P<SUB>j</SUB>)，c＝c+aP<SUB>j</SUB>,a=a(1-P<SUB>j</SUB>)。<BR>　　3)　结束：输出c。<BR>　　利用算法A进行数据加密，有一点必须注意，即当P<SUB>j</SUB>＝0.5，j＝1，2，…，u时，将导致c＝0.s，从而失去了对原始数据的屏蔽作用。因此p的各分量最好不要选得太均匀。<BR>　　相应于加密算法A，我们可以方便地给出解密算法。为此，假设算法A使用密钥p产生的密文为c,s表示算法A中的二进制串。则程序列表如下：<BR>　　算法B：解密<BR>　　1)　初始化：输入密文c和P<SUB>0</SUB>,P<SUB>1</SUB>,…，Pu。<BR>　　2)　解码符号：对j＝0到u，执行<BR>　　<SUP><STRONG>.</STRONG></SUP>　如果c＜P<SUB>j</SUB>,s(j)＝0，c＝c/P<SUB>j</SUB>；否则s(j)＝1,c＝(c－P<SUB>j</SUB>)/(1－P<SUB>j</SUB>)。<BR>　　3)结束：输出s。<BR>　　上述加解密算法看似简单，但仍有许多问题需要解决。首先，算法基于实精度运算，它在有限精度的计算机上很难实现。其次，密钥的长度和实数表达根本无法记忆，必须采用合适的转换形式。另外，P选择的不合理可能导致非常庞大的密码，对于存储和传输都是不利的。这些问题的解决我们将留在下节讨论。</FONT></P>
      <P align=left><FONT size=4><STRONG>4　具体实现</STRONG></FONT></P>
      <P align=left><FONT 
      size=3>　　上节所遇到的问题可以结合数据压缩原理来解决。事实上如果把P选作二进制串的模型概率，则算法A和B正是所谓的纯算术编码，因此可以有效地对二进制串进行压缩，但限制了密钥空间。另一方面，如果P的选取偏离模型概率太大，虽能加大密钥的选取力度，但无法进行压缩。这似乎是个矛盾，特别对固定模型。但该问题有一个非常好的解决方案，那就是采用自适应模型，因为该模型的概率(频率计数)是在编码过程中建立起来的，初始概率对压缩效率的影响甚微。于是，我们可以利用密钥控制初始概率的办法，达到既加密又压缩的目的。<BR>　　实际执行可以利用有限精度技术来解决，这种技术已经被很多作者讨论过。其出发点是利用整数运算代替实数运算。按照这种处理技术，概率表达为频率计数相除的形式。同时，使用两个长度为t的寄存器C和A分别存储算法A中c和a的有效比特位。另外，引进一个长度为m的寄存器z。记载最近处理过的m个比特位。假设s是当前已经编码过的二进制串，自适应模型所使用的概率由P[z]/(P[z]+Q[z])和Q[z]/(P[z]+Q[z])给出，其中P[z]和Q[z]分别表示s中，在z状态下，0和1的个数。<BR>　　为了算法描述方便，我们使用了C语言中的运算符，譬如符号～、｜和<IMG 
      alt="95-1.gif (104 bytes)" height=11 src="通信学报990416.files/95-1.gif" 
      width=14>＝分别表示二进制求反、或和左移位运算。借此，加密算法描述如下：假设待加密的二进制串为s(0)s(1)…s(u)，密钥的二进制表示为k(0)k(1)…k(v)。<BR>　　算法C：加密<BR>　　1.C＝0，A＝2<SUP>t－1</SUP>，z＝0。对j＝0，1，…，2<SUP>m</SUP>－1，P[j]＝Q[j]＝1。<BR>　　2.对j＝0，1，2，…，u作<BR>　　　<SUP><STRONG>.</STRONG></SUP>　如果j＜v执行：若k(j)＝0，P[z]++；否则Q[z]++；<BR>　　　<SUP><STRONG>.</STRONG></SUP>　T＝R*P[z]/(P[z]+Q[z])。<BR>　　　<SUP><STRONG>.</STRONG></SUP>　如果s(j)＝0，则P[z]++，A＝T；否则Q[z]++，A－＝T，C+＝T。<BR>　　　<SUP><STRONG>.</STRONG></SUP>　z<IMG 
      alt="95-1.gif (104 bytes)" height=11 src="通信学报990416.files/95-1.gif" 
      width=14>＝1，z｜＝s(j)<BR>　　3.若A＜2<SUP>t－1</SUP>，循环执行<BR>　　　<SUP><STRONG>.</STRONG></SUP>　输出C最左端的一个比特位。<BR>　　　<SUP><STRONG>.</STRONG></SUP>　C<IMG 
      alt="95-1.gif (104 bytes)" height=11 src="通信学报990416.files/95-1.gif" 
      width=14>＝1，A<IMG alt="95-1.gif (104 bytes)" height=11 
      src="通信学报990416.files/95-1.gif" 
      width=14>＝1.<BR>　　　<SUP><STRONG>.</STRONG></SUP>　若C＞～A，则C＝～A+1.<BR>　　4.输出C的t个比特位.<BR>　　算法C中寄存器z，C和A的长度要有所限制。z的长度m一般大于16，z越长需要的统计缓冲越大，相应的压缩效率也越高。C和A的长度t需要根据计算T所使用的寄存器长度来决定，一般取为16。相应的解密算法与加密算法类似，但需要一个额外的寄存器V来存储待解密的密文，其长度与寄存器C相同。其程序列表如下：<BR>　　算法D：解密<BR>　　1.C＝0，A＝2<SUP>t－1</SUP>，z＝0，对j＝0，1，…，2<SUP>m</SUP>－1，P[j]＝Q[j]＝1。V＝密文中前t个比特。<BR>　　2.对j＝0，1，…，u作<BR>　　　<SUP><STRONG>.</STRONG></SUP>　如果j＜v执行：若k(j)＝0，P[z]++；否则Q[z]++<BR>　　　<SUP><STRONG>.</STRONG></SUP>　T＝R<SUP>*</SUP>P[z]/(P[z]+Q[z])。<BR>　　　<SUP><STRONG>.</STRONG></SUP>　如果T＜V，则s(j)＝0，P[z]++，A＝T；否则s(j)＝1，Q[z]++，A－＝T，C+＝T，V－＝T。<BR>　　　<SUP><STRONG>.</STRONG></SUP>　z<IMG 
      alt="95-1.gif (104 bytes)" height=11 src="通信学报990416.files/95-1.gif" 
      width=14>＝1，z｜＝s(j)。<BR>　　3.若A＜2<SUP>t－1</SUP>，循环执行<BR>　　　<SUP><STRONG>.</STRONG></SUP>　C<IMG 
      alt="95-1.gif (104 bytes)" height=11 src="通信学报990416.files/95-1.gif" 
      width=14>＝1，A<IMG alt="95-1.gif (104 bytes)" height=11 
      src="通信学报990416.files/95-1.gif" width=14>＝1，V<IMG 
      alt="95-1.gif (104 bytes)" height=11 src="通信学报990416.files/95-1.gif" 
      width=14>＝1。<BR>　　　<SUP><STRONG>.</STRONG></SUP>　V｜＝密文中的下一个比特。<BR>　　　<SUP><STRONG>.</STRONG></SUP>　若C＞～A，则C＝～A+1。<BR>　　算法D中没有最后的清理步，其参数的各种限制和取法必须与算法C一致，否则解不出正确的明文.但从上述算法不难发现，明文的长度在加密时必须保存，以便通知解密器。</FONT></P>
      <P align=left><FONT size=4><STRONG>5　如何提高加密安全性</STRONG></FONT></P>
      <P align=left><FONT 
      size=3>　　注意到算法C中对应于公式(3)中的P<SUB>j</SUB>是由P[j]，Q[j]和k(j)来控制的，如果把这些参量代入公式(3)可得到关于k(j)的u次多项。该方程的0-1问题无已知的多项式算法，因此，如果已知s(明文)和C(s)(密文)得到k是计算困难的。但该多项式的变元和次数是u，如果u太小就很难防止枚举求解(3)的可能性。这说明对于短明文，加密数据的安全性不能无限提高。<BR>　　解决这两个问题的办法很简单，只要我们使用一个随机数发生器就可以办到。具体地说，给定任意长的密钥k(0)k(1)…k(v)和二进制串s＝s(0)s(1)…s(u).使用随机数发生器产生一个与密钥同样长的随机二进制串x＝x(0)x(1)…x(v)。然后利用算法C加密组合二进制串xs，其输出作为s的密文。解密由此产生的密文，需要把首先解出的v个比特位扔掉，即扔掉随机串x，随之解出的串才是真正有用的二进制串s。自然加密者不需要知道随机串x的内容。<BR>　　上述处理过程，初看起来似乎是多余的，甚至会增加密码长度，但它确实增加了加密数据的安全性。首先，无论对于多长的密钥，所有的密钥位都会产生对概率的影响，不再依赖于加密数据的长度。其次，即使攻击者同时获取了密文和明文，也无法通过边解密边比较的办法找出密钥。因为首先解出的是随机串x中的位，只有完全正确地解出x才能得到s中的位。但x是随机的，它随加密环境的不同而改变；除了加密者(如果他想这样作的话)，其它人不可能同时获得密文，明文和x。因此这种加密预处理技术是相当安全的。<BR>　　对于算法C和算法D，我们用C编译器在PC机上作过了实验。使用640k统计内存(对应z是16位)对于10k以上长度的文本文件，得到的密文是明文的一半左右。若使用16M统计内存，可以把明文压缩掉60％以上。实验还表明，使用128位密钥对压缩效率几乎没有影响，而算法的最大有效密钥可达到64kbit。<BR>　　以下我们结论性地给出本文算法的优点：(1)本文算法的代码是可公开的；(2)本文算法不限密钥长；(3)本文算法的密文通常是明文的一半；(4)本文算法对信道误码敏感，因此可抵抗插入攻击；(5)本文算法的密文可随加密环境的不同而改变；也就是说，对于同样的二进制串和密钥，本次加密和上次加密的密文完全不一样。<BR>　　最后我们指出，本文算法的速度还无法与DES(美国数据加密标准)匹敌，但本文算法的其他性能指标都比DES好得多。<BR>　　鸣谢：本文谨献给王德人先生，祝他早日康复。在本文的写作过程中，得到了复旦大学专用集成电路与系统实验室章倩玲和张国权老师的帮助，作者在此深表感谢。</FONT></P>
      <P align=left><FONT size=3>*　复旦大学专用集成电路与系统国家重点实验室资助项目</FONT></P>
      <P align=left><FONT size=3>作者单位：赵风光(朗讯科技贝尔实验室　上海 
      200030)<BR>　　　　　倪兴芳(上海交通大学　上海 200030)<BR>　　　　　姜峰(复旦大学　上海 
200433)</FONT></P>
      <P align=left><FONT size=3><STRONG>参考文献</STRONG></FONT></P>
      <P align=left><FONT size=3>　[1]　Rubin F.Arithmetic stream coding using 
      fixed precision registers.IEEE Trans Inf Theory,1979 
      IT-25(6)<BR>　[2]　Witten I H,Neal R M,Cleary J G.Arithmetic coding for data 
      compression.Commun ACM,1987,30(6)<BR>　[3]　Langdon G G,Rissanen J J.A 
      simple general binary source code.IEEE Trans Inf 
      Theory,1982,IT-28(5)<BR>　[4]　Rissanen J J,Mohiuddin K M.A 
      multiplication-free multi-alphabet arithmetic code.IEEE Trans 
      Commun,1989,37(2)<BR>　[5]　Lei S M. Efficient multiplication-free 
      arithmetic codes.IEEE Trans Commun,1995,43(12)<BR>　[6]　Howard P G,Vitter J 
      S.Arithmetic coding for data compression.Proc IEEE,1994,82(6)<BR>　[7]　Zhao 
      F G,Jiang E X,Ni X F.On the specific expression of bit-level arithmetic 
      coding.Numerical Mathematics,A Journal of Chinese 
      Universities.1998(7)2<BR>　[8]　赵风光.位元压缩加密方法与器件.发明专利公报，1997，13(14)</FONT></P>
      <P align=right><FONT 
  size=3>(1997-07-18收到，1999-01-20改定)</FONT></P></TD></TR></TBODY></TABLE></BODY></HTML>