Re: [Cfrg] 1024 bit RSA

[Ilari Liusvaara <[e-mail]>]

On Fri, Nov 04, 2016 at 02:03:13PM -0700, Hal Murray wrote:
> 
> [e-mail] said:
> > So expect RSA 1024 to certainly fall by 2030 and probably by 2025. 
> 
> What are the right units for that discussion?
> 
> I think it has to include cost and time-to-solve.  For compute-intensive 
> approaches that parallize, the time part drops out.  There are probably 2 
> paths, one using COTS gear and another using ASICs.
> 
> Is there something like Moore's Law for breaking crypto?

(Warning: Pretty pure guessing ahead.)


I think it depends on what you are talking about: Using CPUs vs. ASICs.

For CPUs, I think the improvements of Moore's law mostly go to very
modest performance improvements (and to reducing power usage).

Of course, Moore's law might have slowed down by now... And will
probably halt soon (I don't imagine transition off Si being that
smooth... There have been enormous amounts of infrastructure
invested on Si).


For ASICs, those improvments probably could mostly go to improving
performance. The main limit is heat dissipiation.

And when it comes to cost of building ASICs, the costs are mostly
upfront (design, masks, etc... are very expensive). Manufacturing
ASICs (at least if using ordinary digital-only processes) is quite
cheap.

So once one has design and masks for ASIC, one can cheaply get
massive number of copies. And ASICs can be quite specialized.


One fortunate aspect with RSA is that the final step of
factoring involves quite a lot of memory use. But it takes relatively
little time (most of the work is in sieving).

In summary, I would guess that factoring RSA 1024 keys would be within
reach of groups who could do ASIC design and then ordering custom
chips off fabs. Of course, that's still many millions, so one would
need the financial case of spending that much money (it is going to
be millions of dollars at the very least).


-Ilari