NSA Building Encryption Cracking Quantum Computer

[lcpiper]

I was reading here and it suggests this might be possible.

Given sufficient computational resources, a classical computer could be made to simulate any quantum algorithm ... However, the computational basis of 500 qubits, for example, would already be too large to be represented on a classical computer because it would require 2500 complex values (2501 bits) to be stored. (For comparison, a terabyte of digital information is only 243 bits.)

I was simply thinking that given this statement, it might be very possible to leverage distributed computing models in order to achieve sufficient computing power. I offer this link to show how things are changing.

The 120 petabyte “drive”—that’s 120 million gigabytes—is made up of 200,000 conventional hard disk drives working together.

http://www.technologyreview.com/news/425237/ibm-builds-biggest-data-drive-ever/

 

[Ur_Mom]

The NSA is supposed to do this stuff, they are supposed to have these capabilities, it's their job, their reason for existence. No they are not supposed to use this stuff against us in violation of our rights and that's where the disconnect is. Pretty much our only source of information is the media and the media is own and has an agenda. Almost every group going has some agenda, some angel they are working.

Keeping them in line and within their boundaries is where I have a problem. They are supposed to be doing this stuff, it's just where their aim is that I question.

I always wanted to work for the NSA. You know they have the biggest, best toys out there for computer nerds. Now? Not so much. They were granted too much power and too broad of a target. Terrorist. Could be anyone, foreign or domestic of any race or sex or age. So, let's look and listen to everyone and pick out the bad ones.

 

[lcpiper]

The basics of Virtualization are built on the concept of sharing/pooling or computing resources, primarily CPUs, RAM, and Storage. If I used a distributive computing model in order to harness many thousands of machines for the purpose of creating a large 'virtualization resource pool", it might then be possible to harness those resources for quantum computing functionality. It would be a brute force "emulator" if you could make it work.

 

[Red Squirrel]

It's too bad this tech is being designed and used against the people.

Honestly I would not be sad if there was a civil terrorist attack against the NSA. At this point, they are the terrorists.

 

[1.1.2.3.5...]

I was reading here and it suggests this might be possible.

I was simply thinking that given this statement, it might be very possible to leverage distributed computing models in order to achieve sufficient computing power. I offer this link to show how things are changing.

Sufficient for what?

Why is RSA encryption hard to break? You need to ask this question to understand the problem.

The RSA algorithm is public knowledge so everyone is free to attempt to crack it. The reason is is that it is more difficult to factor numbers into primes than it is to find large primes. If you get more cpu power to crack RSA, then likewise there is more computing power to find larger primes. Since factoring is harder than finding new primes the race cannot be won by more computing power (since both the power to find large primes increases with the power to factor integers). As a reference see Elementry Number Theory and its applications by Rosen (5th ed.) chapter 8.4.

Quantum computers are the atom bomb of the information age. Of course a lot of good is possible, but also a hell of a lot of evil.

 

[Lith1um]

Keeping them in line and within their boundaries is where I have a problem. They are supposed to be doing this stuff, it's just where their aim is that I question.

I always wanted to work for the NSA. You know they have the biggest, best toys out there for computer nerds. Now? Not so much. They were granted too much power and too broad of a target. Terrorist. Could be anyone, foreign or domestic of any race or sex or age. So, let's look and listen to everyone and pick out the bad ones.

The US Government's Motto,

“There's no way to rule innocent men. The only power any government has is the power to crack down on criminals. Well, when there aren't enough criminals, one makes them. One declares so many things to be a crime that it becomes impossible for men to live without breaking laws.”

― Ayn Rand

 

[1.1.2.3.5...]

The basics of Virtualization are built on the concept of sharing/pooling or computing resources, primarily CPUs, RAM, and Storage. If I used a distributive computing model in order to harness many thousands of machines for the purpose of creating a large 'virtualization resource pool", it might then be possible to harness those resources for quantum computing functionality. It would be a brute force "emulator" if you could make it work.

I feel like you a missing something very fundamental about computing.

While possible to simulate a 1000 core processor in a single thread, and so possible to write threaded algorithms against the simulated multicore cpu and thus to test the performance improvements you could get with more cores....it would not actually be any faster computing in this way than the single threaded algorithm would. You get that concept, right?

 

[lcpiper]

h. They were granted too much power and too broad of a target. Terrorist. Could be anyone, foreign or domestic of any race or sex or age. So, let's look and listen to everyone and pick out the bad ones.

But that's not what they do. That's what people tell you they do, that's what people insinuate and suggest they do, but it is not what they do.

In the first place, they were not told to go after terrorists, this is the first inaccuracy, the NSA does not do counter-terrorism, the FBI does, and sometimes the FBI needs NSA support. If the target is foreign then it's no problem, if the target turns out to be a US Person, then they get a warrant.

But they don't sit there and suck up everything to run dirty word searches on it all. that would certainly violate the law, be unconstitutional, and horribly inefficient.

Start with the basic premise that for the most part, our threats originate from foreign sources or are influenced from foreign sources. Now the NSA is supposed to be watching everything foreign, that's their job, yet reality tells us sometimes things cross the oceans. Phone calls, email, web searches, whatever, such things cross and pass through our communications infrastructure and servers. And if a threat travels into the US or tries to recruit into the US, the data pointing to this emerging threat will be here on US Systems, stored in the servers of US businesses like Google, AT&T, Verizon, etc.

Now if you have a known bad guy talking to someone in the States, well that one is easy, it's a slam dunk. But when the foreign end is an unknown threat, then it get's tougher. Phone meta-data helps identify people who are connected, patterns emerge. Those known bad guys talk to other bad guys and sometimes they get around to talking to an unknown bad guy .... who happens to be talking to someone in the US. Maybe a US Person, maybe not. But there is a connection and in some cases other information, like who these people are, who they work for, where they have gone to school, all this information might be enough to justify a closer look. Even more so when the US Person is not a US Citizen or is a naturalized US Citizen. Under the right circumstances there may be justification to request additional data from US Service providers. Under the right circumstances they might get a warrant to conduct actual surveillance operations against a US Person.

Privacy Groups are doing their job for us in challenging the Government about these programs, I got no problem with them. But when a media source takes stolen classified information that points out that the NSA has a facility built in Utah, (wherever it was), that is capable of storing the contents of every phone call that millions of American's make, well that same facility would also be needed to store the contents of millions of foreigners in most every other country's government, military, research facilities, universities, tech companies, energy companies, etc in the world. This is the kind of reporting I have a problem with. I also have a problem with the kind of reporting where the article first suggests that a FISA Court judge threatened to shut down a program because of 2,700 violations and makes it sound like 2.700 people's privacy were violated when in fact the violations were 2,700 security violations meaning the information was being handled improperly, not that the Agency was blatantly violating people's rights even though that is precisely what the author wanted the casual reader to believe. I have a problem with this.

And this is why so many people now talk as if the NSA is without any doubt spying on millions of Americans.

Now the bulk collection program is under scrutiny, not a bad thing, it's under challenge although the first laws that allowed the creation of the programs were challenged a decade ago. Still, ten years is nothing for a country that's over 200 years old, and challenging things is part of why America is America. The challenges in the courts and the scrutiny by our people are good things. But misrepresentation and falsehoods are not and our media has plenty of that going and it's up to us, we are the last check, to look, and read, and challenge cause I don't believe any of those bastards in the media. I have seen more then enough lying from both sides to know better.

 

[Ehren8879]

Quantum computers are the atom bomb of the information age. Of course a lot of good is possible, but also a hell of a lot of evil.

I was going to draw a parallel to the Manhattan Project, but thought such a statement would get torn apart here. A quantum computer is something the best minds in computer science, physics and engineering are likely to be involved in.

 

[1.1.2.3.5...]

I was going to draw a parallel to the Manhattan Project, but thought such a statement would get torn apart here. A quantum computer is something the best minds in computer science, physics and engineering are likely to be involved in.

I agree except I would add mathematicians to that list...

 

[/usr/sbin]

Sufficient for what?

Why is RSA encryption hard to break? You need to ask this question to understand the problem.

The RSA algorithm is public knowledge so everyone is free to attempt to crack it. The reason is is that it is more difficult to factor numbers into primes than it is to find large primes. If you get more cpu power to crack RSA, then likewise there is more computing power to find larger primes. Since factoring is harder than finding new primes the race cannot be won by more computing power (since both the power to find large primes increases with the power to factor integers). As a reference see Elementry Number Theory and its applications by Rosen (5th ed.) chapter 8.4.

Quantum computers are the atom bomb of the information age. Of course a lot of good is possible, but also a hell of a lot of evil.

As usual, journalism talking about technical subjects tends to be fuzzy about details...

Assuming that a true Quantum Computer can be built, then:

• RSA, and other algorithms which rely on the hardness of integer factorization (e.g. Rabin), are toast. Shor's algorithm factors big integers very efficiently.
• DSA, Diffie-Hellman ElGamal, and other algorithms which rely on the hardness of discrete logarithm, are equally broken. A variant of Shor's algorithm also applies. Note that this is true for every group, so elliptic curve variants of these algorithms fare no better.
• Symmetric encryption is weakened; namely, a quantum computer can search through a space of size 2n in time 2n/2. This means that a 128-bit AES key would be demoted back to the strength of a 64-bit key -- however, note that these are 264 _quantum-computing_ operations; you cannot apply figures from studies with FPGA and GPU and blindly assume that if a quantum computer can be built at all, it can be built and operated cheaply.
• Similarly, hash function resistance to various kind of attacks would be similarly reduced. Roughly speaking, a hash function with an output of n bits would resist preimages with strength 2n/2 and collisions up to 2n/3 (figures with classical computers being 2n and 2n/2, respectively). SHA-256 would still be as strong against collisions as a 170-bit hash function nowadays, i.e. better than a "perfect SHA-1".

