RSA算法和RSA数字签名算法的实现.doc

1、基于 verilog 的 RSA 实现 和 RSA 数字签名 题 目 ： 基于 verilog 的 RSA 实现 和 RSA 数字签名 学 院： 专 业： 姓 名 ： 学 号： 摘要 : RSA 算法是一种公钥密码算法 .实现 RSA 算法包括生成 RSA 密 钥 ,用 RSA 加密规则和解密规则处理数据 .RSA数字签名算法利用 RSA算法实现数字签名 .本文详述了 RSA算法的基本原理 , RSA 加密算法的实现以及如何利用 RSA 实现数字签名 . 关键字 : RSA 算法 , 数字签名 , 公开密钥 , 私人密钥 , 加密 , 解密 一 、 引言 随着网络技术的飞速发展 ,信息安全性已

2、成为亟待解决的问题 .公钥密码体制中 ,解密和加密密钥不同 ,解密和加密可分离 ,通信双方无须事先交换密钥就可建立起保密通信 ,较好地解决了传统密码体制在网络通信中出现的问题 .另外 ,随着电子商务的发展 ,网络上资金的电子 交换日益频繁 ,如何防止信息的伪造和欺骗也成为非常重要的问题 .数字签名可以起到身份认证 ,核准数据完整性的作用 .目前关于数字签名的研究主要集中基于公钥密码体制的数字签名 . 公钥密码体制的特点是 :为每个用户产生一对密钥 (PK 和 SK);PK 公开 ,SK 保密 ;从 PK 推出 SK是很困难的 ;A,B双方通信时 ,A通过任何途径取得 B的公钥 ,用B 的公钥加

3、密信息 .加密后的信息可通过任何不安全信道发送 .B 收到密文信息后 ,用自己私钥解密恢复出明文 . 公钥密码体制已成为确保信息的安全性的关键技术 .RSA 公钥密码体制到目前为 止还是一种认可为安全的体制 .本文详述了 RSA 算法和用 RSA算法实现数字签名的理论 ,以及它们在实际应用中的实现 . 二 、 RSA算法和 RSA数字签名算法的理论描述 1 RSA 算法 RSA 算法的理论基础是一种特殊的可逆模幂运算 . 设 n是两个不同奇素数 p和 q 的积 ,即 :n=pq, (n)=(p-1)(q-1). 定义密钥空间 k=(n,p,q,d,e)|n=pq,p和 q是素数 ,de1 mo

