RSA算法公钥加密算法

RSA1978年，MIT的Rivest、Shamir、Adleman提出RSA算法

非对称加密（公开密钥加密）密码学的一次革命，定义：KA≠KB ，KA、E和D公开

特点：

基于数论原理(大数分解难题)

是目前应用最广泛的公钥加密算法

属于块加密算法

在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。

RSA算法原理

l 定义：RSA加密算法

确定密钥：

1. 找到两个大质数，p,q

2. Let n=pq

3. let m=(p-1)(q-1);Choose e and d such that de=1(%m).

4. Publish n and e as public key. Keep d and n as secret key.

加密：

C=M^e(%n)

解密：

M=(C^d)%n

其中C=M^e(%n) 为C%n=(M^e)%n

存在的主要问题是大数计算和大数存储的问题。

什么是RSA

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。

RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。

RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。

这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。

RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。

RSA的算法涉及三个参数，n、e1、e2。

其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。

e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。

(n及e1),(n及e2)就是密钥对。

RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n；

e1和e2可以互换使用，即：

A=B^e2 mod n；B=A^e1 mod n；

一、RSA 的安全性

RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。

二、RSA的速度

由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。

三、RSA的选择密文攻击

RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：

( XM )^d = X^d *M^d mod n

前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way HashFunction 对文档作HASH处理，或

四、RSA的公共模数攻击

若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：

C1 = P^e1 mod n

C2 = P^e2 mod n

密码分析者知道n、e1、e2、C1和C2，就能得到P。

因为e1和e2互质，故用Euclidean算法能找到r和s，满足：

r * e1 + s * e2 = 1

假设r为负数，需再用Euclidean算法计算C1^(-1)，则

( C1^(-1) )^(-r) * C2^s = P mod n

另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享模数n。

RSA的小指数攻击。有一种提高RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET( Secure Electronic Transaction )协议中要求CA 采用比特长的密钥，其他实体使用比特的密钥。

在许多应用领域, 公钥密码技术在保障安全方面起了关键的作用在某些场合由于不便频繁更换私人密钥如权威机构的证书密钥、金融机构的签名密钥等, 确保密钥的安全就至关重要防止密钥泄露的一项决定性措施是采用门限密码技术, , 它将一部分密码的功能分散给多人, 而只有一定数量的成员合作方可完成密码运算另外, 在一些特殊场合也须谨防密钥的持有者权力过于集中而滥用职权, 这也要求对密钥进行分散管理, 以克服权力过于集中的弊端实现密钥分散管理的门限密码, 需要解决秘密的分享、密码算法以及结合这两者而设计出新的加密方式密码算法的研究一直是密码理论的主体, 目前已有许多算法可供选择使甩对秘密分享也早有雌, 它是指将系统的秘密s, 分解为N个部分秘密s1,s2,s3…,sn, 系统的N个成员P1,P2,..Pn分别拥有各自的部分秘密, 使得任何少于T个成员都无法从他们的部分秘密得到任何关于系统秘密s信息;借助有效的算法, 任意T成员可从相应的部分秘密得到系统的秘密s.这就是所谓的, (T,N)一门限秘密分享系统在实际应用中,秘密分享系统

存在着不可回避的问题, 即由谁来完成从部分秘密恢复系统秘密的工作因为不论是谁, 他一旦得到了个部分秘密, 就可导出系统的秘密而独享, 除非秘密的恢复是由一个可信的“黑盒子”完成, 为了避免系统秘密的泄露, 文献2提出利用部分密钥将加密的部分结果发给指定的人或机器, 再由部分结果产生最终的结果, 而又不暴露系统的秘密目前, 门限密码已成为密码学中非常活跃的领域.

RSA算法（转）

2008-06-05 10:39

<一>基础

RSA算法非常简单，概述如下：

找两素数p和q

取n=p*q

取t=(p-1)*(q-1)

取任何一个数e,要求满足e

取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=0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85 F5005D

BDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C201343 3B383B

47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E1147 05D7E2

BC511951

d=0x10001

e=0xE760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C5 23C2995

4C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324 E66AFF2

C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782 A592D2B

1965

设原始信息

M=0x11111111111122222222222233333333333

