GPU LLR program

[CRGreathouse]

Originally Posted by jasong

I suppose it's possible the government changed it's mind, which would explain why B2 released the data after months of protest. Note that that's plenty of time for the government to change their codes away from anything having to do with Riesel numbers.

The US government codes are not, and have never been, based on the factorization of Riesel numbers. Maybe you can even figure out why. (Hint: entropy.)

Personally, I'd like to think that the high-level codes are based on the codes outlined in Bernstein's 2009 book. But alas, that's not so, at least through Top Secret for which the use of AES-192 or AES-256 is sufficient:
http://csrc.nist.gov/groups/ST/toolk...k_ciphers.html

Of course AES is symmetric so not really threatened by quantum methods AFAIK.

[mdettweiler]

@jasong: FYI, there has been some work already put into a CUDA-based LLR program here on this forum. See this thread for more details. It's currently in a sort of alpha/beta stage, and can be faster than a modern CPU depending on the size of the numbers being tested. (GPUs, apparently, do much better on large numbers than small, because they parallelize better or something like that; the aforementioned llrCUDA program can do about twice the speed of one CPU core at n=1.3M or so, and four or eight times faster at n=20M, if I remember correctly.)

[jasong]

Originally Posted by CRGreathouse

The US government codes are not, and have never been, based on the factorization of Riesel numbers. Maybe you can even figure out why. (Hint: entropy.)

Personally, I'd like to think that the high-level codes are based on the codes outlined in Bernstein's 2009 book. But alas, that's not so, at least through Top Secret for which the use of AES-192 or AES-256 is sufficient:
http://csrc.nist.gov/groups/ST/toolk...k_ciphers.html

Of course AES is symmetric so not really threatened by quantum methods AFAIK.

I never said they were based on Riesel numbers.

[jasong]

Originally Posted by mdettweiler

@jasong: FYI, there has been some work already put into a CUDA-based LLR program here on this forum. See this thread for more details. It's currently in a sort of alpha/beta stage, and can be faster than a modern CPU depending on the size of the numbers being tested. (GPUs, apparently, do much better on large numbers than small, because they parallelize better or something like that; the aforementioned llrCUDA program can do about twice the speed of one CPU core at n=1.3M or so, and four or eight times faster at n=20M, if I remember correctly.)

Well, then, that's awesome. Last time I read up on that there was a bunch of jabbering about graphics cards not being able to deal with real(as opposed to integer-based) numbers. Bugged the shizzle out of me, since the FFT is obviously 100% integer-based. But if that's out-dated info, then I apologize for starting the thread.

[Christenson]

Originally Posted by jasong

Well, then, that's awesome. Last time I read up on that there was a bunch of jabbering about graphics cards not being able to deal with real(as opposed to integer-based) numbers. Bugged the shizzle out of me, since the FFT is obviously 100% integer-based. But if that's out-dated info, then I apologize for starting the thread.

Hi Jason:
The $500 hardware is a high-end NVIDIA-brand GPU. It runs CUDA. AMD has a competitive offering, OpenCL, for their hardware, but mfakto (as opposed to mfaktc) is about a year behind, due to a failure on the part of AMD to deal with the need for locks/semaphores/serialisation in concurrent computing systems.

CUDAlucas runs the LL tests.

And for TF, GPUs run circles around CPUs...50GHz days/day is what I get for a GTX440, which is all the power supply on my six-core box will support.

And yes, some public-key codes do rely on the difficulty of factoring large composite numbers with just two large factors....so a delay and slight re-direction of certain projects may have helped protect certain codes, particularly RSA-768. As an example of this sort of thing, some time this year, someone on mersenneforum asked for the factors of a random large number, and disappeared when we asked where they got it from.

And as for the real/integer debate...both have their places, P95 just wants as many bits as he can get....as the LL test run-time is about 95% FFTs.

[Christenson]

Jason,
If you want to contribute, there are two aspects of mfaktc that are a bit of a problem.

The first is the tasking model. That is, suppose we have several processes, all under the same user, one mfaktc, the other CUDALucas, making calls to the GPU, simultaneously. The GPU can't do all of them at the same time...so how do things get scheduled?

The second is Reisel numbers...one of the more respected prime hunters asked if we could re-target numbers of a slightly different form with mfaktc. It's a straightforward extension, but I haven't had time to get into the math to do it.

I'm personally working on automating mfaktc by taking a bunch of code from P95. It's going slowly, but it is going. Once what I am doing is done, you may want to take the technique and apply it to CUDALucas...development there is primarily focussed on algorithms at the moment.

Don't forget to polish your code...a few nuts like myself are going to audit it closely.

Eric C.

[xilman]

Originally Posted by jasong

You might think it's extremely funny, but government encryption is based on prime numbers, so there's always the possibility of invading territory that affects government security. Think about it, supercomputers are based on off-the-shelf parts and the BOINC collection could easily fit in the top-20 of supercomputers if people wanted to treat it that way.

I for one find it somewhat (but not extremely) funny.

A tiny amount of "government encryption" may be based on prime numbers but the vast majority is not. I know that sounds like an unsupported pronouncement but

(a) a goodly number of governmental crypto requirements are well specified in publicly visible documents;

(b) there is a large number of people working and publishing in the unclassified world, some of them contributing here, who would agree that my statement is largely true;

(c) there is a smaller number of people with security clearance from their governments who know at least something about the classified world but it's likely that although I believe they would agree with me, it's unlikely they would confirm it in anything but the most ambiguous manner. I know that at least two people posting on the forum have or have had such clearance from their respective government(s) but I have no real idea what they are / have been working on nor whether they can comment on my assertion --- though I expect not and have no intention of asking them outright.

(d) those paying attention to the open literature have a very good grasp on what is currently possible, near-term feasible and long-term infeasible when attacking encryption "based on prime numbers". Do you really believe that the government agencies haven't been paying attention to what the rest of the world have been doing openly and have not been planning ahead? If so, why did kilobit RSA, for example, reach the end of its recommended life last year?

Paul

[bsquared]

Originally Posted by CRGreathouse

Of course AES is symmetric so not really threatened by quantum methods AFAIK.

There's this work from 2000. Also, the topic was recently discussed in the comments section of Schneier's blog in a post discussing a new (theoretical) attack on AES.

[LaurV]

About NIST approvals of encryption algorithms (approximate quotation from my memory):

"It is quite funny when my students come to me with new encryption algorithms, claiming they are impossible to decrypt, and they were approved by US government. I usually ask them 'Approved for what?'. For export? Usually we never approve for export, or standardize, something we can not decrypt." - Fred Cohen.

(that is the same Fred Cohen who is the father of computer viruses, my thesis was about computer viruses and cryptology, but that was 25 years ago)