Re: [Cfrg] Preliminary disclosure on twist security ...

Dan Brown <dbrown@certicom.com> Wed, 26 November 2014 16:50 UTC

Return-Path: <dbrown@certicom.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 163571A014C for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 08:50:03 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.299
X-Spam-Level:
X-Spam-Status: No, score=-1.299 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, J_CHICKENPOX_22=0.6, LOTS_OF_MONEY=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 fBsJYJrcxKl1 for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 08:50:01 -0800 (PST)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id 41DCE1A0143 for <cfrg@irtf.org>; Wed, 26 Nov 2014 08:50:00 -0800 (PST)
Received: from xct106cnc.rim.net ([10.65.161.206]) by mhs210cnc.rim.net with ESMTP/TLS/AES128-SHA; 26 Nov 2014 11:49:56 -0500
Received: from XCT115CNC.rim.net (10.65.161.215) by XCT106CNC.rim.net (10.65.161.206) with Microsoft SMTP Server (TLS) id 14.3.174.1; Wed, 26 Nov 2014 11:49:55 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT115CNC.rim.net ([::1]) with mapi id 14.03.0174.001; Wed, 26 Nov 2014 11:49:54 -0500
From: Dan Brown <dbrown@certicom.com>
To: "'watsonbladd@gmail.com'" <watsonbladd@gmail.com>
Thread-Topic: [Cfrg] Preliminary disclosure on twist security ...
Thread-Index: AdAJieU4Ye2dd7TATPKiXX6WalzfrwAMWVyAAAkAiPA=
Date: Wed, 26 Nov 2014 16:49:54 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5D0742B@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF5D072C5@XMB116CNC.rim.net> <CACsn0ck5vgB5qojL2o38Vb=mt9ZFNres+EVXBsBK=VRjrpwLzw@mail.gmail.com>
In-Reply-To: <CACsn0ck5vgB5qojL2o38Vb=mt9ZFNres+EVXBsBK=VRjrpwLzw@mail.gmail.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_0181_01D0096F.177E5700"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ABJqnm6Z0Y4k9mzaJLYofnq-uZg
Cc: "'cfrg@irtf.org'" <cfrg@irtf.org>, "'djb@cr.yp.to'" <djb@cr.yp.to>
Subject: Re: [Cfrg] Preliminary disclosure on twist security ...
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: Wed, 26 Nov 2014 16:50:03 -0000

> -----Original Message-----
> From: Watson Ladd 
> 
> The patent in question is US6563928.
> 
> The claim cited reads as follows:
> 
> "53. A method of establishing a session key for encryption of data between a
> pair of correspondents comprising the steps of one of said correspondents
> selecting a finite group G, establishing a subgroup S having an order q of the
> group G, determining an element α of the subgroup S to generate greater than
> a predetermined number of the q elements of the subgroup S and utilising said
> element α to generate a session key at said one correspondent."
> 
> "59: 58. A method according to claim 53 wherein said order of said subgroup is
> of the form utilising an integral number of a product of a plurality of large
> primes.
> 59. A method according to claim 58 wherein the order of said subgroup is of
> the form nrr′ where n, r and r′ are each integers and r and r′ are each prime
> numbers."
> 
> This doesn't appear to have anything to do that directly with twist security. 

Well, this is what I was thinking:

Let F_p be the underlying field.

Let E be the twist-secure curve, with size #E(F_p) = hr, where h is a small cofactor and r a large prime.  Its twist E' has size h'r' where h' to the another small cofactor and r' is another large prime.

Now G be the group of F_p^2 rational points, which is a group of size hh'rr', right?  Then let S be the subgroup with of G of size q = rr'.

Let alpha be the element of S used to generate the yet smaller subgroup of size, i.e. the conventional DH prime-order subgroup of E(F_p).  Now alpha generates r elements, which is greater than a predetermined number, e.g. 2^250.

This means putting n =1 in Claim 59.

Best regards,

Dan