IETF Logo Mail Archive

Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

Michael Hamburg <mike@shiftleft.org> Mon, 12 January 2015 17:59 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 03C751ACD1A for <cfrg@ietfa.amsl.com>; Mon, 12 Jan 2015 09:59:50 -0800 (PST)
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 OOMDgcbk9317 for <cfrg@ietfa.amsl.com>; Mon, 12 Jan 2015 09:59:45 -0800 (PST)
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 9DE101AC3B0 for <cfrg@irtf.org>; Mon, 12 Jan 2015 09:59:45 -0800 (PST)
Received: from [192.168.1.117] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 28FFC3AA12; Mon, 12 Jan 2015 09:56:46 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1421085406; bh=TbaFi2UsgZRbx+nseQCzS3LPxKgHUs98E7knj1JZ7wk=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=IXqZMU60/QfLUemxKHvkndKJFgCCJhsW2RRMFVPJ4E+vaCCv75xgE7ez69EXOcZUz u5tscJO+kVNJAArqyc4Go2ZSW0j25ZIy8Ezhdea+yIibpJrEepRZovaTc7vEU1u6Se xFd/yUl12BRYcB7SEIyC6U+nqszfRWPunb+N+yro=
Content-Type: multipart/alternative; boundary="Apple-Mail=_CCE7BC89-288B-452F-8E5E-55A7D7D3BF85"
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.1\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CACsn0c=qxBXCkr7hCtzgY9U+5_N8hY=jShU7g=hUbqkrUMYxNw@mail.gmail.com>
Date: Mon, 12 Jan 2015 09:59:42 -0800
Message-Id: <3C94ED57-5089-4A6D-9CC6-2DCD452C7BCF@shiftleft.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org> <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org> <CACsn0c=qxBXCkr7hCtzgY9U+5_N8hY=jShU7g=hUbqkrUMYxNw@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
X-Mailer: Apple Mail (2.2070.1)
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/mbtULRlzuPkbkEikDhjbUEXEquI>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
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: Mon, 12 Jan 2015 17:59:50 -0000

> On Jan 12, 2015, at 7:28 AM, Watson Ladd <watsonbladd@gmail.com> wrote:
> The table is filled with a cost of 8M for additions and 4M+4S for
> doublings so 2^(w-2)*8M+2^(w-2)*(4M+4S). Then we proceed for
> ceil(255/w)-1steps, each step consisting of (w-1) 3M+4S doublings, and
> 1 4M+4S doubling. Ergo the total cost becomes
> 2^(w-2)*(12M+4S)+(ceil(255/w)-1)*(w*(3M+4S)+1M).

Don’t you need to do some additions at some point as well?  Or do the additions only cost 1M?

— Mike

v2.23.0 | Report a Bug | By Email