完成这么大数字的计算依赖于大数运算库，用perl来运算非常简单：

A) 用d对M进行加密如下：

c=M**d%n :

C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x11111111111122222222222233 333333333, 0x10001,

0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5F

CD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4 F0

17F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108D D6

0438941D2ED173CCA50E114705D7E2BC511951);print $x->as_hex"

0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576 bd

45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa 6b

3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b 91

f1834580c3f6d90898

即用d对M加密后信息为：

c=0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d25 76bd

45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa 6b

3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b 91

f1834580c3f6d90898

B) 用e对c进行解密如下：

m=c**e%n ：

C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x17b287be418c69ecd7c39227ab 681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99e f3

866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb47644 14

65f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898, 0xE7 60A

3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C 5D

86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66A FF

2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD78 2A

592D2B1965, 0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15 F90

B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9C CF

1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD604389 41

D2ED173CCA50E114705D7E2BC511951);print $x->as_hex"

0x11111111111122222222222233333333333

(我的P4 1.6G的机器上计算了约5秒钟）

得到用e解密后的m=0x11111111111122222222222233333333333 == M

C) RSA通常的实现

RSA简洁幽雅，但计算速度比较慢，通常加密中并不是直接使用RSA 来对所有的信息进行加密，

最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用

RSA对刚才的加密密钥进行加密。

最后需要说明的是，当前小于1024位的N已经被证明是不安全的

自己使用中不要使用小于1024位的RSA，最好使用2048位的

RSA算法的数学原理:

先来找出三个数, p, q, r,

其中p, q 是两个相异的质数, r 是与(p-1)(q-1) 互质的数。

p, q, r 这三个数便是private key。接著, 找出m, 使得rm == 1 mod (p-1)(q-1)..... 这个m 一定存在, 因为r 与(p-1)(q-1) 互质, 用辗转相除法就可以得到了..... 再来, 计算n = pq....... m, n 这两个数便是public key。

编码过程是, 若资料为a, 将其看成是一个大整数, 假设 a < n.... 如果 a >= n 的话, 就将 a 表成s 进位(s <= n, 通常取s = 2^t), 则每一位数均小於n, 然後分段编码...... 接下来, 计算 b == a^m mod n, (0 <= b < n), b 就是编码後的资料...... 解码的过程是, 计算 c == b^r mod pq (0 <= c < pq), 於是乎, 解码完毕...... 等会会证明 c 和 a 其实是相等的:) 如果第三者进行窃听时, 他会得到几个数: m, n(=pq), b...... 他如果要解码的话, 必须想办法得到r...... 所以, 他必须先对n 作质因数分解......... 要防止他分解, 最有效的方法是找两个非常的大质数p, q, 使第三者作因数分解时发生困难......... <定理> 若p, q 是相异质数, rm == 1 mod (p-1)(q-1), a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq, 则 c == a mod pq 证明的过程, 会用到费马小定理, 叙述如下: m 是任一质数, n 是任一整数, 则n^m == n mod m (换另一句话说, 如果n 和m 互质, 则n^(m-1) == 1 mod m) 运用一些基本的群论的知识, 就可以很容易地证出费马小定理的........ <证明> 因为rm == 1 mod (p-1)(q-1), 所以rm = k(p-1)(q-1) + 1, 其中k 是整数因为在modulo 中是preserve 乘法的(x == y mod z and u == v mod z => xu == yv mod z), 所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq 1. 如果 a 不是p 的倍数, 也不是q 的倍数时, 则a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q 所以p, q 均能整除a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1 即a^(k(p-1)(q-1)) == 1 mod pq => c == a^(k(p-1)(q-1)+1) == a mod pq 2. 如果 a 是p 的倍数, 但不是q 的倍数时, 则a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q => c == a^(k(p-1)(q-1)+1) == a mod q => q | c - a 因p | a => c == a^(k(p-1)(q-1)+1) == 0 mod p => p | c - a 所以, pq | c - a => c == a mod pq 3. 如果 a 是q 的倍数, 但不是p 的倍数时, 证明同上 4. 如果 a 同时是p 和q 的倍数时, 则pq | a => c == a^(k(p-1)(q-1)+1) == 0 mod pq => pq | c - a => c == a mod pq Q.E.D. 这个定理说明 a 经过编码为 b 再经过解码为 c 时, a == c mod n (n = pq).... 但我们在做编码解码时, 限制0 <= a < n, 0 <= c < n, 所以这就是说 a 等於c, 所以这个过程确实能做到编码解码的功能.....

