euclid算法及扩展在密码学中的研究和应用new

《euclid算法及扩展在密码学中的研究和应用new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第16卷第11期计算机技术与发展Vol.16No.112006年11月COMPUTERTECHNOLOGYANDDEVELOPMENTNov.2006Euclid算法及扩展在密码学中的研究和应用1,223陈良臣,芦东昕,李春葆(1.华北电力大学计算机科学与技术学院,北京102206;2.中兴软件技术(南昌)有限公司,江西南昌330058;3.武汉大学计算机学院,湖北武汉430079)摘要:信息安全是网络时代的焦点,密码技术是信息安全的核心,而算法是密码学的精髓。文中研究了基于因数分解的Euclid算法和扩展Euclid算法,包括算法的基本原理、算法流程

2、及编程实现。分析了Euclid算法的算法复杂性,介绍了Eu2clid算法在RSA和AffineCipher密码系统中的应用,最后指出了该算法存在的缺陷和算法需要改进的方向。关键词:Euclid算法;加密算法;RSA;AffineCipher中图分类号:TP309.7文献标识码:A文章编号:1673-629X(2006)11-0156-04ResearchandApplicationofEuclidAlgorithmandExtendedEuclidAlgorithm1,223CHENLiang2chen,LUDong2xin,LIChun2bao(1.

3、SchoolofComputerScience&Technology,NorthChinaElectricPowerUniversity,Beijing102206,China;2.ZTESoftwareEngineeringCo.,Ltd,Nanchang330058,China;3.SchoolofComputerScience&Technology,WuhanUniversity,Wuhan430079,China)Abstract:Theinformationsecurityisthefocalpointofthenetworktimes.Cr

4、yptologyisthecoreoftheinformationsecurity,andalgorithmisthesoulofthecryptology.InvestigatedtheEuclidalgorithmbasedonfactorizationandextendedEuclidalgorithm,includingtheirratio2nale,processandprogramme.ThenanalyzedthecomplexityoftheEuclidalgorithm,andintroduceditsapplicationinRSA

5、andAffineCi2pher.Atlast,pointoutthelimitationoftheEuclidalgorithmandwherethealgorithmshouldbeimproved.Keywords:Euclidalgorithm;encrpytiontechniques;RSA;AffineCipher0引言Euclid算法在RSA和AffineCipher密码系统中普遍随着计算机与网络技术的不断发展和广泛应用,In2应用,其中RSA是当前最著名、应用最广泛的公钥系统,ternet已经成为一个非常复杂且极不安全的信息载体,信基于

6、因式分解的Euclid算法及扩展Euclid算法是RSA和息安全成为网络信息时代的焦点,密码技术是信息安全的AffineCipher密码系统中实现数据加密的基础。所以研核心,而算法又是密码技术的精髓。所以研究和设计好的究和改进Euclid算法对于密码学的研究和发展有着非常算法是提高信息安全的关键。重要的理论意义。Euclid算法是公元前希腊著名数学家欧几里得提出的,又称为辗转相除法,是基于因式分解求两个整数a,b1相关背景最大公因数的最普遍的算法。Euclid算法对于早期算法定义1设a,b是任意整数,如果存在整数c,使有a和程序性过程的研究起到了非常重

7、要的作用,而且一直沿=bc,则称a是b的倍数,b是a的因数;亦说a被b整除,用至今,在密码学领域和数论研究中具有极其重要的意或b整除a,记为b

8、a。[1]义。定理1设a,b是任意整数且b≠0,则惟一存在整数q和r,使得0≤r<

9、b

10、,a=qb+r。若r>0,则称收稿日期:2006-03-08q为带余除法的不完全商,称r为b除a的余数。基金项目:中国下一代互联网示范工程(CNGI)移动奥运资助项目证明:(CNGI-04-17-2A)1)证存在整数q和r,使得0≤r<

11、b

12、,a=qb+r。作者简介:陈良臣(1982-),男,湖北武汉人,硕士研究生,研究方向

13、考虑b:若b>0,则b的倍数数可递增排列为:⋯,-4b,为网络与信息安全;芦东昕,博士后,教授