Re: [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> Mon, 03 May 2021 13:29 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 CD8BB3A118F for <cfrg@ietfa.amsl.com>; Mon, 3 May 2021 06:29:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level:
X-Spam-Status: No, score=-2.1 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, NICE_REPLY_A=-0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 4naXLVhvOa4u for <cfrg@ietfa.amsl.com>; Mon, 3 May 2021 06:29:28 -0700 (PDT)
Received: from mail-qv1-xf30.google.com (mail-qv1-xf30.google.com [IPv6:2607:f8b0:4864:20::f30]) (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 7B36E3A118E for <cfrg@ietf.org>; Mon, 3 May 2021 06:29:28 -0700 (PDT)
Received: by mail-qv1-xf30.google.com with SMTP id z1so2519606qvo.4 for <cfrg@ietf.org>; Mon, 03 May 2021 06:29:28 -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=Ly+cY5+4TLgdImZ2yw6FXSNa2BiTge2KljSESdvM3pw=; b=XrbGA/yUx91xun3vMPzUpaTc57YP8K5PhJkteer6oU2kgHZrPc6CxkIxLz1XPmui+f 5xsbmMQ+aD0CCx4aBtHtagr3xOdiBgIiH4+eDKgqsAf0uMdiMTqaIVqyvRzL7O1lgZWy Q+rDl/nZOaYiN2/tp0vMEcPFkTTxD4fp/qB0Hf21Og/US9/FmMPoOhOXJjMNdZg6+J/k /OPzpGZSVnp7ZZuInFbOdeyAy+YuK5aSC2gyyTxjbGMjGt57ZDsR1kYGgTQtGyth99mC Mc5yxAcjqmAPSd2yjkM/qbYo+e1ogLfmFe+HgCccpwLMN2P8jieNw5yxd3uhBqwAY7xR pxVg==
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=Ly+cY5+4TLgdImZ2yw6FXSNa2BiTge2KljSESdvM3pw=; b=tqhvZJgPsPWyGFk2cx6Z9CvBD8QkBsQAfsums/ujegHX1jekBU4MM4kexnHykY2JMp Dp/J6tv3oUKN3aMTRBUT2MyEg33Y1yzQ6kctVOwbzE4cqcMjYwy8UOqPHrHwBO64Gbjl ZH7YNNdsLuxaTnreTY57RjD+bPqLLw2klF99wvVtBd1OsRUsaelf+nF79gTh6+szsxKB HVYnUHsLpNFjA3JVJE0Rts/u4vCjgJg7GiC24rpgHbSkZ3v+TyAup1oLOv1NSWxeX7At dEgd0HyAI1UP8HFKK0wESr84Ll1jiltQ1Fq/p9aOqhyFlVMLbWcVbWzktzyd2yR049q/ rxDA==
X-Gm-Message-State: AOAM531DF1iBpHVlMnEZfJMtet/gi46ey62yLS+yZs8r+D4WrRdK3C2N WTJDcafHE+QOWs5OJM3j0I+rVmC1AQg=
X-Google-Smtp-Source: ABdhPJyMGqk39Vf1ONFXQkfcmfJINU1de9fc+vCdfp6LHDi8WmvXU82PKP4F8Ho5V49hzc0SXRzMGw==
X-Received: by 2002:ad4:538a:: with SMTP id i10mr19423697qvv.9.1620048565849; Mon, 03 May 2021 06:29:25 -0700 (PDT)
Received: from ?IPv6:2607:fea8:8a0:1397:f1ac:390c:3f4f:a677? ([2607:fea8:8a0:1397:f1ac:390c:3f4f:a677]) by smtp.gmail.com with ESMTPSA id g13sm3267250qtp.31.2021.05.03.06.29.24 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 03 May 2021 06:29:25 -0700 (PDT)
To: Daira Hopwood <daira@jacaranda.org>, "Riad S. Wahby" <rsw@cs.stanford.edu>
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> <bd249275-09aa-9432-6052-602a832c542f@gmail.com> <e5a4286f-d751-a35e-5ce6-349641a8602b@jacaranda.org>
From: Rene Struik <rstruik.ext@gmail.com>
Message-ID: <c91c2193-f2b2-a910-3c45-0680d5092649@gmail.com>
Date: Mon, 3 May 2021 09:29:22 -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: <e5a4286f-d751-a35e-5ce6-349641a8602b@jacaranda.org>
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/RIVy5H40IdvLdO_l4j3IbFElN0s>
Subject: Re: [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: Mon, 03 May 2021 13:29:30 -0000

Two sentences are all that is needed to describe taking a square root 
and any number of inversions ("Montgomery's trick"), in an easy to read 
format by humans.

On 2021-05-03 2:23 a.m., Daira Hopwood wrote:
> On 23/04/2021 21:47, Rene Struik wrote:
>> 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.
>
> But computing the inverse and the square root in parallel isn't what
> we're doing. The combined inverse-and-sqrt method we're referring to
> here isn't rocket science, it will be familiar to anyone who has
> implemented Ed25519.
>
>> I think this would be easier to read than any "div" verbiage and 
>> avoids having to deal with divisions by zero.
>
> Just to be clear, there are no divisions by zero in the specification
> I gave in my previous post:
>
> Let h be some fixed nonsquare in Fq. Define sqrt_ratio for
> u ∊ Fq and v ∊ Fq* as:
>
>   sqrt_ratio(u, v) = (true, sqrt(u/v)),    if u/v 
is square in Fq
>                    = (false, sqrt(h*u/v)), otherwise.
>
> Notice that sqrt_ratio is not defined for v = 0, and it is easily proven
> that it is never applied with v = 0.
>

-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867