4、d (n),e为随机整数 , 对每一个 k=(n,p,q,d,e), 定义加密变换为 Ek(x)=xb mod n,xZn; 解密变换为 Dk(x)=ya mod n,yZn,Zn 为整数集合 . 公开 n和 b,保密 p,q 和 a. 为证明加密变换 Ek和解密变换 Dk满足 Dk(Ek(x)=x,这里不加证明的引用下面两个定理 : 定理 1(Euler) 对 任 意 的 a(Zn*, 有 a(n)(1 mod n, 其中Zn*=x(Zn|gcd(x,n)=1,( )表示 Euler 函数 . 定理 2 设 p和 q是两个不同的素数 ,n=pq, (n)=(p-1)(q-1),对任意的 x(

5、Zn及任意的非负整数 k,有 xk(n)+1(x mod n. 现在来证明 RSA 算法的加密变换和解密变换的正确性 . 证明 : 对于加密变换 Ek 和解密变换 Dk.因为 ab1 mod (n),所以可设ab=t(n)+1,t 是整数且 t1.对于任意的 xZn,有 Dk(Ek(x)Dk(xb) (xb)axt(n)+1x mod n.因此解密过程是正确的 . 2 RSA 数字签名算法 RSA 数字签名算法的过程为 :A 对明文 m 用解密变换作 : s Dk (m)=md mod n,其中 d,n 为 A 的私人密钥 ,只有 A 才知道它 ;B 收到 A 的签名后 ,用 A 的公钥和加密

6、变 换得到明文 ,因 : Ek(s)= Ek(Dk (m)= (md)e mod n,又 de1 mod (n)即de=l(n)+1,根据欧拉定理 m(n)=1 mod n,所以 Ek(s)=ml(n)+1=m(n)em=m mod n.若明文 m和签名 s 一起送给用户 B,B 可以确信信息确实是 A发送的 .同时 A 也不能否认送给这个信息 ,因为除了 A 本人外 ,其他任何人都无法由明文 m 产生 s.因此 RSA数字签名方案是可行的 . 但是 RSA 数字签名算法存在着因计算方法本身同构造成签名易被伪造和计算时间长的弱点 ,因此实际对文件 签名前 ,需要对消息做 MD5变换 . MD5

7、函数是一种单向散列函数 ,它将任意长度的消息压缩成 128位的消息摘要 .应用 MD5的单向性 (即给定散列值 ,计算消息很难 )和抗碰撞性 (即给定消息 M,要找到另一消息 M 并满足两者的散列值很难 ),可以实现信息的完整性检验 .另外该函数的设计不基于任何假设和密码体制而直接构造 ,执行的速度快 ,是一种被广泛认可的单向散列算法 . 三 、 RSA算法的实现 RSA 算法的实现分为 :生成密钥 ,加密 ,解密 1 密钥的生成 ： 私钥的产生：本实验鉴于运算速度，和存储器的选择。采用由小 到大选择一与(P-1)*(Q-1)互质的 e值。 公钥的产生：通过 e*d=1mod(n)算出 d的值

8、， d即为公钥的值。 2 生成 RSA 密钥需完成下列步骤 : (1) 选择 e 的值为 3至 65536; (2) 随机生成大素数 p,直到 gcd (e,p-1)=1; 其中 gcd(a,b)表示 a,b取最大公约数 (3) 随机生成不同于 p的大素数 q,直到 gcd (e,q-1)=1; (4) 计算 n=pq , (n)=(p-1)(q-1); (5) 计算 d,满足 de1 (mod (n); (6) 计算 d mod (p-1), d mod (q-1); (7) 计算 q-1 mod p; (8) 将 n,e 放入 RSA 公钥 ;将 n,e,d mod (p-1),d mod

9、 (q-1) q-1 mod p 放入 RSA私钥 . 2.1 随机数的产生 随机数不仅用于密钥生成 ,也用作公钥加密时的填充字符 .它必须具有足够的随机性 ,以防止破译者掌握随机数的规律性后重现密钥的配制过程或者探测到加密块中的明文 .因为在计算机上不可能产生真正的随机数 ,实际采用周期大于2256位的伪随机序列发生器 . 实现过程为 : 通过 PRBS 算法，实现 PRBS 随机码。通过一定时间随机选出一个素数。 2.2 素数的产生 对随机数作素性检测 ,若通过则为素数 ;否则增加一个步长后再做素性检测 ,直到找出素数 .素性检测采用 Fermat 测试 .这个算法的理论依据是费尔马小定理

10、 :如果 m是一个素数 ,且 a不是 m的倍数 ,那么根据费尔马小定理有 :a m-1=1 ( mod m). 实际应用时 :a m-1 = 1 ( mod m) a m = a ( mod m) a= a m ( mod m), 因此对于整数 m,只需计算 a m ( mod m),再将结果与 a 比较 ,如果两者相同 ,则 m为素数 .选取 a=2,则 a一定不会是任何素数的倍数 . 3 加密过程 加密规则为 :Ek(x)=xb mod n,xZn 加密过程的输入为 :明文数据 D,模数 n, 加密指数 e(公钥加密 )或解密指数d(私钥加密 ).输出为密文 .D 的长度不超过 log2n

11、-11,以确保转换为 PKCS 格式时 ,填充串的数目不为 0. 格式化明文 . 采用 PKCS 格式 : EB = 00 | BT | PS | 00 | D 其中 BT表示块的类型 ,PS为填充串 ,D为明文数据 .开头为 0确保 EB 长度大于 k.对公钥加密 BT=02,对私钥解密 BT=01.当 BT=02时 ,PS 为非 0随机数 ;当 BT=01,PS 值为 FF. 明文由字符型数据转换成整型数据 . RSA 计算 . 为整数加密块 x 作模幂运算 :y = xc mod n,0 ruslt_nub2)|ruslt_nub1%ruslt_nub2!=0) begin P=rusl

12、t_nub1; Q=ruslt_nub2; end else begin P=b0; Q=b0; end end always begin begin n_tem=(P-1)*(Q-1); n=P*Q; in_dec15:0=input_number3:0+10*input_number7:4+100*input_number11:8+1000*input_number15:12; if(in_tem) int_nub=(e*x-1)%n_tem; else x=x+1; if(int_nub%1=0) begin d=int_nub; x=1; end else int_nub=0; end

13、 endmodule 八 、通过 Quartus II 仿真的底层电路图： i n p u t _ n u m b e r 1 2 . . 1 5 m u l t co r e : m u l t _ co r e : r o m o u t 0 5 0m u l t co r e : m u l t _ co r e : r o m o u t 0 6 1m u l t co r e : m u l t _ co r e : r o m o u t 0 7 2m u l t co r e : m u l t _ co r e : r o m o u t 0 8 3m u l t co r e

14、 : m u l t _ co r e : r o m o u t 0 9 4m u l t co r e : m u l t _ co r e : r o m o u t 0 1 0 5m u l t co r e : m u l t _ co r e : r o m o u t 0 1 1 6m u l t co r e : m u l t _ co r e : r o m o u t 0 1 2 7m u l t co r e : m u l t _ co r e : r o m o u t 0 1 3 8i n p u t _ n u m b e r 8 . . 1 1 m u l t

15、 co r e : m u l t _ co r e : r o m o u t 0 5 0m u l t co r e : m u l t _ co r e : r o m o u t 0 6 1m u l t co r e : m u l t _ co r e : r o m o u t 0 7 2m u l t co r e : m u l t _ co r e : r o m o u t 0 8 3m u l t co r e : m u l t _ co r e : r o m o u t 0 9 4m u l t co r e : m u l t _ co r e : r o m

16、o u t 0 1 0 5A d d 3 0A d d 4 0A d d 5 0i n _ d e c 3 0i n _ d e c 4 2i n _ d e c 5 4i n _ d e c 6 6i n _ d e c 7 8i n _ d e c 8 1 0i n _ d e c 9 1 2i n _ d e c 1 0 1 4i n _ d e c 1 1 1 6i n _ d e c 1 2 1 8i n _ d e c 1 3 2 0i n p u t _ n u m b e r 0 o u t _ d e c 0 . . 4 7 G N DO U T 1 . . 4 8 C I

17、ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 9 6 9 F )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 9 6 1 7 )C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 9 6 1 7 )1C I ND A T A AD A T A B

18、D A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 9 8 E )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 9 6 1 7 )1C I ND A T A AD A T A BC O M B O U TL O G I C _ C E L L _ C O M B ( 8 7 8 7 )D A T A AD A T A BD A T A CD A T A DC O M B O U TL O G I C

19、 _ C E L L _ C O M B ( F 8 8 0 )D A T A AD A T A BD A T A CD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( 8 7 7 8 )D A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 6 8 8 )D A T A CD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( 0 F F 0 )D A T A AD A T A B

20、D A T A CD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( C 8 8 0 )D A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 6 8 8 )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 9 8 E )1D A T A AD A T A BD A T A DC O M B O U TC O U

