[CFRG] (suggested language re mixing square roots and inversions) Re: Comment on draft-irtf-cfrg-hash-to-curve-10
Rene Struik <rstruik.ext@gmail.com> Fri, 23 April 2021 20:47 UTC
Return-Path: <rstruik.ext@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DF8F63A0ADA for <cfrg@ietfa.amsl.com>; Fri, 23 Apr 2021 13:47:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 VX4xr1Lofx_3 for <cfrg@ietfa.amsl.com>; Fri, 23 Apr 2021 13:47:14 -0700 (PDT)
Received: from mail-qk1-x72e.google.com (mail-qk1-x72e.google.com [IPv6:2607:f8b0:4864:20::72e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 806113A0ADD for <cfrg@ietf.org>; Fri, 23 Apr 2021 13:47:14 -0700 (PDT)
Received: by mail-qk1-x72e.google.com with SMTP id y136so18861629qkb.1 for <cfrg@ietf.org>; Fri, 23 Apr 2021 13:47:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:cc:references:from:subject:message-id:date:user-agent :mime-version:in-reply-to:content-transfer-encoding:content-language; bh=PLTMzh+jVe0mtjo2vorgWGzoN5OlOrZJXRb8USYU3kQ=; b=Wv7BZvt169AqxAs4oXqx0fB1hBxX82x8XWH3qwOeBvw/IR0AcdgxE3H7lnVhCBr9Ec YfiKFyIL0No2nVVOpYPu80GAdUKrAoEHcfuzq2cqdSbE+kVMn8cAa6qzZvNl7ZG9tDfR 8hdgOklKFZka/y+M0ub5BDRtSMZdMurdyipfeM/5fwOGL4R+y2H0mEWIYib/0GMYiXEe S4MliCSP9BY1rj7uH7S9aRbTo0IPJu77JHwrvgIrX0lJWhrd/Q8lU/ksYnW/Vl5iBEu/ TCXk+fIlh0DVlcBSt2cdgM5ccKYDHi6kvwaQdutVGA6OEeCQHKn7nHargEZhC6oy3tVg HW6A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:references:from:subject:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=PLTMzh+jVe0mtjo2vorgWGzoN5OlOrZJXRb8USYU3kQ=; b=RghhIgDl18IfRx6TcFWohPLmw2ltMNJrOTo0j5k5kWcBJywC2CDolSnbiL45mKbuJE CLKjrCWAa758rjhpaTlDQqDK1ailL3dqi05wGc2Nd+gPT2EUhaPN49zqA5v+bCMsLEkY J5/AU3jOraX+gNYoUGagRYCLBVEmrOZrX9OPX5MJrPTPOt33xov68bhZx59ltgYOGHbq GQ8wZjeYNOeIR+pmFkpVChiPXftLHf/rHmdUe67vqh3I7tYySIdlJQ2NzHWwIiikVES6 I/FMY+jnsaO0fSI7BoANH53KCmsBI6OoD3AEZ6ek2AItBtzNfiFKQiCxzb/ceNH5AIum s9yQ==
X-Gm-Message-State: AOAM533+7vTayRQaGoOAWMc1M44Hs0CQTRNcTQPgWs8IfbjkpHbTrT8t rbLwSnUQoKZZpZv5hd0xFrAy/665YWI=
X-Google-Smtp-Source: ABdhPJy2CTjkXCgp+zGOEMd6Z7R7dyjFooUqftkTi+tPZhB0SKhv8hxLIG8AbIjOTV2xjsbJ7myVcg==
X-Received: by 2002:a05:620a:11bc:: with SMTP id c28mr5935999qkk.385.1619210832479; Fri, 23 Apr 2021 13:47:12 -0700 (PDT)
Received: from ?IPv6:2607:fea8:8a0:1397:3400:4119:2f4b:1cce? ([2607:fea8:8a0:1397:3400:4119:2f4b:1cce]) by smtp.gmail.com with ESMTPSA id o125sm5122606qkf.87.2021.04.23.13.47.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 23 Apr 2021 13:47:11 -0700 (PDT)
To: "Riad S. Wahby" <rsw@cs.stanford.edu>, Daira Hopwood <daira@jacaranda.org>
Cc: cfrg@ietf.org
References: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org> <108aae2c-576d-ba68-34b8-c539d3fb945d@jacaranda.org> <d2f89438-faeb-47db-97f9-c7ebb394f348@www.fastmail.com> <8c736a71-8ef0-dd8e-1b5a-47cccf1af410@jacaranda.org> <20210422164424.5qwe5msxueqz6rrk@muon> <3360a3c2-9afc-332b-c3c7-6c8c512f8c1b@jacaranda.org> <20210423193036.szrrpvg7zbtplkor@muon>
From: Rene Struik <rstruik.ext@gmail.com>
Message-ID: <bd249275-09aa-9432-6052-602a832c542f@gmail.com>
Date: Fri, 23 Apr 2021 16:47:09 -0400
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.10.0
MIME-Version: 1.0
In-Reply-To: <20210423193036.szrrpvg7zbtplkor@muon>
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Transfer-Encoding: quoted-printable
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/wVJi47Ox_AkoXg1QK7BWDpZtlDo>
Subject: [CFRG] (suggested language re mixing square roots and inversions) Re: Comment on draft-irtf-cfrg-hash-to-curve-10
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 23 Apr 2021 20:47:19 -0000
Hi Riad: Text along the following lines would avoid implementation detail, but would illustrate how one could "mix" inversions and square roots: The inverses of two nonzero elements y1 and y2 of GF(q) can be computed by first computing the inverse z of y1*y2 and by subsequently computing y2*z=:1/y1 and y1*z=:1/y2. This method can be used to compute the inverse and a square root, respectively, of two nonzero elements x and y of GF(q) (where y is a square in GF(q)) by first computing a square root z of 1/(y*x^2) and by subsequently computing a square root of y as x*y*z and the inverse of x as x*y*z^2. I think this would be easier to read than any "div" verbiage and avoids having to deal with divisions by zero. (In the case q = 3 (mod 4), if y is a nonzero element of GF(q) and z:=y^{(q-3)/4}, then y is a square in GF(q) only if y*z^2=1. One can generalize this to q = 5 (mod 8), q = 9 (mod 16), etc., where the general procedure is to compute z:=y^{(q-2^s-1)/2^{s+1}} in GF(q) where q:=2^s+1 (mod 2^{s+1}) and where y is a square in GF(q) only if (y*z^2)=w, where w^{2^{s-1}}=1. For s large, one gets Daira Hopwood's case with higher s, but the principle remains the same (and one could refer to a paper for computational tricks or simply declare this out of scope).) Rene On 2021-04-23 3:30 p.m., Riad S. Wahby wrote: > Hello Daira, > > Thanks for clarifying your feedback. > > I remain concerned about mixing implementation detail with high-level > description. Here I am referring to using divsqrt in place of natural > field arithmetic operations (sqrt, inversion, etc.) in the body text. > Describing the algorithm independent of the implementation details is > a way of specifying the mathematical properties of the algorithm, and > having this specification explicit in the document has value, from my > perspective. > > But as I said in my prior email, it seems like refactoring Appx. G to > use divsqrt and adding a few implementations of that function for the > relevant cases (3 mod 4, 5 mod 8, 9 mod 16, and general, perhaps?) is > a nice way of cleaning things up. And it seems like the same refactor > applied to SvdW and Elligator in Appx. G would help, too. > > This isn't something I can do in the near term, but I'm very happy to > spend time on this once I've got some! I'm hopeful that's about three > weeks from now, but I've been called an optimist before. > > Thanks again for the feedback and best regards, > > -=rsw > > _______________________________________________ > CFRG mailing list > CFRG@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg -- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 287-3867
- [CFRG] Comment on draft-irtf-cfrg-hash-to-curve-10 Daira Hopwood
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Daira Hopwood
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Christopher Wood
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Stanislav V. Smyshlyaev
- [CFRG] Small subgroup question for draft-irtf-cfr… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Loup Vaillant-David
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Russ Housley
- Re: [CFRG] Small subgroup question for draft-irtf… Richard Outerbridge
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Scott Fluhrer (sfluhrer)
- Re: [CFRG] Small subgroup question for draft-irtf… Scott Fluhrer (sfluhrer)
- Re: [CFRG] Small subgroup question for draft-irtf… Rene Struik
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Scott Fluhrer (sfluhrer)
- Re: [CFRG] Small subgroup question for draft-irtf… Armando Faz
- Re: [CFRG] Small subgroup question for draft-irtf… Loup Vaillant-David
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… rsw
- Re: [CFRG] Small subgroup question for draft-irtf… Björn Haase
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… rsw
- [CFRG] please use real names (was: Re: Small subg… Rene Struik
- Re: [CFRG] Small subgroup question for draft-irtf… Hugo Krawczyk
- Re: [CFRG] Small subgroup question for draft-irtf… Rene Struik
- Re: [CFRG] Small subgroup question for draft-irtf… Watson Ladd
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Rene Struik
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] Small subgroup question for draft-irtf… Watson Ladd
- Re: [CFRG] Small subgroup question for draft-irtf… rsw
- Re: [CFRG] Small subgroup question for draft-irtf… Loup Vaillant-David
- Re: [CFRG] Small subgroup question for draft-irtf… Riad S. Wahby
- Re: [CFRG] please use real names (was: Re: Small … Filippo Valsorda
- Re: [CFRG] please use real names (was: Re: Small … Scott Arciszewski
- Re: [CFRG] please use real names (was: Re: Small … Daniel Franke
- Re: [CFRG] please use real names (was: Re: Small … Watson Ladd
- Re: [CFRG] please use real names (was: Re: Small … Michael StJohns
- Re: [CFRG] please use real names (was: Re: Small … Henry de Valence
- Re: [CFRG] please use real names (was: Re: Small … Dan Harkins
- Re: [CFRG] Small subgroup question for draft-irtf… Hugo Krawczyk
- Re: [CFRG] please use real names (was: Re: Small … Peter Gutmann
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] please use real names (was: Re: Small … Squeamish Ossifrage
- Re: [CFRG] please use real names (was: Re: Small … Blumenthal, Uri - 0553 - MITLL
- Re: [CFRG] Small subgroup question for draft-irtf… Stanislav V. Smyshlyaev
- Re: [CFRG] Small subgroup question for draft-irtf… Björn Haase
- Re: [CFRG] please use real names (was: Re: Small … Soatok Dreamseeker
- Re: [CFRG] please use real names (was: Re: Small … Blumenthal, Uri - 0553 - MITLL
- Re: [CFRG] please use real names (was: Re: Small … Soatok Dreamseeker
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] please use real names (was: Re: Small … Daniel Franke
- Re: [CFRG] please use real names (was: Re: Small … Mike Hamburg
- Re: [CFRG] Small subgroup question for draft-irtf… Mike Hamburg
- Re: [CFRG] please use real names (was: Re: Small … Colin Perkins
- Re: [CFRG] please use real names (was: Re: Small … Blumenthal, Uri - 0553 - MITLL
- Re: [CFRG] please use real names (was: Re: Small … Soatok Dreamseeker
- Re: [CFRG] please use real names (was: Re: Small … Mike Hamburg
- Re: [CFRG] please use real names (was: Re: Small … Michael StJohns
- Re: [CFRG] Small subgroup question for draft-irtf… Hao, Feng
- Re: [CFRG] please use real names (was: Re: Small … Michael Sierchio
- [CFRG] Closure (was Re: Small subgroup question f… Hao, Feng
- Re: [CFRG] please use real names (was: Re: Small … Phillip Hallam-Baker
- Re: [CFRG] please use real names (was: Re: Small … Peter Gutmann
- Re: [CFRG] please use real names (was: Re: Small … David Jacobson
- Re: [CFRG] please use real names (was: Re: Small … Julia Hesse
- Re: [CFRG] Closure (was Re: Small subgroup questi… Armando Faz
- Re: [CFRG] Closure (was Re: Small subgroup questi… Hao, Feng
- Re: [CFRG] Closure (was Re: Small subgroup questi… Mike Hamburg
- Re: [CFRG] thoughts on clearing the cofactor in h… Loup Vaillant-David
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Stanislav V. Smyshlyaev
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Daira Hopwood
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Riad S. Wahby
- [CFRG] (suggested language re mixing square roots… Rene Struik
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Loup Vaillant-David
- Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-cur… Daira Hopwood
- Re: [CFRG] (suggested language re mixing square r… Daira Hopwood
- Re: [CFRG] (suggested language re mixing square r… Rene Struik
- Re: [CFRG] please use real names (was: Re: Small … isis agora lovecruft