资源描述：
《数论在密码学中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第19卷 第1期工 程 数 学 学 报Vol.19No.12002年02月Feb.2002JOURNALOFENGINEERINGMATHEMATICS文章编号:100523085(2002)0120014207X数论在密码学中的应用王国俊(西安交通大学基础科学研究中心,西安710049;陕西师范大学数学研究所,西安710062)摘 要:以背包原理、RSA系统和秘密分享方案为例介绍了数论在现代密码学中的应用。关键词:背包原理;RSA系统;秘密分享分类号:AMS(2000)11T71中图分类号:TN918.1文献标识码:A1 引 言语言是
2、人类表达思想和进行交流的基本手段。人们在讲话、写文章或者通信时通常总希望能把自己的意思表达得清清楚楚,使得任何听到讲话或看到文章或信件的人都能正确地领会自己的意思而不致产生任何误解。但在有些情况下,人们只希望某些特定的对象能理解自己的语言而不希望局外人从语言中获得任何信息。这种事例古已有之。比如,我国古代不乏以藏头露尾诗的形式把真正的信息隐藏于整个诗篇中,从而只让某些掌握了规律的人知晓的例子。再如,古罗马恺撒大帝通过将拼音字母向后移三位的方法向赛查罗发布命令。更早些时候,古希腊历史学家波里比阿利用删去了J的25字母方阵创造了通过用表示行
3、和列的两个字母去表示方阵中的一个字母的方法,等等。这些都可看作是密码学的雏形。直到20世纪中叶,密码学主要应用于军事或外交方面的消息传送上。随着计算机科学的迅速发展和信息时代的到来,现代密码学的应用范围已经远远超出了军事与外交领域,它也从狭义的通信保密理论发展为包含了诸如防篡改技术、防假冒技术、安全协议的制订、身份验证、电子签名、电子货币以及秘密分享方案等多方面内容的枝繁叶茂的学科,因而也在金融、财贸和商业等领域有重要的应用。现代密码学当然是与计算机科学紧密联系的,而它所使用的数学工具已涉及数论、布尔函数、Walsh函数、群论、有限域理
4、论、逻辑学乃至代数几何学中的椭圆曲线理论。不过应用最多的还是数论。关于现代密码学已有许多专著,如文[1～10],这篇短文的目的则是力求用最通俗的语言通过背包原理、RSA系统和秘密分享这几个专题向读者说明数论方法在现代密码学中应用之一斑。如果读者能通过本文了解到数论这个数学科学中的“皇后”其实也可以在应用领域大显身手,乃至加盟于密码学研究的X收稿日期:2001211215.作者简介:王国俊(1935年11月生),男,教授,博士生导师,研究方向:非经典逻辑与拓扑.基金项目:国家自然科学基金重点项目,19831040.©1995-2004Ts
5、inghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第1期 王国俊:数论在密码学中的应用15队伍,那将是作者的最大愿望。2 数字语言称人们表达思想或传递信息的原始语言为明文,称将明文以某种方式变换后所得的语言为密文,由它可以经过相反的变换而恢复出明文来。为了实现这种从明文到密文、再从密文回到明文的变换,最方便者莫过于使用拼音文字,因为拼音文字的字母只有有限多个,建立了这有限个字母间的变换法则也就得到了明文与密文间的变换法则。而这有限多个字母是容易用数字来表示、变换和
6、传递的。所以现代密码学中的语言,不论是明文还是密文,实际上都是数字,我们称其为数字语言。以英语的26个拼音字母为例,它们既可以用从1到26的自然数来表达,也可以用计算45机中通用的二进制数来表达,因为26在2与2之间,用5位的二进制数表示这26个字母已经够用了。为简便计,不考虑语言中问号、惊叹号、逗号与句号等的区别,只考虑语言的停顿间隙,并一律用空格表示,那么,组成数字语言的基本单位就有了,共27个,如下表所示: 表1数字语言的基本单元表字母十进制数字二进制数字字母十进制数字二进制数字a100001o1501111b200010p1
7、610000c300011q1710001d400100r1810010e500101s1910011f600110t2010100g700111u2110101h801000v2210110i901001w2310111j1001010x2411000k1101011y2511001l1201100z2611010m1301101空格000000n1401110 有了这张从字母到数字的转换表,就可以将普通语言转换为数字语言了。比如,Iloveyou连中间的空格一起就可按上表中的二进制部分转换为如下的数字语言:0100100000,0
8、110001111,1011000101,0000011001,0111110101这里的逗号是为了读者便于和表1对照而加上的,真正的数字语言中没有这些逗号。3 背包原理3.1 背包原理 设想有一个长方体形
