Just in case you never saw RSA and didn't understand @0xfatty's fun discovery, here's some background.
A thread.
RSA is a famous cryptosystem invented in the 1970s, and still widely deployed. Its inventors won the Turing Award, computer science's equivalent of the Nobel Prize.
A thread.
RSA is a famous cryptosystem invented in the 1970s, and still widely deployed. Its inventors won the Turing Award, computer science's equivalent of the Nobel Prize.
https://twitter.com/XorNinja/status/1437302542547914758
When used properly*, RSA allows humans and machines to digitally sign document to prove authenticity. Given a document and its RSA signature, anyone can verify that the document has not been modified. This is one of the most wonderful inventions of the 20th century.
I put a star to the word property because there are people like yours truly spending their entire adult life on finding, exploiting and preventing improper use of RSA (and other cryptosystems).
Using RSA with a small key is a classical misuse.
Using RSA with a small key is a classical misuse.
What's a RSA key? A RSA key consists of two components: a private key and a public key. To sign documents, one must have the private key. To verify, one only needs the public key. Thus, the private key must be kept secret, but the public key are usually disclosed publicly.
Since the public key is public, it's of paramount importance that nobody can figure out the private key from it.
A RSA private key contains at minimum 4 large numbers: p, q, e, d. A public key contains 2 numbers: e and N = p * q. Yes, N is the multiplication of p and q.
A RSA private key contains at minimum 4 large numbers: p, q, e, d. A public key contains 2 numbers: e and N = p * q. Yes, N is the multiplication of p and q.
p and q are (hopefully) randomly generated prime numbers, and d is called the private exponent. These numbers must be kept secret.
If one can figure out p and q, one can easily compute d which is all one needs to sign documents.
If one can figure out p and q, one can easily compute d which is all one needs to sign documents.
N is called the modulus, and its size in bits is the key size. That is, Hanoi using 512-bit keys means its N is a 512-bit number. This is a huge number, having 154 digits, but, unfortunately, it's still too small. Acceptable RSA deployments nowadays require 2048-bit keys.
Since N is part of the public key, everybody knows its value. The security of RSA therefore relies on the fact that given a sufficiently large N, nobody knows how to compute p and q.
This is a surprisingly hard problem that has remained unsolved for thousands of years.
This is a surprisingly hard problem that has remained unsolved for thousands of years.
What about small N? They are easier to factorize! State of the art algorithm and software can already factorize ~900-bit N. 512-bit should take only hours.
This is exactly what @0xfatty did.
/End
This is exactly what @0xfatty did.
/End
• • •
Missing some Tweet in this thread? You can try to
force a refresh
