RSA公钥加密算法

时间：2023-12-20 04:37:02 电位器rsa0k11v901s

RSA公钥加密算法

1. 什么是RSA？

计算机中常用的加密技术分为对称加密和非对称加密两类。
RSA属于不对称加密。在加密和解密过程中和解密，分为公钥和私钥。公钥可以公开，私钥不能公开。
对称加密：加密和解密使用相同的密钥Key，这个Key需要在网络上传输，不安全，需要不对称加密。

2. RSA算法

2.1 生成公钥和私钥

(1)随意选择两个大素数P和Q，P不等于Q；

（2）令 $\times Q、T = (P - 1) \times (Q - 1)$ ；

(3)选择一个整数E需要满足的是要满足：gcd(E, T)=1 && E；

 （4）根据  $\times E) \ mod \ T = 1$ ，计算出D，作为另一个秘钥；
 （5）使用PK=(N、E)作为公钥、SK=(N, D)作为私钥(当然可以反过来)。


    2.2 使用公钥加密信息
     
      
       使用PK=(N、E)公钥加密信息。
  
       若明文为M，则密文C可按以下计算(要求)M）：
 
 
     
  $C = M ^ E \ mod \ N$ 
 
    2.3 使用私钥解密信息
     
      
       使用SK=(N, D)私钥解密信息。
  
       如密文为C，则明文M可以按照如下计算得到：
  
     
  $M = C ^ D \ mod \ N$ 
 
    3. 一个例子
     
      
      生成公钥和私钥 
      
      
       取P=11、Q=13；
  
        $P\times Q=11\times 13=143、T = (P-1)\times (Q-1)=10\times 12=120$ ；
  
       取E=7；
  
       因为  $\times 7) \ mod \ 120 = 1$ ，得到D=103。
  
       因此公钥(N, E) = (143, 7)，秘钥(N, D)=(143, 103)
  
      
      
      使用公钥加密信息 
      
      
      对数据M = 2进行加密，得到加密后的数据C： 
     
  $C = M ^ E \ mod \ N \\ = 2^7 \ mod \ 143 = 128$  
      
      使用私钥解密 
      
      
      对数据C=128进行解密，解密后的数据为M： 
     
  $M = C ^ D \ mod \ N \\ = 128^{103} \ mod \ 143 = 2$ 
 
    4. RSA的应用：数字签名
     
      
       数字签名是实现安全交易的核心技术之一，实现基础是RSA加密技术。
  
       数字签名类似于我们生活中的手写签名，必须保证签名的人事后不能抵赖，同时不能让别人伪造我们的签名。因此数字签名需要保证： 
        
         （1）发送者事后不能抵赖对报文的签名；
  
         （2）接受者不能伪造对报文的签名。
  
       
  
      
      
      
       如果A向B发送报文M，A手中有私钥，公钥是公开的，A给M使用私钥进行加密再发给B即可。
  
       这样即可保证上述两点： 
        
         （1）因为只有A可以对M使用私钥进行加密，A不能抵赖；
  
         （2）B用公钥可以得到原始信息M，如果伪造成M'，则A可以证明其伪造了信息。
  
       
  
     
 
    5. RSA的安全性
     
      
       RSA算法的安全性依赖于大数分解。因此为了保证安全性，需要使得P、Q非常大。
  
       因为数据很大，又牵涉到幂次运算，因此计算量很大。
  
     
 
    6. 代码实现
     /* 测试用例 11 13 */
#include 

#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;
}
 
      
      参考书：程序员的数学思维修炼。

 
            锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

RSA公钥加密算法

相关文章