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

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


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


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


14

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


14

The bozos at Clown Sterling have adapted the advanced technology of bogosort to factoring: randomly blow a candidate solution out your nose and check whether it works. For a semiprime $n$ chosen by modern RSA key generation methods, there are approximately $\sqrt n$ candidate solutions to check, which is also the expected cost of this method. For instance, ...


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


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


11

I'm one of the authors of the paper. In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each stand on their own mostly independent of the others. "Approximate encoded permutations and piecewise quantum adders ". We put small amounts of padding at various ...


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

TLS 1.3 has a huge clean up as having 5 cipher suites. As stated in the RFC document RFC 8446 section 1.2 : Static RSA and Diffie-Hellman cipher suites have been removed; all public-key based key exchange mechanisms now provide forward secrecy. With forward secrecy (also called PFS for Perfect Forward Secrecy), even if one of the site's key is ...


10

No, unfortunately your well meant comparison with HMAC fails and RSA with SHA-1 - as defined for PKCS#1 v1.5 padding and PSS - is considered insecure. The construction of HMAC makes it near invulnerable to attacks on the collision resistance of the underlying hash. That is because it uses the secret key as input to the hash function to create the additional ...


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


9

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


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

TLDR: the efficiency of what they demo is below state of the art a decade ago. What they describe would be plain abyssal. In the event described in the press release, Crown Sterling made a public demonstration, which can be watched there. The meat of it is a demonstration of the factorization of a 77-digit (256-bit) public modulus of an RSA key, ...


8

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? No. Factoring numbers with special forms like that is easy. You have a Mersenne number, $n = 2^e - 1$, whose exponent $e = 2048$ is composite. Whenever $e = u v$, we have $2^u - 1 \mid (2^u)^v - 1 = 2^e - 1$, since in general $x - 1 \mid x^k - 1$. (...


7

RSA for key exchange is declining rapidly and is not recommended because it does not provide forward secrecy. Without forward secrecy, if someone breaks into the server and obtains the private key, they will be able to fully retroactively decrypt all recorded traffic encrypted under that key. ECDH does not have that problem because the private and public ...


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 wouldn't be a Dave for presenting RSA, but you would be a Dave for following this description to implement anything, and you risk creating Daves with this presentation. I'm not saying you shouldn't do it, but you should emphasize that this is only the mathematical basis of RSA and a lot more is involved in making it do something useful. Your description ...


7

The RSA problem, which is the underlying problem that makes RSA cryptographically secure, is currently considered as an unsolved problem. There exists no known algorithm to efficiently compute P, given the public key (N, e) and the ciphertext C ≡ Pe (mod N). But who cares about theory, right? You claim to have a solution, then try it! Here is an RSA public ...


7

Your N value, 209, has 8 bits. In practice, RSA uses N values larger than 2048 bits, which can't be factorized in reasonable time in a math software or any other software.


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