Cracked RSA Crypto? Or maybe not! – Bare Security

[ad_1]

There’s been a bit of a scramble in the tech media over the past few days about whether the venerable public-key encryption system known as RSA might soon be cracked.

RSA, as you probably know, is short for Rivest-Shamir-Adleman, the three cryptographers who devised what has turned into an amazingly useful and durable encryption system by means of which two people can communicate securely …

…without meeting first to agree on a secret encryption key.

Simply put, RSA does not have one key, like a traditional door lock, but two different keys, one to lock the door and the other to unlock it.

You can generate a pair of keys one to lock and one to unlock pretty quickly, but since there’s only one, you can’t figure out what the other looks like.

So you designate one as your “public key”, which you share with the world, and keep the other as your “private key”.

This means that anyone who wants to send you a private message can lock it with your public key, but (assuming you really treat your private key as private) only you can unlock it – even if you’ve never met the other offline person to share a common front lock and unlock key.

In the other direction, someone who wants you to prove your identity can send you a message and ask you to lock it with your private key and send it back.

If your public key unlocks it correctly, then they have reason to think you are who you say.

(We’ll ignore here the issues of how you make sure a public key really belongs to the person you think you do, what you do if you realize your private key has been stolen, and many other complexities related to use of this type of arrangement in real life The big problem is that RSA provides a two-key system where one key cannot be evolved from the other.)

Public Key Crypto

You’ll see this type of process called public-key cryptography, public-private encryption, or asymmetric encryption (symmetric encryption, such as AES, is where the same key is used to lock and unlock your data).

In fact, if you really know your cryptographic history, you might even know it by the curious name Non-Secret Cipher (NSE), because cryptographers in the UK had had a similar idea a few years earlier, but in this which turned out to be a massively missed opportunity, the British government decided to suppress the discovery, and not to develop or even publish the process.

Even though there are alternatives to RSA today that allow you to have smaller public and private keys, and are based on algorithms that run faster, RSA is still widely used, and there are still a lot of potentially crackable data in archives, log files and network captures protected by RSA during transmission.

In other words, if RSA turns out to be easily crackable (for some senses of easily, at least), for example because a Big Fast Quantum Computer is coming, we would have reasonable cause for concern.

Well, as cybersecurity expert Bruce Schneier recently observed, a large team of Chinese computer scientists just published a paper titled Integer Factoring with Sublinear Resources on a Superconducting Quantum Processor.

The big problem with factoring integers (where you find, for example, that 15 = 3 × 5, or that 15538213 x 16860433 = 261980999226229) is that doing exactly that is at the heart of RSA cracking, which is based on calculations involving two huge random primes.

In RSA everyone knows the number you get when you multiply those numbers together (called the product), but only the person who originally came up with the starting numbers knows how the product was created – the factors together essentially form their private key.

So if you could split the product into its unique pair of prime factors (as they are known), you would be able to crack that person’s encryption.

The thing is, if your initial primes are large enough (nowadays 1024 bits each, or more, for a 2048 bit product, or more), you simply won’t have enough computational power to differentiate the product.

Unless you can build, buy, or rent a powerful enough quantum computer.

Large premium products

Apparently the largest principal product ever accounted for by a quantum computer is just 249919 (491 x 509), which my eight-year-old laptop can handle conventionally, including the time it takes to load the program and print the response, in such a short time that the response is variously reported as 0 milliseconds or 1 millisecond.

And, as Chinese researchers report, standard methods of approaching RSA cracking with a quantum computer would require millions of so-called qubits (quantum computer-like bits), whereas the largest such computer known today has just over 400 qubits.

As you can see, if RSA-2048 needs millions of qubits to break, you need more qubits than there are bits in the number you want to factor.

But the researchers suggest they may have found a way to optimize the cracking process so that it not only requires less than a million qubits, but even fewer qubits than the number of bits in the number that you try to crack:

We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is needed to challenge RSA-2048 using our algorithm. Our study holds great promise for accelerating the application of current noisy quantum computers and paves the way for factoring large integers of realistic cryptographic significance.

The burning question is…

Are they right?

If we already have computers with hundreds of qubits, is the end of RSA-2048 really imminent?

We just don’t have the mathematical expertise to tell you this – their 32-page paper isn’t for the faint-hearted or even for mathematical generalists – but the consensus, for now at least, seems to be. .

No.

Nonetheless, now is a great time to reflect on how prepared you are for any encryption or hashing algorithm to suddenly fail, whether for quantum reasons or not.

[ad_2]