查看: 2192|回复: 5

RSA

[复制链接]
  • TA的每日心情

    2017-5-1 15:59
  • 签到天数: 18 天

    连续签到: 1 天

    [LV.4]偶尔看看III

    发表于 2016-5-15 19:43:41 | 显示全部楼层 |阅读模式
    本帖最后由 零度 于 2016-5-17 21:13 编辑
    1. {:wyy:}{:wyy:}{:wyy:}{:dk:}
    2. 公钥加密算法—RSA
    3. 一、实验目的
    4. 通过使用 RSA 算法对实验数据进行加密和解密,掌握公钥加密算法的基本原理,熟练掌握 RSA 算法各功能模块的工作原理和具体运算过程。
    5. 二、实验原理
    6. RSA 公钥加密算法是 1977 年由 Ron Rivest、Adi Shamirh 和 LenAdleman 在(美国麻省理工学院)开发的。RSA 取名来自开发他们三者的名字。RSA 是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的所有密码攻击,已被 ISO 推荐为公钥数据加密标准。RSA 算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但那时想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。
    7. 1.RSA 的密钥生成RSA 的算法涉及三个参数,n、e、d。
    8. 其中,n 是两个大质数 p、q 的积,n 的二进制表示时所占用的位数,就是所谓的密钥长度。鉴于现代对于大整数分解的水平不断增强,一般 P、Q 的取值都要求在 1024位以上。e 和 d 是一对相关的值,e 可以任意取,但要求 e 与(p-1)*(q-1)互质;再选择 d,要求:(e*d)mod((p-1)*(q-1))=1。<n,e>、<n,d>就是密钥对。一般将前者当作公钥,后者作为私钥使用。
    9. 2.RSA 加密/解密过程
    10. 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;
    11. 三、实验环境
    12. 运行 Windows 或 Linux 操作系统的 PC 机,具有 gcc(Linux)、VC(Windows)等 C 语言编译环境。
    13. 四、实验内容和步骤
    14. 1.根据本讲义提供的 RSA 程序,分析 RSA 算法的实现过程:
    15. (1)利用:void GenerateKey ( RSA_Key & Public Key , RSA_Key &  PrivateKey,unsigned int iKeySize)函数根据实际需要生成符合要求长度的公钥和私钥,大致步骤如下:
    16. a)随机生成两个指定长度的大素数 P,Q。
    17. b) 计算 N=P*Q,以及 N 的欧拉函数 φ(N)=(P-1)*(Q-1)。
    18. c) 随机生成一个与 φ(N)互素的大整数 E(公钥)。
    19. d) 根据公式 ed≡1(modΦ(N)),利用函数 multi_inverse(1, Big*, Big, Big*)计算出私钥 D。
    20. (2)将某个大整数赋值给一个 Big 型变量 M(明文)。
    21. (3)调用函数 powmod(..,..,..,..)对明文 M 加密得到密文 C。
    22. (4)调用函数 powmod(..,..,..,..)对密文 C 解密得到明文 D。
    23. (5)比较 M 与 D 是否一致,判断实验结果是否正确。
    24. (6)调换公钥、私钥后重复以上步骤,验证 e、d 的可互换性,并思考为什么可以这样做。
    25. 2.使用实例分析
    26. 取 p=11,q=13。
    27. 首先计算:n=pq=11×13=143; φ(n)=(p-1)(q-1)=(11-1) ×(13-1)=120
    28. 然后选择 e=17,满足 gcd(e,φ(n))=gcd(17,120)=1,然后根据 ed≡1(modφ(N))计算 d=113。则:公钥:<17,143>、私钥:<113, 143>。
    29. 设明文信息:m=24。对明文信息加密,得密文为:
    30. c≡m^e % N=24^17%143=7
    31. 密文 c 经过公开信道发送到接收方后,接收方用私钥 d 对密文进行解密:
    32. m≡c^d % N=7^113%143=24
    33. 从而正确地恢复出明文。
    34. 五、思考题
    35. 1.阐明 RSA 密钥生成以及加密、解密流程
    36. a)RSA密钥生成:找出p,q,r三个数,p,q互质,r与(p-1)(q-1)互质,p,q,r这三个数便是private key。找出m,使得mr==1 mod (p-1)(q-1)计算n=pq,m,n这两个数便是public key
    37. b)流程:用户A用B的公钥对key进行加密,B收到消息后用自己的私钥进行解密获取key。
    38. 2.使用提供的模块编写 RSA 加密程序对数据进行加密和解密,提交程序代码和执行结果。
    39. 3.程序代码:
    40. 1.#include "time.h"
    41. 2.#include "big.h"
    42. 3.#include <iostream>
    43. 4.
    44. 5.#define BUFFERSIZE 4096
    45. 6.
    46. 7.static miracl* mip = mirsys ( BUFFERSIZE, 0 );
    47. 8.
    48. 9.struct RSA_Key//密钥结构体
    49. 10.{
    50. 11.        Big e;
    51. 12.        Big N;
    52. 13.};
    53. 14.
    54. 15.
    55. 16.int main(void)
    56. 17.{
    57. 18.        void GenerateKey(RSA_Key& PublicKey,RSA_Key& PrivateKey,unsigned int iKeySize);//密钥生成函数
    58. 19.        
    59. 20.        RSA_Key PublicKey;//公钥 <e,N>
    60. 21.        RSA_Key PrivateKey;//私钥 <d,N>
    61. 22.        Big M;//明文M
    62. 23.        Big C;//密文C
    63. 24.        Big D;//解密文D
    64. 25.        unsigned int iKeySize;
    65. 26.        std::cout<<"请输入加密密钥长度(单位比特)"<<std::endl;
    66. 27.        std::cin>>iKeySize;
    67. 28.
    68. 29.        std::cout<<"密钥生成中......"<<std::endl;
    69. 30.        GenerateKey(PublicKey,PrivateKey,iKeySize/4);//产生iKeySize bit密钥
    70. 31.        std::cout<<"密钥生成完毕"<<std::endl;
    71. 32.
    72. 33.        std::cout<<"请输入明文:"<<std::endl;
    73. 34.        std::cin>>std::hex>>M;
    74. 35.
    75. 36.        powmod(M.getbig(), PublicKey.e.getbig(), PublicKey.N.getbig(), C.getbig());//调用加密函数计算:C=(M^e)%N
    76. 37.        std::cout<<"RSA加密密文:"<<std::endl;
    77. 38.        std::cout<<std::hex<<C<<std::endl;
    78. 39.
    79. 40.        powmod(C.getbig(), PrivateKey.e.getbig(), PrivateKey.N.getbig(), D.getbig());//解密与加密使用同一函数,只是密钥不同即:D=(C^d)%N
    80. 41.        std::cout<<"解密:"<<std::endl;
    81. 42.        std::cout<<std::hex<<D<<std::endl;//若D与M相同,可认为正确
    82. 43.        
    83. 44.
    84. 45.        system("Pause");
    85. 46.        return 0;
    86. 47.}
    87. 48.
    88. 49.void GenerateKey(RSA_Key& PublicKey,RSA_Key& PrivateKey,unsigned int iKeySize)
    89. 50.{
    90. 51.        void GeneratePrime(Big* bigGenPrime,int iLength, int iBase);
    91. 52.        unsigned int InitRandom();
    92. 53.
    93. 54.        unsigned int RAND_SEED = InitRandom();
    94. 55.        irand(RAND_SEED);
    95. 56.        mip->IOBASE = 16;
    96. 57.        set_io_buffer_size( BUFFERSIZE);
    97. 58.        
    98. 59.        Big E,D,P,Q,N,Z;
    99. 60.
    100. 61.
    101. 62.        GeneratePrime(&P, iKeySize /4, 16);//生成强素数P
    102. 63.        GeneratePrime(&Q, iKeySize /4, 16);//生成强素数Q
    103. 64.        N =P *Q;//计算N
    104. 65.        Z = (P-1) * (Q-1);//计算N的欧拉函数
    105. 66.
    106. 67.        do
    107. 68.        {
    108. 69.                GeneratePrime(&D, iKeySize /4, 16);
    109. 70.
    110. 71.        }while(Z % D == 0);//反复生成素数,直到该素数与Z互素,得到密钥D
    111. 72.
    112. 73.
    113. 74.        
    114. 75.        multi_inverse(1, &D, Z, &E);                // 根据公式ed mod z = 1 计算E
    115. 76.
    116. 77.        PublicKey.e=E;
    117. 78.        PublicKey.N=N;
    118. 79.
    119. 80.        PrivateKey.e=D;
    120. 81.        PrivateKey.N=N;
    121. 82.
    122. 83.        return;
    123. 84.}
    124. 85.void GeneratePrime(Big* bigGenPrime,int iLength, int iBase)
    125. 86.{
    126. 87.        *bigGenPrime = 4;                // 任取非素数
    127. 88.        set_io_buffer_size(50000);
    128. 89.        while (!isprime(bigGenPrime->getbig()))//若非素数则:
    129. 90.        {
    130. 91.                bigdig (iLength,iBase,bigGenPrime->getbig());//重新生成
    131. 92.        }
    132. 93.        return;
    133. 94.}
    134. 95.unsigned int InitRandom()//随机数生成函数
    135. 96.{
    136. 97.        __time64_t long_time;               
    137. 98.    srand((unsigned)time(&long_time));
    138. 99.    unsigned int RAND_SEED=rand();
    139. 100.        return RAND_SEED;
    140. 101.}
    复制代码
  • TA的每日心情

    2017-5-1 15:59
  • 签到天数: 18 天

    连续签到: 1 天

    [LV.4]偶尔看看III

     楼主| 发表于 2016-5-15 19:45:12 | 显示全部楼层
    有没有会的大仙

    该用户从未签到

    发表于 2016-5-15 20:00:55 | 显示全部楼层
    你这标题能不能改改

    点评

    改了,别太介  详情 回复 发表于 2016-5-17 21:30
  • TA的每日心情
    奋斗
    2017-2-28 02:11
  • 签到天数: 234 天

    连续签到: 1 天

    [LV.7]常住居民III

    发表于 2016-5-15 22:25:03 | 显示全部楼层
    我觉得吧,你到这发还不如到开源社区问,那里才是高手云集的地方。
    你没发现吗,这里的无非就是破解版和一些采集而已。
    当然,我为啥没事关注下这里,就是仰慕这些“大神”门

    点评

    谢谢推荐  详情 回复 发表于 2016-5-17 21:31
  • TA的每日心情

    2017-5-1 15:59
  • 签到天数: 18 天

    连续签到: 1 天

    [LV.4]偶尔看看III

     楼主| 发表于 2016-5-17 21:30:39 | 显示全部楼层
    blackhat 发表于 2016-5-15 20:00
    你这标题能不能改改

    改了,别太介
  • TA的每日心情

    2017-5-1 15:59
  • 签到天数: 18 天

    连续签到: 1 天

    [LV.4]偶尔看看III

     楼主| 发表于 2016-5-17 21:31:43 | 显示全部楼层
    yzwm110 发表于 2016-5-15 22:25
    我觉得吧,你到这发还不如到开源社区问,那里才是高手云集的地方。
    你没发现吗,这里的无非就是破解版和一 ...

    谢谢推荐
    您需要登录后才可以回帖 登录 | 注册

    本版积分规则

    站长推荐上一条 /1 下一条