RSA加密算法_源代码__C语言实现

RSA算法 1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。 RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 密钥对的产生。选择两个大素数，p 和q 。计算：n = p * q 然后随机选择加密密钥e，要求e 和( p - 1 ) * ( q - 1 )互质。最后，利用Euclid 算法计算解密密钥d, 满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q 不再需要，应该丢弃，不要让任何人知道。加密信息m（二进制表示）时，首先把m分成等长数据块m1 ,m2,..., mi ，块长s，其中2^s <= n, s 尽可能的大。对应的密文是：ci = mi^e ( mod n ) ( a ) 解密时作如下计算：mi = ci^d ( mod n ) ( b ) RSA 可用于数字签名，方案是用( a ) 式签名，( b )式验证。具体操作时考虑到安全性和m信息量较大等因素，一般是先作HASH 运算。RSA 的安全性。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA 就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。 */ #include #include #include using namespace std;//RSA算法所需参数 typedef struct RSA_PARAM_Tag { unsigned __int64 p, q; //两个素数，不参与加密解密运算 unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算 unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1 unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1 unsigned __int64 s; //块长，满足2^s<=n的最大的s，即log2(n) } RSA_PARAM;//小素数表 const static long g_PrimeTable[]= { 3, 5, 7, 11, 13, 17, 19, 23,

RSA公钥加密算法及其安全性讨论

RSA公钥加密算法及其安全性讨论 RSA algorithm for public-key encryption and its security 摘要：RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。但是，RSA的安全性依赖于大数的因子分解，却并没有从理论上证明破译RSA的难度与大数分解难度等价，即RSA的重大缺陷是无法从理论上把握它的保密性能到底如何。随着计算能力的不断进步和各种攻击方法的出现，RSA算法是否真的安全。 关键词：RSA，公钥，加密，大数分解，攻击，安全性 1 RSA加密算法 1.1公钥简介 密码体制按密钥类型分为对称密钥和不对称密钥。对称密钥即加密、解密用的是同一个密钥，又称为私钥。不对称密钥即公钥加密，加密、解密用的是不同的密钥，一个密钥“公开”，即公钥，另一个自己秘密持有，即私钥，加密方用公钥加密，只有用私钥才能解密——史称公钥加密体系：PKI。 1.2 RSA算法简介 RSA加密算法是一种非对称加密算法。RSA加密算法是Ron Rivest、Adi Shamirh和Len Adleman于1977年在美国麻省理工学院开发出来的，次年首次对外公开宣布，是第一个既能用于数据加密也能用于数字签名的算法。RSA就是他们三人姓氏开头字母拼在一起组成的。RSA是建立在“大整数的素因子分解是困难问题”基础上的，其安全性取决于大数分解，也就是大数分解质因数的困难性。换言之，对一极大整数做因式分解愈困难，RSA演算法愈可靠。假如有人找到一种快速因式分解的演算法的话，那么用RSA加密的信息的可靠性肯定会急剧下降，但找到这样的演算法的可能性是非常小的，今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。 1.3 RSA算法 1.3.1公钥和私钥的产生 假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥： （1）选两个保密的足够大的素数p和q。同时对p, q严加保密，不让任何人知道。 （2）计算N=p×q。 （3）计算f(n)=(p-1)(q-1)。 （4）找一个与f(n)互质的数e，且1

RSA加密算法的基本原理

