# Tag Info

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

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

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 = (... 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 ... 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 ... 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 ... 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 ... 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 ... 3 We have$y^2-1 \equiv 0 \pmod n$, meaning that$y^2-1 = (y+1)(y-1)$is a multiple of$n$.$y \not \equiv \pm 1 \pmod n$means that neither of$y+1$and$y-1$is a multiple of$n$. Now, clearly$\gcd(y-1,n)$is a divisor of$n$; we want to show that it is not$1$or$n$. It cannot be$1$, because that would imply that$n$divides$y+1$, which we assume is ... 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? 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, ... 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 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 ... 1 The binary base 64 encoded blob contains a modulus which is 257 bytes in size: ... 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 ... 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 (... 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, ...

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/

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