网络安全之RSA加密算法介绍

xbai921031

发布于 2022-05-25 15:29:09

2.6K0

发布于 2022-05-25 15:29:09

文章被收录于专栏：汽车软件工程师汽车软件工程师

密码体制

1.对称加密

信息的加密和解密用的是相同的密匙。常见的对称加密算法有AES，DES等。

2.非对称加密

信息的加密和解密需要用两个密匙，分别为公开的公钥（Public Key）和私有的密钥（Private Key）。比较常见的非对称加密算法有RSA算法。

预备知识

1.互质

公约数只有1的两个整数构成互质关系。（注：不是质数也可构成互质关系）

2.欧拉函数

对于正整数n，欧拉函数f(n)是小于n的正整数中与n互质的数的个数。

3.模反元素

如果两个正整数a和n互质，那么一定可以找到一个整数b，使得a*b-1可以被n整除，即

(a * b) mod n = 1

以上即为了解RSA算法的一些必备知识，本文对RSA算法背后的数学原理不做解释（原谅笔者水平有限），仅仅从应用的角度去阐述在实际应用中如何使用RSA算法。

RSA加密及解密

图1 RSA加密解密过程图解

1.加密及解密过程

甲：信息传递方

乙：信息接收方

（1）乙生成公钥和密钥，并且把公钥发送给甲

（2）甲使用公钥将信息进行加密，并将密文传递给乙

（3）乙用私钥对加密信息进行解密

2.密钥生成步骤

（1）随机选择两个不相等的质数p和q

（2）计算乘积n = p * q，n的长度就是密钥的长度

（3）计算欧拉函数f(n) = (p - 1) * (q - 1)（注：这里用了欧拉函数的性质，读者可以自行网上查阅）

（4）随机选取一个整数e，使其满足1 < e < f(n)，且e要与f(n)互质

（5）计算e关于f(n)的模反元素d（选择一个符合条件的值即可）：

e * d - 1 = k * f(n)

（6）得到公钥（Public Key）与私钥（Private Key）

公钥（Public Key）:（e，n）

私钥（Private Key）：（d，n）

3.加密及解密算法

明文：m

密文：c

加密：c = (m ^ e) mod n

解密：m = (c ^ d) mod n

4.RSA算法为什么具有可靠性

（1）对外公开的只有e和n

（2）根据模反元素计算公式：

e * d - 1 = k * f(n)

只有知道f(n)才能推导出d

（3）而f(n) = (p - 1) * (q - 1)，只有知道了p和q才能计算出f(n)

（4）n = p * q，只有将n因数分解才可以计算出p和q

根据数论知识我们知道，大整数的因数分解是很困难的，所以这就决定了RSA算法的安全性。

RSA允许你选择公钥的大小。512位的密钥被视为不安全的；768位的密钥不用担心受到除了国家安全管理（NSA）外的其他事物的危害；1024位的密钥几乎是安全的。百度百科

所以在实际应用中使用1024位及以上的密匙就可以保证信息的安全。

代码演示

注：本文只使用一个简单的示例来阐述RSA算法加密解密的过程，实际应用中读者可以找到RSA算法库进行代码移植。

#include <stdio.h>
#include <math.h>

/* Two prime */
#define P    3
#define Q    11

/* Product of prime numbers */
#define N    (P * Q)
/* Euler function */
#define Z    ((P - 1) * (Q - 1))

/* Random number,1 < E < N,coprime with Z */
#define E    3
/* Modulo Multiplicative Inverse:E * D - 1 = kZ */
#define D    7

#define MsgLen    1

/* Public Key:(E,N), Private Key:(D,N) */
/* m:Original Message, c:Encrypted Message */
int main()
{
    int i;
    int EncryptedMsg[MsgLen],DecryptedMsg[MsgLen];
    int TransMsg[MsgLen] = {2};

    /* Encryption Process */
    printf("Encryption Process:\n");
    printf("Original Message\tEncrypted Message\n");

    for(i = 0;i < MsgLen;i ++)
    {
        /* c = (m ^ E) mod N */
        EncryptedMsg[i] = ((int)pow(TransMsg[i],E)) % N;
        printf("%d\t\t\t%d\n",TransMsg[i],EncryptedMsg[i]);
    }

    printf("\n");

    /* Decryption Process */
    printf("Decryption Process:\n");
    printf("Encrypted Message\tOriginal Message\n");

    for(i = 0;i < MsgLen;i ++)
    {
        /* m = (c ^ D) mod N */
        DecryptedMsg[i] = ((int)pow(EncryptedMsg[i],D)) % N;
        printf("%d\t\t\t%d\n",EncryptedMsg[i],DecryptedMsg[i]);
    }

    getchar();

    return 0;
}

代码运行结果如下：