New answers tagged

4

This remark is about the eprint version 20210303:182120 and makes use of the notation defined therein. Existing answers here have already pointed to the matrix $R_{n,f}$ defined at the bottom of page 2. It is given as $$R_{n,f}=\begin{pmatrix} N f(1) & 0 & \cdots & 0 & 0 \\ 0 & \ddots & \ddots & \vdots & \vdots \\ \vdots ...


1

If you start at $k=1$, we expect you to end the loop at some smallish $k_P$ (and smallish $k_Q$). Note that this makes $P-Q=(k_P-k_Q)\cdot A+(P'-Q')$ so that it is not uncommon to have $k_P=k_Q$ so that $P\approx Q$ and factorization of $N$ is facilitated. If you collect many, many backdoored $N$, you may succeed sometimes. (I know that still $P'-Q'\gg1$, ...


0

does starting the iteration from k=1 instead of k=P′ make a difference? Then both primes $P$ and $Q$ will be very close to small multiples of $A$ and it would be easy to factor without knowing $A$. For example, after guessing those factors $a,b$ such that $P=aA+P',Q=bA+Q'$, we could run Fermat's method on $abN=abPQ=(baA+bP')(baA+aQ')$. Note the difference ...


1

does starting the iteration from $k=1$ instead of $k=P'$ make a difference? If you start iteration from $k=P'$ then you get; $$P = A\cdot (P'+i) + P'$$ where $ i = 0,1,2,\ldots$. Take modulo $A$ $$P = A\cdot (P'+i) + P' \pmod A$$ $$P = P' \pmod A$$ Therefore it will still work to reveal the $P'$ in the way $N'$ is generated, what is the best way to ...


21

Disclaimer: This is a rough statement. Caveat emptor. The error in upper bounding the determinant of the matrix $\mathbf{R}_{n,f}$ by $$N^{n+1} \frac{n(n+1)}{2} \ln N$$ instead of by $$N^{n+1} n! \ln N$$ seems to lead to an error in upper bounding the initial short vector by $$\Vert \mathbf{b}_1 \Vert< \exp(2 \ln n/2)$$ instead of by $$\Vert \mathbf{b}_1 \...


31

Big issue at the bottom of page 2 where the determinant is quoted as $N^{n+1}\frac{n(n+1)}2 \ln n$ when it should be $N^{n+1} n! \ln n$. If this formula is used directly in the numerical estimates then are likely to be highly inaccurate. UPDATE (5th March): I've taken a bit more time to work through the paper in detail. There's no asymptotic analysis of the ...


66

No. If the claim was true, then there would be an extremely simple way to prove it: $10^{10}$ arithmetic operations is nothing. There are tons of 800-bit factoring challenges available online. The author could just solve them and include the factorization in the submission; the lack of such a straightforward validation should be taken as empirical evidence ...


5

If so, then make the seed >128-bit and be safe from Shor. Then, why there are so much fear of Shor's algorithm for RSA? Well, remember that the assumption in the original question was that we kept the RSA public key secret. That is a nonstandard assumption; we generally assume that the attacker knows the RSA public key (and in practice with most uses of ...


Top 50 recent answers are included