What Would Happen If All Encryption Could Be Broken? (wikipedia.org) 316
"What would happen, or what should happen, if tomorrow a trivial method was discovered for Prime Factorization?" asks Slashdot reader medv4380:
By trivial I mean an algorithm that runs in relatively constant time that could factor a number like 2737631357921793461914298938174501291 relatively instantly on most modern hardware today. And that even increasing the bit length wouldn't slow it down much. How much chaos would result if such a method were revealed tomorrow with little warning?
Keeping it a secret only means that others may have long ago exploited the method at the expense of others. Should proof be presented without revealing the method, to reduce the impact, and who should be told first if at all?
Slashdot reader Shikaku sees a real possibility of this actually happening when quantum computers are developed, adding that quantum-resistant encryption "is an ongoing experiment."
But if development lags -- what would happen if all encryption could be broken?
Keeping it a secret only means that others may have long ago exploited the method at the expense of others. Should proof be presented without revealing the method, to reduce the impact, and who should be told first if at all?
Slashdot reader Shikaku sees a real possibility of this actually happening when quantum computers are developed, adding that quantum-resistant encryption "is an ongoing experiment."
But if development lags -- what would happen if all encryption could be broken?
It would impact some encryption (Score:5, Informative)
It would impact some encryption, but only those that relies on private/public keys.
Other encryptions using symmetric keys are not sensitive to this issue, but they may be sensitive to other kinds of attack. Like the Enigma machine, it was never using any prime numbers, but had other flaws causing it to be cracked.
Re: (Score:2)
impact some encryption
Modestly said. For instance, millions of websites rely on private/public keys. So one day HTTPS will be as bad as HTTP. And I'm not sure if quantum resistant HTTPS will work fast on conventional hardware. Also there are many encrypted files/archives, signed executables etc.
Re: (Score:3)
Note that even for asymmetric encryption, there are some asymmetric algorithms that we are getting confidence in that can provide the same public/private key behaviors to be a mainstay of https.
If the time should ever come that Shor's algorithm can actually be brought to bear, it seems near certain that TLS will have a comfortably ubiquitous solution.
Re:It would impact some encryption (Score:5, Interesting)
Some quantum-safe algorithms, such as the ones based on lattices, are actually faster than ECC.
The trade-off for quantum safety is usually larger keys and/or signatures, or greater computation.
Citation: In my day job I work at implementing quantum-safe algorithms.
tinyssh (Score:4, Informative)
A post-quantum key exchange algorithm has been added to tinyssh [tinyssh.org], which has also been added to OpenSSH as an experimental feature.
Postquantum crypto: sntrup4591761x25519-sha512@tinyssh.org
Author: djm@openbsd.org <djm@openbsd.org>
Date: Mon Jan 21 10:20:12 2019 +0000
upstream: Add support for a PQC KEX/KEM:
sntrup4591761x25519-sha512@tinyssh.org using the Streamlined NTRU Prime 4591^761 implementation from SUPERCOP coupled with X25519 as a stop-loss. Not enabled by default.
introduce KEM API; a simplified framework for DH-ish KEX methods.
from markus@ feedback & ok djm@
Re: (Score:2)
An honest question. How many attacks today try to hit sites without encryption to get their data?
Before the early 2000's Networking gear was wicked expensive. So most people just used normal hubs on their network. These hubs allowed for easy packet sniffing.
That was 20 years ago. Most networks now use switches and routers for the network traffic. Even home use, people will not be getting hubs anymore. This makes it harder to sniff traffic, as your particular wire gets data that has been meant for your com
Re: (Score:2)
Yes, without encryption, my neighbor or third party attackers are likely still going to have a tricky time getting in the data path.
However your network provider (your corporate network, your ISP, the open wifi at the cofee shop) is a very likely adversary. Even if they aren't, they represent a huge attack surface for those third parties to get at your traffic.
Additionally, encryption is also the backbone of site identity authentication. One of the best ways to get information that isn't sniffing is phish
Re:It would impact some encryption (Score:5, Funny)
Other encryptions using symmetric keys are not sensitive to this issue, but they may be sensitive to other kinds of attack. Like the Enigma machine, it was never using any prime numbers, but had other flaws causing it to be cracked.
The biggest flaws in Engima, JN25 and almost any cypher or coding scheme used by humans are the humans. With Engima and JN25 allied code breakers relied on what they called "cribs" or now days called a "known plaintext attack". British code breakers learned certain terms that German operators often used, things like names of girlfriends, jokes, et al. that made breaking the code extremely easy, especially early in the war. Add this to the superior detection capabilities of the British that could identify where the signals were being sent from.
The Germans were aware of this flaw and took steps to correct it, especially later in the war but the Japanese were far worse with their culture having very rigid honorifics. American code breakers knew that a message to fleet admirals, high ranking captains, et al. would start with these honorifics and used that as a basis for rapidly decrypting the entire message.
BTW, if anyone ever finds themselves in the Milton Keynes area, the Bletchley Park site has been turned into a museum and well worth a visit, but so is the UK's National Museum of Computing which is right next door to it and criminally overlooked. Apart from that, I'd recommend getting out of Milton Keynes.
Re: (Score:3)
"All encyrption can be broken..."
Yeah, but no. There are a few companies producing one-time pads (OTP), for clients. Huge strings of random data, delivered to both parties. PITA to implement, compared to other methods ... but the messages themselves are secure. OTP is the *only* encryption method that is theoretically unbreakable.
Random number generation is too important to be left to chance. :)
Re: (Score:2)
OTP is the *only* encryption method that is theoretically unbreakable.
Not quite.
If you categorize "secure quantum communication" as a form of encrypted communication, it's also theoretically un-eavesdroppable.
Re: (Score:2)
Un-eavesdroppable is not quite the same as unbreakable
Also, 'secure quantum communication', as currently implemented, allows for a certain error rate (usually set somewhere between 15 and 20%) ... if you keep your sampling of the communication low, then it renders this method *practically* eavesdroppable. And yes, this attack method has been demonstrated, successfully, without the sender/receiver being able to identify it.
Re: (Score:3)
Like the Enigma machine, it was never using any prime numbers, but had other flaws causing it to be cracked.
The biggest problem with Enigma was laziness on the operator's behalf. Rather than changing the code-wheels on a regular basis, the operators kept the same code wheels for months because they believed the encryption was uncrackable.
The problem also contains it's own solutions (Score:3)
Before quantum becomes so good it can crack primenumbers it will be also good enough for private message distribution.
The primary use of assymetric key encription-- the ones based on prime number factoring-- is to distribute a symmetric key securely. So all you need to do is solve the secure key distribution problem.
Quantum distribution doesn't prevent eavesdropping per-se. It just makes eaves dropping detectable. So you don't want to send the secret payload message that way. INstead you send the encryp
Re:It would impact some encryption (Score:5, Interesting)
The fact that Quantum computers might be good at number factoring doesn't mean they'll break encryption.
Plus: Nobody's demonstrated that arbitrarily large quantum computations are even possible.
Quantum decoherence becomes a problem within nanoseconds of starting programs and results start to go useless after that.
Quantum factoring algorithms work in sqrt(time), not instant time. Adding enough bits to the keys will make quantum attack impossible and it may be that we're already using enough bits for that.
https://en.wikipedia.org/wiki/... [wikipedia.org]
Re: (Score:3, Informative)
You're thinking of Grover's algorithm, not Shor's algorithm (which is log-time). If practical quantum computers are developed, then prime factorisation based encryption will be essentially broken: of course you can always add bits to the keys in order to make it out of range for current computers, but firstly the difficulty of factorisation won't rise very fast (so doing something like taking ten times as many bits will not be a great long-term security guarantee) and secondly, the RSA and similar cryptosys
Re: (Score:2)
Isn't encryption a force-multiplier? Would an encryption scheme made for a quantum computer be uncrackable by a quantum computer? Once tech becomes prevalent and widespread, both sides of the equation can use it. Just wait, your corporate executive will complain that his phone's Q-crypter is being painfully slow and he really needs to send out these cat-memes. Time to put that Quantum mechanics cert to good use.
Re: (Score:2)
I'm not an encryption expert, but have studied it. The timing relationships between devices permits an autonomous domain. Eventually, the autonomous domain can be assessed. How? Not sure. Any non-transient system can at some point (given the right computing strength), be assessed for its denominators and thereby become decrypted, is my assessment. I could be wrong, but where a transient system comes about, providing no rhythm, assessment from outside the communications chain becomes crazy difficult.
Re:It would impact some encryption (Score:5, Informative)
The cracking of Enigma DID have to do with flaws in it. In particular, there was a flaw where a character could never be encoded into itself.
The worrying thing is (Score:5, Interesting)
Communication or archives you've encrypted years ago with encryption X, Y or Z that are now considered weak. Revisit the files today and hey presto, fascist states of all kinds know what you've been doing years ago and can come after you for it.
Re:The worrying thing is (Score:4, Informative)
Only if the underlying keys are retrievable by primes. Large random aes keys by themselves are still close to heat death of the universe timescales, or at least, that is an entirely different kind of math problem than the pki one.
Re: (Score:2)
What Would Happen If All Encryption Could Be Broke (Score:4, Interesting)
I think Quantum Computing is overstated when it comes to decryption. Is like people is thinking "quantum computing can do whetever a normal computer can't". But this is not true. Sure, if you find a simple method to approach prime numbers theorem, you could break SOME kind of encryption currently in use. Besides, For cryptographic purposes, though, we do know that cracking a 2048-bit RSA key will require thousands of entangled quantum bits (qubits). Entangled qubits form a single, very large state capable of doing the complex calculations needed to crack RSA. Entangling different kinds of qubits—photons, ions, or superconductors—is done with different processes. So far, no process seems to be more successful than the others.
The best results so far are:
- 18 fully entangled photon qubits in 2018
- 16 superconducting qubits, also in 2018
- 14 calcium ion qubits in 2011
Clearly there has been progress since the first pair of qubits was entangled in 1998, but it is not clear which process will scale best and no one has come close to the thousands of entangled qubits that will be needed to crack contemporary cryptosystems.
At this rate, RSA will not be cracked soon. Some researchers suggest five years; NIST thinks it may be 15. We'll see whose guess is closest eventually, but it seems fairly sure that there are at least a few years to prepare.
Re:What Would Happen If All Encryption Could Be Br (Score:5, Interesting)
Indeed. And considering they have been at this for over 30 years, it seems there is an inverse-exponential scaling at work, i.e. adding one qbit adds exponentially larger effort. With that, they may never even reach 30 qbits and will stay far, far below what a modern programmable pocket calculator can do.
Incidentally, for block-ciphers with long keys a QC is not even a threat: It just halves the key-bits. For example, AES-256 stays completely secure.
Re: (Score:2)
AES-256 still uses a 128 bit block size.
There's a 1:1 mapping of blocks to keys so there's always a 128 bit key that will decrypt a block of data that was encrypted with AES-256, yes.
OTOH only the most naive of encryption systems will encrypt messages block by block using the same key. Real life systems use CBC modes, key salting, etc. Your attack only gets you one block of data from a single message.
(and if it's not a known-plaintext attack then you're not event sure you got the right 128-bit key, you're just guessing)
Re: (Score:2)
There's a 1:1 mapping of blocks to keys so there's always a 128 bit key that will decrypt a block of data that was encrypted with AES-256, yes.
OTOH only the most naive of encryption systems will encrypt messages block by block using the same key. Real life systems use CBC modes
The way CBC works is XOR to plaintext starting with IV from preceding block. The key itself remains static with each AES block operation.
key salting
What does this even mean in the context of symmetric encryption?
and if it's not a known-plaintext attack then you're not event sure you got the right 128-bit key, you're just guessing
If you are just brute forcing keys (128-bit is too damn big of a search space for any such attack) when something that makes sense shakes out you win.
Re: (Score:3)
I think Quantum Computing is overstated when it comes to decryption. Is like people is thinking "quantum computing can do whetever a normal computer can't".
It's basically the same thing with stem cells. Some people want to believe in a magic bullet which can do anything, it's just a matter of "a few small details!" Details which they have no capability to understand, so they simply assume that someone that knows more will figure it out. Then we get people just randomly injecting stem cells, believing that of course they will cure whatever random ailment that person has, and with no other side-effects.
"Star Trek has sliding doors and warp drives. We already ha
Re: What Would Happen If All Encryption Could Be B (Score:4, Interesting)
I refer you to Clifford Cocks.
https://en.wikipedia.org/wiki/... [wikipedia.org]
Re: (Score:2)
Except for the NSA, who is more focused on spying and not original research, mathematicians generally publish research without restriction. I can't imagine a mathematician failing to publish an important theorem on prime factorization.
NSA employs more mathematicians than pretty much any other single organization in the world.
Nothing is safe online (Score:2)
Re: (Score:2)
Will not happen (Score:2)
First, even working QCs could not do that. Second, we will very likely not get working QCs. And third, what the hell?
One time pads will always be secure (Score:2)
As long as they're close to or greater then the length of what they're encrypting.
The same thing that happens (Score:3)
when aliens arrived...
when other algorithms are found vulnerable...
You find a new way, and watch as software slowly updates.
Same thing as when anything breaks (Score:3)
Life would change a lot (Score:3, Insightful)
As someone else mentioned, one time pads could be used in certain applications, but the following things (and certainly more) could no longer be trusted:
Re:Life would change a lot (Score:5, Informative)
>Email
Email has never been trustworthy, it was originally designed as a plain-text prototcol, and virtually every advancement in security has been a patchwork at best, in order to maintain backwards compatibility with existing infrastructure. That's why everyone always tells you to never send passwords, bank information, or any other sensitive information by email.
You can use something like PGP to safely ignore the insecurity of email by using an "encrypted envelope" separate from the email infrastructure, but almost nobody does that.
One time pads are not a solution (Score:2)
As someone else mentioned, one time pads could be used in certain applications
Yes they could but the list is short because the logistics, effort, and cost involved in using one time pads is challenging even in the best of (non-trivial) cases. If they were practical to use for every day normal life then they would already be used. That's why they are only used for the most sensitive of use cases where security concerns are sufficient to justify the overhead and cost of using them. The problem is in the key exchange and keeping the keys secure. This problem is the entire reason pub
Switch to different algorithm (Score:3, Informative)
If prime factorization became an easily solved problem then people would switch to cryptography based on a different underlying hard problem, like a lattice-based system for public/private keys. Quantum computers canâ(TM)t break RSA today but it will come eventually, companies with a lot of money at stake are already looking at alternatives now because changing the banking infrastructure can take 10 years or more. As others have said, breaking prime factorization for 2k or 4k numbers would mean data previously encrypted or signed would become suspect so if youâ(TM)re worried about it happening in 10 years and your data will need to survive more than 10 years (e.g. the RSA signature of some legal record) you need to worry about this today.
All Encryption? (Score:3)
Clearly, there would be no more secrets. Didnâ(TM)t this guy watch âoeSneakersâ?
Seriously, as someone else noted before me, not all encryption is based on prime factorization. elliptic curved donâ(TM)t rely on prime factorization. And, there are other âoepost quantumâ algorithms in existence all ready. Heck, even the one-time pad is still considered secure.
Re: (Score:3)
The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems can be easily solved on a sufficiently powerful quantum computer running Shor's algorithm.
- Post-quantum cryptography [wikipedia.org]
Elliptic curves are, as I recall, even worse off than regular RSA, because ECC keys are smaller.
Re: (Score:2)
Setec Astronomy (Score:2, Insightful)
Shares in the above will go up.
All crypto currency would be worthless. (Score:5, Funny)
Finally Bitcoin reaches its actual value!
There's a movie about that (Score:3)
The question is if it already has been (Score:5, Informative)
The NSA is known to have the money and the personnel to do the research, so i would expect them to have their own QC research project.
As some already stated, prime factorization affects only some encryption, and AFAIK there is research which public key encryption methods can be attacked by QC, but i wouldn't put it past them to have broken at least some encryption and make use of that. The surest sign of that would be recommendations to government agencies not to use specific encryption methods (because they'd figure that others can replicate their work).
Re: (Score:2)
The NSA don't do that kind of thing anymore, if they ever did. These days, when they find vulnerabilities they just sit on them and exploit them until their work becomes public and the internet shits itself [theverge.com].
On the other hand, NIST (among others) does make such recommendations, but they're hardly privy to NSA capabilities.
One Time Pad (Score:5, Interesting)
One time Pad has been proven mathematically unbreakable ... So not all encryption
The only issue is they are inconvenient to use which is why we use prime numbers of most day to day encryption
Not helpful (Score:3)
One time Pad has been proven mathematically unbreakable ... So not all encryption
A distinction without a difference for practical use. How about we keep the discussion to forms of encryption that are actually being used by approximately normal people under normal circumstances?
The only issue is they are inconvenient to use which is why we use prime numbers of most day to day encryption
"Inconvenient" hugely understates what a pain in the ass they are to use. One time pads work great but we don't use them because they are immensely cumbersome and expensive to use and to administer. It's why they seldom see use outside of extremely high stakes situations like war and spying. Heck, public key
Example please (Score:2)
Actually, for banking you can and should use one time pads.
Please show me a single example of a bank using a one time pad for any form of internet banking for any reasonably common transaction.
I cannot see any practical means by which you could reasonably expect non-technical banking customers to properly maintain and exchange one time pad keys.
i would sell it to the govt for millions (Score:2)
Obligatory XKCD (Score:2)
It's really easy to rob someone (Score:3)
You can walk up to anyone on the street, and demand their money. Maybe you have a weapon, maybe you hold a baseball bat, maybe it's your finger in your pocket, maybe it's a threat, or maybe it's just being scary. By the way, it's just as easy, if not easier, to kill a stranger in exactly the same way. And breaking into someone's house through their glass window is easier still.
The one and only thing that stops billions of people from doing billions of bad things like thievery and murder is the concept of consequences. Not getting away with it, punishment, prison, and guilt.
We don't tend to peak at stalls in bathrooms. We don't look sideways standing in front of urinals. It's not because of prime factorization. I know this to a high degree of certainty.
We're still in the wild wild west era of digital crimes. There are very few electronic criminals who can't easily get away with murder.
That's the only thing that needs to change. And we have a word for that kind of change: "civilization". Being "civilized" is exactly that.
So the current solution of encryption isn't the long term solution. The long term solution is accountability -- which is to say, law enforcement.
I have no idea what that would look like. I'm pretty sure the wild wild west had no idea how a gun-toting public would ever be ruled by a single sheriff with a badge. But that's exactly what happened.
I'm certainly not suggesting that government oversight, all-tracked, all-the-time, is any sort of answer -- that's not what ended the wild wild west either. I don't know what did, but I'd guestimate that the benefits and stability of living in a known residence, and a court system, probably combined to make it easier to work legitimately than to get away with criminal activity.
So that's my answer: what would happen without encryption? Better law enforcement -- because it would become immediately mandatory to civilization. And it could probably be as simple as the rest of our court system -- a complaint, a detailed log of the incident, a subpoena for ISP logs, an international treaty, an accusation, an arrest, an inquisition, and a sentence.
Obligatory xkcd: Security (Score:2)
Re: (Score:2)
I've always loved that one!
recursive prime number factorisation (Score:4, Interesting)
interestingly, a mathematician friend of mine told me of a serious debate over *whether* to publish a paper on an algorithm that they discovered on how to speed up prime number factorisation. in the end, they decided, against my advice, *not* to publish the algorithm, despite it being a huge leap forward in number theory.
what little i remember of the algorithm - they didn't send me the paper - was that it was based on the riemann zeta function, it was recursive, and it *did not use divide*, which is incredibly important for speeding up prime number detection, given that the "usual" methods are to attempt factorisation (through division). having worked on hardware pipelined implementations of divide and of square-root (and inverse square root), i suspect that the algorithm somehow "absorbed" these "long-square-root" functions, somehow.
hopefully, someone else will discover - and this time publish - the algorithm, because, just as the OP says, you can bet that someone with a lot to gain (criminals, various TLAs), have long since discovered the algorithm and are exploiting it. then, once it is well-known, the bar on RSA and Diffie-Helmann, and anything else that relies on factorisation of prime numbers, can be properly raised to give people privacy and security back.
This was done (Score:2)
To France by the NSA and GCHQ before France fully understood TEMPEST.
What happened was the US and UK had so much material in French in real time they needed more translators.
Germany with Enigma.
The Falklands War and Argentina. A total loss of all mil communications systems to the GCHQ in real time.
The NSA / GCHQ with Bullrun / Edgehill https://en.wikipedia.org/wiki/... [wikipedia.org]
SEATEC Astronomy (Score:2)
I think we need to call Dan Aykroyd.
we would rewrite mathematics (Score:2)
Cryptography depends on mathematics. In order for crypto to be easily compromised, our understanding of mathematics would have to be incorrect. The upheaval from a complete rewrite of the math textbooks would probably have a greater impact than the loss of effective encryption.
However, more than even mathematics would have to change in order for one-time pads to become ineffective. Reality would have to go totally topsy-turvy. Night becoming day and black becoming white (and plaid becoming paisley) would be
What would happen if ? (Score:2)
The canary (Score:2)
If you have nothing to hide, then nothing to fear! (Score:2)
Taking a Leaf-blower to the Privacy Curtain (Score:2)
Many would scramble and panic at their loss of perceived privacy.
Anyone who practices safe, secure communications would consider tweaking their usual jargon and keep on keeping on.
If encryption is your only "secure" way to communicate, you're not doing it right.
Post-quantum cryptography (Score:2)
Fortunately
It already is broken.. (Score:2)
Encryption is already broken, with ONE exception, where the encryption key is used only once and is at least as big as the message being sent. Even this is breakable, but the issue is you don't know which of the plain text messages you can generate from the encrypted message is the right one.
The question isn't can we break encryption, we ALWAYS can, but HOW LONG will it take? Guessing a key is all one needs to do, it may take you 1,000 years to try them all, but eventually you will find the right one. The
One-time pads cannot be broken (Score:2)
Since some encryption (one-time pads) cannot be broken by any amount of computing power, the question is moot.
The keys must be genuinely random. If there's an algorithm behind them they can be cracked.
...laura
Fear (Score:2)
Either everyone would have it or nobody would. Paper would be cool again. www.travellingsalesmanmovie.com/
Re: (Score:2)
Re: (Score:2)
You abuse the terminology. And what you imply is wrong.
Re:Umm, all encryption CAN be broken (Score:5, Insightful)
No. [wikipedia.org] Key exchange is a problem, but a one-time pad, if implemented correctly, cannot be cracked.
One time pads are irrelevant to the discussion (Score:2)
No. Key exchange is a problem, but a one-time pad, if implemented correctly, cannot be cracked.
So what? That is effectively of zero utility for the vast majority of what we use encryption for. If one time pads were actually of practical utility outside of some extreme situations we would be using them for everything. We don't because they are extremely cumbersome in practical use day to day. Unless you are at war or doing something similarly high stakes with substantial funding, one time pads simply aren't a practical solution. Imagine trying to explain to your grandparent that they have to use
Re: (Score:2)
However, if public key encryption were broken, you can guarantee that people would come up with ways to do that.
That would solve some, but not all, the uses of encryption.
Re: (Score:2)
So what? That is effectively of zero utility for the vast majority of what we use encryption for.
If one time pads were actually of practical utility outside of some extreme situations we would be using them for everything.
No whatever is cheapest and most convenient is used. Communicating in morse over telegraph lines has practical utility yet sending packets over the Internet or using POTS is way easier and less expensive.
If in an alternate universe only telegraph lines existed and you wanted to transmit a message telegraphs would again have tremendous value.
We don't because they are extremely cumbersome in practical use day to day. Unless you are at war or doing something similarly high stakes with substantial funding, one time pads simply aren't a practical solution.
TFA stipulates a "what if" ... OTP is not practical in todays environment thanks to the presence of more easily managed forms of trust. If those options disappeared th
Re:Umm, all encryption CAN be broken (Score:5, Informative)
Is this a joke? Something encrypted with a OTP can be 'decrypted' into absolutely anything of the same length. You can't look for something that 'looks right'.
Re: (Score:2)
Talk to some great-grandparents at Bletchley Park. If you know what some of the message is supposed to be and you know the pseudo-random generator function to the pad, you can work out the details.
Re:Umm, all encryption CAN be broken (Score:5, Insightful)
Then by definition it is not a One Time Pad.
Re:Umm, all encryption CAN be broken (Score:5, Informative)
OTP can be cracked if the same pad is reused for multiple messages
That would defeat the whole purpose of the "O" in OTP.
Re: (Score:2)
OTP can be cracked if the same pad is reused for multiple messages or the random number generator, its seed (i.e. a default value), and encryption methods are known (i.e. xor per byte).
Nobody would ever do that when it's so easy to generate new pads on modern PCs.
It's about key exchange (Score:2)
Nobody would ever do that when it's so easy to generate new pads on modern PCs.
The problem has NEVER been generating new pads. That's always been a fairly easy problem though there are of course ways to screw it up. No, the problem that makes one time pads not viable for most day to day use is the key exchange and key management. The entire reason public/private key encryption exists is precisely because of this problem.
Re: (Score:3)
You can transmit them over an encrypted line.
Re:Umm, all encryption CAN be broken (Score:4, Interesting)
I think you may want to read up on one-time-pads, what everyone else is saying is true - they can't be broken. They can be compromised if an attacker gets a copy of the pad, but without that you're adding (or xoring, or some other usually-simple, reversible mangling function) truly random noise with each character of the message - without knowing exactly what the noise is, you can't remove it. Even knowing exactly how a message starts only lets you recreate the OTP up to that point, which doesn't give you any information about what the rest of the pad would be (unless the encoder did something stupid like use the text from a book or some other non-random source as the one-time pad)
Re: (Score:2)
Actually, an anonymous coward made an insightful comment upthread.
In principle, real-world one-time pads can be cracked, because the one-time key isn't mathematically random.
Computers don't generate random numbers, they generate pseudo-random numbers, and pseudo-random numbers are algorithmic. We rely on the assumption that the internal pattern in (pseudo)random numbers is not crackable, but that's an assumption.
Re: (Score:3)
Re: (Score:3)
I would say the description of OTP includes not only the fact that the pad can only be used once, but also that it can also only be created once. If you are using a 'OTP' that is based on a PRNG, or the name of a book, or some other such thing, then you are not using a OTP - you are using a weak encryption where the 'key' is the seed for the PRNG or the title of the book.
And, as pointed out above, SOFTWARE may only be able to create pseudo-random numbers, but HARDWARE can create true random numbers.
Re: (Score:2)
As true as irrelevant. This is about asymmetric cryptography, about which we not only know that, but more important even HOW it can be broken. And that "how" boils down to pencil and paper. Very much pencils, even more paper and an indefinite amount of time. But it is secure because as we know what calculations need to be done to break the code, we have some good estimates how long it would take.
Re: (Score:3)
Or, instead of the pencils, one real quantum computer that can simultaneously attempt all possible factorings.
I recall an article, a couple decades old at this point, describing a quantum algorithm that would factor an N bit number in sqrt(N) time, revealing the encryption key. I believe it required an N-qbit computer though, which at current rates would seem to mean 2048-bit keys are safe for the foreseeable future. Immature technology rarely advances at a steady rate though, and there could be a breakth
Re: (Score:2)
All encryption can be broken. If it couldn't be broken, it would be useless because you would never be able to recover the encrypted information.
Really?
Ok, here is the setup:
Me and my friend know a secret number X, we have not told anyone.
I want to send him a number Y through a public channel and you are a spy trying to figure out what Y is.
I send him a message with the number 135, which I obtained by calculating X + Y = 135
My friend received the 135, and calculates 135 - X to get the secret number.
You intercept the number 135 and you even know I got it from calculating X + Y. You do not know what X is.
How on earth are you going to guess wh
Re: One time pads and quantum encryption (Score:4, Insightful)
Only half of that statement is correct.
Given that, to the worldâ(TM)s knowledge, quantum computers capable of dealing with this issue have not yet been built, we have no idea if the second statement is, or ever will be, true.
Re: (Score:2)
The useful point of quantum encryption is that the pad cannot be copied: copying a key changes it.
Re: (Score:2)
Only in a theoretical situation. But both OTP and QE suffer from the fact that we don't have truly random number generators in every home. We're still relying on PRNGs that are or can be made to be very weak. Once stronger encryption becomes a problem, malware will be affecting the PRNG in a computer in some non-obvious ways, if certain government agencies aren't already.
Re: (Score:2)
>Assume any device on the Internet is backdoored,
Probably good advice if you're doing anything where absolute security is important
>which means the key is too.
and then you overreached.
You just alluded at how to maintain the integrity of the key - never connect your en/decryption device to the internet. Plenty of offline ways to transfer data to and from your "magic box".
Re:Nothing will happen (Score:5, Funny)
Re:Nothing will happen (Score:5, Funny)
By "this space," I assume you mean the entire spacetime of the universe.
Re: (Score:2)
Re: (Score:2)
Sure, for 37 digits, where all primes of equal or lesser size are well known, thus enabling a dictionary attack. Try it again using a number with a length of 2048 bits (617 decimal digits).
Sorry - they would survive. (Score:2)
While encryption based on primes is used in most cryptos, none of the major ones depends on it. For instance, the bitcoin family uses this type of encryption for the transactions, but in order to obtain the public key from any address, you need to break a secure hash function, which isn't susceptible. The rest of the protocol uses encryption based on elliptic curves, not primes.
The system only reveals the public key when a transaction is broadcast - a transaction includes the public keys, and you use the ha
Re: (Score:3)
The German code did not use one time pads.
They used an encryption that they thought was too complex to be broken. It turned out not.
One time pads can only be broken if the decryption pad is stolen.
Ways to screw up one time pads (Score:3)
The German code did not use one time pads. They used an encryption that they thought was too complex to be broken. It turned out not.
Yes they did. [wikipedia.org] And US Signals Intelligence broke them because the means they used to generate them was insufficiently random. They were one time pads, just poorly implemented.
One time pads can only be broken if the decryption pad is stolen.
They can also be broken if they are reused or if the mechanism that generates the pad isn't sufficiently random. One time pads work great but it's quite trivial to screw them up such that they can be broken by a sophisticated counterparty.
Re: (Score:2)
The German code did not use one time pads. They used an encryption that they thought was too complex to be broken. It turned out not.
Yes they did. [wikipedia.org] And US Signals Intelligence broke them because the means they used to generate them was insufficiently random. They were one time pads, just poorly implemented.
Interesting. I only knew about the Enigma machine encoding and the Bletchley Park codebreaking; didn't know about that one. I stand corrected.
Re: (Score:2)
Thats why better encryption systems got used to send back so much data quickly.
One time pads got used once and needed time to work with. Then got used once.
What happened when an embassy has to send back more? Use the code twice?
Wait for the next set of one time pads to arrive?
The problem with one time pads was it does not scale to nation wide use.
Embassy safe access can slip and result in code books getting a copy m
Re: (Score:2)
This is running Python code:
rpn 2737631357921793461914298938174501291 factor -t
[ 1238179781035456451, 2211012810782926841 ]
30.984 seconds
On the other hand, YAFU factored the the number in less than 78 milliseconds.