Re: [Cfrg] ECC reboot

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Thu, 23 October 2014 19:28 UTC

Return-Path: <ilari.liusvaara@elisanet.fi>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E8C401A19EC for <cfrg@ietfa.amsl.com>; Thu, 23 Oct 2014 12:28:05 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id k1VQBFejMR-g for <cfrg@ietfa.amsl.com>; Thu, 23 Oct 2014 12:28:04 -0700 (PDT)
Received: from emh06.mail.saunalahti.fi (emh06.mail.saunalahti.fi [62.142.5.116]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 098A81A064C for <cfrg@irtf.org>; Thu, 23 Oct 2014 12:28:04 -0700 (PDT)
Received: from LK-Perkele-VII (a88-112-44-140.elisa-laajakaista.fi [88.112.44.140]) by emh06.mail.saunalahti.fi (Postfix) with ESMTP id B8165699AF; Thu, 23 Oct 2014 22:28:01 +0300 (EEST)
Date: Thu, 23 Oct 2014 22:28:01 +0300
From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
To: Phillip Hallam-Baker <phill@hallambaker.com>
Message-ID: <20141023192801.GA30191@LK-Perkele-VII>
References: <5218FD35-E00A-413F-ACCB-AA9B99DEF48B@shiftleft.org> <m3r3y6z3z8.fsf@carbon.jhcloos.org> <CA+Vbu7x4Y_=JZ9Ydp=U5QnJokL28QMQnV4XUn9S6+CUZR9ozEw@mail.gmail.com> <5444D89F.5080407@comodo.com> <90C609A5-ECB2-4FDC-9669-5830F3463D2B@akr.io> <5448DBE2.10107@comodo.com> <CACsn0cne95adtTbCf6WyAZGyCSyLXo5L0302rm7238yHAsE5EQ@mail.gmail.com> <54493DB1.5070204@akr.io> <CALCETrWjR4ROJJFBTo-zAVUg6t50ppm0O_fd=gf2tCr8-evDwg@mail.gmail.com> <CAMm+Lwi-X5_Bh-dwe54uzratLzpds=719F=hzpATCME4wDqxhA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <CAMm+Lwi-X5_Bh-dwe54uzratLzpds=719F=hzpATCME4wDqxhA@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/dnOpiU_N_AGgtpoowJ6OLbAQhrw
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] ECC reboot
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 23 Oct 2014 19:28:06 -0000

On Thu, Oct 23, 2014 at 02:17:35PM -0400, Phillip Hallam-Baker wrote:
> 
> And the AVX-512 extensions provide 512 bit native registers.

Those are vectored registers. The widest multiply appears to be
64x64->128.

Even if 2^512-569 seems like it fits into 8x64 bits, unless you have
good carry handling (you don't for SIMD on Intel CPUs), you need 9x64
bits for optimal speed.

Now, the 9x64 bits could also store 2^521-1 (or 2^522-2), which have
faster reductions due to constant being small and power of two (or 1).

This explains why 2^521-1 is faster than 2^512-567, despite having to
do 9 extra bits and seemingly break word boundary.


Similarly, current fastest implementations for Curve25519 use 5x64
bits, not 4x64 bits.


-Ilari