3
$\begingroup$

The high security of RSA is granted, because it is very hard to factorize $$ N = p * q $$

Nevertheless, there is actually no need of factorizing $N$, in order to generate the $Private$ $Key$, but the need of knowing $$Φ (N) = (p - 1) * (q - 1) = N - (p + q-1)$$ If we think of $N$ as a rectangle with the width $p$ and the height $q$, we are able to find this geometrical coherence enter image description here

That means, if there is an efficient way to find pairs of square numbers with a distance of $4*N$, RSA would be broken.

Please leave opinions on that.

$\endgroup$
2
  • 4
    $\begingroup$ crypto.stackexchange.com/q/16036/991 $\;$ $\endgroup$
    – user991
    Commented Aug 1, 2014 at 12:08
  • $\begingroup$ What's your question, specifically? This is not the place for open-ended questions ("Please leave opinions on that") -- this is for specific, answerable questions. In any case, this is a duplicate of the other question that Ricky Demer identifies. $\endgroup$
    – D.W.
    Commented Aug 2, 2014 at 0:28

1 Answer 1

11
$\begingroup$

Ricky's link answers your main question in the comments (that knowing the private key is equivalent to knowing the factorization of $N$). But your "attack" is unfortunately part of a class of properties which might appear insightful at first, but which eventually boil down to something like this: "find integers $(m,k)$ such that $m+kn$ is a perfect square" (with sufficiently powerful conditions on $m$). These kinds of questions are known to be difficult, and we simply do not know of an efficient way of answering them for general composites of unknown factorization.

Reformulating the problem geometrically does not appear to be helpful in this case (for instance, you need to know $p + q$ to know the side length of the square, and, of course, if you know $pq= N$ and $p + q$ then you can already factor $N$ efficiently without further techniques necessary).


As an aside, it is striking that we should not be able to answer questions about the behaviour of a simple function over the integers like $f(x) = x^2 \bmod{N}$, but recall that modular arithmetic is intrinsically linear: two integers $x$ and $y$ are congruent modulo $N$ if and only if $x - y = kn$ for some integer $k$. If you come from a programming background, it is a bit like mixing addition/multiplication and XOR/OR/AND in your algorithms - as long as you stick to one or the other, math it easy (standard algebra for the first, boolean logic/De Morgan's laws and so on for the other) and you can easily rearrange things around and so on, but as soon as you use both, even the simplest functions become very hard to understand and work with (a fact often used in symmetric cryptography). As an another example, mixing continuous functions like $\sin(x)$ with discrete functions like $\lfloor x \rfloor$. Same with mixing modular arithmetic and nonlinear functions like squaring. We do know how to work with these - to some extent - modulo primes or prime powers, a surprising result of number theory (for instance, it is easy to take square roots modulo a prime), and the Chinese remainder theorem [which, by the way, essentially borrows ideas from linear algebra] lets us extend these results to any integer whose factorization is known. But if the factorization is not known, there does not appear to be an easy shortcut in the general case (yet, of course, it is not proven that none exist).

As a result it is not surprising that most* of the current most efficient general purpose factorization algorithms use linear algebra techniques at their core to find a factorization of $N$ - it's about the only thing we can do if we know nothing about $N$ or it doesn't have any special structure (for instance, a prime factor with a smooth multiplicative order over some group that's easy to compute in, e.g. integers/elliptic curve). This is not to say that these algorithms are trivial. The fastest one (the number field sieve) uses powerful and nontrivial results from the theory of finite fields, but still builds on the same structural framework as the quadratic sieve and other sieving algorithms.

* The ECM algorithm is kind of in a class of its own, since it can be considered general purpose, yet uses group-theoretic ideas to find factors of $N$ while remaining rather competitive up to a certain input size - if you are interested in integer factorization, it is well worth your time to read all you can about this algorithm, and its predecessors the $p - 1$ and $p + 1$ algorithms (which are all conceptually similar but approach the problem in different and insightful directions)

$\endgroup$
2
  • $\begingroup$ I was just wondering, if brute force like this would be more efficient with $|p-q| * 0.5$ tries than a factorization with $\sqrt(N)$ tries. $\endgroup$
    – Entimon
    Commented Aug 3, 2014 at 19:03
  • 1
    $\begingroup$ @Entimon If $p$ and $q$ are known to be close to one another, then, yes, it is fast (just like Fermat's algorithm), but if $p$ and $q$ are chosen properly (or even randomly, for sufficiently large $p$ and $q$) then $\lvert p - q \rvert$ is on the same order as $\sqrt{N}$, and in the same realm: infeasible. $\endgroup$
    – Thomas
    Commented Aug 4, 2014 at 0:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.