RSA加密算法的基本原理 1978年RSA加密算法是最常用的非对称加密算法，CFCA 在证书服务中离不了它。但是有不少新来的同事对它不太了解，恰好看到一本书中作者用实例对它进行了简化而生动的描述，使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读，希望能够对时间紧张但是又想了解它的同事有所帮助。 RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。RSA以它的三个发明者Ron Rivest,Adi Shamir,Leonard Adleman的名字首字母命名，这个算法经受住了多年深入的密码分析，虽然密码分析者既不能证明也不能否定RSA的安全性，但这恰恰说明该算法有一定的可信性，目前它已经成为最流行的公开密钥算法。 RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积（这是公认的数学难题）。 RSA的公钥、私钥的组成，以及加密、解密的公式可见于下表： 可能各位同事好久没有接触数学了，看了这些公式不免一头雾水。别急，在没有正式讲解RSA加密算法以前，让我们先复习一下数学上的几个基本概念，它们在后面的介绍中要用到： 一、什么是“素数”？ 素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”（或“互素数”）？ 小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种（不限于此）： （1）两个质数一定是互质数。例如，2与7、13与19。 （2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与26。（3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。（4）相邻的两个自然数是互质数。如15与16。 （5）相邻的两个奇数是互质数。如49与51。 （6）大数是质数的两个数是互质数。如97与88。 （7）小数是质数，大数不是小数的倍数的两个数是互质数。如7和16。 （8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，

密码学实验-RSA公钥密码

实验报告 实验八、RSA公钥密码 实验目的： 熟练掌握RSA公钥密码算法原理及实现。 实验内容： 1、写出RSA公钥密码算法及其实现。 2、当取两素数分别为17、23，加密密钥为35时，写出其明文空间，并求出下列明文的密 文：1、15、17、23、48、235。 3、当取两素数分别为17、23，加密密钥为35时，求相应的解密密钥。 实验结果： 1.算法： Step1：选取两个大素数p和q，p和q保密 Step2：计算n=pq，f（n）=（p-1）（q-1），n公开，f（n）保密 Step3：随机选取正整数1 #include #include void main() { int i; double M,C,e,n,p,q,t; cout<<"请输入素数p:"; cin>>p; cout<<"请输入素数q:"; cin>>q;

