According to Wikipedia RSA definitions are :
so we have $n$ and $e$
because $p$ and $q$ are prime so there is only one $p$ & $q$ which fit to n so from n we can have $p$ and $q$
so we have $\phi(n)$
in the algorithm $d$ is an integer which doesn't effect rest of algorithm, that done before so any $d$ with definition of wiki is OK to use in decryption
now we have $p, q, \phi(n), n, e$
we can calculate $d$ with a simple code that is only a for and $a$ if:
for(int i = 2; i < 1e6; i++):
if( (i * 3120 + 1) % 17 == 0)
{
cout << "d is : " (i*3120 + 1)/17 << endl;
break;
}
where %
means mod
to find $p$ & $q$ we just have to find one of them like $q$ that $(n mod q) = 0$ and $p = {n \over q}$
finding $p$ is as hard for us as the person who use RSA. I mean we use the global algorithm for finding prime that anyone (RSA user) use
Isn't RSA crack-able for this reason?
int
in C++ (and C) is rarely larger than 32 bits (and the standards permit it to be as small as 16 bits and some systems do) and 1000000*3120 exceeds the range of signed-32bit causing Undefined Behavior which on most implementations is silent wraparound to a wrong result. Of course if you actually have phi you don't need this trial-and-error at all, just use Extended Euclid as explained in wikipedia and every textbook ever. And for RSA sizes actually used you can't factor and get phi. $\endgroup$ – dave_thompson_085 Oct 12 '17 at 3:18