RSA Lattice Siever (2.0) -beendet

[rebirther]

http://boinc.unsads.com/rsals/

Team

[rebirther]

Scheinbar verfolgt das Projekt jetzt ein anderes Ziel, wer sich das etwas durchliest, findet sicherlich ein Bezug auf yoyo@home ;)

First of all, a little historic note: the project was born to centralize sieving of 13 of the 14 512-bit public RSA keys used for cryptographic signature in TI-Z80 and TI-68k calculators, using a BOINC-ified version of ggnfs-lasieve4I14e.
After deducing the private keys from the factors, we can now sign whatever software we want (third-party OS and "FlashApps", without any code originating from TI because that would be illegal in some countries) for tinkering with our moddable devices sold by millions. The freedom to tinker with the devices we own.

For some reason, and fortunately, RSALS didn't get the French equivalent of a US DMCA takedown notice. But various sites and persons in the USA did, and TI's improper use of the DMCA claims earned the keys a permanent place on Wikileaks, and earned TI's behaviour a spotlight on Slashdot, CNET, The Register, Boing Boing, Ars Technica, Wall Street Journal... between many others !
The EFF successfully defended several US citizens that had been targetted by TI's improper DMCA claims: first post , second post.

Then, we switched to factoring integers of mathematical interest. So far, we're sticking to siever 14e:

•XYYXF integers, in chronological order of appearance, by GNFS or SNFS depending on the difficulty: C151_105_101, C152_107_66, C157_105_74, C160_110_47, C157_109_50, C151_110_49, C152_112_59, C142_121_87, C146_107_103, C202_120_49, C203_132_100, C211_114_71, C208_122_82, C157_113_57, C201_122_47, C200_125_42, C145_134_41, C151_127_80, C199_137_31, C151_142_94, C150_134_102, C150_134_114, C179_111_76, C179_111_71, C179_107_74, C178_140_48, C176_121_51, C175_113_65, C170_120_53, C172_118_100, C173_137_32, C173_109_76, C173_132_76, C173_125_41.

•near-repdigit integers, in chronological order of appearance, all by SNFS so far: 17777_207, 17777_218, 17777_227, 54449_201, 66661_190, 35553_197, 52229_205, 57771_204, 11113_210, 48887_203, 52227_203, 37771_205, 35557_204, 20009_229.

•aliquot: a C158 at index 1635 in aliquot sequence 276 by GNFS.
•Homogenous Cunningham: a C202 cofactor of 8^233-3^233 by SNFS.
•more to come :-)

[rebirther]

An advance notification (which will be relayed at other places as well): RSALS is going to be fully replaced by NFS@Home in the next few weeks, and shut down.

(warning, long post ahead )

The reasons behind this move are:
* the fact that the server is old and pretty expensive for such a low amount of computing power, and we want to get rid of it;
* the fact that RSALS's sievers would need an upgrade, the addition of a 64-bit Linux siever and of MacOS X siever(s ?). The larger NFS@Home grid has already had that for a long time, and had 14e sievers, unused until now;
* the fact that the BOINC code itself would need an upgrade, once in a while;
* the fact that squalyl and I don't have much free time.

Given this, why not just use NFS@Home for 14e sievings as well, and potentially have more people maintaining and contributing to a single, stronger grid ?

Unless other people want to do that job, I can (and for now, plan to) stay involved in feeding NFS@Home's 14e siever with numbers originating from OddPerfect and other projects.


On the occasion of the project winding down, after about three years of operation, it's definitely time to look back at history