n=p*q; t=(p-1)*(q-1); cout<<"请输入加密密钥e:"; cin>>e; cout<<"输入明文M:"; cin>>M; C=1; for(i=0;i

RSA加密算法java编程实现

一、RSA加密算法的原理 (1)、RSA算法描述 RSA公钥密码体制的基本原理：根据数论，寻求两个大素数比较简单，而将他们的乘积分解开则极为困难。 (2)、RSA算法密钥计算过程： 1.用户秘密选取两个大素数p 和q，计算n=pq，n称为 RSA算法的模数，公开。 2.计算出n的欧拉函数Φ(n) = (p-1)×(q-1)，保密。 3.从(1, Φ(n))中随机地选择一个与Φ(n)互素的数e作为加 密密钥，公开。 4.计算出满足下式的d 作为解密密钥，保密。 ed=1 mod Φ(n) (3)、RSA算法密钥： 加密密钥PK = |e, n| 公开 解密密钥SK = |d, n| 保密 (4)、RSA算法加密解密过程： RSA算法属于分组密码，明文在加密前要进行分组，分组 的值m 要满足：0 < m < n 加密算法：C = E(m) ≡me mod n 解密算法：m = D(c) ≡cd mod n (5)、RSA算法的几点说明： 1．对于RSA算法，相同的明文映射出相同的密文。

2.RSA算法的密钥长度：是指模数n的长度，即n的二进 制位数，而不是e或d的长度。 3.RSA的保密性基于大数进行因式分解很花时间，因此， 进行RSA加密时，应选足够长的密钥。512bit已被证明 不安全，1024bit也不保险。 4.RSA最快情况也比DES慢100倍，仅适合少量数据的加 密。公钥e取较小值的方案不安全。 二．RSA公钥加密算法的编程实现 以下程序是java编写的实现RSA加密及解密的算法 import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import java.security.interfaces.RSAPrivateKey; import java.security.interfaces.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码形式

常见公钥加密算法有哪些

常见公钥加密算法有哪些 什么是公钥加密公钥加密，也叫非对称（密钥）加密（public key encrypTIon），属于通信科技下的网络安全二级学科，指的是由对应的一对唯一性密钥（即公开密钥和私有密钥）组成的加密方法。它解决了密钥的发布和管理问题，是目前商业密码的核心。在公钥加密体制中，没有公开的是私钥，公开的是公钥。 常见算法RSA、ElGamal、背包算法、Rabin（Rabin的加密法可以说是RSA方法的特例）、Diffie-Hellman （D-H）密钥交换协议中的公钥加密算法、EllipTIc Curve Cryptography （ECC，椭圆曲线加密算法）。使用最广泛的是RSA算法（由发明者Rivest、Shmir和Adleman 姓氏首字母缩写而来）是著名的公开金钥加密算法，ElGamal是另一种常用的非对称加密算法。 非对称是指一对加密密钥与解密密钥，这两个密钥是数学相关，用某用户密钥加密后所得的信息，只能用该用户的解密密钥才能解密。如果知道了其中一个，并不能计算出另外一个。因此如果公开了一对密钥中的一个，并不会危害到另外一个的秘密性质。称公开的密钥为公钥；不公开的密钥为私钥。 如果加密密钥是公开的，这用于客户给私钥所有者上传加密的数据，这被称作为公开密钥加密（狭义）。例如，网络银行的客户发给银行网站的账户操作的加密数据。 如果解密密钥是公开的，用私钥加密的信息，可以用公钥对其解密，用于客户验证持有私钥一方发布的数据或文件是完整准确的，接收者由此可知这条信息确实来自于拥有私钥的某人，这被称作数字签名，公钥的形式就是数字证书。例如，从网上下载的安装程序，一般都带有程序制作者的数字签名，可以证明该程序的确是该作者（公司）发布的而不是第三方伪造的且未被篡改过（身份认证/验证）。 对称密钥密码体制 所谓对称密钥密码体制，即加密密钥与解密密钥是相同的密码体制。 数据加密标准DES属于对称密钥密码体制。它是由IBM公司研制出，于1977年被美国

密码学-RSA加密解密算法的实现课程设计报告

密码学课程报告《RSA加密解密算法》 专业：信息工程（信息安全） 班级：1132102 学号：201130210214 姓名：周林 指导老师：阳红星 时间：2014年1月10号

一、课程设计的目的 当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。 RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。 公钥加密算法中使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。此外，RSA加密系统还可应用于智能IC卡和网络安全产品。 二、RSA算法的编程思路 1.确定密钥的宽度。 2.随机选择两个不同的素数p与q，它们的宽度是密钥宽度的1/2。 3.计算出p和q的乘积n 。 4.在2和Φ(n)之间随机选择一个数e , e 必须和Φ(n)互素，整数e 用做加密密钥（其中Φ(n)=(p-1)*(q-1)）。 5.从公式ed ≡ 1 mod Φ(n)中求出解密密钥d 。 6.得公钥（e ，n ）, 私钥 (d , n) 。 7.公开公钥，但不公开私钥。 8.将明文P (假设P是一个小于n的整数)加密为密文C，计算方法为： C = Pe mod n 9.将密文C解密为明文P，计算方法为：P = Cd mod n 然而只根据n和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密 三、程序实现流程图： 1、密钥产生模块：

用实例讲解RSA加密算法(精)

可能各位同事好久没有接触数学了，看了这些公式不免一头雾水。别急，在没有正式讲解RSA加密算法以前，让我们先复习一下数学上的几个基本概念，它们在后面的介绍中要用到： 一、什么是“素数”？ 素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”（或“互素数”）？ 小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种（不限于此）： （1）两个质数一定是互质数。例如，2与7、13与19。 （2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与26。（3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。（4）相邻的两个自然数是互质数。如15与16。 （5）相邻的两个奇数是互质数。如49与51。 （6）大数是质数的两个数是互质数。如97与88。 （7）小数是质数，大数不是小数的倍数的两个数是互质数。如7和16。 （8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，这两个数为互质数。等等。 三、什么是模指数运算？ 指数运算谁都懂，不必说了，先说说模运算。模运算是整数运算，有一个整数m，以n 为模做模运算，即m mod n。怎样做呢？让m去被n整除，只取所得的余数作为结果，就

RSA加密算法及实现

数学文化课程报告题目：RSA公钥加密算法及实现

RSA公钥加密算法及实现 摘要 公钥密码是密码学界的一项重要发明，现代计算机与互联网中所使用的密码技术都得益于公钥密码。公钥密码是基于数学的上的困难问题来保证其性。其中RSA加密算法是一项重要的密码算法，RSA利用大整数的质数分解的困难性，从而保证了其相对安全性。但如果发现了一种快速进行质数分解的算法，则RSA算法便会失效。本文利用C 语言编程技术进行了RSA算法的演示[1]。 关键词：C语言编程、RSA算法、应用数学。

RSA public key encryption algorithm Abstract Public key cryptography is an important invention in cryptography, thanks to public key cryptography, and it is used in modern computer and Internet password technology. Public key cryptography is based on the mathematics difficult problem to ensure its confidentiality. The RSA public key encryption algorithm is an important cryptographic algorithm, RSA using the difficulty that large integer is hard to be factorized into prime Numbers to ensure it safety. But if you can find a kind of fast algorithm to do the factorization, RSA algorithm will be failure. In this paper we used C language programming technology to demonstrate the RSA algorithm. Keywords：C language programming、RSA algorithm、Applied mathematics

公钥加密算法

实验五公钥加密算法—RSA 一、实验目的 通过使用RSA算法对实验数据进行加密和解密，掌握公钥加密算法的基本原理，熟练掌握RSA算法各功能模块的工作原理和具体运算过程。 二、实验原理 RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。 1. RSA的密钥生成 RSA的算法涉及三个参数，n、e、d。 其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。鉴于现代对于大整数分解的水平不断增强，一般P、Q的取值都要求在1024位以上。 e和d是一对相关的值，e可以任意取，但要求e与(p-1)*(q-1)互质；再选择d，要求： (e*d)mod((p-1)*(q-1))=1。 、就是密钥对。一般将前者当作公钥，后者作为私钥使用。 2. RSA加密/解密过程 RSA加解密和解密的算法完全相同,设A为明文，B为密文，则： A=B^e mod n；B=A^d mod n； e和d可以互换使用，即： A=B^d mod n；B=A^e mod n; 三、实验环境 运行Windows或Linux操作系统的PC机，具有gcc(Linux)、VC（Windows）等C语言编译环境。 四、 实验内容和步聚 1.根据本讲义提供的RSA程序，分析RSA算法的实现过程： (1).利用：void GenerateKey(RSA_Key& PublicKey,RSA_Key& PrivateKey,unsigned int iKeySize)函数根据实际需要生成符合要求长度的公钥和私钥，大致步骤如下： a) 随机生成两个指定长度的大素数P，Q。 b) 计算N=P*Q，以及N的欧拉函数φ(N)=(P-1)*(Q-1)。 c) 随机生成一个与φ(N)互素的大整数E（公钥）。 d) 根据公式ed≡1(modΦ(N)),利用函数multi_inverse(1, Big*, Big, Big*)计算出 私钥D。 (2).将某个大整数赋值给一个Big型变量M（明文）。 (3).调用函数powmod(..,..,..,..)对明文M加密得到密文C。 (4).调用函数powmod(..,..,..,..)对密文C解密得到明文D。 (5).比较M与D是否一致，判断实验结果是否正确。

