БЛОГ

Apr 8, 2019

QC — Cracking RSA with Shor’s Algorithm

Posted by in categories: cybercrime/malcode, encryption, information science

With new advances in technology it all comes down to simple factoring. Classical factoring systems are outdated where some problems would take 80 billion years to solve but with new technologies such as the dwave 2 it can bring us up to speed to do the same problems in about 2 seconds. Shores algorithm shows us also we can hack anything with it simply would need the technology and code simple enough and strong enough. Basically with new infrastructure we can do like jason…


RSA is the standard cryptographic algorithm on the Internet. The method is publicly known but extremely hard to crack. It uses two keys for encryption. The public key is open and the client uses it to encrypt a random session key. Anyone intercepts the encrypted key must use the second key, the private key, to decrypt it. Otherwise, it is just garbage. Once the session key is decrypted, the server uses it to encrypt and decrypt further messages with a faster algorithm. So, as long as we keep the private key safe, the communication will be secure.

RSA encryption is based on a simple idea: prime factorization. Multiplying two prime numbers is pretty simple, but it is hard to factorize its result. For example, what are the factors for 507,906,452,803? Answer: 566,557 × 896,479.

Based on this asymmetry in complexity, we can distribute a public key based on the product of two prime numbers to encrypt a message. But without knowing the prime factors, we cannot decrypt the message to its original intention. In 2014, WraithX used a budget of $7,600 on Amazon EC2 and his/her own resources to factorize a 696-bit number. We can break a 1024-bit key with a sizeable budget within months or a year. This is devasting because SSL certificates holding the public key last for 28 months. Fortunately, the complexity of the prime factorization problem grows exponentially with the key length. So, we are pretty safe since we switch to 2048-bit keys already.

Read more

Leave a reply