# Tag Info

75

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

39

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

23

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 \Vert< \exp(\ln n)$$ which is an exponential ...

9

The Prime Number Theorem proves that there are approximately $\frac{x}{\ln x}$ primes less than any positive integer $x$. There are thus about $\frac{2^{2048}-1}{\ln (2^{2048}-1)}-\frac{2^{2047}}{\ln (2^{2047})}=22.8\times 10^{612} - 11.4\times 10^{612}=11\times 10^{612}$ 2048-bit primes. That's a rather large number, since there are only about $10^{80}$ ...

6

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including with a modulus much too large to be factored. I'll assume unknown $n=p\,q$ with $p$ and $q$ unknown distinct large primes of comparable order of magnitude, say $\max(p,q)<... 5 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 ... 5 In the normal setting n=pq is public knowledge and \varphi(n) is hidden, for a start. I will assume$$ed\equiv 1 \pmod {\varphi(n)}\quad(1).$$Since$$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$Also, n = pq and some manipulation gives$$n = p \left ( n + 1 - \varphi{(n)} - p \right ) = -p^2 + (n + 1 - \varphi{(n)})pand then ... 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 ... 4 As mentioned in the other answer, the probabilistic method always works, and I've described both of these methods before. We'll deal exclusively with p, q of approximately the same size here. Suppose l = \gcd(p-1, q-1), the ratio between \phi(n) = (p-1)(q-1) and \lambda(n) = \mathrm{lcm}(p-1, q-1). As usual, let n = pq, e be the public exponent, ... 4 My questions are, how reasonable are these claims? Sounds fairly reasonable; they suggest an alternative factoring algorithm where they trade-off circuit depth to reduce the number of qubits required. Would this trade-off be a good thing in practice? We don't know. We don't have a large scale quantum computer in front of us, and so we don't know the ... 3 There is a simple way to detect if a number is square because there is an efficient way to compute square roots. This should not be a realistic threat as the chance of picking two b-bit primes uniformly at random and getting a match will be about b(\log 2)/2^b. Given that a broken random number generator that always returns the same value would cause ... 3 Yes we can factor an RSA modulus n given n and k \cdot \phi(n), including where k is a (reasonably) large prime. We just use f\gets k \cdot \phi(n) instead of f\gets e\,d-1 in the algorithm of this answer. The algorithm is heuristic, and I do not claim a rigorous proof of the distribution of the runtime. Also, a larger k tends to make it more ... 3 Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards? Actually, it would not be an "additional barrier", instead, it would be an additional avenue of attack. After all, the standard attacks against a discrete log problem still work ... 2 Breaking the Generalized Diffie-Hellman (GDH) assumption is known to imply Factoring for Blum-integers. This is a result by Biham et al. Since the (non)-equivalence of the RSA and Factoring assumptions is one of the biggest open questions in the RSA literature, it would be really surprising if there was a reduction from GDH to the RSA assumption, because ... 2 Russell Impaglizzio wrote "A personal view of average case complexity" roughly 25 years ago. In this work, he describes "five worlds" that we could live in with regards to the P\stackrel{?}{=} NP problem. In two of these worlds one can do cryptography, they are roughly summarized as: Minicrypt: One-way functions exist Cryptomania: Trapdoor one-way ... 2 Yes, this trivially compromises them. Simply compute the gcd of n_1 and n_2, which will return p_1 (assuming q_1 \neq q_2). The gcd can be computed efficiently using Euclid's algorithm. 2 Firstly, the phi-hiding assumption [CMS,KK] states that it is computationally-hard to distinguish the cases (e,\phi(N))=1 (where (\cdot,\cdot) denotes the GCD) and e|\phi(N) for a given RSA modulus N and "small" prime e>2 (e\ll N^{1/4}, to be precise). In the former case, the exponentiation map x\mapsto x^e\bmod{N} is injective (i.... 2 The RSA problem, which you describe, is not known to be equivalent to factoring and there is evidence both ways. In [BV] it is shown that this barrier might be inherent: using a black-box separation technique called meta-reductions, they show that certain restricted class of reductions are not possible. On the other hand, it was shown later in [AM] that in ... 2 In addition to squares being trivial to factor, if you get p=q then the usual RSA formulas just don't work. RSA exponents e,d are chosen such that ed \equiv 1 \pmod{(p-1)(q-1)}. But if p=q then (p-1)(q-1) is not the correct totient of pq. Raising to the eth power is not the inverse of raising to the dth power. Concrete example: \begin{align*} ... 2 3174654383 is a very small number & can be factored using a lot of different methods. Here is an online factoring page & it factored it in seconds - https://www.calculatorsoup.com/calculators/math/prime-factors.php 3174654383 = 52673 x 60271 The page also explains how it is done. Your n is 32 bit. In actual RSA, n is typically 1024 or 2048 bits & ... 1 I don't think that we currently know how to exploit such structure. The set-up immediately makes one think of Coppersmith's method for factoring RSA moduli with some bits of the factors known. This constructs a two-variable integer polynomial with an unusually small integer solution and uses lattice methods to find the solution. In this case the polynomial (... 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, ... 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 AP = P' \pmod A$Therefore it will still work to reveal the$P'$in the way$N'$is generated, what is the best way to ... 1 Can we have a full-fledged PKI with just a strong signature scheme when factoring and all varieties of DH are broken? Of course we can; we have a number of signature algorithms that do not rely on either factoring or DH (or Discrete Log, for that matter) how long would such an effort take? That's the hard question; while efforts are currently underway (... 1 However, to my understanding, the only purpose of Shor's Algorithm is quickly finding the prime factors of very large numbers. Your understanding is incorrect. Shor's Algorithm is usable for both factoring integers and finding discrete logarithms. Shor's algorithm works in two parts. First, it turns the problem (factoring or discrete log) into one of ... 1 Miller-Rabin has been known since at least 1980 (according to Wikipedia). Even though it's probabilistic, it's good enough. For example, openssl uses it$^\textrm{1}$. Chapter 4 of the handbook talks about various primality tests, which may gave you a better understanding of the authors' thoughts.$^\textrm{1}$See the source code for bn_prime.c 1 Can Eve break it if she can solve Diffie-Hellman problem? Yes, at least, the computational Diffie-Hellman problem. This problem is "given the triplet$h, h^x, h^y$, recover$h^{xy}$" Let us assume that Eve has an Oracle that solves this problem. Then, she sets$h=m^{ab}$,$h^x = m^b = (m^{ab})^{a^{-1}}$and$h^y = m^a = (m^{ab})^{b^{-1}}$, and passes$h, ...

Only top voted, non community-wiki answers of a minimum length are eligible