rsa公钥加密算法的提出者_rsa生成公钥和私钥的步骤「建议收藏」

rsa公钥加密算法的提出者_rsa生成公钥和私钥的步骤「建议收藏」RSA公钥加密算法1.什么是RSA?计算机中常用的加密技术分为两类:对称加密、非对称加密

RSA公钥加密算法

1. 什么是RSA?

  • 计算机中常用的加密技术分为两类:对称加密、非对称加密。

  • RSA属于非对称加密。加密、解密过程使用不同的秘钥,分为公钥、私钥。公钥可以公开,私钥不可以。

  • 对称加密:加密和解密使用相同的的秘钥Key,这个Key需要在网络上传输,不安全,因此需要非对称加密。

2. RSA算法

2.1 生成公钥和私钥

(1)随意选择两个大的素数PQP不等于Q

(2)令 N = P × Q 、 T = ( P − 1 ) × ( Q − 1 ) N = P \times Q、T = (P – 1) \times (Q – 1) N=P×QT=(P1)×(Q1)

(3)选择一个整数E作为秘钥,需要满足:gcd(E, T)=1 && E<T

(4)根据 ( D × E )   m o d   T = 1 (D \times E) \ mod \ T = 1 (D×E) mod T=1,计算出D,作为另一个秘钥;

(5)使用PK=(N、E)作为公钥、SK=(N, D)作为私钥(当然可以反过来)。

2.2 使用公钥加密信息

  • 使用PK=(N、E)公钥加密信息。

  • 若明文为M,则密文C可以按照如下计算得到(要求M<N):

C = M E   m o d   N C = M ^ E \ mod \ N C=ME mod N

2.3 使用私钥解密信息

  • 使用SK=(N, D)私钥解密信息。

  • 如密文为C,则明文M可以按照如下计算得到:

M = C D   m o d   N M = C ^ D \ mod \ N M=CD mod N

3. 一个例子

生成公钥和私钥

  • P=11、Q=13

  • N = P × Q = 11 × 13 = 143 、 T = ( P − 1 ) × ( Q − 1 ) = 10 × 12 = 120 N = P\times Q=11\times 13=143、T = (P-1)\times (Q-1)=10\times 12=120 N=P×Q=11×13=143T=(P1)×(Q1)=10×12=120

  • E=7

  • 因为 ( D × 7 )   m o d   120 = 1 (D \times 7) \ mod \ 120 = 1 (D×7) mod 120=1,得到D=103

  • 因此公钥(N, E) = (143, 7),秘钥(N, D)=(143, 103)

使用公钥加密信息

  • 对数据M = 2进行加密,得到加密后的数据C

C = M E   m o d   N = 2 7   m o d   143 = 128 C = M ^ E \ mod \ N \\ = 2^7 \ mod \ 143 = 128 C=ME mod N=27 mod 143=128

使用私钥解密

  • 对数据C=128进行解密,解密后的数据为M

M = C D   m o d   N = 12 8 103   m o d   143 = 2 M = C ^ D \ mod \ N \\ = 128^{103} \ mod \ 143 = 2 M=CD mod N=128103 mod 143=2

4. RSA的应用:数字签名

  • 数字签名是实现安全交易的核心技术之一,实现基础是RSA加密技术。

  • 数字签名类似于我们生活中的手写签名,必须保证签名的人事后不能抵赖,同时不能让别人伪造我们的签名。因此数字签名需要保证:

    • (1)发送者事后不能抵赖对报文的签名;

    • (2)接受者不能伪造对报文的签名。


  • 如果AB发送报文MA手中有私钥,公钥是公开的,AM使用私钥进行加密再发给B即可。

  • 这样即可保证上述两点:

    • (1)因为只有A可以对M使用私钥进行加密,A不能抵赖;

    • (2)B用公钥可以得到原始信息M,如果伪造成M',则A可以证明其伪造了信息。

5. RSA的安全性

  • RSA算法的安全性依赖于大数分解。因此为了保证安全性,需要使得P、Q非常大。

  • 因为数据很大,又牵涉到幂次运算,因此计算量很大。

6. 代码实现

/* 测试用例 11 13 */
#include <iostream>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

int p, q;  // 两个质数
int N, T;
int E, D;  // 公钥: (N, E), 私钥: (N, D)

PII PK, SK;  // 公钥、私钥

int gcd(int a, int b) { 
   
    return b ? gcd(b, a % b) : a;
}

void gen_keys() { 
     // 生成公钥、私钥
    
    N = p * q, T = (p - 1) * (q - 1);
    
    for (E = 2; ; E++)
        if (gcd(E, T) == 1)
            break;
    for (D = 2; ; D++)
        if (D * E % T == 1)
            break;
    
    PK = { 
   N, E}, SK = { 
   N, D};
}

int qmi(int a, int b, int p) { 
   
    
    int res = 1 % p;
    while (b) { 
   
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int encryption(int m) { 
     // 加密
    
    int n = PK.x, e = PK.y;
    return qmi(m, e, n);
}

int decrypt(int c) { 
     // 解密
    
    int n = SK.x, d = SK.y;
    return qmi(c, d, n);
}

int main() { 
   
    
    cin >> p >> q;
    
    // 第一步:生成公钥、私钥
    gen_keys();
    printf("公钥: (%d, %d)\n", PK.x, PK.y);
    printf("私钥: (%d, %d)\n", SK.x, SK.y);
    
    // 第二步:加密
    int m = 2;
    int c = encryption(m);
    printf("%d 加密后的数据: %d\n", m, c);
    
    // 第三步:解密
    printf("%d 解密后的数据: %d\n", c, decrypt(c));
    
    return 0;
}
  • 参考书:程序员的数学思维修炼。

今天的文章rsa公钥加密算法的提出者_rsa生成公钥和私钥的步骤「建议收藏」分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/75461.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注