Re: [Cfrg] Hashing to EC group elements

Paul Lambert <paul@marvell.com> Mon, 06 January 2014 20:48 UTC

Return-Path: <paul@marvell.com>
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 6034B1AE211 for <cfrg@ietfa.amsl.com>; Mon, 6 Jan 2014 12:48:10 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.967
X-Spam-Level:
X-Spam-Status: No, score=-0.967 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, IP_NOT_FRIENDLY=0.334, J_CHICKENPOX_54=0.6, 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 5c_tE5feMLG3 for <cfrg@ietfa.amsl.com>; Mon, 6 Jan 2014 12:48:09 -0800 (PST)
Received: from mx0b-0016f401.pphosted.com (mx0b-0016f401.pphosted.com [67.231.156.173]) by ietfa.amsl.com (Postfix) with ESMTP id 146161AE20F for <cfrg@irtf.org>; Mon, 6 Jan 2014 12:48:08 -0800 (PST)
Received: from pps.filterd (m0045851.ppops.net [127.0.0.1]) by mx0b-0016f401.pphosted.com (8.14.5/8.14.5) with SMTP id s06Klxvj024992; Mon, 6 Jan 2014 12:47:59 -0800
Received: from sc-owa01.marvell.com ([199.233.58.136]) by mx0b-0016f401.pphosted.com with ESMTP id 1h6q2mgev1-1 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT); Mon, 06 Jan 2014 12:47:58 -0800
Received: from SC-vEXCH2.marvell.com ([10.93.76.134]) by SC-OWA01.marvell.com ([10.93.76.21]) with mapi; Mon, 6 Jan 2014 12:47:58 -0800
From: Paul Lambert <paul@marvell.com>
To: Robert Ransom <rransom.8774@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Date: Mon, 6 Jan 2014 12:47:57 -0800
Thread-Topic: [Cfrg] Hashing to EC group elements
Thread-Index: Ac8Jj121g+//U8qISBy56gfIkQ0GHQBj93Jg
Message-ID: <7BAC95F5A7E67643AAFB2C31BEE662D018B7D6E09C@SC-VEXCH2.marvell.com>
References: <CABqy+sr2z5cV_7snYGz98Xj9QVj4xpYd1L+DQ6O7sO29zyYKKA@mail.gmail.com>
In-Reply-To: <CABqy+sr2z5cV_7snYGz98Xj9QVj4xpYd1L+DQ6O7sO29zyYKKA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.11.87, 1.0.14, 0.0.0000 definitions=2014-01-06_03:2014-01-06, 2014-01-06, 1970-01-01 signatures=0
X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=7.0.1-1305240000 definitions=main-1401060140
Subject: Re: [Cfrg] Hashing to EC group elements
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, 06 Jan 2014 20:48:10 -0000


> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Robert Ransom
> Sent: Saturday, January 04, 2014 12:56 PM
> To: cfrg@irtf.org
> Subject: [Cfrg] Hashing to EC group elements
> 
> For any odd-characteristic elliptic curve with a rational point of
> order 2, the ‘Elligator 2’ injective map described in
> <http://elligator.cr.yp.to/elligator-20130828.pdf> can be used to map
> an element of the coordinate field to a point on the curve.

Interesting.

> 
> If a curve in short-Weierstrass form (y^2 = x^3 + ax + b) has no
> rational points of order 2, then x^3 + ax + b is irreducible and the
> curve has full 2-torsion over the degree-3 extension of its coordinate
> field.  It's straightforward to modify the Elligator 2 formulas to map
> to a curve in short-Weierstrass form *given the x coordinate of a point
> of order 2*; once one has hashed to a point P over the extension field,
> P + f(P) + f(f(P)) (where f is the Frobenius automorphism of the
> extension field holding the base field fixed) is a point over the base
> field.  (If the input to the Elligator map is in the base field, an
> equivalent formulation is to use the Elligator 2 formulas with each of
> the three 2-torsion points, and add the resulting points.)
May seem easy to you ... could you help to provide more explicit formulas.
For example, for x1 and y1 below ...

def elligator(curve, element):
    """ Maps an arbitrary element to a point on the curve """
    assert 0 < element < curve.p  # p is prime order of curve
    assert curve.type = 'smallWeirstrass'
  
    x1 = 
    y1 = 
    return curve.point(x1,x2)



Paul



> 
> Robert Ransom
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg