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


33

The answer is "not safe". But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice. Google found one collision based on some existing, publicly known collision attacks on SHA-1. Sees the introduction of Google's paper for a complete list of prior work. First, let me briefly explain how RSA-SHA1 ...


21

In summary: Modern practice is to fix a small public exponent $e$ such as $e=2^{(2^4)}+1=65537$, then choose a public modulus $N$ of $\text{nlen}$ bits (the key size) with large random prime factors compatible with $e$, then compute the RSA private exponent $d$ from that. With near certainty, that $d$ will be at least $\text{nlen}/2$-bit. That can be used ...


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


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

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


15

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

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

No, "RSA with some random bits added" does not suffice. There have been attacks against many of bad padding techniques for RSA. Instead a known secure mode of operation is required. The most well known secure mode is RSA-OAEP. The earlier RSA with PKCS#1 v1.5 padding may also be secure, but it has a well known attack against it called the Bleichenbacher ...


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


10

Overall I find the proposed definition and methods satisfactory in principle, barring quantum computers usable for factorization; but the 512-bit limit for factor, and to a lesser degree the 2048-bit unfactored limit, are not conservative. Unfactored limit As noted in comment, for long term security or/and convincing security authorities, it's probably ...


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


10

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


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

Simple answer: you cannot. Identity-based encryption is an advanced cryptographic primitive, you cannot simply take any existing encryption algorithm and make it identity-based with simple modifications. There exists several constructions of IBE, but they all strongly differ from the standard RSA algorithm. You can find more information on the wikipedia page....


8

Modern cryptography generally chooses a static public exponent. Nowadays this is almost universally the fifth prime of Fermat or F4, 65537 or 010001 in hexadecimals. From this the private key is calculated given the two prime numbers that are half the size of the key size. The calculation that is performed can be seen in the answer to Calculating RSA ...


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


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