21、 TL O G I C _ C E L L _ C O M B ( 6 6 8 8 )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 9 0 6 )C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 9 8 E )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L

22、 L _ C O M B ( 9 6 1 7 )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 9 8 E )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 9 6 1 7 )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 9

23、 8 E )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 9 6 1 7 )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 9 8 E )1C I ND A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 3 C 3 F )1C I ND A T A BD A T

24、A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( C 3 0 C )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 9 6 1 7 )1C I ND A T A AD A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 6 9 8 E )1 C I ND A T A AD A T A BD A T A DC O M B O U TC

25、 O U TL O G I C _ C E L L _ C O M B ( 9 6 1 7 )1C I ND A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( C 3 0 C )1 C I ND A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( 3 C 3 F )1 C I ND A T A BD A T A DC O M B O U TC O U TL O G I C _ C E L L _ C O M B ( C 3 0

26、 C )1C I N C O M B O U TL O G I C _ C E L L _ C O M B ( F 0 F 0 )C I N C O M B O U TL O G I C _ C E L L _ C O M B ( F 0 F 0 )a l w a y s0 2P 1 0P 2 1P 3 2P 4 3P 5 4P 6 5Q 1 0Q 2 1Q 3 2Q 4 3Q 5 4Q 6 5r u sl t _ n u b 1 7 G N DO U T 1 . . 1 5 D A T A AD A T A BD A T A CD A T A DC O M B O U TL O G I C

