扩展Euclid算法及其在RSA中的应用

journal6 ›› 2011, Vol. 32 ›› Issue (2): 22-25.

扩展Euclid算法及其在RSA中的应用

(1.杭州电子科技大学通信工程学院,浙江杭州310018；2.安徽工业大学计算机学院,安徽马鞍山 243002）

出版日期:2011-03-25 发布日期:2012-04-09
作者简介:周建钦(1963-),男,山东巨野人，杭州电子科技大学通信工程学院教授,主要从事密码学、通信编码、组合数学和算法研究.
基金资助:
浙江省自然科学基金资助项目(Y1100318，R1090138)；国家自然科学基金委员会与中国工程物理研究院联合基金资助项目(10776077)

Extended Euclid Algorithm and Its Application in RSA

(1.College of Telecommunication,Hangzhou Dianzi University,Hangzhou 310018,China;2.College of Computer Science,Anhui University of Technology,Maanshan 243002,Anhui China)

Online:2011-03-25 Published:2012-04-09

摘要/Abstract

摘要：RSA以大数因子分解困难性为基础，目前广泛使用的是公钥密码体制.Euclid算法和扩展Euclid算法是求解RSA公钥、私钥的最普遍算法.对IEEE P1363中的扩展Euclid算法进行了改进,消除了扩展Euclid算法中负数的运算，从而减少了RSA占用的计算资源.

关键词： Euclid算法, 扩展Euclid算法, 加密算法, RSA

Abstract: RSA,an encryption and decryption system based on the great difficulty of integer factorization，is the widely-used public-key cryptosystem.Euclid algorithm and extended Euclid algorithm are the best algorithms to solve the public key and private key in RSA.Extended Euclid algorithm in IEEE P1363 is improved by eliminating the negative integer operation,hence the computing resources occupied by RSA are reduced.

Key words: Euclid algorithm, extended Euclid algorithm, encryption algorithm, RSA

周建钦, 胡军, 崔洪成. 扩展Euclid算法及其在RSA中的应用[J]. journal6, 2011, 32(2): 22-25.

ZHOU Jian-Qin, HU Jun, CUI Hong-Cheng. Extended Euclid Algorithm and Its Application in RSA[J]. journal6, 2011, 32(2): 22-25.

[1]	江治国. AES算法在智能家居通信安全系统中的应用[J]. 吉首大学学报（自然科学版）, 2018, 39(3): 25-30.
[2]	向进. RSA加密算法的安全性分析[J]. journal6, 2011, 32(1): 42-44.
[3]	朱丹. 股价服从跳－扩散模型的可转换债券的定价[J]. journal6, 2008, 29(1): 34-38.
[4]	游新娥. RSA算法中安全大素数生成方法及其改进[J]. journal6, 2007, 28(5): 34-37.
[5]	朱丹. 价格波动源模型下欧式上入局期权的鞅定价[J]. journal6, 2006, 27(3): 23-26.