Re: RSA Secret-Key Challenge Termination

Yeah, what happened to the FPGA boards? The guy that 
was programming them had just about finished his octal
anti-symmetric, or whatever.
Seriously, this is an area that is going to become hot +
like when the D.net project got started, I'm guessing.

In addition to the RC5 project (wich I hope will continue)
we should also look into the factoring challenge.

RC5 is np-complete, by definition. Which makes it an
important benchmarking project. Factoring is believed
to be np-complete, but there isn't any proof. However
there are quite a number of algorithms, with code ready.
D.net could adapt this to an applet easily.

----- Original Message ----
From: Jim C. Nasby <decibeldistributed.net>
To: D.net Discussion <rc5lists.distributed.net>
Sent: Saturday, May 26, 2007 8:37:19 PM
Subject: Re: [RC5] RSA Secret-Key Challenge Termination


On Thu, May 24, 2007 at 01:52:15PM -0700, Demitrius Nelon
wrote:
> I like the idea of some shorter term projects (as
> others have suggested), but I certainly understand the
> issue of the amount of effort to update the network
> and client software.  Maybe there are some medium
> sized projects that could be finished in the 6 months
> to 1 year range.  I've been participating for a decade
> (give or take a couple months) and I'd love to see
> some more success stories.  I think that finding
> projects with cash prizes is a good idea to continue
> an attempt at funding distributed.net as well, but I'm
> not aware of any.

I think the key point about the amount of work required
isn't a matter
of "how much".. it's really a question of
"who". Perhaps some history
will help...

Back in the late 90's, d.net had a "core group" of
about a dozen people
that were very active and involved. This group is what got
stuff done.
Part of that was that distributed computing was newer and
sexier then.
Another part is that most of us had jobs we weren't really
passionate
about.

But all that has changed. While only two folks remain at
United Devices,
those two are quite passionate about the work they're doing
there.
Others have gone on to found successful ventures of their
own. Some are
simply just working at a job that they find challenging,
engaging and
rewarding.

Another consideration is that we're all 10 years older now.
We've got
different responsibilities and different things competing
for our
limited free time.

Does this mean we don't care about d.net? Not at all. But
none of us are
really in a position to push things forward like before.

We would love to have more projects to offer, and we have
made some
limited progress in that area. But for new projects to
happen, *someone*
(or some group of someones) is going to have to really drive
them
forward. This doesn't mean they have to come forward with a
100%
complete solution, but they will need to do a good chunk of
work, and
they'll need to push others into action (which isn't quite
as hard as it
sounds).
-- 
Jim C. Nasby, Database Architect            decibeldistributed.net
Give your computer some brain candy! www.distributed.net
Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"
_______________________________________________
rc5 mailing list
rc5lists.distributed.net
htt
p://lists.distributed.net/mailman/listinfo/rc5
_______________________________________________
rc5 mailing list
rc5lists.distributed.net
htt
p://lists.distributed.net/mailman/listinfo/rc5

On Sat, May 26, 2007 at 12:30:14PM -0700, david fleischer
wrote:
> RC5 is np-complete, by definition. Which makes it an
> important benchmarking project. Factoring is believed
> to be np-complete, but there isn't any proof. However
> there are quite a number of algorithms, with code
ready.
> D.net could adapt this to an applet easily.

Got that running in our public code yet? 
-- 
Jim C. Nasby, Database Architect            decibeldistributed.net
Give your computer some brain candy! www.distributed.net
Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"

_______________________________________________
rc5 mailing list
rc5lists.distributed.net
htt
p://lists.distributed.net/mailman/listinfo/rc5

Le May 26, 2007 à 4:30 PM, david fleischer a écrit :

> In addition to the RC5 project (wich I hope will
continue)
> we should also look into the factoring challenge.
>
> RC5 is np-complete, by definition. Which makes it an
> important benchmarking project. Factoring is believed
> to be np-complete, but there isn't any proof. However
> there are quite a number of algorithms, with code
ready.
> D.net could adapt this to an applet easily.

I'm sorry, I wish it was that easy, but it's not.

Currently, factoring large integers is accomplished using
either the  
elliptic curve method (ECM) or the number field sieve (NFS).
The  
former is well suited to implementation in a distributed
effort over  
the internet (independent work units, with no communication
between  
participants and little communication between participants
and the  
server), and it's quite efficient for removing `small'
factors out of  
large or huge numbers, hence suitable for factoring most
integers  
(due to the distribution of prime factors in a `random'
integer) --  
unfortunately, RSA challenge numbers are far from random in
that  
regard; it is known that they factor into two
similarly-sized prime  
factors, each of which is about half the size of the
original  
integer. For such integers, only the latter algorithm (NFS)
is  
practical. NFS is divided into 5 main stages:

1. Polynomial selection: probably doable over a distributed
network;
2. Sieving: most expensive part of the algorithm, known to
be doable  
over a distributed network;
3. Filtering: requires an SMP machine or a cluster with
high-speed  
interconnect, but not all that expensive, wouldn't be a
bottleneck;
4. Linear algebra: very expensive, requires an SMP machine
or a  
cluster with high-speed interconnect;
5. Square root: small cost, some hours (or at most a few
days) in a  
single fast computer.

If it weren't for step 4, the algorithm could be implemented
in a  
distributed network such as distributed.net. As it stands,
some kind  
soul would have to arrange for processing time in the sorts
of  
expensive machines that can tackle problems of this size
(and few are  
willing to give such processing time away). More esoteric  
possibilities would be to develop a linear algebra algorithm
suitable  
for a distributed network topology (good luck with that) or 

implementing this step in ASICs or FPGAs -- see for instance
Dan  
Bernstein's proposal for integer factoring circuits, which
uses a  
mesh architecture for linear algebra.

Note though that the cost of factoring a 1024-bit RSA
modulus, the  
next milestone of real interest, is estimated to be similar
to that  
of an 80-bit symmetric key crack, i.e. RC5-80, which by
itself is  
~2^8 = 256 times harder than RC5-72, and we know first-hand
how hard  
RC5-72 already is...

Décio
_______________________________________________
rc5 mailing list
rc5lists.distributed.net
htt
p://lists.distributed.net/mailman/listinfo/rc5