So symmetric cryptography would not be severely damaged if a quantum computer turned out to be built. Even if it could be built very cheaply actual symmetric encryption and hash function algorithms would still offer a very fair bit of resistance. For asymmetric encryption, though, that would mean trouble. We nonetheless know of several asymmetric algorithms for which no efficient QC-based attack is known, in particular algorithms based on lattice reduction (e.g. NTRU), and the venerable McEliece encryption. These algorithms are not very popular nowadays, for a variety of reasons (early versions of NTRU turned out to be weak; there are patents; McEliece's public keys are huge; and so on), but some would still be acceptable.

Study of cryptography under the assumption that efficient quantum computers can be built is called post-quantum cryptography.


I don't believe that 80 millions dollars budget would get the NSA far. IBM has been working on that subject for decades and spent a lot more than that, and their best prototypes are not amazing. It is highly plausible that NSA has spent some dollars on the idea of quantum computing; after all, that's their job, but there is a difference between searching and finding... -- Thomas Pornin

 

[Ur_Mom]

They have admitted to collecting the data. Not running searches for individual things, but they are collecting the data (meta data or whatever) of people both foreign and US citizens. That they have admitted to. They get a warrant to search the data that was previously collected. From there, they can trace it back to however far back they want to for contacts. Does it work? Yes, if you have one person in mind you can trace them back to some other contact that may now be a major terrorist... That's the great thing about big data. It's a shit ton of information and you can connect the dots of a lot of things.

That's where I have the issue. Would I allow someone to video tape me and everything I do as long as they promise not to view it unless they had a reason to? No. If I was suspect of a crime or anything - then yes. But, it should wait until that time. Just my thought on the thing.

But that's not what they do. That's what people tell you they do, that's what people insinuate and suggest they do, but it is not what they do.

In the first place, they were not told to go after terrorists, this is the first inaccuracy, the NSA does not do counter-terrorism, the FBI does, and sometimes the FBI needs NSA support. If the target is foreign then it's no problem, if the target turns out to be a US Person, then they get a warrant.

But they don't sit there and suck up everything to run dirty word searches on it all. that would certainly violate the law, be unconstitutional, and horribly inefficient.

Start with the basic premise that for the most part, our threats originate from foreign sources or are influenced from foreign sources. Now the NSA is supposed to be watching everything foreign, that's their job, yet reality tells us sometimes things cross the oceans. Phone calls, email, web searches, whatever, such things cross and pass through our communications infrastructure and servers. And if a threat travels into the US or tries to recruit into the US, the data pointing to this emerging threat will be here on US Systems, stored in the servers of US businesses like Google, AT&T, Verizon, etc.

Now if you have a known bad guy talking to someone in the States, well that one is easy, it's a slam dunk. But when the foreign end is an unknown threat, then it get's tougher. Phone meta-data helps identify people who are connected, patterns emerge. Those known bad guys talk to other bad guys and sometimes they get around to talking to an unknown bad guy .... who happens to be talking to someone in the US. Maybe a US Person, maybe not. But there is a connection and in some cases other information, like who these people are, who they work for, where they have gone to school, all this information might be enough to justify a closer look. Even more so when the US Person is not a US Citizen or is a naturalized US Citizen. Under the right circumstances there may be justification to request additional data from US Service providers. Under the right circumstances they might get a warrant to conduct actual surveillance operations against a US Person.

Privacy Groups are doing their job for us in challenging the Government about these programs, I got no problem with them. But when a media source takes stolen classified information that points out that the NSA has a facility built in Utah, (wherever it was), that is capable of storing the contents of every phone call that millions of American's make, well that same facility would also be needed to store the contents of millions of foreigners in most every other country's government, military, research facilities, universities, tech companies, energy companies, etc in the world. This is the kind of reporting I have a problem with. I also have a problem with the kind of reporting where the article first suggests that a FISA Court judge threatened to shut down a program because of 2,700 violations and makes it sound like 2.700 people's privacy were violated when in fact the violations were 2,700 security violations meaning the information was being handled improperly, not that the Agency was blatantly violating people's rights even though that is precisely what the author wanted the casual reader to believe. I have a problem with this.

And this is why so many people now talk as if the NSA is without any doubt spying on millions of Americans.

Now the bulk collection program is under scrutiny, not a bad thing, it's under challenge although the first laws that allowed the creation of the programs were challenged a decade ago. Still, ten years is nothing for a country that's over 200 years old, and challenging things is part of why America is America. The challenges in the courts and the scrutiny by our people are good things. But misrepresentation and falsehoods are not and our media has plenty of that going and it's up to us, we are the last check, to look, and read, and challenge cause I don't believe any of those bastards in the media. I have seen more then enough lying from both sides to know better.

 

[1.1.2.3.5...]

...snip...

-- Thomas Pornin

I am having a hard time understanding what you wrote and what Thomas Pornin wrote. Never the less, thanks for the post.

To me it seems to me (I could be wrong) that based on what T.P. wrote there is still a race to be had for some algorithms even with QC. If that is true, that means the first people to get the tech working will less have more secure communication.

Obviously, there are are always more to the details than meets the eye on something sufficiently technical and only experts working the the field ever really know what is going on.

 

[1.1.2.3.5...]

I am having a hard time understanding what you wrote and what Thomas Pornin wrote. Never the less, thanks for the post.

To me it seems (I could be wrong) that based on what T.P. wrote there is still a race to be had for some algorithms. If that is true, that means the first people to get the tech working will (more likely) have more secure communication.

Obviously, there are are always more to the details than meets the eye on something sufficiently technical and only experts working the the field ever really know what is going on.

Dangit....I wish there were a better way to deal with errors in a post and yet let people delete their post. Like a version history for post that cannot be deleted. Then I could edit my post with having to make a whole new post, and yet not remove the original.

 

[SS_Wehrwolf]

Every year we hear about the same stories dealing with Quantum Computers..Every year we hear nothing more about it... until the next slow news cycle picks up and says, Quantum Computer encryption is the next best thing... followed by.. Quantum Encryption hacked with a simple man in the middle attack... followed by... start over again. Nothing to see here you cant read about in scholarly articles and papers every couple months.