2
$\begingroup$

A probable attack for RSA (factorization): how to improve it?

$N=8*G+3$ can be factored if there is a non-trivial negative $k$ such that

$\frac{(N*(9+24*k)-3)}{8}=-6*m^2 $

[to exclude the two trivial solutions $m=\frac{(N+1)}{4}-N*t$ and $m=N-\frac{(N+1)}{4}-N*t $]

given the system

$ \frac{[[8*[\frac{(N*(9+24*k)-3)}{8}+2*x^2*h^2-2*x^2+2*x*h-2*x]+3+6*n-(n*(n+4))]-4*n*y-3]}{8}-[4-\frac{(-(2*h-2)-7)*(-(2*h-2)-5)}{8}] = -(2*h-2)*(h*x-1) $

,

$ h=-4*sqrt[\frac{-(N*(9+24*k)-3)}{48}] $

,

$ n=h^2-1 $

,

$ (4*x+2)^2-(2*y-1)^2=N*(9+24*k) $

you will have

$GCD(4*x+1-2*(y-1),N)= p || q || N$

Example

$ \frac{[[8*[\frac{(N*(9+24*k)-3)}{8}+2*x^2*h^2-2*x^2+2*x*h-2*x]+3+6*n-(n*(n+4))]-4*n*y-3]}{8}-[4-\frac{(-(2*h-2)-7)*(-(2*h-2)-5)}{8}] = -(2*h-2)*(h*x-1) $

,

$ h=-4*sqrt[\frac{-(N*(9+24*k)-3)}{48}] $

,

$ n=h^2-1 $

,

$ (4*x+2)^2-(2*y-1)^2=N*(9+24*k) $

,

$k=-10$

,

$N=187$

$->x=30 ; y=121$

$GCD(4*30+1-2*(121-1),187)=17$

I had thought of this solution:

calculate $k$ as a function of $x$ or $y$ and see with the Coppersmith method if there is an $x ​​<sqrt (N)$

if it exists and all the variables of the system are integers then we are done and we will find $p$ and $q$

Example as a function of $x$

$N*k=\frac{(-3*N-16*x^2+1)}{8}$

$N*k=\frac{(-3*N-16*x^2-32*x-15)}{8}$

how to improve it? Do you have any ideas?

$\endgroup$
5
  • 2
    $\begingroup$ This is about presentation rather than content: You might want to look into formatting your post with MathJax, to make it easier for people to parse. Mathematical expressions in code blocks are not very easy on the eyes. :) $\endgroup$
    – Morrolan
    Oct 24, 2022 at 9:00
  • $\begingroup$ @Morrolan I apologize for this, but I don't know how to use MathJax $\endgroup$ Oct 24, 2022 at 9:09
  • 2
    $\begingroup$ math.meta.stackexchange.com/questions/5020/… $\endgroup$
    – user93353
    Oct 24, 2022 at 11:27
  • $\begingroup$ @user93353 thank you $\endgroup$ Oct 24, 2022 at 12:37
  • $\begingroup$ we could multiply N * (1 + 8 * s) which will be our new N and try the Coppersmith method on x What do you think? $\endgroup$ Oct 26, 2022 at 6:47

1 Answer 1

3
+50
$\begingroup$

This appears to be a special case of congruence of squares factoring. I don't see any particular reason why this form of congruence should be easier to solve than the generic form.

The congruence of squares method has of course led to many of the best factorisation algorithms including the best-known general purpose classical algorithm, the number field sieve.

$\endgroup$
4
  • $\begingroup$ The problem has been moved from finding k to finding x. $\endgroup$ Oct 27, 2022 at 5:26
  • $\begingroup$ @AlbericoLepore No, the question has been moved from finding to any $(k,x)$ pair (in congruence of squares) to finding any $x$ that works with a particular $k$ in your method. This is more specific question and any solution to your method corresponds to a congruence of squares solution, but not every congruence of squares solution corresponds to a solution under your method. $\endgroup$
    – Daniel S
    Nov 2, 2022 at 12:51
  • $\begingroup$ thank you ,....... $\endgroup$ Nov 2, 2022 at 13:17
  • $\begingroup$ you should try changing n $\endgroup$ Nov 3, 2022 at 14:43

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.