-2
$\begingroup$

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?

|improve this question
$\endgroup$
  • 2
    $\begingroup$ If you use a realistically sized n (2048 bits), finding p and q given n is very hard. $\endgroup$ – CodesInChaos Oct 11 '17 at 16:10
  • 1
    $\begingroup$ The point of RSA is that you can't do efficient integer factorization for larger numbers. Determining the key is only trivial for small n. $\endgroup$ – Arminius Oct 11 '17 at 16:13
  • 1
    $\begingroup$ Of course it is crackable - how much time have you got? The point to crypto is not that it is so complex that it can't be understood, but that it is infeasible to try and crack it $\endgroup$ – schroeder Oct 11 '17 at 16:22
  • 1
    $\begingroup$ 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
  • 1
    $\begingroup$ For $p$ and $q$ remember that they are primes between $2^{2047}$ and $2^{2048}$. Those numbers do not even fit into a stack exchange comment, so I cannot show them here. Here one is in WolfromAlpha though, it gives you some idea of the complexity involved. It also helps to remember that the distance between primes doesn't go down as fast as you may think. $\endgroup$ – Maarten Bodewes♦ Oct 17 '17 at 16:56
3
$\begingroup$

isn't it crack-able?

Yes, but it gets exponentially a lot harder to do the bigger n is.

Their are POC side channel attacks that are claimed to crack a 4096 key: https://www.extremetech.com/extreme/173108-researchers-crack-the-worlds-toughest-encryption-by-listening-to-the-tiny-sounds-made-by-your-computers-cpu.

If you are just attacking the maths directly then the biggest key cracked to date was 768, in 2009 (https://en.wikipedia.org/wiki/RSA_Factoring_Challenge). At this time they estimated it would take 1000 times longer to crack a 1024 bit key on the same hardware then a further 4.3 billion times longer to crack a 2048 key.

Obviously hardware is a huge factor in these times and quantum computing is not even considered here.

Hopefully however this does at least hint at the exponential difficulty when increasing n.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ nitpick: the factoring cost only grows sub-exponentially with the size of the modulus. $\endgroup$ – CodesInChaos Oct 11 '17 at 17:32
  • $\begingroup$ Nitpick away. My maths is no where near good enough to argue past the explanation above ;-) $\endgroup$ – Trickycm Oct 11 '17 at 17:34
  • $\begingroup$ in the way I told, first of all we can find the primes easy(because the RSA user need primes to make n = p*q so he had find them before) then we need to check that n % p =? 0 and that take something like O(log n) to check each prime. so the complexity would be O(RSA) * O(log n) which log n isnt important when we talk about 2^4096, just some more computer needed! $\endgroup$ – user160958 Oct 11 '17 at 18:48
  • $\begingroup$ @user160958 There are a lot of prime numbers. If your plan involves "generate a list of all 2048-bit primes," you need a new plan. It's a lot easier to find one 2048-bit prime than to make a list of all 2048-bit primes. $\endgroup$ – cpast Oct 11 '17 at 23:07
  • 1
    $\begingroup$ nitpick^2: The attack in the question grows exponentially, the best known attacks are sub-exponential. $\endgroup$ – Meir Maor Oct 18 '17 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy