-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?

$\endgroup$
7
  • 4
    $\begingroup$ If you use a realistically sized n (2048 bits), finding p and q given n is very hard. $\endgroup$ Oct 11, 2017 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, 2017 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, 2017 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$ Oct 12, 2017 at 3:18
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because it lacks basic research in the difficulty of factoring, and modulus size actually used for RSA. $\endgroup$
    – fgrieu
    Jan 29, 2020 at 21:42

1 Answer 1

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.

$\endgroup$
6
  • 3
    $\begingroup$ nitpick: the factoring cost only grows sub-exponentially with the size of the modulus. $\endgroup$ Oct 11, 2017 at 17:32
  • $\begingroup$ Nitpick away. My maths is no where near good enough to argue past the explanation above ;-) $\endgroup$
    – Trickycm
    Oct 11, 2017 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, 2017 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, 2017 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, 2017 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.