New answers tagged

2

No an attacker will not be able to factor your $n$ (e.g. break it). Your $n$ is of size 700 decimal digits which is $\frac{700}{\log_{10}(2)}\approx2325$ bits. Now 2048-bit moduli is the most widespread size used on the internet and hasn't seen a failure yet (without exploiting bad random number generators), so you are secure with that modulus size. As for ...


3

If $p_0$ and $q_0$ are known then so are $p_i$ and $q_i$ by iterating. To factor $N$, do the following: $(p,q) \gets (p_0,q_0)$ while ($p \nmid N$) do $(p,q) \gets (next\_prime(p^2+q^2), next\_prime(2pq))$ Return $(p,q)$


2

Here is the solution to M^e is less than N: http://asecuritysite.com/encryption/crackrsa2 An alternative method is here as a fun article: http://asecuritysite.com/encryption/crackrsa5 Do you have the Cipher value?


0

The previous comment left a term out of the numerator. $$x = \frac{1.923 \times \sqrt[3]{L \times ln(2)} {\sqrt[3]{[ln(L \times ln(2))]^2}} - 4.69}{ln(2)}$$ I find this formula on page 92 of the NIST document that was previously mentioned: http://csrc.nist.gov/groups/STM/cmvp/documents/fips140-2/FIPS1402IG.pdf The GNU bc code to implement this equation ...


1

A simple way to consider the question is: Can we factor a given 2048-bit RSA modulus $N$, assumed to be the product of two 1024-bit primes $p$ and $q$, if also given the 256 high-order bits of $p$? That class of problems is studied by Don Coppersmith: Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, in Journal of Cryptology (...


5

There is some confusion here. The definition of prime numbers states that cannot be factored (see Definition of prime numbers) You seem to be talking about RSA modulus which is the product of two prime numbers (see RSA cryptosystem). As far as keylength is concerned 768 bits is not considered safe today. Note that the keylength choice is a compromise ...


1

The security levels for RSA are based on the strongest known attacks against RSA compared to amount of processing that would be needed to break symmetric encryption algorithms. The equation NIST recommends to compute approximate length for key is found in FIPS 140-2 Implementation Guidance Question 7.5. It is: $x = \frac{1.923 \times \sqrt[3]{L \times ln(...


1

I have reformatted the above equation as a program for GNU bc (part of GNU coreutils, found on most Linux systems). GNU bc will be much easier to find than Mathematica (although it is quite eccentric). Here is the code: $ cat RSA-gnfs.bc #!/usr/bin/bc -l scale = 14 a = 1/3 b = 2/3 #print "RSA Key Length? " c = read() t = l( l(2 ^ c) ) # if b < 1, ...


2

Let $n = pq$. By assumption, $3$ divides $\varphi(n) = (p-1)(q-1)$. Without loss of generality, I assume that $3$ divides $(p-1)$ or, equivalently, that $p \equiv 1 \pmod {3}$. Fact Let $p$ be a prime such that $p \equiv 1 \pmod 3$. Let also $c$ be a cubic residue modulo $p$. If $y$ is a cubic root of $c$ then so are $y\cdot \omega \pmod p$ and $y \cdot \...


1

Answering my own question, with some degree of uncertainty. The basic Quadratic Sieve (as in Wikipedia's algorithm and the example quoted in the question) finds smooth integers among $x^2\bmod N$, for $x$ starting at $\lceil\sqrt N\rceil$. Until $x$ reaches $\lceil\sqrt{2N}\rceil$, it is searched smooth numbers among $x^2-N$. If this is divisible by a prime ...



Top 50 recent answers are included