列表

详情

NC15887. Let's brute force RSA

描述

RSA encryption algorithm which based on prime factorizations of large integers is a asymmetric algorithm. An asymmetric algorithm uses a different key for encrypting or decrypting the message; one of the keys must be kept secret which called secret key, and the other key is usually made public which called public key. So RSA encryption also has a secret key and a public key. But how to get secret key and public key? Here is the answer.

1. We have two pairs of keys:
        public key = (E, N), sender has this key
        secret key = (D, N), receiver has this key
    And we have this amazing conclusion:
        ciphertext = plaintext^E mod N 
        plaintext = ciphertext^D mod N
2. Here are steps to get keys:
    1) get the two big prime number p and q, and N = p*q ;
    2) get the integer L = (p-1)*(q-1);
    3) get the integer E, where 1<E<L and GCD(E, L) = 1; (GCD, Greatest Common Divisor)
    4) get the integer D, where 1<D<L and E*D mod L = 1;
3. Why?
    We know the Euler Theorem:
        if GCD(a, b) = 1, a^phi(b) mod b = 1; (the function phi(x) is euler function of x);
    So if the receiver want to get the plaintext from ciphertext, he can do this:
        plaintext = ciphertext^D mod N 
                      = (plaintext^E mod N)^D mod N 
                      = plaintext^E^D mod N 
                      = plaintext^(E*D) mod N
                      = plaintext^(E*D mod phi(N)) mod N 
                      = plaintext^(E*D mod (p-1)*(q-1)) mod N 
                      = plaintext^1 mod N
                      = plaintext
4. The define of the phi(x) is the amount of K:
    where 1<=K<=x and GCD(K, x) = 1;

Now, you get the public key (E, N).
How do you get the secret key (D, N)?
So let's brute force RSA!

输入描述

first line is the T, means there are T tests; ( 1<=T<=100 )
next T lines, each line includes Ei, Ni; ( 2<=E<=10^6, 2<=N<=10^12 )

输出描述

output T lines;
each line include the answer Di, Ni of Ei, Ni;

示例1

输入: 

5
974401 501569099893
36581 46714958161
857177 106063763381
724433 233034079387
98853 149852280313

输出: 

452341087681 501569099893
38956587221 46714958161
95253670889 106063763381
171607017881 233034079387
34970286381 149852280313

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 52ms, 内存消耗: 4704K, 提交时间: 2020-03-02 12:44:02 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int T,p[1000010],vis[1000010],ct;
void db()
{
    for(int i=2; i<=1000000; i++)
    {
        if(!vis[i]) p[++ct]=i;
        for(int j=1; j<=ct&&p[j]*i<=1000000; j++)
        {
            vis[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }
}
void exgcd(ll a,ll b,ll& d,ll& x,ll& y)
{
    if(!b)
    {
        d=a;
        x=1;
        y=0;
    }
    else
    {
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
ll inver(ll a,ll n)
{
    ll d,x,y;
    exgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}
int main()
{
    db();
    ll E,D,N,L,s,t;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&E,&N);
        for(int i=1; i<=ct; i++)
            if(N%p[i]==0&&!vis[N/p[i]])
            {
                s=p[i];
                t=N/p[i];
                break;
            }
        L=(s-1)*(t-1);
        D=inver(E,L);
        cout<<D<<' '<<N<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 64ms, 内存消耗: 4692K, 提交时间: 2018-05-27 13:00:14 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000;
int p[maxn+10],vis[maxn+10],cnt;
void solve()
{
	for(int i=2;i<=maxn;i++){
		if(!vis[i]) p[++cnt]=i;
		for(int j=1;j<=cnt&&p[j]*i<=maxn;j++){
			vis[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}
void extgcd(ll a,ll b,ll& d,ll& x,ll& y){  
    if(!b){ d=a; x=1; y=0;}  
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }  
}  
ll inverse(ll a,ll n){  
    ll d,x,y;  
    extgcd(a,n,d,x,y);  
    return d==1?(x+n)%n:-1;  
}  
int main()
{
	solve();
	int T,i,j; ll E,D,N,pp,qq,L;
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld",&E,&N);
		for(i=1;i<=cnt;i++){
			if(N%p[i]==0&&!vis[N/p[i]]){
				pp=p[i]; qq=N/p[i];
				break;
			}
		}
		L=(pp-1)*(qq-1);
		D=inverse(E,L);
		cout<<D<<" "<<N<<endl;
	}
	return 0;
}

上一题

© 2025 nowcoder.com