RSA算法的C语言实现
本帖最后由 LegendSaber 于 2021-10-24 13:17 编辑想要实现RSA算法，就需要使用Miller-Rabin概率素性检验算法和扩展Euclid算法
以下是Miller-Rabin概率素性检验算法的实现
#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的算法实现
#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算法的实现
#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);
}
运行结果如下
现在实际应用基本都用openssl，不过学习和研究算法还得自己动手{:1_921:} 看着，想着，好容易，实现却好难，
页:
[1]