5 ms·

RSA Algorithm

55 points by keyboardman 7y ago

arberavdullahu 7y ago
> Quantum computer, however, is good at integer factorization. Using Shor’s algorithm, quantum computer does integer factorization in polynomial time, which makes cracking the RSA cryptosystem possible. Does increasing the size of the key get around this problem, if not is there any solution to this?
- LocalRSAExpert 7y ago
  Yes, between 100 GB and 1 TB of private key does it.
  - cipherboy 7y ago
    Citation, for those curious: https://cr.yp.to/papers/pqrsa-20170419.pdf https://cr.yp.to/papers/pqrsa-20170419.pdf
- selfup 7y ago
  The end game is to switch to a post-quantum algorithm. Essentially something that both quantum and classical computers cannot crack/brute force. I would look into lattice-based crypto. It is one of the strongest candidates under review by NIST for post-quantum public/private key mechanisms.
LocalRSAExpert 7y ago
> RSA (Rivest–Shamir–Adleman) algorithm is an asymmetric cryptographic algorithm that is widely used in the modern public-key cryptosystems. The very definition of modern public-key crypto is that it doesn't use RSA :) > Cracking the RSA encryption system using brute force is not practically feasible. Cracking the RSA encryption system as implemented by someone reading a lecture like this is straightforward. Heck, "padding" doesn't even appear in it, most university slides at least mention "oh by the way, this thing's pretty useless without padding". In my opinion this article falls squarely in the "talking about RSA considered harmful" category: showing textbook RSA, then saying it [RSA] is secure, without mentioning how hard it actually is to achieve that.
- cipherboy 7y ago
  Relevant exercises: https://cryptopals.com/sets/6 https://cryptopals.com/sets/6 Reminds me of when I was at University. One of my professors had implemented RSA as one of his lecture examples in their advanced C class. I forget why, I was too busy reading the implementation. The net result was that a brute-force attack was possible, simply because the keys were generated from an insecure RNG and seeding system: https://github.com/cipherboy/coms327-RSA_Crack https://github.com/cipherboy/coms327-RSA_Crack
- giggly_gopher 7y ago
  I cringed when I read > The ordinary algorithm to do integer factorization takes sub-exponential time according to the Wikipedia. This is the fundamental reason which makes the RSA cryptosystem so reliable.
- SAI_Peregrinus 7y ago
  Not only does it show textbook RSA, it doesn't even show signing! There are two secure ways to use RSA: as a signature scheme with appropriate padding (PSS), or as a Key Encapsulation Mode (KEM) which inherently doesn't require padding. The general rule is that if an article on RSA includes anything about "encrypting a message" it's naive and outdated, and should be ignored. RSA encryption is slow and error-prone. RSA signatures are slow to generate (though fast to verify) and error-prone. RSA-KEM is at least not any more error-prone than the rest of cryptography, it's just slow.
- skizm 7y ago
  What is the state of the art asymmetric crypto algorithm?
6c696e7578 7y ago
Is it wrong that I think https://en.wikipedia.org/wiki/Clifford_Cocks https://en.wikipedia.org/wiki/Clifford_Cocks should have some credit? I always feel sorry for him that so much infrastructure depends on RSA, yet he almost goes unknown.
- hyper_reality 7y ago
  That's really his problem for working in secret for GCHQ. Diffie, Hellman, Rivest, Shamir, and Adleman are the ones who are rightfully lauded for bringing public key cryptography to the public sphere.
- Fnoord 7y ago
  If you invent something, but you do not share it with the general public, and a group of other people invent an equivalent, then who was first to invent? Who is going to have the credit? I'd say it is akin to a proprietary technology which never got released to the general public, and then some FOSS technology comes along which does arguably the same, yet is FOSS and gets widely adopted. Want the credit? Should've released it to the public then. That's a side effect of working for secret services; you don't get much, if any, personal credit. Nor even credit as a secret service. E.g. because the ops remain secret.

55 points by keyboardman 7y ago

> Quantum computer, however, is good at integer factorization. Using Shor’s algorithm, quantum computer does integer factorization in polynomial time, which makes cracking the RSA cryptosystem possible. Does increasing the size of the key get around this problem, if not is there any solution to this?

LocalRSAExpert 7y ago
Yes, between 100 GB and 1 TB of private key does it.
- cipherboy 7y ago
  Citation, for those curious: https://cr.yp.to/papers/pqrsa-20170419.pdf https://cr.yp.to/papers/pqrsa-20170419.pdf
selfup 7y ago
The end game is to switch to a post-quantum algorithm. Essentially something that both quantum and classical computers cannot crack/brute force. I would look into lattice-based crypto. It is one of the strongest candidates under review by NIST for post-quantum public/private key mechanisms.

LocalRSAExpert 7y ago

> RSA (Rivest–Shamir–Adleman) algorithm is an asymmetric cryptographic algorithm that is widely used in the modern public-key cryptosystems. The very definition of modern public-key crypto is that it doesn't use RSA :) > Cracking the RSA encryption system using brute force is not practically feasible. Cracking the RSA encryption system as implemented by someone reading a lecture like this is straightforward. Heck, "padding" doesn't even appear in it, most university slides at least mention "oh by the way, this thing's pretty useless without padding". In my opinion this article falls squarely in the "talking about RSA considered harmful" category: showing textbook RSA, then saying it [RSA] is secure, without mentioning how hard it actually is to achieve that.

cipherboy 7y ago
Relevant exercises: https://cryptopals.com/sets/6 https://cryptopals.com/sets/6 Reminds me of when I was at University. One of my professors had implemented RSA as one of his lecture examples in their advanced C class. I forget why, I was too busy reading the implementation. The net result was that a brute-force attack was possible, simply because the keys were generated from an insecure RNG and seeding system: https://github.com/cipherboy/coms327-RSA_Crack https://github.com/cipherboy/coms327-RSA_Crack
giggly_gopher 7y ago
I cringed when I read > The ordinary algorithm to do integer factorization takes sub-exponential time according to the Wikipedia. This is the fundamental reason which makes the RSA cryptosystem so reliable.
SAI_Peregrinus 7y ago
Not only does it show textbook RSA, it doesn't even show signing! There are two secure ways to use RSA: as a signature scheme with appropriate padding (PSS), or as a Key Encapsulation Mode (KEM) which inherently doesn't require padding. The general rule is that if an article on RSA includes anything about "encrypting a message" it's naive and outdated, and should be ignored. RSA encryption is slow and error-prone. RSA signatures are slow to generate (though fast to verify) and error-prone. RSA-KEM is at least not any more error-prone than the rest of cryptography, it's just slow.
skizm 7y ago
What is the state of the art asymmetric crypto algorithm?

6c696e7578 7y ago

Is it wrong that I think https://en.wikipedia.org/wiki/Clifford_Cocks https://en.wikipedia.org/wiki/Clifford_Cocks should have some credit? I always feel sorry for him that so much infrastructure depends on RSA, yet he almost goes unknown.

hyper_reality 7y ago
That's really his problem for working in secret for GCHQ. Diffie, Hellman, Rivest, Shamir, and Adleman are the ones who are rightfully lauded for bringing public key cryptography to the public sphere.
Fnoord 7y ago
If you invent something, but you do not share it with the general public, and a group of other people invent an equivalent, then who was first to invent? Who is going to have the credit? I'd say it is akin to a proprietary technology which never got released to the general public, and then some FOSS technology comes along which does arguably the same, yet is FOSS and gets widely adopted. Want the credit? Should've released it to the public then. That's a side effect of working for secret services; you don't get much, if any, personal credit. Nor even credit as a secret service. E.g. because the ops remain secret.