吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 1547|回复: 2
收起左侧

[C&C++ 转载] RSA算法的C语言实现

  [复制链接]
LegendSaber 发表于 2021-10-24 13:13
本帖最后由 LegendSaber 于 2021-10-24 13:17 编辑

     想要实现RSA算法,就需要使用Miller-Rabin概率素性检验算法和扩展Euclid算法
以下是Miller-Rabin概率素性检验算法的实现
[C] 纯文本查看 复制代码
#include <cstdio>
#include <stack>
#include <cmath>

using namespace std;

typedef unsigned long long int ll;

bool isPrime(ll a, ll n);

int main()
{
        bool bIsPrime = true;
        double p = 0;
        ll s = 0, n = 0, a = 0, i = 0;
        
        printf("请输入概率p和要检测的素数n:");
        scanf("%lf %d", &p, &n); 
        
        s = log(1 / (1 - p)) / log(2);
        
        for (i = 1; i <= s && i < n; i++)
        {
                if (!isPrime(i, n))        bIsPrime = false;
        }
        
        if (bIsPrime) printf("%ld is a prime\n", n);
        else printf("%ld is not a prime\n", n);
        return 0;        
}

bool isPrime(ll a, ll n)
{
        ll tmp = n - 1;
        ll d = 1;
        stack<ll> s;
        ll x = 0;
        
        while (tmp)
        {
                s.push(tmp % 2);
                tmp /= 2;
        }

        while (!s.empty())
        {
                x = d;
                d = (d * d) % n;
                if (d == 1 && x != 1 && x != n - 1) return false;
                if (s.top() == 1) d = (d * a) % n;
                s.pop();
        }
        
        if (d != 1) return false;
        return true;
}


接着是扩展Euclid的算法实现
[C] 纯文本查看 复制代码
#include <cstdio>
#include <stack>
#include <cmath>

using namespace std;

typedef unsigned long long int ll;

bool isPrime(ll a, ll n);

int main()
{
        bool bIsPrime = true;
        double p = 0;
        ll s = 0, n = 0, a = 0, i = 0;
        
        printf("请输入概率p和要检测的素数n:");
        scanf("%lf %d", &p, &n); 
        
        s = log(1 / (1 - p)) / log(2);
        
        for (i = 1; i <= s && i < n; i++)
        {
                if (!isPrime(i, n))        bIsPrime = false;
        }
        
        if (bIsPrime) printf("%ld is a prime\n", n);
        else printf("%ld is not a prime\n", n);
        return 0;        
}

bool isPrime(ll a, ll n)
{
        ll tmp = n - 1;
        ll d = 1;
        stack<ll> s;
        ll x = 0;
        
        while (tmp)
        {
                s.push(tmp % 2);
                tmp /= 2;
        }

        while (!s.empty())
        {
                x = d;
                d = (d * d) % n;
                if (d == 1 && x != 1 && x != n - 1) return false;
                if (s.top() == 1) d = (d * a) % n;
                s.pop();
        }
        
        if (d != 1) return false;
        return true;
}


最后给出RSA算法的实现
[C] 纯文本查看 复制代码
#include <cstdio>
#include <stack>
#include <cmath> 
#include <cstdlib>

using namespace std;

typedef unsigned long long int ll;

bool isPrime(ll a, ll n);        //判断是否为素数 
ll ex_gcd(ll a, ll b, ll &x1, ll &y1);        //扩展欧几里得算法 
ll quick_cal(ll a, ll b, ll n);        //快速指数算法 
ll getRandomNumber();        //用来随机选取两个素数 
ll gcd(ll a, ll b);

int main()
{
        ll m = 1900, c = 0;
        ll p = 0, q = 0, n = 0, d = 0, n_1 = 0;
        ll x = 0, y = 0, e = 0;
        
        p = getRandomNumber();

        q = getRandomNumber();
        
        n = p * q;
        n_1 = (p - 1) * (q - 1);
        
        for (int i = 2; i < n_1; i++)
        {
                if (gcd(n_1, i) == 1 && ex_gcd(i, n_1, x, y) == 1 && x < n_1)
                {
                        e = i;
                        d = x;
                }
        }
        
        printf("RSA加密前的数据:%ld\n", m);
        c = quick_cal(m, e, n);
        printf("RSA加密后的数据:%ld\n", c);
        m = quick_cal(c, d, n);
        printf("RSA解密后的数据:%ld\n", m);
        
        return 0;
}

ll quick_cal(ll a, ll b, ll n)
{
        ll d = 1;
        ll tmp = b;
        stack<ll> s;
        
        while (tmp)
        {
                s.push(tmp % 2);
                tmp /= 2;
        }
        
        while (!s.empty())
        {
                d = (d * d) % n;
                if (s.top() == 1) d = (d * a) % n;
                s.pop();
        }
        
        return d;
}

ll getRandomNumber()
{
        ll number = rand() % 1000;
        
        while (number < 100 || !isPrime(95, number)) number = rand() % 1000;
        
        return number;
}

ll ex_gcd(ll a, ll b, ll &x1, ll &y1)
{
        if (b == 0)
        {
                x1 = 1;
                y1 = 0;
                
                return a;
        }
        
        ll x2, y2;
        ll d = ex_gcd(b, a % b, x2, y2);
        
        x1 = y2;
        y1 = x2 - (a / b) * y2;
        
        return d;
}
 
bool isPrime(ll a, ll n)
{
        ll tmp = n - 1;
        ll d = 1;
        stack<ll> s;
        ll x = 0;
        
        while (tmp)
        {
                s.push(tmp % 2);
                tmp /= 2;
        }

        while (!s.empty())
        {
                x = d;
                d = (d * d) % n;
                if (d == 1 && x != 1 && x != n - 1) return false;
                if (s.top() == 1) d = (d * a) % n;
                s.pop();
        }
        
        if (d != 1) return false;
        return true;
}

ll gcd(ll a, ll b)
{
        return b == 0 ? a : gcd(b, a % b);
}
 

运行结果如下
VTUVV(SX9TVZ6P37QWL.png

免费评分

参与人数 1吾爱币 +10 热心值 +1 收起 理由
苏紫方璇 + 10 + 1 欢迎分析讨论交流,吾爱破解论坛有你更精彩!

查看全部评分

本帖被以下淘专辑推荐:

  • · Aarow|主题: 991, 订阅: 304

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

flyingdancex 发表于 2021-10-24 14:03
现在实际应用基本都用openssl,不过学习和研究算法还得自己动手
daishen 发表于 2021-10-24 19:51
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:本版块禁止灌水或回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-3-29 18:29

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表