15

The bozos at Clown Sterling have adapted the advanced technology of bogosort to factoring: randomly blow a candidate solution out your nose and check whether it works. For a semiprime $n$ chosen by modern RSA key generation methods, there are approximately $\sqrt n$ candidate solutions to check, which is also the expected cost of this method. For instance, ...


8

TLDR: the efficiency of what they demo is below state of the art a decade ago. What they describe would be plain abyssal. In the event described in the press release, Crown Sterling made a public demonstration, which can be watched there. The meat of it is a demonstration of the factorization of a 77-digit (256-bit) public modulus of an RSA key, ...


8

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? No. Factoring numbers with special forms like that is easy. You have a Mersenne number, $n = 2^e - 1$, whose exponent $e = 2048$ is composite. Whenever $e = u v$, we have $2^u - 1 \mid (2^u)^v - 1 = 2^e - 1$, since in general $x - 1 \mid x^k - 1$. (...


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


6

Actually, a well known result is that, for any cryptosystem that relies on the hardness of the DLog problem (including ECDlog), there is no such reduction in strength if you have $k$ keys. That is, the problem of "here are $k$ keys, break any one" is essentially as hard as the problem "here is one key, break it". The proof is straight-...


5

There are many different special-case factoring algorithms for when $(p,q)$ have some special structure. Which of these attacks on semi-primes with special structure are devastating enough such that proper generation of $(p,q)$ should explicitly check that they don't have that structure? TLDR: None in modern practice. Except when there's a regulatory ...


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)})p$$ and then ...


4

This question looked due to the Cold boot attack, by Halderman et. al. Normally researchers look at some random known bit known due to the decaying of the memory. 2009 Heninger et. al Reconstructing RSA Private Keys from Random Key Bits if $\delta = .57$ fraction of the bits of $p$ and $q$ is randomly is given they can construct them. The closest article ...


4

This system was invented in 1973 by Clifford Christopher Cocks of the GCHQ and described in his document (then secret) A note on Non-Secret Encryption, before RSA was published. See this question for more context. Is this scheme more secure or less secure than the normal RSA? Better or worse? On security, we know no difference with RSA. The restriction ...


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

Which algorithms give the best performance for 30 decimal digit numbers? 30 decimal digits is 100 binary digits. Trial division will require around $2^{50}$ divisions. Pollard-Rho-Factoring will require around $2^{25}$ checks - this may be a good pick for you if you want to implement it yourself quickly and don't mind having to wait a bit on an optimized ...


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

Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$? If the multiplication is done within $Z_q^*$, then it's easy - pick an arbitrary nonzero $a$ and compute $b = a^{-1}X$; you're done. You can compute $a^{-1}$ by either the Extended Euclidean method, or by ...


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

Your proof is essentially correct. You may improve rigor by either calculating exactly or giving a bound on it's expected runtime. If we take the simple case(which is also the worst case) where k=2 we get a probability of 1/2 to get a different root. It should be noted that since our root x was uniformly random over Z/nZ it is also uniformly random over ...


1

By construction, RSA moduli are the product of two large primes.


1

ell is the largest factor of $p-1$, remember the Sophie Germain prime $p=2q+1$ All below from mail thread of [Cado-nfs-discuss] DLP and well explained with a sageMath code. cado-nfs is right, but maybe the printed info is scarce or misleading. Here's a verification script. > sage: p=53236943330228380237618624445646085674945074907141464418703 >...


1

I believe Carl Pomerance (the inventor of the quadratic sieve algorithm) gives a great explanation in: Pomerance, C. (2008). Smooth numbers and the quadratic sieve. In Algorithmic Number Theory Lattices, Number Fields, Curves and Cryptography (pp. 69-81). Cambridge: Cambridge University Press. The quote below comes from page 72. "A number ...


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