27、_ C E L L _ C O M B ( F F F E )D A T A BD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( C C 0 0 )D A T A CD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( F 0 0 0 )D A T A CD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( F 0 0 0 )D A T A BD A T A DC O M B O U TL O G I C _ C E L L _

28、C O M B ( C C 0 0 )D A T A BD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( C C 0 0 )D A T A BD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( C C 0 0 )D A T A CD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( F 0 0 0 )D A T A BD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( C

29、C 0 0 )D A T A CD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( F 0 0 0 )D A T A BD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( C C 0 0 )D A T A AD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( A A 0 0 )D A T A AD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( A A 0 0 )D A T

30、 A BD A T A CD A T A DC O M B O U TL O G I C _ C E L L _ C O M B ( C C F 0 )o u t _ d e c 4 7 _ C O M BO U To u t _ d e c 4 6 _ C O M BO U To u t _ d e c 4 5 _ C O M BO U To u t _ d e c 4 4 _ C O M BO U To u t _ d e c 4 3 _ C O M BO U To u t _ d e c 4 2 _ C O M BO U To u t _ d e c 4 1 _ C O M BO U T

31、o u t _ d e c 4 0 _ C O M BO U To u t _ d e c 3 9 _ C O M BO U To u t _ d e c 3 8 _ C O M BO U To u t _ d e c 3 7 _ C O M BO U To u t _ d e c 3 6 _ C O M BO U To u t _ d e c 3 5 _ C O M BO U To u t _ d e c 3 4 _ C O M BO U To u t _ d e c 3 3 _ C O M BO U To u t _ d e c 3 2 _ C O M BO U To u t _ d e

32、c 3 1 _ C O M BO U To u t _ d e c 3 0 _ C O M BO U To u t _ d e c 2 9 _ C O M BO U To u t _ d e c 2 8 _ C O M BO U To u t _ d e c 2 7 _ C O M BO U To u t _ d e c 2 6 _ C O M BO U To u t _ d e c 2 5 _ C O M BO U To u t _ d e c 2 4 _ C O M BO U To u t _ d e c 2 3 _ C O M BO U To u t _ d e c 2 2 _ C O

33、M BO U To u t _ d e c 2 1 _ C O M BO U To u t _ d e c 2 0 _ C O M BO U To u t _ d e c 1 9 _ C O M BO U To u t _ d e c 1 8 _ C O M BO U To u t _ d e c 1 7 _ C O M BO U To u t _ d e c 1 6 _ C O M BO U To u t _ d e c 1 5 _ C O M BO U To u t _ d e c 1 4 _ C O M BO U To u t _ d e c 1 3 _ C O M BO U To u

