I've been toying with the idea of running that popular RC5 key search on a
PIC. Now, I realize it probably won't be cost effective, because I have
estimated the performance of it on a PIC - with $1 per a 20 MHz pic, I'd spend
more money on just the PICs than buying a complete K6-2 or Celeron system, to
get equivalent performance.

What really hurts the performance is the 32-bit data, and how to handle it.
I've managed to do a 32-bit rotate (which can roll the data 0-31 bits left),
which takes 17-47 instruction cycles (average 35.25), but haven't looked
further into it. I'd be ecstatic if I managed to get above 5000 keys/second
from a single PIC, but I have a feeling that it will be difficult if not even
impossible.