首页
社区
课程
招聘
[原创]RSA的数学原理与实现
发表于: 2023-4-17 23:34 18525

[原创]RSA的数学原理与实现

2023-4-17 23:34
18525

经常看到各位大佬挥毫泼墨,就算法和密码问题各抒己见,小弟今天斗胆也来上一课。

关于RSA的数学原理和实现,本文根据数论中的知识给出了证明,然后是自己手撸的64位RSA算法。

1.基础知识

辗转相除法:

a=bx+c,(a,b)=(b,c)若a = bx + c,则(a,b) = (b,c)a=bx+c,(a,b)=(b,c)

证明略。

欧拉函数:

ϕ(n)=n(/p)(/q)=(p)(q)\phi(n) = n*(1 - 1 /p)(1 - 1/q) = (p - 1)*(q - 1)ϕ(n)=n(11/p)(11/q)=(p1)(q1)

证明自行百度。

2. RSA加解密的条件

3. 加解密过程

加密:c=E(m)=mwmodnc = E(m) = m ^w mod \quad nc=E(m)=mwmodn

解密:m=D(c)=cdmodnm = D(c) = c^d mod \quad nm=D(c)=cdmodn

4. 证明过程:

(mwmodn)dmodn=mwdmodn[mw=an+b,(mwmodn)dmodn=bdmodnmwdmodn=(an+b)dmodn=(an)n+Cdn(an)nb+...+bdmodn=bdmodn](m^w mod\quad n)^d mod \quad n = m^{wd} mod \quad n\\ [\\ 证明:\\ 假设m^w = a n + b,则(m^w mod \quad n)^d mod \quad n = b ^ d mod \quad n\\ 而m^{wd} mod \quad n = (an+b)^d mod \quad n = (an)^n + \mathrm{C}_d^{n-1}(an)^{n-1}b + ... + b^d mod \quad n = b^d mod \quad n\\ ](mwmodn)dmodn=mwdmodn[证明:假设mw=an+b,(mwmodn)dmodn=bdmodnmwdmodn=(an+b)dmodn=(an)n+Cdn1(an)n1b+...+bdmodn=bdmodn]

所以,要证明加解密过程的正确性,即证明:
mwdmodn=mm^{wd} mod \quad n = mmwdmodn=m
因为:
wd(modϕ(n))wd \equiv 1(mod \quad \phi(n))wd1(modϕ(n))
所以
wd=Aϕ(n)+wd = A \phi(n) + 1wd=Aϕ(n)+1

(1). 若m与n互素
根据欧拉定理可得:
mϕ(n)(modn)mkϕ(n)+m(modn)m^{\phi(n)} \equiv 1(mod \quad n) \\ m^{k \phi(n)+1} \equiv m(mod \quad n)mϕ(n)1(modn)mkϕ(n)+1m(modn)

(2). 若m与n不互素
因为m是合数,n=pq, 根据算数基本定理,m必包含p或者q,假设m包含q,则根据fermat定理可得,
mp(modp)m ^{p -1} \equiv 1(mod \quad p)mp11(modp)

等式得证。

屈婉玲等几位老师的《离散数学》证明如下:
图片描述

代码是自己根据数学公式一行一行写的,因为对照公式可以很容易识别各个函数的用途,所以没写注释,请大家见谅。
只是为了学习验证,可能有所缺陷,敬请批评指正。

c++文件:

头文件:

调用方式是在main函数中执行那个如下代码,main函数就先省略了:)

1.pow_i函数中为什么要取余数?为了防止溢出?数学知识不扎实。

2.加密之前与解密之后的bit位数应该长度相同,加密之后的bit数与解密之前的bit位长度应该相同。

#include "rsa.h"
#include <windows.h>
#include <stdio.h>
 
myInt64 g_n = 0;
 
myInt64 g_d = 0;
 
myInt64 g_w = 0;
 
int g_blocksize = 0;
 
