Re: [Cfrg] 1024 bit RSA

Ilari Liusvaara <> Fri, 04 November 2016 21:23 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 972EA1296B0 for <>; Fri, 4 Nov 2016 14:23:55 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.397
X-Spam-Status: No, score=-3.397 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-1.497] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id EPxL-9Ax96m9 for <>; Fri, 4 Nov 2016 14:23:54 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id 11976129697 for <>; Fri, 4 Nov 2016 14:23:52 -0700 (PDT)
Received: from localhost (localhost []) by (Postfix) with ESMTP id 9976711583; Fri, 4 Nov 2016 23:23:51 +0200 (EET)
X-Virus-Scanned: Debian amavisd-new at
Received: from ([IPv6:::ffff:]) by localhost ( [::ffff:]) (amavisd-new, port 10024) with ESMTP id mHkOgQX8lBv9; Fri, 4 Nov 2016 23:23:51 +0200 (EET)
Received: from LK-Perkele-V2 ( []) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPSA id 0C5892313; Fri, 4 Nov 2016 23:23:51 +0200 (EET)
Date: Fri, 04 Nov 2016 23:23:48 +0200
From: Ilari Liusvaara <>
To: Hal Murray <>
Message-ID: <>
References: <>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
In-Reply-To: <>
User-Agent: Mutt/1.5.23 (2014-03-12)
Archived-At: <>
Cc: Cfrg <>
Subject: Re: [Cfrg] 1024 bit RSA
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 04 Nov 2016 21:23:55 -0000

On Fri, Nov 04, 2016 at 02:03:13PM -0700, Hal Murray wrote:
> 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

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).