[URI ONLINE JUDGE] – 1716 – RSA

RSA is one of the most used cryptographic algorithms and it is considered to be one of the most secure existing alternatives. Its basic operation is described below.

Two odd prime numbers P and Q are chosen and N = PQ is computed. Then the totient function φ(N) = (P − 1)(Q − 1) is computed and an integer e satisfying 1 < E < φ(N) is chosen so that gcd(φ(N), E) = 1. Finally the integer D, the inverse multiplicative of e module φ(N) is computed, that is, the integer D satisfying DE ≡ 1 mod φ(N).

In that way we obtain the public key, which consists of the pair of integers N and E, and the secret key, containing the integers N and D.

To encrypt a message M, with 0 < M < N, we calculate C = Me mod N, and C is the encrypted message. To decrypt the message, that is, to recover the original message, it suffices to compute M = Cd mod N. Note that, in order to do that, the secret key must be known; knowing the public key is not enough to decrypt the message.

In this problem your task is to break the RSA cryptography.

Input

The input contains several test cases. A test case consists of one line, which contains three integers N, E, and C, where 15 ≤ N ≤ 109 , 1 ≤ E < N and 1 ≤ C < N , such that N and E constitute the RSA public key described above, and C is a message encrypted with that public key.

Output

For each test case in the input your program must produce a single line, containing a single integer M , 1M < N , the original message.

Sample Input Sample Output
1073 71 436 726

 

my solution:

 

<br />#include<bits/stdc++.h>
using namespace std;
typedef long long num;
const int MP = 100004;
num n, m, e, d, c, phi, aux;
int primes[MP], ps;
char comp[MP];

num mod( num x, num y )
{ return (x%y + y)%y; }

num tot( num n )
{
num ans = n, aux = n;
for(int i=0;i<ps;i++)
if( aux%primes[i] == 0 )
{
while( aux%primes[i] == 0 )
aux /= primes[i];
ans = ans/primes[i]*(primes[i]-1);
}
return ans;
}

num euclid(num a, num & x, num b, num & y)
{
num d, ix, iy;
if( a%b == 0 )
{
x = 0ll;
y = 1ll;
return b;
}
d = euclid(b,ix,a%b,iy);
x = iy;
y = ix - (a/b)*iy;
return d;
}

num fexp( num a, int e )
{
num t = 1;
while(e)
{
if(e%2) t = mod(t*a, n);
a = mod(a*a,n);
e /= 2;
}
return t;
}

int main()
{
comp[0] = comp[1] = 1;
for(int i=2;i<MP;i++)
if( !comp[i] )
{
primes[ps++] = i;
for(int j=2*i;j<MP;j+=i)
comp[j] = 1;
}

scanf("%lld %lld %lld", &n, &e, &c);
phi = tot(n);
euclid(e,d,phi,aux);
d = (d%phi + phi)%phi;
printf("%lld\n", mod(fexp(c,d),n) );
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s