int g_blocksize_src = 1;
 
myInt64 pow_i_old(myInt64 a, myInt64 b, myInt64 p) {
    myInt64 res = 1;
    for (myInt64 i = 0; i < b; i++)
    {
        res = (res * a) % p;
        if (res == 0)           //caution here: avert to overlow
        {
            break;
        }
    }
 
    return res;
}
 
 
myInt64 pow_i(myInt64 x, myInt64 n, myInt64 p)
{
    if (n == 0)
    {
        return 1;
    }
    myInt64 temp = pow_i((x * x) % p, n / 2, p); //递归计算(X*X)^[N/2]
    if ((n & 1) != 0) //判断n的奇偶性
    {
        temp = (temp * x) % p;
    }
    return temp;
}
 
 
myInt64 pow_ii(myInt64 a, myInt64 b, myInt64 g_n) {
    myInt64 res = 1;
    for (myInt64 i = 0; i < b; i++)
    {
        res = (res * a) % g_n;
        if (res == 0)           //caution here: avert to overlow
        {
            //break;
        }
    }
 
    return res;
}
 
 
int isMutualPrime(myInt64 n, myInt64 m) {
    return 1;
}
 
int isPrimeNumber(myInt64 n) {
    for (myInt64 i = 2; i < n; i++)
    {
        myInt64 quotient = n % i;
        if (quotient == 0)
        {
            return FALSE;
        }
    }
 
    return TRUE;
}
 
 
 
int rsaInit(myInt64 p, myInt64 q)
{
    if (p == q || p <= 2 || q <= 2 || isPrimeNumber(p) == 0 || isPrimeNumber(q) == 0)
    {
        return FALSE;
    }
 
    g_n = p * q;
    if (g_n < 128)
    {
        return FALSE;
    }
 
    myInt64 mi64 = 0x8000000000000000;
    int bh = 63;
    for (int i = 63; i >= 0; i--)
    {
        if (g_n & mi64)
        {
            bh = i;
            break;
        }
        mi64 = mi64 >> 1;
    }
 
    if (bh >= 32)
    {
        g_blocksize = 8;
    }
    else if (bh >= 16)
    {
        g_blocksize = 4;
    }
    else if (bh >= 8)
    {
        g_blocksize = 2;
    }
    else
    {
        g_blocksize = 1;
    }
 
 
    myInt64 fai_n = (p - 1) * (q - 1);
 
    myInt64 w = 2;
    myInt64 d = 2;
    for (w = 2; w < fai_n; w++)
    {
        int result = isPrimeNumber(w);
        if (result)
        {
            for (d = 2; d < fai_n; d++)
            {
                result = isPrimeNumber(w);
                if (result) {
                    myInt64 m = w * d;
                    if ((d != w) && (m % fai_n == 1))
                    {
                        g_d = d;
                        g_w = w;
                        return TRUE;
                    }
                }
            }
        }
    }
    return FALSE;
}
 
