5 ms·

Quick summary, he's found a faster way to factor numbers. He hasn't found a way to break RSA that isn't equivalent to factoring the modulus. (As far as I know

by KMag 6y ago

Quick summary, he's found a faster way to factor numbers. He hasn't found a way to break RSA that isn't equivalent to factoring the modulus. (As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. RSA always uses odd exponents. The Rabin cryptosystem is similar to RSA except that it always uses 2 as the public exponent and is provably as difficult as factoring, but if the modulus has 2 prime factors p and q, then by the Chinese remainder theorem, the output will always be a quadratic residue modulo p and also a quadratic residue modulo q. In other words, the number of possible plaintexts is 4 times the number of possible ciphertexts, so decryption gives you back 4 possibilities and you need some convention that only one of those was a legal message.) Unfortunately, this is a faster factoring method, so it also applies to the Rabin cryptosystem, the Blum-Blum-Shub pseudorandom number generator, and Rivest's time lock puzzles (repeated squaring modulo a large composite).

phkahler 6y ago
>> As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one. Edit: oh maybe you mean that it's possible to break RSA faster without factoring... Its been too long since I looked at that.
- KMag 6y ago
  > No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one. You have misread my post. The conjecture is that the RSA problem is as difficult as the factoring problem. In other words, it's possible that solving the RSA problem isn't as difficult as the factoring problem (but most people doubt it). A <= B. Most people think A == B. This is the inverse of your statement. Factoring breaking RSA doesn't tell us if there's a non-factoring solution to the RSA problem. Everyone knows breaking RSA is no more difficult than factoring, but it may be easier than factoring. A break in the Rabin cryptosystem would provably break RSA, but it's not necessarily true that a break in RSA would break the Rabin cryptosystem. Edit: Paragraph 4 of https://en.wikipedia.org/wiki/RSA_problem https://en.wikipedia.org/wiki/RSA_problem at least believes it's still a conjecture that RSA is as difficult as the factoring problem.
  - phkahler 6y ago
    Yeah, that's what I tried to say with my edit.
airhead969 6y ago
Seems like not a fault of the construction of RSA or anything else that relies on the cost of factoring, but a fault of appropriately anticipating the costs to break it. Useable quantum will also make crypto security more expensive and complicated. Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.
- deleted 6y ago
  [deleted]
- KMag 6y ago
  > Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force. People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. In general, there's not a linear relation between the two, and the time for initial TLS session setup matters. If it takes a year to hit amazon.com for the first time, how many people are going to visit amazon.com?
  - arghwhat 6y ago
    > People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. If it takes me k time to decrypt something where there are N key variations and where I can run p attempts in parallel, the maximum runtime for a brute force attack is k*N/p. Perfectly linear relationship. This is why we want large key spaces, and why algorithms needing offline brute force protection like password hashing algorithms artificially increase execution time and resource requirements to very large numbers.
    - KMag 6y ago
      > This is why we want large key spaces, This is a subset of what I'm talking about. Encryption/decryption times aren't linear with key space sizes. Force the number of required parallel instances to exceed the number of atoms on Earth, and bruit force time rapidly diverges from being linear with encryption/decryption time.
thaumasiotes 6y ago
> the number of possible plaintexts is 4 times the number of possible ciphertexts, so decryption gives you back 4 possibilities and you need some convention that only one of those was a legal message. This condition is satisfied by ~100% of all communications, including stuff like software downloads. (If I send you a file, then yes, any message is legal, but as soon as you try to do anything with it, you'll know whether the message was correct or not.)
- KMag 6y ago
  More importantly, Rabin would be used in a hybrid cryptosystem, including message authentication codes, so you could calculate MACs using all 4 possible keys. Though, it would be much lower overhead and safer to use OAEP[0] to encode the symmetric cipher/MAC key(s) and then encrypt with Rabin. There's very low probability that more than one of the 4 possible plaintexts has all zeroes for padding after OAEP decoding. [0] https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_...

by KMag 6y ago

phkahler 6y ago

>> As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one. Edit: oh maybe you mean that it's possible to break RSA faster without factoring... Its been too long since I looked at that.

KMag 6y ago
> No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one. You have misread my post. The conjecture is that the RSA problem is as difficult as the factoring problem. In other words, it's possible that solving the RSA problem isn't as difficult as the factoring problem (but most people doubt it). A <= B. Most people think A == B. This is the inverse of your statement. Factoring breaking RSA doesn't tell us if there's a non-factoring solution to the RSA problem. Everyone knows breaking RSA is no more difficult than factoring, but it may be easier than factoring. A break in the Rabin cryptosystem would provably break RSA, but it's not necessarily true that a break in RSA would break the Rabin cryptosystem. Edit: Paragraph 4 of https://en.wikipedia.org/wiki/RSA_problem https://en.wikipedia.org/wiki/RSA_problem at least believes it's still a conjecture that RSA is as difficult as the factoring problem.
- phkahler 6y ago
  Yeah, that's what I tried to say with my edit.

airhead969 6y ago

Seems like not a fault of the construction of RSA or anything else that relies on the cost of factoring, but a fault of appropriately anticipating the costs to break it. Useable quantum will also make crypto security more expensive and complicated. Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.

deleted 6y ago
[deleted]
KMag 6y ago
> Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force. People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. In general, there's not a linear relation between the two, and the time for initial TLS session setup matters. If it takes a year to hit amazon.com for the first time, how many people are going to visit amazon.com?
- arghwhat 6y ago
  > People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. If it takes me k time to decrypt something where there are N key variations and where I can run p attempts in parallel, the maximum runtime for a brute force attack is k*N/p. Perfectly linear relationship. This is why we want large key spaces, and why algorithms needing offline brute force protection like password hashing algorithms artificially increase execution time and resource requirements to very large numbers.
  - KMag 6y ago
    > This is why we want large key spaces, This is a subset of what I'm talking about. Encryption/decryption times aren't linear with key space sizes. Force the number of required parallel instances to exceed the number of atoms on Earth, and bruit force time rapidly diverges from being linear with encryption/decryption time.

thaumasiotes 6y ago

> the number of possible plaintexts is 4 times the number of possible ciphertexts, so decryption gives you back 4 possibilities and you need some convention that only one of those was a legal message. This condition is satisfied by ~100% of all communications, including stuff like software downloads. (If I send you a file, then yes, any message is legal, but as soon as you try to do anything with it, you'll know whether the message was correct or not.)

KMag 6y ago
More importantly, Rabin would be used in a hybrid cryptosystem, including message authentication codes, so you could calculate MACs using all 4 possible keys. Though, it would be much lower overhead and safer to use OAEP[0] to encode the symmetric cipher/MAC key(s) and then encrypt with Rabin. There's very low probability that more than one of the 4 possible plaintexts has all zeroes for padding after OAEP decoding. [0] https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_...