Hot answers tagged

52

Asymmetric encryption is vastly inferior to symmetric encryption. That is, in all respects, except one -- being asymmetric. When that property is needed, there's no way around it, obviously. Asymmetric encryption is much slower. It is much more susceptible to showing recognizable patterns of some kind given non-random input. You need much larger key sizes ...


17

Actually, someone who gets two plaintext/ciphertext pairs (after padding; randomized padding foils this attack), and guesses the small exponent can recover the modulus, allowing him to decrypt other ciphertexts. The relation between plaintext, ciphertext and modulus is: $$C^e \equiv P \pmod N$$ or $$C^e - P = kN$$ for some integer $k$. Hence, if we ...


16

Digital signatures are not designed for confidentiality. For the simplest counterexample to the implicit conclusion that there is no point to digital signatures without confidentiality, consider the use of PGP signatures. People may sign a message that they send to a public mailing list, allowing others to verify that they indeed said that and not an ...


16

RSA-768 took 2000 years of 2.2Ghz single core Opteron from year 2009 [1]. DJB et al wrote in 2013 [2] that RSA-1024 would take $2^{70}$ differences with $2^{24}$ per machine per second in 2009, so 2 million years. Hardware improved since then, and GNFS can use GPUs, so maybe better, but about a million years I guess. Absolutely the computation can be ...


15

PKCS#1 v1.5 describes a method (formally known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption scheme for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider). For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be ...


15

Are there other public key systems that do not have this property? A more cogent question might be "are there any public key systems other than RSA that does have this property?" In particular, I'm calling "this property" the idea that you can swap the public and private keys and remain secure (which you can do with RSA, as long as you select large public ...


13

Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption. This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with ...


13

It is not that RSA becomes insecure when used with public exponent $2$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't actually work. The problem is that for $N = pq$ for two primes $p$ and $q$, the function $f : x \mapsto x^2 \bmod N$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the ...


13

It might be feasible, or not. If "digits" had been binary digits or bits, the answer would have been yes. Anything about 600-bit can be factored by GNFS. The public record is for a 768-bit RSA modulus, factored in 2009. 600-bit is within reach of CADO-NFS and Msieve. That's even packaged into factoring as a service for semi-deep-pocketed script kiddies. It ...


13

The cold boot attack can be performed on any encryption scheme as long as the keys reside in memory. For full-disk encryption (FDE) with symmetric algorithms like AES, you will need to take the key out from the TPM, where you will be susceptible to a cold boot attack. Though the TPM is capable of RSA encryption and decryption, for FDE RSA has problems, in ...


12

How does the new attack work at top level? In short They used BEAST-like Man in the Browser attack by using Cache-like attacks to perform a downgrade attack against any TLS connection to a vulnerable server. With this, they showed the feasibility of using Cache-like attacks. More detailed Even over the years, numerous mitigation techniques are ...


11

Was RSA inspired by Diffe-Hellman, published the year before in 1976 Update I met Ron Rivest at MIT's LCS35 time capsule unveiling and asked him this question for you. The answer is yes. Original Answer In "The first ten years of public-key cryptography", the following social relationships are mentioned: Ron Rivest had been a graduate student in ...


11

One can still access the challenge rules from the archive.org Each contest is based on a specified cipher. A brief piece of printable ASCII text (containing byte values in hexadecimal notation from 0x20 to 0x7e) will be appended to the fixed 24-character string "The unknown message is:". The result will be padded and then encrypted with the associated ...


11

What I wonder is, what motivated the creation of RSA? Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure? The New Directions In Cryptography paper introduced the idea of public-key cryptography (though it had been proposed by Merkle before), and public-key cryptography was intended to solve two ...


10

Algorithm An RSA modulus $N$ product of large distinct primes can be factored given $(N,e,d)$ per: Compute $f\gets e\,d-1$, and express $f$ as $2^s\,t$ with $t$ odd Set $i\gets s$ and $a\gets2$ Compute $b\gets a^t\bmod N$ , and if $b=1$ then set $a$ to the next prime, and proceed at 3 If $i\ne1$ then compute $c\gets b^2\bmod N$ , and if $c\ne1$ then ...


10

There is no more efficient way of generating a safe prime. Even in OpenSSL's optimized code, it can take a long time to generate a safe prime (30 seconds, a minute, 2 minutes). Run "openssl gendh 1024" on your computer to see (on my 2015 MacBook pro it can take a long time, but the variance is really high so try a few times). The comments talk about safe ...


10

The Structure of PKCS#1 v1.5 as follows; The message $m$ is padded to x = 0x00 || 0x02 || r || 0x00 || m and the ciphertext calculated as $c=x^e\bmod N$ not by $m^e\bmod N$, where $r$ is a random string. Cube root attack cannot be applied since the padding guarantees that messages are not short. The random $r$ make the encryption probabilistic so that ...


9

You can use the multiplicative group $\mathbb{Z}_p^*$, provided you use a key long enough to be secure. Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields. The challenge is that since then several methods have been found to reduce the ...


9

Sadly I'd like to know an answer for your first question as well. For your second question, you just need to see the difference between the description of a protocol and an actual instantiation of it (meaning, a cryptographic scheme). Diffie-Hellman is a cryptographic protocol, describing a way for two parties to exchange a common element in fixed ambient ...


9

You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 \lt x, y \lt B$. Then $n = x y B^2 + (x^2 + y^2)...


9

TPMs do not perform the actual encryption used for full disk encryption. All they do is encrypt the key while the system is powered off or in a suspended state. The key is decrypted and passed once to the operating system over the LPC bus, which then keeps it in memory while encryption is performed. The reason a TPM would be a poor choice for securely ...


9

If you reuse the same key material for different algorithms, you rely not on the security of any one algorithm individually, but on the security of the composition of the two algorithms simultaneously. For a particularly egregious example, if you use the same RSA public key for RSASSA-PKCS1-v1_5 and for HMAC-SHA256, the results might be entertaining. It ...


8

Yes, it's broken. Here is the approach I see: $$p = \text{gcd}( n, r^e - r \bmod n)$$ with quite high probability, for random $r$. This happens because $e \equiv 1 \bmod p-1$, and hence $r^e \equiv r \pmod p$ (for any $r$). It is unlikely that $r^e \equiv r \pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.


8

From your equations, one can write: \begin{eqnarray*} x + a_1 &=& \frac{1}{y_1} \mod \phi(n) \\ x + a_2 &=& \frac{1}{y_2} \mod \phi(n) \\ \end{eqnarray*} and thus: \begin{eqnarray*} a_1 - a_2 &=& \frac{1}{y_1} - \frac{1}{y_2} \mod \phi(n) \\ \end{eqnarray*} which leads to: \begin{eqnarray*} (a_1 - a_2) y_1 y_2 - y_2 + y_1 &=& ...


8

Using AES-256 instead of, say, AES-128 is not merely ‘future-proofing’: AES-128 provides a security level far below the standard of 128 bits today. If your application has four billion users, the expected cost of breaking one of them by the best generic brute-force attack is about $2^{96}$ evaluations of AES-128, which can be parallelized. This might not ...


8

That's correct. In some cases, you could, if you really wanted, make a public key equal the private key. It would completely negate the benefit of using a public key cryptosystem, though, because access to the public key would imply access to the private key. It would turn it into a crappy symmetric scheme. As noted in comments, most common RSA ...


7

There are RSA keys pairs in the validation suite for the RSA part of FIPS 186-4 (see second part of this answer for details). Because "encrypt/decrypt by RSA method" is not well-defined (for lack of indication of the padding method), there's no way to tell which Known Answer Test vectors for it fit the question's need. Also, only the decryption code can be ...


7

Symmetric analogue of signatures. The symmetric analogue of a signature is variously called a message authentication code, MAC, or authenticator. The same key is used to create and verify authentication tags on messages. Consequently, unlike signatures, third parties can't meaningfully verify MACs: if Alice sends a message with a MAC to Bob, Bob can't use ...


7

Steps: Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$. In your case, $2685735182215186 = 2 \times 1342867591107593$ For each prime factor $q$ of $p-1$, verify that $g^{(p-1)/q} \not\equiv 1\pmod p$ If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.


7

You can't have two different public keys for the same RSA private key. That's just not how RSA works. Well, almost. There's a minor technical loophole, and it's the fact that RSA has equivalent keys. In particular, the public keys $(n, e)$ and $(n, e + \lambda(n))$ are equivalent, in the sense of producing the same ciphertext for the same (padded) ...


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