//g_w is used to encrypt and g_d used to decrypt,and g_w must be primer to fai(n)
int rsa_encrypt(char* data, int size, char* dst) {
    if (g_n == 0 || g_w == 0 || g_d == 0)
    {
        return FALSE;
    }
    int block_cnt = size / g_blocksize_src;
    int mod = size % g_blocksize_src;
 
    unsigned char* s = (unsigned char*)data;
    myInt64* d = (myInt64*)dst;
    for (int i = block_cnt; i > 0; i--)
    {
        myInt64 tmp = 0;
        if (g_blocksize == 8)
        {
            tmp = *s;
            tmp = (tmp & 0xffffffffffffffff);
            tmp = (pow_i_old(tmp, g_w, g_n));
            *d = tmp;
        }
        else if (g_blocksize == 4)
        {
            tmp = *s;
            tmp = tmp & 0xffffffff;
            tmp = (pow_i_old(tmp, g_w, g_n));
            *(DWORD*)d = *(DWORD*)&tmp;
        }
        else if (g_blocksize == 2)
        {
            tmp = *s;
            tmp = tmp & 0xffff;
            tmp = (pow_i_old(tmp, g_w, g_n));
            *(WORD*)d = *(WORD*)&tmp;
        }
        else if (g_blocksize == 1)
        {
            tmp = *(unsigned char*)s;
            tmp = (tmp & 0xff);
            tmp = (pow_i_old(tmp, g_w, g_n));
            *(unsigned char*)d = *(unsigned char*)&tmp;
        }
 
        s = (unsigned char*)((unsigned char*)s + g_blocksize_src);
        d = (myInt64*)((unsigned char*)d + g_blocksize);
    }
 
    if (mod)
    {
        myInt64 tmp = 0;
        memcpy(&tmp, s, mod);
        if (g_blocksize_src == 8)
        {
            tmp = tmp & 0xffffffffffffffff;
        }
        else if (g_blocksize_src == 4)
        {
            tmp = tmp & 0xffffffff;
        }
        else if (g_blocksize_src == 2)
        {
            tmp = tmp & 0xffff;
        }
        else if (g_blocksize_src == 1)
        {
            tmp = tmp & 0xff;
        }
        tmp = pow_i_old(tmp, g_w, g_n);
        memcpy(d, &tmp, mod);
    }
    return size;
}
 
int rsa_decrypt(char* data, int size, char* dst) {
    if (g_n == 0 || g_w == 0 || g_d == 0)
    {
        return FALSE;
    }
    int block_cnt = size / g_blocksize_src;
    int mod = size % g_blocksize_src;
 
    myInt64* s = (myInt64*)data;
    unsigned char* d = (unsigned char*)dst;
    for (int i = block_cnt; i > 0; i--)
    {
        myInt64 tmp = 0;
        if (g_blocksize == 8)
        {
            tmp = *s;
            tmp = (tmp & 0xffffffffffffffff);
            tmp = (pow_i_old(tmp, g_d, g_n));
            *d = (unsigned char)tmp;
        }
        else if (g_blocksize == 4)
        {
            tmp = *(DWORD*)s;
            tmp = tmp & 0xffffffff;
            tmp = (pow_i_old(tmp, g_d, g_n));
            *d = (unsigned char)tmp;
        }
        else if (g_blocksize == 2)
        {
            tmp = *(WORD*)s;
            tmp = tmp & 0xffff;
            tmp = (pow_i_old(tmp, g_d, g_n));
            *d = (unsigned char)tmp;
        }
        else if (g_blocksize == 1)
        {
            tmp = *(unsigned char*)s;
            tmp = (tmp & 0xff);
            tmp = (pow_i_old(tmp, g_d, g_n));
            *d = (unsigned char)tmp;
        }
        s = (myInt64*)((unsigned char*)s + g_blocksize);
        d = (unsigned char*)((unsigned char*)d + g_blocksize_src);
    }
 
    if (mod)
    {
        myInt64 tmp = 0;
        memcpy(&tmp, s, mod);
        if (g_blocksize == 8)
        {
            tmp = tmp & 0xffffffffffffffff;
        }
        else if (g_blocksize == 4)
        {
            tmp = tmp & 0xffffffff;
        }
        else if (g_blocksize == 2)
        {
            tmp = tmp & 0xffff;
        }
        else if (g_blocksize == 1)
        {
            tmp = tmp & 0xff;
        }
        tmp = pow_i_old(tmp, g_d, g_n);
        memcpy(d, &tmp, mod);
    }
    return size;
}
#include "rsa.h"
#include <windows.h>
#include <stdio.h>
 
myInt64 g_n = 0;
 
myInt64 g_d = 0;
 
myInt64 g_w = 0;
 
int g_blocksize = 0;
 
int g_blocksize_src = 1;
 