RSA加密算法

RSA加密算法 RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，这个算法经受住了多年深入的密码分析，虽然密码分析者既不能证明也不能否定RSA的安全性，但这恰恰说明该算法有一定的可信性，目前它已经成为最流行的公开密钥算法。 RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积（这是公认的数学难题）。 RSA的公钥、私钥的组成，以及加密、解密的公式可见于下表： 可能各位同事好久没有接触数学了，看了这些公式不免一头雾水。别急，在没有正式讲解RSA加密算法以前，让我们先复习一下数学上的几个基本概念，它们在后面的介绍中要用到： 一、什么是“素数”？ 素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”（或“互素数”）？ 小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种（不限于此）： （1）两个质数一定是互质数。例如，2与7、13与19。 （2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与 26。 （3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。 （4）相邻的两个自然数是互质数。如 15与 16。 （5）相邻的两个奇数是互质数。如 49与 51。 （6）大数是质数的两个数是互质数。如97与88。 （7）小数是质数，大数不是小数的倍数的两个数是互质数。如 7和 16。（8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，这两个数为互质数。等等。

用实例给新手讲解RSA加密算法

RSA加密算法是最常用的非对称加密算法，CFCA在证书服务中离不了它。但是有不少新来的同事对它不太了解，恰好看到一本书中作者用实例对它进行了简化而生动的描述，使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读，希望能够对时间紧张但是又想了解它的同事有所帮助。 RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，这个算法经受住了多年深入的密码分析，虽然密码分析者既不能证明也不能否定RSA的安全性，但这恰恰说明该算法有一定的可信性，目前它已经成为最流行的公开密钥算法。 RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积（这是公认的数学难题）。 RSA的公钥、私钥的组成，以及加密、解密的公式可见于下表： 可能各位同事好久没有接触数学了，看了这些公式不免一头雾水。别急，在没有正式讲解RSA加密算法以前，让我们先复习一下数学上的几个基本概念，它们在后面的介绍中要用到： 一、什么是“素数”？ 素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”（或“互素数”）？ 小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种（不限于此）： （1）两个质数一定是互质数。例如，2与7、13与19。 （2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与26。 （3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。 （4）相邻的两个自然数是互质数。如15与16。 （5）相邻的两个奇数是互质数。如49与51。 （6）大数是质数的两个数是互质数。如97与88。 （7）小数是质数，大数不是小数的倍数的两个数是互质数。如7和16。 （8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，这两个数为互质数。等等。 三、什么是模指数运算？ 指数运算谁都懂，不必说了，先说说模运算。模运算是整数运算，有一个整数m，以n为模做模运算，即m mod n。怎样做呢？让m去被n整除，只取所得的余数作为结果，就叫做模运算。例如，10 mod 3=1； 26 mod 6=2；28 mod 2 =0等等。

