網安實驗 RSA實作

RSA的簡單實作，未作優化，不能擴充到超出long long範圍的質數上。

由于是按位加密，比較備援，可以自己加上字元的映射去減少密文的長度。

使用了米勒羅賓判斷素數。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int L=101;
bitset<64> charToBitset(const char s[8])//轉換函數
{
	bitset<64> bits;
	for(int i=0; i<8; ++i)
		for(int j=0; j<8; ++j)
			bits[i*8+j] = ((s[i]>>j) & 1);
	return bits;
}
string multiply(string a, string b)//大數乘法
{
	int len = a.size() + b.size() + 10;
	string ans(len, '0');
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	for (int i = 0; i < a.size(); i++)
	{
		int t = 0;
		for (int j = 0; j < b.size(); j++)
		{
			t += (ans[i + j] - '0') + (a[i] - '0') * (b[j] - '0');
			ans[j + i] = t % 10 + '0';
			t /= 10;
			if (t && j == b.size() - 1)
			{
				ans[j + i + 1] = t + '0';
			}
		}
	}
	reverse(ans.begin(), ans.end());
	return ans.substr(ans.find_first_not_of('0'));
}
string sub(string a,string b)//隻限兩個非負整數相加
{

    string ans;
    int na[L] = {0};
    int nb[L] = {0};
    int la = a.size();
    int lb = b.size();
    //倒序存儲
    for (int i=0;i<la;i++)
    {
        na[la-1-i] = a[i]-'0';
    }
    //倒叙存儲
    for (int i=0;i<lb;i++)
    {
        nb[lb-i-1] = b[i]-'0';
    }
    int lmax = max(la,lb);
    //從個位開始相減
    for (int i=0;i<lmax;i++)
    {
        na[i] -= nb[i];
        while (na[i]<0)
        {
            na[i] += 10;
            na[i+1]--;
        }
    }
    //處理前置0
    while (!na[lmax])
        lmax--;
    if (lmax<0)
        ans = "0";
    else {
        for (int i = lmax; i >= 0; i--)
            ans += na[i] + '0';
    }
    return ans;
}
ll gcd(ll a,ll b) {
	if(!b) return a;
	else return gcd(b,a%b);
}
ll select(ll h,ll t) {
	for(ll i=t-2;i>=1;--i) {
		if(gcd(i,t)==1)
			return i;
	}
	return t-1;
}

ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0) {
        x=1,y=0;
        return a;
    }
    ll t=ex_gcd(b,a%b,x,y);
    ll temp=y;
    y=x-(a/b)*y;
    x=temp;
    return t;
}
ll solved(ll a,ll b) {
	ll x,y;
	ll g=ex_gcd(a,b,x,y);
	b/=g;
	x=(x%b+b)%b;
	x+=7*b;
	return x;
}
ll fast_mul(ll a,ll b,ll mod)
{
    ll ans=0;//ans最終求餘的結果
    while(b)
    {
        if(b&1)
            ans=(ans%mod+a%mod)%mod;
        a=(a%mod+a%mod)%mod;
        b>>=1;
    }
    return ans%mod;//傳回a*b%mod的結果
}

ll qpow(ll a,ll b,ll mod)
{
    ll res=1;
    a%=mod;
    while(b)
    {
        if(b&1) res=fast_mul(res,a,mod);
        a=fast_mul(a,a,mod);
        b>>=1;
    }
    return res;
}
const int MAX=1e7+2;
int tot=0;
bool vis[MAX];
int prime[MAX];
void init()
{
    memset(vis,false,sizeof(vis));
    vis[1]=vis[0]=true;
    for(int i=2;i<MAX;i++)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
        }
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>=MAX)
                break;
            vis[prime[j]*i]=true;
            if(i%prime[j]==0)
                break;
        }
    }
}
ll qqpow(ll a,ll b,ll mod)
{
    ll res=1;
    while(b)
    {
        if(b&1)res=(res%mod*a)%mod;
        a=(a%mod)*a%mod;
        b>>=1;
    }
    return res;
}
bool MRT(ll x)
{
    if(x==2)return true;
    if(x==1)return false;
    for(int i=1;i<=30;i++)
    {
        ll base=rand()%(x-2)+2;
        if(qqpow(base,x-1,x)!=1)return false;
    }
    return true;
}
int  main() {
	/*string p,q,tempor; tempor="1";
	cout<<"請輸入兩個互不相等的質數：";
	cin>>p>>q;
	cout<<"      n="<<multiply(p,q)<<endl;
	cout<<"計算出n的歐拉函數：";
	string eulern;
	eulern=multiply(sub(p,tempor),sub(q,tempor));
	cout<<"euler(n)="<<eulern<<endl;
	cout<<"請從1到euler(n)的開區間中選擇一個整數e與"<<eulern<<"互質,e作為公鑰";
	*/
	ios::sync_with_stdio(false);
    string MW,SW[10010],HG;
	init();
	ll p,q;
	cout<<"請輸入兩個互不相等的質數：";
	cin>>p>>q;
    getline(cin,MW);
	if(!MRT(p)|| !MRT(q) || p==q) {
        cout<<"p,q不是互不相等的質數，無法作為基數"<<endl;
        return 0;
	}
	ll n=p*q;
	cout<<"           n="<<q*p<<endl;
	cout<<"計算出n的歐拉函數：";
	ll eulern=(p-1)*(q-1);
	cout<<"euler(n)="<<eulern<<endl;
	cout<<"請從1到euler(n)的開區間中選擇一個整數e與"<<eulern<<"互質,作為公鑰"<<endl;
	ll e=select(1,eulern);
	cout<<"e="<<e<<endl;
	cout<<"由公鑰計算我們選擇的私鑰d*e=1 mod euler(n)"<<endl;
	ll d=solved(e,eulern);
	cout<<"d="<<d<<endl;
	cout<<"公開密鑰PU={e,n}={"<<e<<","<<n<<"}"<<endl;
	cout<<"私密密鑰PR={d,n}={"<<d<<","<<n<<"}"<<endl;
	cout<<"請輸入所需要加密的明文：";
	getline(cin,MW);
	int LEN=0;
	for(int i=0;i<MW.length();++i) {
        ll hh=MW[i];
        ll C=qpow(hh,e,n);
        HG=to_string(C);
        SW[++LEN]=HG;
        HG.clear();
	}
	cout<<"加密後為：";
	for(int i=1;i<=LEN;++i) {
        cout<<SW[i];
	}
	cout<<endl;
	MW.clear();
    for(int i=1;i<=LEN;++i) {
        ll hh=atof(SW[i].c_str());
        ll C=qpow(hh,d,n);
        MW+=C;
	}
	cout<<"解密後為: "<<MW<<endl;
	return 0;
}