myInt64 pow_i_old(myInt64 a, myInt64 b, myInt64 p) {
    myInt64 res = 1;
    for (myInt64 i = 0; i < b; i++)
    {
        res = (res * a) % p;
        if (res == 0)           //caution here: avert to overlow
        {
            break;
        }
    }
 
    return res;
}
 
 
myInt64 pow_i(myInt64 x, myInt64 n, myInt64 p)
{
    if (n == 0)
    {
        return 1;
    }
    myInt64 temp = pow_i((x * x) % p, n / 2, p); //递归计算(X*X)^[N/2]
    if ((n & 1) != 0) //判断n的奇偶性
    {
        temp = (temp * x) % p;
    }
    return temp;
}
 
 
myInt64 pow_ii(myInt64 a, myInt64 b, myInt64 g_n) {
    myInt64 res = 1;
    for (myInt64 i = 0; i < b; i++)
    {
        res = (res * a) % g_n;
        if (res == 0)           //caution here: avert to overlow
        {
            //break;
        }
    }
 
    return res;
}
 
 
int isMutualPrime(myInt64 n, myInt64 m) {
    return 1;
}
 
int isPrimeNumber(myInt64 n) {
    for (myInt64 i = 2; i < n; i++)
    {
        myInt64 quotient = n % i;
        if (quotient == 0)
        {
            return FALSE;
        }
    }
 
    return TRUE;
}
 
 
 
int rsaInit(myInt64 p, myInt64 q)
{
    if (p == q || p <= 2 || q <= 2 || isPrimeNumber(p) == 0 || isPrimeNumber(q) == 0)
    {
        return FALSE;
    }
 
    g_n = p * q;
    if (g_n < 128)
    {

[课程]FART 脱壳王!加量不加价!FART作者讲授!

最后于 2024-2-2 09:59 被satadrover编辑 ,原因:
收藏
免费 4
支持
分享
最新回复 (11)
雪    币: 2385
活跃值: (30681)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
感谢分享
2023-4-18 09:12
1
雪    币: 13936
活跃值: (17153)
能力值: ( LV12,RANK:290 )
在线值:
发帖
回帖
粉丝
3
感谢分享
2023-4-18 09:31
0
雪    币: 555
活跃值: (203)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
请问楼主有用过Python实现吗?
2023-4-19 00:22
0
雪    币: 555
活跃值: (203)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
Conney 请问楼主有用过Python实现吗?
我在用Python3实现rsa解密的时候遇到些问题,在此真诚请教楼主
2023-4-19 00:23
0
雪    币: 2479
活跃值: (3112)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
6
Conney 我在用Python3实现rsa解密的时候遇到些问题,在此真诚请教楼主
python不熟悉呀
2023-4-19 18:10
0
雪    币: 10845
活跃值: (1054)
能力值: (RANK:190 )
在线值:
发帖
回帖
粉丝
7
是一个好的入门帖
2024-2-1 12:31
0
雪    币: 2479
活跃值: (3112)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
8
看场雪 是一个好的入门帖[em_63]
谢谢版主大人夸奖,懂一点点,还差得远呢
2024-2-2 09:52
0
雪    币: 2
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
9
RSA已经被人废了,别用了;
2024-2-2 15:21
0
雪    币: 2479
活跃值: (3112)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
10
pingbo RSA已经被人废了,别用了;
我觉得,rsa算法本身没有问题,有问题的是对其安全标准的遵守。
2024-2-3 15:48
0
雪    币: 92
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
11
为什么中文和英文数字加密会失效,可是查看内存,可以正常解密英文数字,中文就失败
2024-2-15 13:13
0
雪    币: 2479
活跃值: (3112)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
12
史D芬周 为什么中文和英文数字加密会失效,可是查看内存,可以正常解密英文数字,中文就失败
使用大一点的素数,例子里的素数比较小
2024-2-17 11:59
0
游客
登录 | 注册 方可回帖
返回
//