Quantum Cryptography Leaving the Lab 345
Theodore Logan writes "More than a year ago, MagiQ announced the world's first commercial quantum cryptography system (pdf), with ID Quantique following closely in their footsteps. Currently, the technology is limited to offering point-to-point connections up to a maximum distance of around 50 km, but this is likely to be greatly improved on in coming years. The systems available today are prohibitely expensive for the average Joe (MagiQ's are priced at more than $50,000 per unit), but one could envision a future in which they are built into the infrastructure by non-end user actors. Does this spell the end of the field of cryptography? Will systems like this ever become commonplace, or will they be reserved for sensitive financial transactions and military applications? What impact will quantum cryptography have on society? Good articles available from International Herald Tribune, EE Times and CNET."
It's worse than that, it's physics Jim (Score:5, Informative)
Since they make a point that they "Rely on the laws of physics", they're bound by them too (maths is far more forgiving
OTOH, it's the first generation of these devices, and perhaps IPv8 will somehow encode an encryption hierarchy (packets get encrypted sequentially in one direction, and decrypted on the way back, assuming the same route is taken, each node only needs to know the encryption to the next one worked ok to guarantee the encryption was ok. You'd still want to be in control of all the nodes along the way though...)
As for price - if they can solve the networking issue, that'll come down dramatically - it'll be onboard in the equivalent of the BIOS that we have in ten years time (when we all have fibre to the home. Possible optimistic
Simon
Does this spell the end of the field... (Score:3, Informative)
Uh, no. Quantum key distribution is completely useless unless you have a cryptographic algorithm and protocol using that key for encryption. I suppose you could just send the message over quantum channels, but a quantum channel for key distribution is probably many orders of magnitude too slow for the acutal data.
Re:Quantum Cryptography (Score:5, Informative)
Re:Quantum Cryptography (Score:3, Informative)
Re:Quantum Cryptography (Score:5, Informative)
The purpose of cryptography is to transmit information in such a way that access to it is restricted entirely to the intended recipient. Originally the security of a cryptotext depended on the secrecy of the entire encrypting and decrypting procedures; however, today we use ciphers for which the algorithm for encrypting and decrypting could be revealed to anybody without compromising the security of a particular cryptogram. In such ciphers a set of specific parameters, called a key, is supplied together with the plaintext as an input to the encrypting algorithm, and together with the cryptogram as an input to the decrypting algorithm.The encrypting and decrypting algorithms are publicly announced; the security of the cryptogram depends entirely on the secrecy of the key, and this key must consist of any randomly chosen, sufficiently long string of bits.
Read more here [qubit.org]
Quantum Crypto != Quantum Computing (Score:5, Informative)
Quantum crypto is a misnomer, it isnt even crypto at all. It's an intrusion detection system. Quantum crypto works by sending sensitive photons through a tight channel as bits which will get disturbed by an eavesdropper. Where as electrical signal on a wire expects static, and a wiretap isnt noticed.
Quantum computing however, works on electron entanglement, and is pretty far off.
Re:Quantum Cryptography (Score:5, Informative)
It's similar to Schrodinger's cat: Schrodinger comprised a thought experiement where a cat was put into a sealed box with a poison and a radioactive atom. In the course of 1 hour, the atom has a 50/50 chance of decaying, thus killing the cat. At the end of the hour, the cat is neither dead or alive, but in a state of flux. It's not until you observe the system that you fix the state of the cat as being dead or alive.
magiq whitepaper (Score:5, Informative)
Theorys and more (Score:5, Informative)
Re:Quantum Crypto != Quantum Computing (Score:1, Informative)
With advances in quantum computing and the potential which it holds, it has the ability to render most encryptions schemes as nothing more than a minor inconvience to someone trying to decrypt the data contained within.
At that point he feels quantum cryptography will be the only method in which to safely encrypt data.
Re:Of course.. (Score:5, Informative)
This is bullshit. First off, you have to assume that
a) non-trivial Quantum computers can be constructed at all [who says there are not limits?]
b) The time per solution is not greater than a brute force attack.
I mean sure a single cycle AES cracker would be cool. But if the machine took 2^100 years to build who gives a shit?
This type of hype always pisses me off.
To boot as I understand it, QC only "attacks" in sqrt time by meet-in-the-middle approaches. So AES-256 would provide all the security ya need.
Tom
Re:Quantum Cryptography (Score:2, Informative)
Re:Does this spell the end of the field... (Score:5, Informative)
How quantum crypto works (Score:5, Informative)
Alice sends Bob a series of polarized photons.
There are four possibilities: -, |,
Bob sets up his polarization detector randomly so that each "qbit" is measured either for horizontal/vertical polarization or diagonal polarization. If a - or | photon hits the detector and it was set up for horizontal/vertical, he gets a good bit, otherwise a bad bit. And if a / or \ photon hits the detector and it was set up for diagonal polarization, same story. The key point is this: if the detector was set one way and the photon is polarized the other, it is in principle impossible to know its true polarization.
So Bob has a sequence of photons, some of which he knows, and some he doesn't, and he knows which are which. He sends Alice a clear-text message saying which ones he knows. Alice then encrypts the true plaintext by XOR'ing it with the values of the photons that Bob knows, using some convention like "- and / are 0, | and \ are 1".
Example:
Alice sends...: - \ - | / - | (random)
Bob's detector: + + X + X X + (random)
Bob's result..: - ? ? | / ? |
Bob's response: 1 0 0 1 1 0 1
Key...........: 0 1 1 1
If Eve tries to listen in on the photons Alice sends to Bob, she perturbs them irrevocably.
A bad description -- go buy Bruce's book for a better one.
Because linear key improvement isn't an advantage. (Score:5, Informative)
The reason most encryption works is because when you linearly increase key size, you exponentially increase the amount of time required to crack the key if you have no special knowledge, meaning it is much more difficult (impossible for practical purposes) to decrypt without a key than encrypt or decrypt with the necessary keys.
Doubling the key size may only double the work of the one encrypting and decrypting using a key but exponentially increases the work of the one trying to break it without a key. Almost no matter how easy it is to crack a short key, you can increase key size until the advantage of linear versus exponential is overwhelming.
But quantum computing -- encoding the problem into the quantum matrix, not to be confused with the quantum encryption described in this article -- threatens to be able to solve such problems in linear time instead of exponential time.
This means that when the user doubles the size of his key instead of exponentially (enormously) increasing the amount of work to solve the problem, it only doubles the amount of work required to crack it, which would make decryption a simple footrace even if you do not have the key, if the amount of work required to crack the key is proportional to the amount of work required to encrypt / decrypt instead of an exponential relationship.
Primes would not seem to be adequate at all, if quantum computing allows them to be solved linearly. At best, if you could find something that had the difficulty of non-quantum primes under quantum computing, then perhaps you could use that.
Re:Does this spell the end of the field... (Score:3, Informative)
Re:Uh Oh (Score:3, Informative)
However, quantum cryptography does not rely on large numbers that are hard to factor, but on the fact that it is impossible (according to currently known physics, as correctly pointed out) for someone to eavesdrop without being detected.
www.qubit.org has this [qubit.org] explanation:
The basic idea of cryptosystems (B) is as follows. A sequence of correlated particle pairs is generated, with one member of each pair being detected by each party (for example, a pair of so-called Einstein-Podolsky-Rosen photons, whose polarisations are measured by the parties). An eavesdropper on this communication would have to detect a particle to read the signal, and retransmit it in order for his presence to remain unknown. However, the act of detection of one particle of a pair destroys its quantum correlation with the other, and the two parties can easily verify whether this has been done, without revealing the results of their own measurements, by communication over an open channel.
So to use this for safe communication, you would send some random data through the connection, and once you are sure there were no eavesdroppers, you can use this random data as the key for normal symmetrical encryption. And if the random key is as large as the data you encrypt with it, even normal symmetrical encryption can't be cracked with a quantum computer.
Re:A way to break it? (Score:3, Informative)
Furthermore, in accord with the Heisenberg uncertainty principle, you cannot determine all of the properties, of, for example, an electron. Knowing (measuring) one property makes the others unknowable (NOT unmeasurable). For example, if you measure the postion of an electron, then you cannot also know the energy that electron has at that instant, and vice versa. Thus, what property you choose to measure determines what you can know.
Back to crpto - the system uses spin as the property measured, because pairs of particles with opposite spins can be created and sent to different places. No one can know the spin of each particle until the measurement is made. At that point, the other particle must have the opposing spin (you now know this because of conservation of spin).
If someone intercepts the particle, they must first know which property to measure. Once it is measured, though, they are exposed and the information is, essentially destroyed.
The universe is nothing more that probability. See Douglas Adams for further elaboration.
Molecular Mechanic
Re:Does this spell the end of the field... (Score:3, Informative)
You can't just send the data over the quantum channel - it could be intercepted.
Quantum cryptography does not prevent interception of messages. It merely allows the sender and recipient to know that a message was intercepted.
So a practical QC scheme would be:
1. Send one-time-pad to recipient.
2. See if message was intercepted. If so, send somebody with a baseball bat down the wire to take care of the problem.
3. If key was not intercepted, use it to encrypt the message and send that conventionally.
If speed is a problem you could send a conventional symmetric key, but that is less secure than sending an OTP.
While I'm sure QC is slower than 10gigabit ethernet over fiber, it is probably fast enough for many purposes. There really isn't any reason that it can't go as fast as any other technology. It just isn't that mature yet.
A Useful but Long Quote. (Score:5, Informative)
I have written this book partly to correct a mistake.
Seven years ago I wrote another book: Applied Cryptography. In it I described a mathematical utopia: algorithms that would keep your deepest secrets safe for millennia, protocols that could perform the most fantastical electronic interactions-unregulated gambling, undetectable authentication, anonymous cash-safely and securely. In my vision cryptography was the great technological equalizer; anyone with a cheap (and getting cheaper every year) computer could have the same security as the largest government. ...I went so far as to write: "It is insufficient to protect ourselves with laws; we need to protect ourselves with mathematics."
It's just not true. Cryptography can't do any of that.
It's not that cryptography has gotten weaker since 1994, or that the things I described in that book are no longer true; it's that cryptography doesn't exist in a vacuum.
Cryptography is a branch of mathematics. And like all mathematics, it involves numbers, equations, and logic. Security, palpable security that you or I might find useful in our lives, involves people: things people know, relationships between people, people and how they relate to machines. Digital security involves computers: complex, unstable, buggy computers.
Mathematics is perfect; reality is subjective. Mathematics is defined; computers are ornery. Mathematics is logical; people are erratic, capricious, and barely comprehensible.
The error of Applied Cryptography is that I didn't talk at all about the context. I talked about cryptography as if it were The Answer(TM). I was pretty naïve.
The result wasn't pretty. Readers believed that cryptography was a kind of magic security dust that they could sprinkle over their software and make it secure. ... A colleague once told me that the world was full of bad security systems designed by people who read Applied Cryptography.
Since writing the book, I have made a living as a cryptography consultant: designing and analyzing security systems. To my initial surprise, I found that the weak points had nothing to do with the mathematics. They were in the hardware, the software, the networks, and the people. Beautiful pieces of mathematics were made irrelevant through bad programming, a lousy operating system, or someone's bad password choice. ...
Any real-world system is a complicated series of interconnections. ... No system is perfect; no technology is The Answer(TM).
This is obvious to anyone involved in real-world security. In the real world, security involves processes. It involves preventative technologies, but also detection and reaction processes, and an entire forensics system to hunt down and prosecute the guilty. Security is not a product; it itself is a process. And if we're ever going to make our digital systems secure, we're going to have to start building processes.
A few years ago I heard a quotation, and I am going to modify it here: If you think technology can solve your security problems, then you don't understand the problems and you don't understand the technology.
This book is about those security problems, the limitations of technology, and the solutions.
Re:Solving the wrong problem (Score:2, Informative)
I think that's a little too simple. The quantim crypto part is used to transmit a one-time pad, which is probably unbreakable. However, one-time pads suffer from key-distributions problems, which is where the quantum bit--no pun intended*--comes in. So it makes for a nice marriage between the two.
* A desparate punster submitted ten puns to a local newspaper to try to win the grand punster prize. His hopes were dashed, however, to find out that not only did he not win the prize, but no pun in ten did.
Re:Not a question of if, but when (Score:3, Informative)
The one-time pad, which is only feasable by quantum cryptography, is impossible to decrypt without the key. Or rather, impossible to know which decryption is correct, as you can easily decrypt it into whatever you want.
You have no idea whether:
"5preio2309d91kcn2s02ia"
actually means:
"al-Qaeda strikes again" or
"Hi there, how are you?" or
"ZekdjEs322SKE#aap2MZal"
and so on. You can say it means whatever you want, but you'll never really have any idea if that is what it meant or not unless you have the key.
Yes, someone may break quantum cryptography, but to say that it will happen because is has happened before is silly.
Re:It's worse than that, it's physics Jim (Score:5, Informative)
Re:Uh Oh (Score:5, Informative)
Besides the Shamir attack, there's always the wait-for-your-opponent-to-screw-up attack. One time pads are theoretically unbreakable, with mathematically provable security. This didn't stop the US from reading the Venona intercepts. The Soviets had used one time pads two times, and that mistake destroyed the security.
Re:Of course.. (Score:2, Informative)
OK, why would you assume some arbitrary limit on the number of quantum gates that can be linked together? You only need to link as many gates as the bits of encryption you're trying to crack. I know that currently quantum computers are only factoring numbers like 15, and that the methods that are used to link the gates are not easy, but there is no reason that the exact same methods can't be used to link more gates.
b) The time per solution is not greater than a brute force attack.
OK, now I know you're just a complete dumbass! Do you know anything about quantum computing? I don't know how long you think it takes an electron to change state, but in case you're wondering, it's not very long. All of the work in a quantum computer is actually done before you ask for the solution. The actual work side also takes virtually no time. You'll simply be asking it the same question every time, and it calculates all the answers for you (over simplified to the point of being wrong, but at this point it seems quite necessary) and you simply tell it which answer you'd like. The time it takes for all this to happen is short enough that I doubt it could be measured. Even if the different gates in your computer are miles or light years apart, the quantumly linked actions are (were last time I read) considered to be instantaneous (yes, faster than light). The slowest part of the system will be where you want to interface your quantum computer with the "real" world.
This type of hype always pisses me off.
Why don't you read some literature the explains quantum computing and then read your comments again. If you haven't read anything about how it actually works, then you can only depend on the
I fear that I've greatly over-estimated the average
Re:A way to break it? (Score:3, Informative)
The "standard" use of these devices is for point-to-point communication. Put one end in the White House and the other in the Pentagon (about 40km away) and you have a communications channel that can not be sniffed without detection. So far, so good.
But this doesn't scale well. Talking from DC to Moscow would probably require some sort of relay system, just as a relay system would be required if we wanted to have this enter people's homes (otherwise you'd need direct fiber connections between you and everyone you ever want to talk to). So now the relays need to be "trusted", and the possibility of a MITM attack is introduced.
As you have discovered, QC protects the security of the link, not the endpoints, relays, etc.
Disclaimer: IAAPP (I *am* a particle physicist)
Re:It's worse than that, it's physics Jim (Score:2, Informative)
RSA and other public-key cryptosystems relying on the (presumed) difficulty of things like factoring, finding solutions of the Pell Equation or computing Gauss sums are compromised by a quantum computer. DES, on the other hand, is a block cipher key and AFAIK there is no specific quantum-enhanced attack on it.
So wouldn't that make the secure transfer of the keys somewhat pointless?
no, since the ultimate encryption algorithm - which is unbreakable by both quantum and classical computers) just needs a secret random string of the same length as the message ("Vernam cipher") -- and this is just what "quantum cryptography" (quantum key distribution) allows to generate.
distributing keys is only made pointless by a QC if you want to use them in a sub-par way, sending a message much longer than the key.
Re:Of course.. (Score:1, Informative)
To address your second paragraph.... "time per solution" meant the time it takes to make the actual device. If it takes 2^100 years to design an AES cracker I don't care.
Overall... I never said QC is impossible. I just hate how people spin [forgive the pun] things to no logical ends.... OMG they can factor the number 15. That means the technology works. Doesn't mean it will scale. Factoring 15 and a 1000-bit composite are not the same order of magnitude.
Similarly AES is not a trivial algorithm. Designing a QC for AES may prove to be intractable. Which means all the QC hype in the world won't break AES.
Who knows. Keep an open mind and don't make stupid conclusions like "crypto is dead" or "your mother is a whore".
Tom
Re:Of course.. (Score:3, Informative)
Last I heard, there is still a ton of comp-sci problems that are hard, even in the quantum world. NP problems will still be NP problems---quantum computers don't help with those.
Also, unless some really major innovations come up, we won't see quantum computers anytime soon (and I mean in centuries, not years).
Re:It's worse than that, it's physics Jim (Score:2, Informative)
wrong and right! The Vernam cipher or one-time pad is a provably secure encryption method. But is indeed a classical method that involves a key which is as long as the message. Quantum ethods only come in as a method (the only known one) for provably securely distributing such keys.
Re:What application? (Score:3, Informative)
Re:Wrong (Score:1, Informative)
>This is true for a passive attack, i.e., one were the attacker can only eavesdrop on a connection.
>However, in a man-in-the-middle attack, the attacker can also arbitrarily modify data.
But the point of quantum crypto is that there's no such thing as a passive MITM attack. Quantum MITM can't help but be active. So after the transmission of the qubits, Alice should have guessed the right polaraization for about half of the qubits. For these qubits, Alice and Bob should have measured the same bits. Alice and Bob now pick some subset of these bits and announce publicly what they each got.
If their bits agree here, then they of course are sacrificed, but if the bits disagree, then Alice and Bob know that there must have been an eavesdropper listening.
Re:Wrong (Score:1, Informative)
Thus if an attacker (Eve) were to also Man in the Middle the out of band communication I think they could be successful in their nefarious goals.
Re:Wrong (Score:3, Informative)
Basically, no way to recreate the bit you receive in such a way that Bob wont know it was modified.
Re:It's worse than that, it's physics Jim (Score:2, Informative)
Re:It's worse than that, it's physics Jim (Score:2, Informative)
RSA and 3DES are completely different. The first is an asymmetrical encryption algorith, the second is symmetrical.
The point of asymmetrical encryption algorithms (or at least this one and all others I know of) is to solve the problem of key transportation - you need to send secure data to someone, so you want to encrypt it. But how do you give him the key, as you have no secure channels? RSA solves that by having a public and a private key, a public key which anyone can get to encrypt data, and a private key which only you have that can decrypt the data encrypted using the public key. Problem solved. The private key cannot be easily deduced by examining the public key or the encrypted data, and that has been proven mathematically. The amount of calculations needed to find the key depend on the key length, but it takes a very large amount of time for even the shortest length keys (we're talking decades). This process is called factoring and relies on a certain meaning being in the key, a certain logic.
Quantum Computing (which I am not even going to try and explain) has way more computing power than today's computers for certain algorithms, and factoring algorithms are some of these. So, using quantum computers, factoring the private key of an RSA key-pair is a lot faster.
Now, this is irrelevant when we're talking of Quantum Encryption, which has no connection at all to quantum computing, in this context. So don't mix the two terms. Quantum encrytion is a method of transferring data securely relying on certain physical laws to make sure that no one can read the data without the receiving side knowing of the leak. This has nothing at all to do with either symmetric or asymmetric encryption algorithms - it is a secure channel, and so - a solution to both the key transfer problem and better yet - to simple data transfer.
The product reviewed here solves the key transfer problem by using quantum key transfer - this is a secure link based on quantum encryption (afaics), though apparently not very fast, as they could simply transfer the data but chose not to. This transfered key is used as a symmetric key in a symmetric encryption algorithm (which uses the same key to encrypt and decrypt data), which can be DES or 3DES in the QPN (from what I could see). Factoring isn't something related at all to symmetric algorithms. That's like talking of a clutch pedal for a car with an automatic gear: not relevant at all. The key in a symmetric encryption algorithm is simply a random number, which cannot be logically deduced looking at plain encrypted data, nor is there a public key (well, not exactly, but for this simplistic discussion - this will do). This is in contrast to the keys in an asymmetric encryption algorithms. And so, quantum computing will not help with this. (Even though I assume brute-forcing might be faster using quantum computing).
I hope that clears it up a bit.
The one thing I don't really get is that they do oddly talk of Diffie-Hellman in the QPN data sheet - if anyone can clarify this, I'd be interested to hear the explanation, as it makes no sense: Diffie-Hellman is an algorithm used for secure key transfer (generation actually), though it has its own vulnerabilities and downsides. I am not sure how this is related to quantum key transfer, though I assume it is just a method to transfer keys securely internally in a deeper layer of the system, beneath under the quantum key transfer layer - to prevent decryption, even if someone hacks into the system circulating the quantum encryption protection.
Sorry for any typos, too tired to proofread this.
Re:It's worse than that, it's physics Jim (Score:3, Informative)
Godel, although brilliant, has created a philosophy. Science and philosophy are an interesting dance, but science always wins.
I believe you are also not clearly thinking out something you are referring to called "self-referential paradox". The symbolic systems we use to describe the universe are not separate from the universe: they are a part of the universe just as we are a part of the universe. Since we are within the system, our understanding is 'the system modeling itself'. The paradox you are referring to is that the completion of the model can never happen because of the basic self-referential paradox: The model is within the universe. Or you can view it n another way: The model models the universe. The universe includes the model. The model must model itself. The model must model the model of itself.. ad absurdum. This is interesting, although it would enlighten you to search in Google (since I am not sure you have access to a University research Library) and look for "Godel Incompleteness Theorem Counter Proofs". Godel appears to clearly not be a mechanist.
On an interesting note to the CS majors on Slashdot. Godel also predicted that Artificial Intelligence can never be achieved, as there are only a finite number of variables that can be calculated using a machine. Will this be proven true? I do not believe so. As Godel was apparently not a mechanist, it follows that he would have concluded that statement.
In layman's terms, do some research before posting a reply next time, Anonymous Coward.
Re:It's worse than that, it's physics Jim (Score:2, Informative)
First, the magic of Quantum Cryptography is NOT that the signal cannot be eavesdropped on without being detected -- that's simple non-relativistic quantum mechanics. The trick to QC is that there's an algorithm which can calculate exactly which bits were sniffed, so that a key can be composed of the remaining safe bits. For example, I wish to transmit a PGP private key of 2048 bits. Eavesdropper E picks up half the message. Using QC, I can calculate which part of the message was compromised, and construct the private key of the 1024 bits that are pristine (this is an oversimplification: the algorithm is nondeterministic, but that's the essential point).
Classical switching, such as networks, cannot occur in QC, because no FANOUT operation is allowed. This is a consequence of the no-cloning theorem.
QC can be done with photons, molecules in NMR, electrons, etc. Anything that can be reduced to an EPR pair (or alternately, a Hadamard gate) is a basis for QC.
A quantum computer, by itself, does not give you an O(1) prime-number crunching machine. You need an algorithm which can leverage the strength of the quantum computer. Shor's algorithm does polynomial-time factoring of numbers, and Grover's algorithm does O(sqrt(N)) selection from a list.
Finally, we have a pretty good handle on NRQM and even Quantum Field Theory; quantum mechanics is pretty-well understood in the realm of physics we observe now.
And before someone says "quantum gravity", first tell me what you mean by the term, since it really hasn't been defined yet in terms of physical theory -- meaning there are lots of candidates (string theory, braneworlds, Kaluza-Klein theory, etc), but no results.
Re:Generating that "random" number? (Score:2, Informative)
Thermal noise can not be easily detected from afar (afaik), and if you're close physically - you might as well just take the data by physical force. But guessing the possible thermal noise based on know patterns makes guessing the pseudo-random number that much easier.
Re:Wrong (Score:2, Informative)
If you don't know what system the photon was encoded in, you will have to guess. When you guess incorrectly, the result of your measurement will be 0/1 randomly (indepentantly, of course, of what the photon was representing in the correct system), this is what the 45 degrees are about. When she guesses correctly, Eve can manufacture a new photon which is sufficiantly identical to the original to fool Bob. However, half (on average) of her incorrect guesses will give her away.
Re:IANAMBMSI (Score:2, Informative)
Using RSA as an example, here's a less-than-six-step process for finding the private key given the public key (exponent e and modulus m=pq):
(1) Factor m into p and q (both distinct primes).
(2) Calculate phi(m) = (p-1)(q-1).
(3) Find the reciprocal of e in this new modulus phi(m). That's the private key.
Once you have step 1, the rest takes a very short amount of time (less than a second). And you don't even need a sample message....
The problem is you can solve for the third thing, but some things are harder to solve for than others. All of the security of public key cryptosystems depend on the "hardness" of the "third thing" you need to solve for.
To give an easy example of how one way can be harder than the other, try doing this problem by hand:
Given y = x^3 - x^2 + 5x - 4,
(1) Find y given x=3.
(2) Find x given y=10.
Why is one way harder than the other? Because it's easy to multiply things together, but not so easy to factor. It's the same thing with cryptosystems. So, I doubt anyone will find a simple algorithm to make them equally "easy." The best factoring algorithms in the world are still nowhere as simple as multiplication.
OTOH, quantum computing can do exponential time problems in something like linear time, so a quantum computer could just factor and we'd be done with it. No need for a fancy mathematical algorithm. We already know how to do it -- it's built right into the cryptosystem.
Re:It's worse than that, it's physics Jim (Score:2, Informative)