APP下载

RSA算法研究及其计算技巧分析

2012-09-25贾美娟

大庆师范学院学报 2012年6期

贾美娟,孔 靓,李 梓,杨 红

(大庆师范学院 计算机科学与信息技术学院,黑龙江 大庆 163712)

0 引言

无论是古老的手工密码还是机电式密码,甚至是利用了计算机的现代对称密码,这些编码系统越来越复杂,但都是建立在基本的替代和置换工具的基础上,而公钥密码体制的编码系统是基于数学中的单向陷门函数。更重要的是,公钥密码体制采用了两个不同的密钥,这对于目前在开放的网络上进行的密钥分配、保密通信、认证和数学签名等都具有非常重要的意义。因此,可以说公钥密码体制的发现是密码学发展史上的一次革命[1]。目前公钥密码系统单向陷门函数的设计主要依赖3种数学难题,即:背包问题、大整数因子分解问题及离散对数问题。

1 RSA算法

1978年麻省理工学院的三位科学家Ron Rivest,Adi Shamir和Leonard Adleman提出的公钥系统简称为RSA系统。它的安全性是基于大素数因子分解的困难性,其公钥和私钥是一对大素数(100到200位的十进制数或更大)的函数。从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积,而大素数因子分解问题是数学上的著名难题,因而可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法,自提出以来就一直是人们研究的焦点,经受住了多年来许多资深密码学家的密码分析[2]。

1.1 RSA算法描述

RSA算法是利用单向陷门函数的一种可逆模指数运算,它是迄今为止在理论上最为成熟完善的公钥密码体制。具体描述如下:

1)RSA算法密钥的产生

登录APP查看全文