New answers tagged

1

No, there is no checksum built-in to the RSA keys per se. There is no need for that. Does this breaks the key ? Or changes the key internally, without breaking it ? [EDIT] It was rightfully pointed out to me that at least one of the statements I typed (in haste) was plain wrong. Now that the answer has served its initial purpose, I've removed my ...


7

What's missing is the authentication of the entities. If you don't authenticate the entity then you don't know who you've established the master secret with. This means an attacker can pose as a man in the middle or the attacker can simply act as one of the entities. You can use static DH key pairs, but in that case the DH public keys must be trusted and ...


1

The binary base 64 encoded blob contains a modulus which is 257 bytes in size: ...


5

The usual methods of RSA signature with message recovery (that is, embedding a part of the message in the signature, known as the revoverable message) are those in ISO/IEC 9796-2:2010 (partial preview). There are three: Scheme 1; it is an ad-hoc scheme that essentially concatenates the recoverable message, the hash of the whole message, and a little fixed ...


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


1

Instead of using probabilistic methods to generate large primes, as indicated in the other answers, one can (IMHO better) employ Maurer's algorithm of generating provable primes. I have a Python code implementing that algorithm, available at s13.zetaboards.com/Crypto/topic/7234475/1/


0

What you could do, is use a Mill's constant for generation. Then, a test for primarity would be good anyways...(in case that not exact enough constant is chosen, so you could end up with non prime) Mill's constant is such a number, that if powered to 3, and then powered to any N, where N is an usigned integer, we get value V wich, rounded down, is a prime. ...


4

There exists a distinguisher that works with nontrivial advantage, $O(1/\log \phi(m))$. This is because $q_0$ must be a multiple of $p_0$; however $q_1$ is a random value between $0$ and $\phi(m)-1$. Hence, the distinguisher is "test both for primality, if one is prime, say that one is $r \cdot p_1 \bmod \phi(m)$" $q_1$ is a random value, and hence it ...


7

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$. We know that $P^e = C \bmod N$; that's equivalent to $P^e - C = kN$ for some integer $k$; if $e$ is small, then Shor's algorithm might be able to factor $P^e - C$; allowing you to recover $N$. Alternatively, if you ...


1

I'ld say the answer is “no”. Usually you need to factor the modulus $N$ to break RSA. Now $N$ is not available to the attacker. So with a single plain text and cipher text I'm pretty sure the attacker has too little information to retrieve N or any other key component. Your pre-condition of not having the public key and therefore the modulus $N$ available ...


2

The OpenPGP message you posted is a signature, not a key. As it was issued by GnuPG, I assume you're using GnuPG anyway. To export your public key, run gpg --armor --export [key-id]. --armor wraps the output in a base64-like encoding (like the signature block you provided in your question), otherwise you'll get binary output. If you don't know your key-id, ...


0

TL;DR: As of 2015 quantum computing is not an immediate threat to RSA. But it is a long-term threat (decades away). Whether you should be worried depends whether you are interested in keeping the secrets for so long (2035, if you want a pessimistic guesstimate). As the other answers already say, D-Wave machines ARE not generic quantum computers and will ...


5

TL;DR: The main reasons to prefer RSA over ElGamal signatures boild down to speed, signature size, standardization, understandability of the method and historical establishment as the result of a lot of lobby work. The main technical advantage of RSA is speed. With RSA you only need to do a small-exponent exponentation to verify a signature, where as with ...


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?


6

When choosing the public exponent $e$, if the value chosen is the first coprime after $\phi(n)/2$ then the resulting public and private exponents are equal. Well, yeah, that'll always be true. Why does this happen? We have $e=d$ whenever we have both of the following true: $$e^2 \equiv 1 \pmod{p-1}$$ $$e^2 \equiv 1 \pmod{q-1}$$ Now, if $e = (...


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


2

Let's assume that T does send A,Kxt(Ra,Ts) to B as you have indicated. In that case upon reception and validating the signature, B would immediately be able to tell that the signature does not belong to A (and should thus not continue the exchange). To try to take advantage of the exchange, T would have to alter the message from A so that it still looks ...


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


4

OK, so this takes a bit of guessing, but I'm assuming the following: A is the identity of A, which can be used to select the right public key of A; Kxa() is a signing operation (with message recovery) that signs the random Ra and a tag Ts which is used as proof; Kya() is an encryption operation with the public key A, so that the session key Ks is kept ...


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



Top 50 recent answers are included