最近工作中用到了RSA算法，找了一些相关的资料和代码，整理了一下，汇总成这篇文章。
<一>基础
RSA算法非常简单，概述如下：
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e<t并且e与t互素（就是最大公因数为1）
取d*e%t==1
这样最终得到三个数： n d e
设消息为数M (M
设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则 m == M，从而完成对c的解密。
注：**表示次方,上面两式中的d和e可以互换。
在对称加密中：
n d两个数构成公钥，可以告诉别人；
n e两个数构成私钥，e自己保留，不让任何人知道。
给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。
别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。
rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解
从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法
求得d。
<二>实践
接下来我们来一个实践，看看实际的操作：
找两个素数：
p=47
q=59
这样
n=p*q=2773
t=(p-1)*(q-1)=2668
取e=63，满足e
用perl简单穷举可以获得满主 e*d%t ==1的数d：
C:\Temp>perl -e “foreach $i (1..9999){ print($i),last if $i*63%2668==1 }”
847
即d＝847
最终我们获得关键的
n=2773
d=847
e=63
取消息M=244我们看看
加密：
c=M**d%n = 244**847%2773
用perl的大数计算来算一下：
C:\Temp>perl -Mbigint -e “print 244**847%2773″
465
即用d对M加密后获得加密信息c＝465
解密：
我们可以用e来对加密后的c进行解密，还原M：
m=c**e%n=465**63%2773 ：
C:\Temp>perl -Mbigint -e “print 465**63%2773″
244
即用e对c解密后获得m=244 , 该值和原始信息M相等。
<三>字符串加密
把上面的过程集成一下我们就能实现一个对字符串加密解密的示例了。
每次取字符串中的一个字符的ascii值作为M进行计算，其输出为加密后16进制
的数的字符串形式，按3字节表示，如01F
代码如下：
#!/usr/bin/perl -w
#RSA 计算过程学习程序编写的测试程序
#watercloud 2003-8-12
#
use strict;
use Math::BigInt;my %RSA_CORE = (n=>2773,e=>63,d=>847); #p=47,q=59
my $N=new Math::BigInt($RSA_CORE{n});
my $E=new Math::BigInt($RSA_CORE{e});
my $D=new Math::BigInt($RSA_CORE{d});print “N=$N D=$D E=$E\n”;
sub RSA_ENCRYPT
{
my $r_mess = shift @_;
my ($c,$i,$M,$C,$cmess);for($i=0;$i < length($$r_mess);$i++)
{
$c=ord(substr($$r_mess,$i,1));
$M=Math::BigInt->new($c);
$C=$M->copy(); $C->bmodpow($D,$N);
$c=sprintf “%03X”,$C;
$cmess.=$c;
}
return \$cmess;
}sub RSA_DECRYPT
{
my $r_mess = shift @_;
my ($c,$i,$M,$C,$dmess);for($i=0;$i < length($$r_mess);$i+=3)
{
$c=substr($$r_mess,$i,3);
$c=hex($c);
$M=Math::BigInt->new($c);
$C=$M->copy(); $C->bmodpow($E,$N);
$c=chr($C);
$dmess.=$c;
}
return \$dmess;
}my $mess=”RSA 娃哈哈哈～～～”;
$mess=$ARGV[0] if @ARGV >= 1;
print “原始串：”,$mess,”\n”;my $r_cmess = RSA_ENCRYPT(\$mess);
print “加密串：”,$$r_cmess,”\n”;my $r_dmess = RSA_DECRYPT($r_cmess);
print “解密串：”,$$r_dmess,”\n”;#EOF
测试一下：
C:\Temp>perl rsa-test.pl
N=2773 D=847 E=63
原始串：RSA 娃哈哈哈～～～
加密串：5CB6CD6BC58A7709470AA74A0AA74A0AA74A6C70A46C70A46C70A4
解密串：RSA 娃哈哈哈～～～C:\Temp>perl rsa-test.pl 安全焦点（xfocus）
N=2773 D=847 E=63
原始串：安全焦点（xfocus）
加密串：3393EC12F0A466E0AA9510D025D7BA0712DC3379F47D51C325D67B
解密串：安全焦点（xfocus）
<四>提高
前面已经提到，rsa的安全来源于n足够大，我们测试中使用的n是非常小的，根本不能保障安全性，
我们可以通过RSAKit、RSATool之类的工具获得足够大的N 及D E。
通过工具，我们获得1024位的N及D E来测试一下：
n=0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F
90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD
55EDBC4F017F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5A
D2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951d=0×10001
e=0xE760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87
A3106DD28C523C29954C5D86B36E943080E4919CA8CE08718C3B0930867A98F635E
B9EA9200B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9D8B4B7A3C9EE05
FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B1965
设原始信息
M=0×11111111111122222222222233333333333
完成这么大数字的计算依赖于大数运算库，用perl来运算非常简单：
A) 用d对M进行加密如下：
c=M**d%n :
C:\Temp>perl -Mbigint -e ” $x=Math::BigInt->bmodpow(0×1111111111112222
2222222233333333333, 0×10001, x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5F
CD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278
F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B47D80EC74B
51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173C
CA50E114705D7E2BC511951);
print $x->as_hex “0x17b287be418c69ecd7c39227ab681ac422fcc84bb35
d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef38
66af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b3028f9461a3b
1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea
89b91f1834580c3f6d90898
即用d对M加密后信息为：
c=0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de2
88a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed
1d4cc4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb47644146
5f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d
90898
B) 用e对c进行解密如下：
m=c**e%n ：
C:\Temp>perl -Mbigint -e ” $x=Math::BigInt->bmodpow(0x17b287be4
18c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d
2576bd45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26
bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb476441465f10d8ad47452a
12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898,
0xE760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9
D87A3106DD28C523C29954C5D86B36E943080E4919CA8CE08718C3B0930867
A98F635EB9EA9200B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9D
8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A
592D2B1965,
0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD1
5F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A
6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D
6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2B
C511951);
print $x->as_hex”
0×11111111111122222222222233333333333
(P4 1.6G的机器上计算需要约5秒钟）
得到用e解密后的m=0×11111111111122222222222233333333333 == M
C) RSA通常的实现
RSA简洁幽雅，但计算速度比较慢，通常加密中并不是直接使用RSA 来对所有的信息进行加密，
最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用
RSA对刚才的加密密钥进行加密。
最后需要说明的是，当前小于1024位的N已经被证明是不安全的
自己使用中不要使用小于1024位的RSA，最好使用2048位的。
———————————————————-
一个简单的RSA算法实现 PHP 源代码：filename:RSA.php
/*
* Implementation of the RSA algorithm
* (C) Copyright 2004 Edsko de Vries, Ireland
*
* Licensed under the GNU Public License (GPL)
*
* This implementation has been verified against [3]
* (tested Java/PHP interoperability).
*
* References:
* [1] "Applied Cryptography", Bruce Schneier, John Wiley & Sons, 1996
* [2] "Prime Number Hide-and-Seek", Brian Raiter, Muppetlabs (online)
* [3] "The Bouncy Castle Crypto Package", Legion of the Bouncy Castle,
* (open source cryptography library for Java, online)
* [4] "PKCS #1: RSA Encryption Standard", RSA Laboratories Technical Note,
* version 1.5, revised November 1, 1993
*/
/*
* Functions that are meant to be used by the user of this PHP module.
*
* Notes:
* - $key and $modulus should be numbers in (decimal) string format
* - $message is expected to be binary data
* - $keylength should be a multiple of 8, and should be in bits
* - For rsa_encrypt/rsa_sign, the length of $message should not exceed
* ($keylength /- 11 (as mandated by [4]).
* - rsa_encrypt and rsa_sign will automatically add padding to the message.
* For rsa_encrypt, this padding will consist of random values; for rsa_sign,
* padding will consist of the appropriate number of 0xFF values (see [4])
* - rsa_decrypt and rsa_verify will automatically remove message padding.
* - Blocks for decoding (rsa_decrypt, rsa_verify) should be exactly
* ($keylength /
* - rsa_encrypt and rsa_verify expect a public key; rsa_decrypt and rsa_sign
* expect a private key.
*/
function rsa_encrypt($message, $public_key, $modulus, $keylength)
{
$padded = add_PKCS1_padding($message, true, $keylength / 8);
$number = binary_to_number($padded);
$encrypted = pow_mod($number, $public_key, $modulus);
$result = number_to_binary($encrypted, $keylength / 8);return $result;
}
function rsa_decrypt($message, $private_key, $modulus, $keylength)
{
$number = binary_to_number($message);
$decrypted = pow_mod($number, $private_key, $modulus);
$result = number_to_binary($decrypted, $keylength / 8);
return remove_PKCS1_padding($result, $keylength / 8);
}
function rsa_sign($message, $private_key, $modulus, $keylength)
{
$padded = add_PKCS1_padding($message, false, $keylength / 8);
$number = binary_to_number($padded);
$signed = pow_mod($number, $private_key, $modulus);
$result = number_to_binary($signed, $keylength / 8);
return $result;
}
function rsa_verify($message, $public_key, $modulus, $keylength)
{
return rsa_decrypt($message, $public_key, $modulus, $keylength);
}
/*
* Some constants
*/
define(“BCCOMP_LARGER”, 1);
/*
* The actual implementation.
* Requires BCMath support in PHP (compile with –enable-bcmath)
*/
//–
// Calculate (p ^ q) mod r
//
// We need some trickery to [2]:
// (a) Avoid calculating (p ^ q) before (p ^ q) mod r, because for typical RSA
// applications, (p ^ q) is going to be _WAY_ too large.
// (I mean, __WAY__ too large – won’t fit in your computer’s memory.)
// (b) Still be reasonably efficient.
//
// We assume p, q and r are all positive, and that r is non-zero.
//
// Note that the more simple algorithm of multiplying $p by itself $q times, and
// applying “mod $r” at every step is also valid, but is O($q), whereas this
// algorithm is O(log $q). Big difference.
//
// As far as I can see, the algorithm I use is optimal; there is no redundancy
// in the calculation of the partial results.
//–
function pow_mod($p, $q, $r)
{
// Extract powers of 2 from $q
$factors = array();
$div = $q;
$power_of_two = 0;
while(bccomp($div, “0″) == BCCOMP_LARGER)
{
$rem = bcmod($div, 2);
$div = bcdiv($div, 2);if($rem) array_push($factors, $power_of_two);
$power_of_two++;
}
// Calculate partial results for each factor, using each partial result as a
// starting point for the next. This depends of the factors of two being
// generated in increasing order.
$partial_results = array();
$part_res = $p;
$idx = 0;
foreach($factors as $factor)
{
while($idx < $factor)
{
$part_res = bcpow($part_res, “2″);
$part_res = bcmod($part_res, $r);
$idx++;
}array_pus($partial_results, $part_res);
}
// Calculate final result
$result = “1″;
foreach($partial_results as $part_res)
{
$result = bcmul($result, $part_res);
$result = bcmod($result, $r);
}
return $result;
}
//–
// Function to add padding to a decrypted string
// We need to know if this is a private or a public key operation [4]
//–
function add_PKCS1_padding($data, $isPublicKey, $blocksize)
{
$pad_length = $blocksize – 3 – strlen($data);
if($isPublicKey)
{
$block_type = “\x02″;$padding = “”;
for($i = 0; $i < $pad_length; $i++)
{
$rnd = mt_rand(1, 255);
$padding .= chr($rnd);
}
}
else
{
$block_type = “\x01″;
$padding = str_repeat(“\xFF”, $pad_length);
}return “\x00″ . $block_type . $padding . “\x00″ . $data;
}
//–
// Remove padding from a decrypted string
// See [4] for more details.
//–
function remove_PKCS1_padding($data, $blocksize)
{
assert(strlen($data) == $blocksize);
$data = substr($data, 1);
// We cannot deal with block type 0
if($data{0} == ‘\0′)
die(“Block type 0 not implemented.”);
// Then the block type must be 1 or 2
assert(($data{0} == “\x01″) || ($data{0} == “\x02″));
// Remove the padding
$offset = strpos($data, “\0″, 1);
return substr($data, $offset + 1);
}
//–
// Convert binary data to a decimal number
//–
function binary_to_number($data)
{
$base = “256″;
$radix = “1″;
$result = “0″;
for($i = strlen($data) – 1; $i >= 0; $i–)
{
$digit = ord($data{$i});
$part_res = bcmul($digit, $radix);
$result = bcadd($result, $part_res);
$radix = bcmul($radix, $base);
}
return $result;
}
//–
// Convert a number back into binary form
//–
function number_to_binary($number, $blocksize)
{
$base = “256″;
$result = “”;
$div = $number;
while($div > 0)
{
$mod = bcmod($div, $base);
$div = bcdiv($div, $base);$result = chr($mod) . $result;
}
return str_pad($result, $blocksize, “\x00″, STR_PAD_LEFT);
}
一个简单的RSA算法实现JAVA源代码：filename:RSA.java
/*
* Created on Mar 3, 2005
*
* TODO To change the template for this generated file go to
* Window – Preferences – Java – Code Style – Code Templates
*/
import java.math.BigInteger;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.FileWriter;
import java.io.FileReader;
import java.io.BufferedReader;
import java.util.StringTokenizer;
/**
* @author Steve
*
* TODO To change the template for this generated type comment go to
* Window – Preferences – Java – Code Style – Code Templates
*/
public class RSA {/**
* BigInteger.ZERO
*/
private static final BigInteger ZERO = BigInteger.ZERO;/**
* BigInteger.ONE
*/
private static final BigInteger ONE = BigInteger.ONE;/**
* Pseudo BigInteger.TWO
*/
private static final BigInteger TWO = new BigInteger(“2″);private BigInteger myKey;
private BigInteger myMod;
private int blockSize;
public RSA (BigInteger key, BigInteger n, int b) {
myKey = key;
myMod = n;
blockSize = b;
}public void encodeFile (String filename) {
byte[] bytes = new byte[blockSize / 8 + 1];
byte[] temp;
int tempLen;
InputStream is = null;
FileWriter writer = null;
try {
is = new FileInputStream(filename);
writer = new FileWriter(filename + “.enc”);
}
catch (FileNotFoundException e1){
System.out.println(“File not found: ” + filename);
}
catch (IOException e1){
System.out.println(“File not found: ” + filename + “.enc”);
}/**
* Write encoded message to ‘filename’.enc
*/
try {
while ((tempLen = is.read(bytes, 1, blockSize / 8)) > 0) {
for (int i = tempLen + 1; i < bytes.length; ++i) {
bytes[i] = 0;
}
writer.write(encodeDecode(new BigInteger(bytes)) + ” “);
}
}
catch (IOException e1) {
System.out.println(“error writing to file”);
}/**
* Close input stream and file writer
*/
try {
is.close();
writer.close();
}
catch (IOException e1) {
System.out.println(“Error closing file.”);
}
}public void decodeFile (String filename) {
FileReader reader = null;
OutputStream os = null;
try {
reader = new FileReader(filename);
os = new FileOutputStream(filename.replaceAll(“.enc”, “.dec”));
}
catch (FileNotFoundException e1) {
if (reader == null)
System.out.println(“File not found: ” + filename);
else
System.out.println(“File not found: ” + filename.replaceAll(“.enc”, “dec”));
}BufferedReader br = new BufferedReader(reader);
int offset;
byte[] temp, toFile;
StringTokenizer st = null;
try {
while (br.ready()) {
st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens()){
toFile = encodeDecode(new BigInteger(st.nextToken())).toByteArray();
System.out.println(toFile.length + ” x ” + (blockSize / 8));if (toFile[0] == 0 && toFile.length != (blockSize / 8)) {
temp = new byte[blockSize / 8];
offset = temp.length – toFile.length;
for (int i = toFile.length – 1; (i <= 0) && ((i + offset) <= 0); –i) {
temp[i + offset] = toFile[i];
}
toFile = temp;
}/*if (toFile.length != ((blockSize /
temp = new byte[(blockSize /
System.out.println(toFile.length + ” x ” + temp.length);
for (int i = 1; i < temp.length; i++) {
temp[i] = toFile[i - 1];
}
toFile = temp;
}
else
System.out.println(toFile.length + ” ” + ((blockSize /
os.write(toFile);
}
}
}
catch (IOException e1) {
System.out.println(“Something went wrong”);
}/**
* close data streams
*/
try {
os.close();
reader.close();
}
catch (IOException e1) {
System.out.println(“Error closing file.”);
}
}/**
* Performs base^pow within the modular
* domain of mod.
*
* @param base the base to be raised
* @param pow the power to which the base will be raisded
* @param mod the modular domain over which to perform this operation
* @return base^pow within the modular
* domain of mod.
*/
public BigInteger encodeDecode(BigInteger base) {
BigInteger a = ONE;
BigInteger s = base;
BigInteger n = myKey;while (!n.equals(ZERO)) {
if(!n.mod(TWO).equals(ZERO))
a = a.multiply(s).mod(myMod);s = s.pow(2).mod(myMod);
n = n.divide(TWO);
}return a;
}
}
在这里提供两个版本的RSA算法JAVA实现的代码链接：
1. 来自于 http://www.javafr.com/code.aspx?ID=27020 的RSA算法实现源代码包；
2. 来自于 http://www.ferrara.linux.it/Members/lucabariani/RSA/implementazioneRsa/ 的实现；
RSA加密的 JavaScript 实现: http://www.ohdave.com/rsa/
Post a Comment