RSA加密算法的编程实现论文.doc

RSA加密算法的编程实现论文RSA算法是在1978年由美国麻省理工学院三位密码学专家R on R ivest、Adi Sh amir和Leonard Adleman发明的。RSA算法是一种典型的公开密钥体制算法，它的发明是对密码学的一个杰出贡献。RSA算法得到了世界上最广泛的应用，并在1992年被ISO 国际标准化组织正式纳入国际标准13。与传统的对称密码算法相比，RSA算法最大贡献是为实现数字签名和数字证实提供了手段，为现代网络安全技术、电子商务、电子政务等打下了坚实的基础。RSA算法实现(1) 在产生公开密钥前先要选择两个不同的素数p、q，判断素数的方法很多，本程序判断素数的方法是：设n从3开始，每次增加2(排除偶数)，除以 的所有素数，如不存在被整除的数，则n为素数。(2) 有了p、q值，就可以根据(r)的值选择一个公开密钥pk，一般来说密钥长度越长安全性越好，但密钥的值应小于(r)的值，否则不能正确求出私人密钥sk。程序中使用了欧几里德算法求出最大公约数：设有整数a、b，ab0，先令b 为余数，a 为除数，用每次余数为除数，去除以上次的除数，直到余数为0时，则上次的余数就是最大公约数。(3) 已知整数a、r，如果ab1modr 成立，也就是ab 的乘积被r 除所得的余数等于1，用欧几里德扩展算法可以求出b。先令a作为余数，r作为上次除数，根据欧几里德算法，由数学归纳法可以证明出求a的乘逆b的递推公式如下：b-1=0，b=1b=|bj|其中j为整数，从1开始，qj是rj/aj的整数部分，当rj/aj 的余数为1时，则a 的乘逆b=|bj|。(4) 加密、解密时，由于P=123456789值巨大，直接计算mamodr的值是很不方便的，使用“平方-乘算法”将极大地提高计算mamodr的速度。先将a转换为二进制数b，令L 为b的二进制位数，c=1，“平方-乘算法”伪码如下：F O R I=L -1 TO 0 DO c=cc mod r；IF bi=1 TH E N c=cm mod r；则c就是mamodr 的值，其中bi是b 的第i 位值。RAS 算法举例下面我们举一个例子说明R AS加密和解密过程：(1) 选素数，如选p=47，q=61。(2) 计算公开模数r=pq=461=2867。(3) 计算欧拉函数k。(4) 利用求最大公约数算法等，选择一个与(r)互质的量k，可以选k=167，并令sk=k=167。(5) 根据skpk1mod(r)，用求乘逆算法求出pk=1223。这样我们就求出R SA算法3个关键值：r=2876， pk=1223，sk=167(6) 加密时，假如明文P=123456789，可以将明文分成3组，即P1=123，P2=456，P3=789。用私人密钥sk加密时：C1=P1167 mod r=1770C2=P2167 mod r=1321C3=P3167 mod r=1297所以密文C=177013211297。(7) 解密时，如用公开密钥pk解密时，只要计算：P1=C11223 mod r=123P2=C21223 mod r=456P3=C31223 mod r=789P=123456789这样，就将明文还原出来了。以下程序是java编写的实现RSA加密及解密的算法 import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import erfaces.RSAPrivateKey; import erfaces.RSAPublicKey; import javax.crypto.Cipher; /RSATest类即为测试类public class RSATest /主函数 public static void main(String args) try RSATest encrypt = new RSATest(); String encryptText = encryptText;/输入的明文 KeyPair keyPair = encrypt.generateKey();/调用函数生成密钥对，函数见下 RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate(); RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic(); byte e = encrypt.encrypt(publicKey, encryptText.getBytes();/调用自己编写的encrypt函数实现加密， byte de = encrypt.decrypt(privateKey, e); /调用自己编写的decrypt函数实现解密， System.out.println(toHexString(e); /输出结果，采用ASSIC码形式 System.out.println(toHexString(de); catch (Exception e) e.printStackTrace(); / generateKey密钥对生成函数的实现 public KeyPair generateKey() throws NoSuchAlgorithmException KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(RSA); /返回生成指定算法的 public/private 密钥对的 KeyPairGenerator 对象。 keyPairGen.initialize(1024, new SecureRandom(); /使用给定的随机源（和默认的参数集合）初始化确定密钥大小的密钥对生成器。 KeyPair keyPair = keyPairGen.generateKeyPair();/生成一个密钥对 return keyPair; / encrypt加密函数 protected byte encrypt(RSAPublicKey publicKey, byte data) if (publicKey != null) try Cipher cipher = Cipher.getInstance(RSA);/返回实现指定转换的 Cipher 对象。 cipher.init(Cipher.ENCRYPT_MODE, publicKey);/用密钥初始化此 Cipher,第一个参数表示加密 return cipher.doFinal(data); /按单部分操作加密或解密数据，或者结束一个多部分操作。数据将被加密或解密（具体取决于此 Cipher 的初始化方式）。 catch (Exception e) e.printStackTrace(); return null; / decrypt解密函数 protected byte decrypt(RSAPrivateKey privateKey, byte raw) if (privateKey != null) try Cipher cipher = Cipher.getInstance(RSA); cipher.init(Cipher.DECRYPT_MODE, privateKey); /第一个参数表示解密 return cipher.doFinal(raw); catch (Exception e) e.printStackTrace(); return null; / toHexString将字节数组变为ASSIC码表示的字符串 public static String toHexString(byte b) StringBuilder sb = new StringBuilder(b.length * 2);/构造一个不带任何字符的字符串生成器，其初始容量由 capacity 参数指定。 for (int i = 0; i 4); / append 方法始终将这些字符添加到生成器的末端；而 insert 方法则在指定的点添加字符。/调用HEXCHAR方法 sb.append(HEXCHARbi & 0x0f); return sb.toString(); /构建一