RSA加密算法(C实现)

RSA加密算法的编程实现 学号：0806580114 姓名：管睿 RSA算法是世界上第一个既能用于数据加密也能用于数字签名的非对称性加密算法。它易于理解和操作，所以流行甚广。算法的名字以发明者的名字命名，他们是：Ron Rivest，Adi Shamir 和Leonard Adleman。虽然RSA的安全性一直未能得到理论上的证实，但它经历了各种攻击，至今未被完全攻破。 在RSA算法中，先要获得两个不同的质数P和Q做为算法因子，再找出一个正整数E，使得E与 ( P - 1 ) * ( Q - 1 ) 的值互质，这个E就是私钥。找到一个整数D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立1[1]，D就是公钥1。设N为P和Q的乘积，N则为公钥2。加密时先将文转换为一个或一组小于N的整数I，并计算I D mod N的值M，M就密文。解密时将密文M E mod N，也就是M的E次方再除以N所得的余数就是明文。 因为私钥E与( P - 1 ) * ( Q - 1 )互质，而公钥D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N，如果想要得到E，必须得出( P - 1 ) * ( Q - 1 )，因而必须先对N进行因数分解。如果N很大那么因数分解就会非常困难，所以要提高加密强度P和Q的数值大小起着决定性的因素。一般来讲当P和Q都大于2128时，按照目前的机算机处理速度破解基本已经不大可能了。 RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先作HASH 运算。RSA 的安全性。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。*/ #include #include #include using namespace std;//RSA算法所需参数 typedef struct RSA_PARAM_Tag { unsigned __int64 p, q; //两个素数，不参与加密解密运算 unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算 unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1 unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1 unsigned __int64 s; //块长，满足2^s<=n的最大的s，即log2(n)

RSA算法公钥加密算法

RSA1978年，MIT的Rivest、Shamir、Adleman提出RSA算法 非对称加密（公开密钥加密）密码学的一次革命，定义：KA≠KB ，KA、E和D公开 特点： 基于数论原理(大数分解难题) 是目前应用最广泛的公钥加密算法 属于块加密算法 在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 RSA算法原理 l 定义：RSA加密算法 确定密钥： 1. 找到两个大质数，p,q 2. Let n=pq 3. let m=(p-1)(q-1);Choose e and d such that de=1(%m). 4. Publish n and e as public key. Keep d and n as secret key. 加密： C=M^e(%n) 解密： M=(C^d)%n 其中C=M^e(%n) 为C%n=(M^e)%n 存在的主要问题是大数计算和大数存储的问题。 什么是RSA RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。

RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。 这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。 RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。 RSA的算法涉及三个参数，n、e1、e2。 其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。 e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。 (n及e1),(n及e2)就是密钥对。 RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n； e1和e2可以互换使用，即： A=B^e2 mod n；B=A^e1 mod n； 一、RSA 的安全性 RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。 二、RSA的速度 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。 三、RSA的选择密文攻击 RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：

用java编程实现RSA加密算法

用java编程实现RSA加密算法 RSA加密算法是目前应用最广泛的公钥加密算法，特别适用于通过Internet传送的数据，常用于数字签名和密钥交换。那么我今天就给大家介绍一下如何利用Java编程来实现RSA 加密算法。 一、RSA加密算法描述 RSA加密算法是1978年提出的。经过多年的分析和研究，在众多的公开密钥加密算法中，RSA加密算法最受推崇，它也被推荐为公开密钥数据加密标准。 由数论知识可知，若将一个具有大素数因子的合数进行分解是很困难的，或者说这个问题的计算量是令人望而生畏的，而RSA加密算法正是建立在这个基础上的。 在RSA加密算法中，—个用户A可根据以下步骤来选择密钥和进行密码转换： （1）随机的选取两个不同的大素数p和q（一般为100位以上的十进制数），予以保密；（2）计算n=p*q，作为用户A的模数，予以公开； （3）计算欧拉（Euler）函数z=（p-1）*（q-1），予以保密； （4）随机的选取d与z互质，作为A的公开密钥； （5）利用Euclid算法计算满足同余方程e*d≡1modz的解d，作为用户A的保密密钥；（6）任何向用户A发送信息M的用户，可以用A的公开模数D和公开密钥e根据C=Me mod n得到密文C；

RSA加密算法的安全性是基于大素数分解的困难性。攻击者可以分解已知的n，得到p和q，然后可得到z；最后用Euclid算法，由e和z得到d。然而要分解200位的数，需要大约40亿年。 二、用Java语言描述RSA加密算法的原理 假设我们需要将信息从机器A传到机器B，首先由机器B随机确定一个private_kcy（我们称之为密钥），可将这个private_key始终保存在机器B中而不发出来。然后，由这个private_key计算出public_key（我们称之为公钥）。这个public_key的特性是：几乎不可能通过该public_key计算生成它的priyate_key。接下来通过网络把这个public_key传给机器A，机器A收到public_key后，利用public_key将信息加密，并把加密后的信息通过网络发送到机器B，最后机器B利用已知的pri.rate_key，就可以解开加密信息。 步骤： （1）首先选择两个大素数p和q，计算n=p*q；m=（p-1）（q一1）； （2）而后随机选择加密密钥public_key，要求和m互质（比如public_key=m-1）；（3）利用Euclid算法计算解密密钥priyate_key，使private_key满足public_key*private_key—1(mod m)，其中public_key，n是作为公钥已知，priVate_key 是密钥； （4）加密信息text时，利用公式secretWord=texI^Public_key (mod n)得到密文8ecretword； （5）解密时利用公式word=text^priVate_key(mod n)得到原文word=text。

RSA加密算法的研究与实现

RSA加密算法的研究与实现 摘要：在信息时代，如何保证信息的安全是个十分重要的问题。在多年的发展中,人们提出了许多不同类型的加密算法。其中RSA加密算法是公认的最经典的非对称密码算法之一。本文首先介绍了课题研究的背景和意义，再介绍了使用的研究工具，然后使用Verilog 硬件描述语言设计了一个RSA的加密系统，最后通过Modelsim进行了仿真测试。结果证明本文通过硬件实现的RSA加密算法可以有效的加密数据。 关键词：RSA；Verilog；Modelsim；硬件仿真； Abstract：In the information age, the security of information is a very important issue. In the years of development, people have proposed many different types of encryption algorithms. RSA encryption algorithm is one of the most classical asymmetric cryptographic algorithms. This paper first introduces the background and significance of the research, then introduces the research tools, then designs a RSA encryption system using Verilog hardware description language, and finally performs simulation tests through Modelsim. The result proves that the RSA encryption algorithm implemented in hardware can be effective and efficient. Keywords：RSA; Verilog; Modelsim; Hardware simulation;