34、t _ d e c 1 2 _ C O M BO U To u t _ d e c 1 1 _ C O M BO U To u t _ d e c 1 0 _ C O M BO U To u t _ d e c 9 _ C O M BO U To u t _ d e c 8 _ C O M BO U To u t _ d e c 7 _ C O M BO U To u t _ d e c 6 _ C O M BO U To u t _ d e c 5 _ C O M BO U To u t _ d e c 4 _ C O M BO U To u t _ d e c 3 _ C O M BO U

35、 To u t _ d e c 2 _ C O M BO U To u t _ d e c 1 _ C O M BO U To u t _ d e c 0 _ C O M BO U TG N D _ C O M BO U Tl p m _ m u l t : M u l t 4 _ O U TA d d 3 4 _ C O U TA d d 2 1 _ C O M BO U TA d d 3 6 _ C O M BO U TA d d 3 6 _ C O U Tl p m _ m u l t : M u l t 1 _ O U Tl p m _ d i v i d e : M o d 0 _

36、a l t _ u _ d i v _ 0 0 f : d i v i d e r: o p _ 6 0a l w a y s 0 0 _ C O M BO U Tl p m _ d i v i d e : M o d 0 _ a l t _ u _ d i v _ 0 0 f : d i v i d e r: o p _ 6 2a l w a y s 0 1 _ C O M BO U Tru s l t _ n u b 1 1 _ C O M BO U Tru s l t _ n u b 1 2 _ C O M BO U Tru s l t _ n u b 1 3 _ C O M BO U

37、Tru s l t _ n u b 1 4 _ C O M BO U Tru s l t _ n u b 1 5 _ C O M BO U Tru s l t _ n u b 1 6 _ C O M BO U Tru s l t _ n u b 2 1 _ C O M BO U Tru s l t _ n u b 2 2 _ C O M BO U Tru s l t _ n u b 2 3 _ C O M BO U Tru s l t _ n u b 2 4 _ C O M BO U Tru s l t _ n u b 2 5 _ C O M BO U Tru s l t _ n u b 2

38、6 _ C O M BO U Tre g e r 7 _ C O M BO U Tre g e r 0 cl kct rl _ O U T C L Kru s l t _ n u b 1 7 _ C O M BO U T111i n p u t _ n u m b e r 0 . . 1 5 l p m _ m u l t : M u l t 2A d d 3 1 0i n _ d e c 4 2A d d 3 4 A d d 4 2A d d 3 1 2A d d 2 1A d d 3 0A d d 4 4A d d 4 0i n _ d e c 5 4i n _ d e c 6 6i n

39、_ d e c 7 8i n _ d e c 8 1 0i n _ d e c 9 1 2i n _ d e c 1 0 1 4i n _ d e c 1 1 1 6i n _ d e c 1 2 1 8i n _ d e c 1 3 2 0A d d 4 6A d d 4 8A d d 4 1 0A d d 4 1 2A d d 4 1 4A d d 4 1 6A d d 4 1 8A d d 5 0l p m _ m u l t : M u l t 1a l w a y s 0 2P 1 0P 2 1P 3 2P 4 3P 5 4P 6 5Q 1 0Q 2 1Q 3 2Q 4 3Q 5 4

40、ru s l t _ n u b 1 7 Q 6 5A d d 3 8A d d 2 2A d d 3 2i n _ d e c 3 0A d d 2 3l p m _ m u l t : M u l t 3A d d 2 0l p m _ m u l t : M u l t 4九、 结束语 ： 本文讨论了 RSA 算法的基本原理和 RSA 的 verilog 实现 .RSA 算法是一种安全技术 ,但是 RSA 算法的安全性只是一种计算安全性 ,绝不是无条件的安全性 ,这是由它的理论基础决定的 .本文基于硬件实现 RSA 算法，在实际应用中发挥了FPGA 的高速性和 FPGA 在实际嵌入式系统中的方便性。 但是本文有很多不足，本文的实现比较简单，没有把 e 值取得足够大。而且也没有考虑由于密钥和算法中巨大的数字而引起的存储空间的问题 ，所以本文离应用还有一段距离。