Re: [Cfrg] Progress on curve recommendations for TLS WG

Michael Hamburg <mike@shiftleft.org> Sun, 17 August 2014 08:20 UTC

Return-Path: <mike@shiftleft.org>
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 CF5331A0785 for <cfrg@ietfa.amsl.com>; Sun, 17 Aug 2014 01:20:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
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 lckQuGe7kctP for <cfrg@ietfa.amsl.com>; Sun, 17 Aug 2014 01:20:18 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E39591A0784 for <cfrg@irtf.org>; Sun, 17 Aug 2014 01:20:17 -0700 (PDT)
Received: from [192.168.1.146] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 1C6DC3AA12; Sun, 17 Aug 2014 01:18:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1408263530; bh=rIBsXX01kGSNDe2MlTsom1fkOf3yzx0v0MbkMUT4Anw=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=O5IZ5kypiT/k2Gnxz2OHmr43l/f0mvLCDRDHORIIDH/NQiOayBI3AhfxsCmcgHSbZ K0o6DEz5o5mepUXq8Af+tinlnVTDvLPCsgAZ8NWfAuB4GF1naDwcdeT0CtHAHdDD6h /l71Gp34GbDnC7ApVQgHSf4TpTCT3doRL770S1F4=
Content-Type: multipart/alternative; boundary="Apple-Mail=_D450F7EB-8542-44EB-9B15-A4A99E55FFD5"
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1971.5\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <53F05207.1050509@brainhub.org>
Date: Sun, 17 Aug 2014 01:20:14 -0700
Message-Id: <5A46CF1A-CBF3-4954-AB53-257E13BBEF1A@shiftleft.org>
References: <CFFB1371.2916E%kenny.paterson@rhul.ac.uk> <20140808141506.GA24645@LK-Perkele-VII> <53EDEE67.6090308@secunet.com> <A1FCAAE8-4F20-4AC1-A635-AED20E8F7D5C@shiftleft.org> <53EE8F45.9070908@brainhub.org> <F3296E50-46AD-4653-BCCA-5435D6ECB78F@shiftleft.org> <53F05207.1050509@brainhub.org>
To: Andrey Jivsov <crypto@brainhub.org>
X-Mailer: Apple Mail (2.1971.5)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/r-9GJmz88-9pIJiJ4Lvuwv5Ip4Q
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
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: Sun, 17 Aug 2014 08:20:19 -0000

> On Aug 16, 2014, at 11:56 PM, Andrey Jivsov <crypto@brainhub.org>; wrote:
> 
> I looked at my implementation of modp reduction I did a few years ago for a fixed p. I used Barrett reduction.
> 
> At closer look I don't see why multiply+reduction mod p, for a random but fixed p, is 2n^2 + n. I got a corrected value for Barrett reduction below.

You can reduce one digit at a time.  Eg just cancel the top digit at a cost of one multiply to find the approximate factor plus n to multiply by p, then repeat.  It’s a little easier with Montgomery than with Barrett, since Montgomery always cancels the low digit out exactly.

This is why it’s a pain to reduce with Karatsuba, though.  I don’t know an easy way around it: you either reduce by several digits at a time and pay an extra cost like in your calculations, or you do one at a time but can’t use Karatsuba.

— Mike