[Computational Complexity] Decryption by Clancy
Consider the following paragraphs from Tom Clancy's novel Rainbow Six.
The phone they spoke over was the Russian version of the American STU-3, the technology having been stolen about three years before by a team working for Directorate T of the First Chief Directorate. The internal microchips, which had been slavishly copies, scrambled the incoming and outgoing signals with a 128-bit encryption system whose key changed every hour, and changed further with the individual users whose personal codes were part of the insertable plastic keys they used. The STU system had defined the Russians' best efforts to crack it, even with exact knowledge of the internal workings of the system hardware, and they assumed the the Americans had the same problems—after all, for centuries Russia had produced the world's best mathematicians, and the best of them hadn't even come up with a theoretical model for cracking the scrambling system.I doubt anyone could turn a souped-up Connection Machine into a quantum computer. But one could imagine some smart NSA scientists finding a way to simulate a variation of Shor's quantum factoring algorithm on such a device, well enough to break moderately long RSA codes. Just thinking.
But the Americans had, with the revolutionary application of quantum theory to communications security, a decryption system so complex that only a handful of the "Directorate Z" people at the National Security Agency actually understood it. But they didn't have to. They had the world's most powerful supercomputers to do the real work. They were located in the basement of the sprawling NSA headquarters building, a dungeonlike area whose roof was held up with naked steel I-beams because it had been excavated for just this purpose. The star machine there was one made by the company gone bankrupt, the Super-Connector from Thinking Machines, Inc., of Cambridge, Massachusetts. The machine, custom build for NSA, had sat largely unused for six years, because nobody had come up with a way to program it efficiently, but the advent of quantum theory had changed that, too, and the monster machine was now cranking merrily away while its operators wondered who they could find to make the next generation of this complex machine.
Posted by Lance to Computational Complexity at 12/14/2004 05:21:02 PM