Cryptography after the landing of aliens
- Transfer
The author of the article: Bruce Schneier is an American cryptographer, a writer and computer security specialist. Author of several books on security, cryptography and security. Founder of the cryptographic company Counterpane Internet Security, Inc., member of the board of directors of the International Association for Cryptological Research and member of the advisory board of the e-Privacy Information Center.
Quantum computing is a new way to perform calculations that will allow humanity to perform calculations that are simply impossible using modern computers. The ability to quickly search will break some of the modern encryption algorithms. A light factorization of large numbers will break the RSA cryptosystem with any key length.
That is why cryptographers are now hard at work developing and analyzing "quantum-stable" public-key algorithms. Currently, quantum computing is not yet ready for a normal assessment: what is safe and what is not. But if we assume that the aliens have developed the technology in full, then quantum computing is not the end of the world for cryptography. For symmetric cryptography, to provide quantum stability is elementary, and now we are looking for quantum-resistant public key encryption algorithms. If public-key cryptography turns out to be a temporary anomaly that exists due to gaps in our mathematical knowledge and computational abilities, we will still survive. And if some unthinkable alien technology breaks all cryptography, we’ll have a secret based on information theory,
In essence, cryptography relies on a mathematical twist that some things are easier to do than to undo. How easier it is to break a plate than to glue it back together, it is also much easier to multiply two primes than decompose the result back. Asymmetries of this kind - one-way functions and one-way functions with a secret entrance - underlie all cryptography.
To encrypt a message, we combine it with a key to form a ciphertext. Without a key, the process is harder to reverse. Not just a little harder, but astronomically more difficult. Modern encryption algorithms are so fast that they encrypt your entire hard drive without any slowdowns, and the breaking of the cipher will continue until the thermal death of the Universe.
With symmetric cryptography used to encrypt messages, files, and disks, this imbalance is exponential and increases with increasing keys. Adding one bit of the key increases the encryption complexity by less than a percentage (roughly speaking), but doubles the complexity of the hacking. Thus, a 256-bit key seems to be only twice as complicated as a 128-bit key, but (with our current knowledge of mathematics) 340 282 366 920 938 463 463 374 607 431 768 211 456 times more difficult to break.
Public key encryption (used mainly for key exchange) and digital signatures are more complex. Since they rely on complex mathematical problems, such as factorization, there are more different tricks to reverse. So here you will see keys with a length of 2048 bits for RSA and 384 bits for algorithms based on elliptic curves. But again, the breaking of ciphers with these keys goes beyond the current capabilities of mankind.
The behavior of one-way functions is based on our mathematical knowledge. When you hear about a cryptographer who "breaks" the algorithm, it means that he has found a new trick that simplifies reversing. Cryptographers find new tricks all the time, so we tend to use keys longer than is strictly necessary. This is true for both symmetric algorithms and public key algorithms: we are trying to guarantee their reliability in the future.
Quantum computers promise to change a lot of this. By their nature, they are well adapted to the computations that are needed to invert these one-way functions. For symmetric cryptography, this is not so bad. Grover's algorithmshows that a quantum computer accelerates attacks so that the effective key length is halved. That is, a 256-bit key is just as complicated for a quantum computer as a 128-bit key is for a regular computer: both are safe for the foreseeable future.
For public key cryptography, the results are worse. Shor's algorithm easily breaks all popular public-key algorithms based on both factorization and discrete logarithms. Doubling the key length increases the difficulty of hacking by a factor of eight. This is not enough for sustainable development.
Regarding the last two paragraphs, there are many reservations, the main of which is that quantum computers capable of doing something like this do not currently exist, and no one knows when we can build one — and if we can. We also do not know what practical difficulties will arise when we try to implement the algorithms of Grover or Shor on anything other than toy-sized keys (an error correction mechanism on a quantum computer can easily become an insurmountable problem). On the other hand, we do not know what other methods will be discovered as soon as people start working with real quantum computers. I am betting that we will overcome engineering problems and that there will be many achievements and new methods, but it will take time to invent them. Just as it took us decades,
In the short term, cryptographers make considerable efforts to develop and analyze quantum-stable algorithms. They will probably remain safe for decades. The process will probably go slowly, because good cryptanalysis takes time. Fortunately, we have time. In practice, real quantum computing seems to be always “ten years in the future.” In other words, no one has the slightest idea.
But there is always a chance that the algorithms will be hacked by aliens with the best quantum technologies. I’m less worried about symmetric cryptography, where Grover’s algorithm is essentially the maximum limit to quantum computing. But public-key algorithms based on number theory seem more fragile. It is possible that quantum computers will ever break them all - even those that are considered quantum-stable today.
If this happens, we will remain in a world without public key cryptography. This will be a huge blow to security and will break many systems, but we will be able to adapt. In the 1980s, Kerberos was a fully symmetric authentication and encryption system. And now the GSM cellular standard performs both authentication and key distribution - on a large scale - only with symmetric cryptography. Yes, these systems have centralized points of trust and rejection, but other systems can be developed that use both secret separation and secret sharing to minimize this risk. (Imagine that a pair of communication partners receives a portion of the session key from each of the five different key servers). The widespread distribution of communications eases the situation. We can use out-of-band protocols: for example, your phone will help generate a key for the computer. For additional security, you can use personal registration: perhaps in the store where you buy a smartphone or register an online service. The development of hardware will also help protect keys in this world. I am not trying to invent anything, just saying that there are many possibilities. We know that cryptography is based on trust, and we have much more trust management methods than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection. in the store where you buy a smartphone or register an online service. The development of hardware will also help protect keys in this world. I am not trying to invent anything, just saying that there are many possibilities. We know that cryptography is based on trust, and we have much more trust management methods than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection. in the store where you buy a smartphone or register an online service. The development of hardware will also help protect keys in this world. I am not trying to invent anything, just saying that there are many possibilities. We know that cryptography is based on trust, and we have much more trust management methods than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection. than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection. than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection.
This is a strange future. Perhaps the whole idea of cryptography on number theory, like modern public-key systems, is a temporary phenomenon that exists due to gaps in the computation model. Now that the model has expanded and included quantum computing, we can find ourselves where we were in the late 1970s and early 1980s: symmetric cryptography, code-based cryptography, Merkle's signature. It will be funny and ironic.
Yes, I know that the distribution of quantum keys is a potential replacement for public-key cryptography. But let's be honest: does anyone even believe that a system that requires specialized communication equipment and cables will be used for anything other than niche applications? The future is mobile, constantly powered computing devices. All security systems for them will be software only.
There is another scenario for the future, not to mention quantum computers. One-way functions are based on several mathematical theories that have not yet been proved. This is one of the open problems in computer science. Just as a smart cryptographer can find a new trick that makes it easier to crack a specific algorithm, we can imagine aliens with enough mathematical theory to break all encryption algorithms. For us today, it's just ridiculous. Public key cryptography is a number theory, potentially vulnerable to mathematically more literate aliens. Symmetric cryptography is so nonlinearly complex, and the key length increases so easily that the future is hard to imagine. Imagine an AES version with a 512-bit block and key size, and 128 rounds encryption. Unless you come up with a fundamentally new math,
But if the unimaginable happens, then cryptography will remain, based solely on information theory: disposable notebooks and their variants. This will be a huge blow to security. Disposable notebooks can be theoretically safe, but in practical terms they are not suitable for anything other than specialized niche applications. Today, only psychos are trying to build common use systems based on disposable notebooks - and cryptographers laugh at them, because they replace the problems of developing algorithms (light) with problems of managing keys and physical security problems (which is much, much more difficult). Perhaps in our fantastic future, captured by aliens, we will have only such a way out.
Against these godlike aliens, cryptography will remain the only technology we can be sure of. Nuclear bombs may not explode, and fighters may fall from the sky, but we can still communicate safely using disposable notebooks. There is a certain optimism in this.
Quantum computing is a new way to perform calculations that will allow humanity to perform calculations that are simply impossible using modern computers. The ability to quickly search will break some of the modern encryption algorithms. A light factorization of large numbers will break the RSA cryptosystem with any key length.That is why cryptographers are now hard at work developing and analyzing "quantum-stable" public-key algorithms. Currently, quantum computing is not yet ready for a normal assessment: what is safe and what is not. But if we assume that the aliens have developed the technology in full, then quantum computing is not the end of the world for cryptography. For symmetric cryptography, to provide quantum stability is elementary, and now we are looking for quantum-resistant public key encryption algorithms. If public-key cryptography turns out to be a temporary anomaly that exists due to gaps in our mathematical knowledge and computational abilities, we will still survive. And if some unthinkable alien technology breaks all cryptography, we’ll have a secret based on information theory,
In essence, cryptography relies on a mathematical twist that some things are easier to do than to undo. How easier it is to break a plate than to glue it back together, it is also much easier to multiply two primes than decompose the result back. Asymmetries of this kind - one-way functions and one-way functions with a secret entrance - underlie all cryptography.
To encrypt a message, we combine it with a key to form a ciphertext. Without a key, the process is harder to reverse. Not just a little harder, but astronomically more difficult. Modern encryption algorithms are so fast that they encrypt your entire hard drive without any slowdowns, and the breaking of the cipher will continue until the thermal death of the Universe.
With symmetric cryptography used to encrypt messages, files, and disks, this imbalance is exponential and increases with increasing keys. Adding one bit of the key increases the encryption complexity by less than a percentage (roughly speaking), but doubles the complexity of the hacking. Thus, a 256-bit key seems to be only twice as complicated as a 128-bit key, but (with our current knowledge of mathematics) 340 282 366 920 938 463 463 374 607 431 768 211 456 times more difficult to break.
Public key encryption (used mainly for key exchange) and digital signatures are more complex. Since they rely on complex mathematical problems, such as factorization, there are more different tricks to reverse. So here you will see keys with a length of 2048 bits for RSA and 384 bits for algorithms based on elliptic curves. But again, the breaking of ciphers with these keys goes beyond the current capabilities of mankind.
The behavior of one-way functions is based on our mathematical knowledge. When you hear about a cryptographer who "breaks" the algorithm, it means that he has found a new trick that simplifies reversing. Cryptographers find new tricks all the time, so we tend to use keys longer than is strictly necessary. This is true for both symmetric algorithms and public key algorithms: we are trying to guarantee their reliability in the future.
Quantum computers promise to change a lot of this. By their nature, they are well adapted to the computations that are needed to invert these one-way functions. For symmetric cryptography, this is not so bad. Grover's algorithmshows that a quantum computer accelerates attacks so that the effective key length is halved. That is, a 256-bit key is just as complicated for a quantum computer as a 128-bit key is for a regular computer: both are safe for the foreseeable future.
For public key cryptography, the results are worse. Shor's algorithm easily breaks all popular public-key algorithms based on both factorization and discrete logarithms. Doubling the key length increases the difficulty of hacking by a factor of eight. This is not enough for sustainable development.
Regarding the last two paragraphs, there are many reservations, the main of which is that quantum computers capable of doing something like this do not currently exist, and no one knows when we can build one — and if we can. We also do not know what practical difficulties will arise when we try to implement the algorithms of Grover or Shor on anything other than toy-sized keys (an error correction mechanism on a quantum computer can easily become an insurmountable problem). On the other hand, we do not know what other methods will be discovered as soon as people start working with real quantum computers. I am betting that we will overcome engineering problems and that there will be many achievements and new methods, but it will take time to invent them. Just as it took us decades,
In the short term, cryptographers make considerable efforts to develop and analyze quantum-stable algorithms. They will probably remain safe for decades. The process will probably go slowly, because good cryptanalysis takes time. Fortunately, we have time. In practice, real quantum computing seems to be always “ten years in the future.” In other words, no one has the slightest idea.
But there is always a chance that the algorithms will be hacked by aliens with the best quantum technologies. I’m less worried about symmetric cryptography, where Grover’s algorithm is essentially the maximum limit to quantum computing. But public-key algorithms based on number theory seem more fragile. It is possible that quantum computers will ever break them all - even those that are considered quantum-stable today.
If this happens, we will remain in a world without public key cryptography. This will be a huge blow to security and will break many systems, but we will be able to adapt. In the 1980s, Kerberos was a fully symmetric authentication and encryption system. And now the GSM cellular standard performs both authentication and key distribution - on a large scale - only with symmetric cryptography. Yes, these systems have centralized points of trust and rejection, but other systems can be developed that use both secret separation and secret sharing to minimize this risk. (Imagine that a pair of communication partners receives a portion of the session key from each of the five different key servers). The widespread distribution of communications eases the situation. We can use out-of-band protocols: for example, your phone will help generate a key for the computer. For additional security, you can use personal registration: perhaps in the store where you buy a smartphone or register an online service. The development of hardware will also help protect keys in this world. I am not trying to invent anything, just saying that there are many possibilities. We know that cryptography is based on trust, and we have much more trust management methods than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection. in the store where you buy a smartphone or register an online service. The development of hardware will also help protect keys in this world. I am not trying to invent anything, just saying that there are many possibilities. We know that cryptography is based on trust, and we have much more trust management methods than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection. in the store where you buy a smartphone or register an online service. The development of hardware will also help protect keys in this world. I am not trying to invent anything, just saying that there are many possibilities. We know that cryptography is based on trust, and we have much more trust management methods than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection. than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection. than in the early years of the Internet. Some important technologies, such as direct secrecy, will become much more difficult, but as long as symmetric cryptography works, we still have protection.
This is a strange future. Perhaps the whole idea of cryptography on number theory, like modern public-key systems, is a temporary phenomenon that exists due to gaps in the computation model. Now that the model has expanded and included quantum computing, we can find ourselves where we were in the late 1970s and early 1980s: symmetric cryptography, code-based cryptography, Merkle's signature. It will be funny and ironic.
Yes, I know that the distribution of quantum keys is a potential replacement for public-key cryptography. But let's be honest: does anyone even believe that a system that requires specialized communication equipment and cables will be used for anything other than niche applications? The future is mobile, constantly powered computing devices. All security systems for them will be software only.
There is another scenario for the future, not to mention quantum computers. One-way functions are based on several mathematical theories that have not yet been proved. This is one of the open problems in computer science. Just as a smart cryptographer can find a new trick that makes it easier to crack a specific algorithm, we can imagine aliens with enough mathematical theory to break all encryption algorithms. For us today, it's just ridiculous. Public key cryptography is a number theory, potentially vulnerable to mathematically more literate aliens. Symmetric cryptography is so nonlinearly complex, and the key length increases so easily that the future is hard to imagine. Imagine an AES version with a 512-bit block and key size, and 128 rounds encryption. Unless you come up with a fundamentally new math,
But if the unimaginable happens, then cryptography will remain, based solely on information theory: disposable notebooks and their variants. This will be a huge blow to security. Disposable notebooks can be theoretically safe, but in practical terms they are not suitable for anything other than specialized niche applications. Today, only psychos are trying to build common use systems based on disposable notebooks - and cryptographers laugh at them, because they replace the problems of developing algorithms (light) with problems of managing keys and physical security problems (which is much, much more difficult). Perhaps in our fantastic future, captured by aliens, we will have only such a way out.
Against these godlike aliens, cryptography will remain the only technology we can be sure of. Nuclear bombs may not explode, and fighters may fall from the sky, but we can still communicate safely using disposable notebooks. There is a certain optimism in this.