The initial purpose and results of RSALS
As indicated in the topic introducing NFS@Home ( http://www.mersenneforum.org/showthread.php?t=12388 ), created shortly before this one, RSALS was the first BOINC wrapper for NFS factoring, made by squalyl. It was created by amateurs who had never used NFS before (as you'll see if you read my posts near the beginning of the NFS@Home topic: I didn't know that NFS existed in General and Special flavors), out of the need to factor a dozen remaining 512-bit RSA public keys more quickly (after starting the two first keys by what is termed "team sievings" here). Honestly, I don't think that any of us had projected RSALS into the long term - at least, I don't remember about discussions on the topic of what to do after the factorization of all keys
Said RSA public keys are used for validating signed OS updates and "FlashApps" (larger programs executing directly from Flash memory) in several TI graphing calculators based on Z80 and 68000 processors, collectively known as "TI-Z80" and "TI-68k" series. For more detail on the initial purpose of the RSALS grid, see the first post of this topic ( http://www.mersenneforum.org/showthread.php?t=12456 ).

After deducing the private keys from the factors of the public keys, we can now sign whatever software we want (third-party OS and "FlashApps", without any code originating from TI because that would be illegal in some countries) for tinkering with our moddable devices sold by millions. The freedom to tinker with the devices we own.

For some reason, and fortunately, RSALS didn't get the French equivalent of a US DMCA takedown notice. But various sites and persons in the USA did, and TI's improper abuse of the DMCA claims earned the keys a permanent place on Wikileaks, and earned TI's behaviour a spotlight on Slashdot, CNET, The Register, Boing Boing, Ars Technica, Wall Street Journal... among many others !
The EFF successfully defended several US citizens that had been targetted by TI's illegal DMCA claims: first post , second post.


RSALS's second life as a grid for factoring numbers of mathematical interest
We sieved about 400 composite integers of mathematical interest, obtained though a wide range of forms (a^n-1, a^n+1, x^y+y^x, near-repdigit, Aliquot, a^n-b^n, etc.). We sneaked in a couple 512-bit RSA keys, for the 3DO games console, whose hobbyists were in the same situation wrt. signature and validation as we TI graphing calculator community were. We turned down several other requests for factoring 512-bit RSA keys, but pointed the persons who had contacted us to Jeff Gilchrist's pages, indicating them that a single recent quad-core computer would do the job in less than one month.
Nowadays, http://www.mersenneforum.org/showthread.php?t=16114 has become another option for factoring 512-bit RSA keys.

We went through rough times due to low disk space and the fluctuating computing power of the grid. I made several mistakes, under the form of ECM misses, as shown in this topic. For my defense, the most glaring ECM misses were due to the most massive influx of clients ever on RSALS. I just didn't know what to feed them, and I queued 4 hard numbers from near-repdigit, 2 of which proved to be significant ECM misses... I just forgot to run more ECM on another hard, but known under-ECM-ized, near-repdigit number.
That said, these ECM misses produced a great effect: they prompted William Lipp (OddPerfect) to offer partnership, which solved both the low disk space and numbers which hadn't received enough ECM work, and made RSALS a much more serious project - effectively, its second beginning
Since then, the vast majority of the 350+ numbers I queued to RSALS (with the then-new automated work generation infrastructure made by squalyl) were well ECM-ized a^n-1 numbers useful to OddPerfect, Cyclotomic, Brent and other projects. That worked pretty well until recently, when RSALS ended up burning almost entirely the queue of OddPerfect numbers suitable for NFS (under the 2/9 rule of thumb); to give OddPerfect a rest, I queued various well-ECM-ized near-repdigit and GCW numbers, and even a Cunningham composite

Another mistake I did was to let database corruption occur as a result of all too delayed raw relations files cleanup, at the end of 2011. Restoring RSALS from backups worked, but there was significant downtime, and that was the first time squalyl, frmky and I seriously talked about moving the 14e sievings from RSALS to NFS@Home.


On a personal level
I became involved in RSALS somewhat by accident, by doing some polynomial selection work and participating to the forums of the TI graphing calculator community, before becoming the co-admin of RSALS during squalyl's holidays. I queued the WUs for the last few RSA keys, and since RSALS outlived its initial purpose of factoring TI's RSA keys, I acted as the public face of RSALS.

I learnt a lot about the names and usage of factoring algorithms, their range of applicability, etc. However, I'm still (nearly) as incompetent as ever on the workings of factoring algorithms (how and why they work) - besides TF, of course. I never try to explain factoring algorithms to people who know them better than I do, and some of the attendees of this forum would want to slaughter me if I dared explaining them my understanding of NFS
I tried to apply the experience of the many people, here on MersenneForum, who know better than I do, and I learnt the orders of magnitude; but I'm not convinced that knowing precisely how NFS works would have made me much better at managing RSALS.


Special thanks
* "FloppusMaximus" Benjamin Moody, for leading the way and making many people from the TI community realize that we could easily factor 512-bit RSA public keys (something that people here on MersenneForum knew);
* squalyl for creating the grid, performing the bulk of the sysadmin work, the automated work generation infrastructure, and paying the bills for that shitty server for so long;
* jasonp, for the invitation to MersenneForum. Someone (frmky ?) had pointed him to the United-TI topic where the first factorization was announced (or one of the sibling topics), where he was mentioned, and he kindly posted there;
* frmky, for his help in the initial post-processing (IIRC, he post-processed several RSA keys), for discussions which enabled me to improve the operation of RSALS, and for NFS@Home;
* William Lipp (OddPerfect), for the aforementioned partnership for finding a reliable source of numbers and post-processing power, which enabled RSALS to keep existing for so long;
* yoyo for yoyo@home, for the preparatory ECM work for OddPerfect, near-repdigit and other projects. We have had little direct contact, but the yoyo@home grid was invaluable to RSALS and other projects;
* our many post-processers, especially Jeff Gilchrist, Pace Nielsen, Carlos Pinho. For a more complete list, see http://boinc.unsads.com/rsals/crunching.php , which shows post-processing information for all numbers handled by the automated work generation and results collation infrastructure (several dozens of numbers are therefore missing);
* of course, the owners of thousands of cores which have participated, to some extent, to the fluctuating throughput of RSALS.


Open questions
* how to handle RSALS credits wrt. NFS@Home ? Stats-minded people who contributed a lot to RSALS but never contributed to NFS@Home might not be too happy to restart from zero. That said, in the transition, it's only a secondary concern, to be addressed after primary concerns such as copying RSALS's automated work generation infrastructure (I can't live without it, as my estimates for the number of relations remain frequently off by +/-10%) to NFS@Home.

In ein paar Wochen wird das Projekt komplett in NFS einfließen, danach ist es beendet.