Re: [Cfrg] ECC mod 8^91+5

David Jacobson <dmjacobson@sbcglobal.net> Wed, 17 May 2017 04:28 UTC

Return-Path: <dmjacobson@sbcglobal.net>
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 5317F12F547 for <cfrg@ietfa.amsl.com>; Tue, 16 May 2017 21:28:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Level:
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=sbcglobal.net
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 8vvQAd5Jlm13 for <cfrg@ietfa.amsl.com>; Tue, 16 May 2017 21:28:43 -0700 (PDT)
Received: from nm18-vm1.access.bullet.mail.gq1.yahoo.com (nm18-vm1.access.bullet.mail.gq1.yahoo.com [216.39.63.16]) (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 548A312EBBA for <cfrg@irtf.org>; Tue, 16 May 2017 21:25:31 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s2048; t=1494995129; bh=bEHzVgvpVKXM4oNVZ7A/G8D7oU5aXI5b2LTq8DJ38PY=; h=Subject:To:References:From:Date:In-Reply-To:From:Subject; b=Q3OKpsulm0tgVuvj1BQViyoo7l59t2LPqRnwKnLdsKCN2chlMSzO4ZY4Fn1WVJxoEnOmmbVzl9YSqLLEsvyIA1UiuUeQX/DRSuXjbXyjgUMG7p7LsmhMqJwKds+Ci8Py4Qg8ENImz+8BxnsEnmxhdi7W9FR5T7Knk3P2+TWjfP/04xX1/ELuZXT5edgEpNlG+BCQAqzbkfxV4Q5mMsKdciuIw8AChxfhtAyxztjNrj+F6zEerrwWQ9CN29IV+f+FDmR4nOYGgSOKwidsSzIb2ANGVZw2HzjG99k9aTXR1CLMb7cvB0WwZviD0u34aA+/yzltKMNDh0sPOc8IaJAQXQ==
Received: from [216.39.60.171] by nm18.access.bullet.mail.gq1.yahoo.com with NNFMP; 17 May 2017 04:25:29 -0000
Received: from [98.138.104.100] by tm7.access.bullet.mail.gq1.yahoo.com with NNFMP; 17 May 2017 04:25:29 -0000
Received: from [127.0.0.1] by smtp120.sbc.mail.ne1.yahoo.com with NNFMP; 17 May 2017 04:25:29 -0000
X-Yahoo-Newman-Id: 810081.19752.bm@smtp120.sbc.mail.ne1.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: 77rw7hcVM1nOiCxqyj1Lvuh63.Yoehh2jg1TA7t.8eXPUll VEcYLYCHM9IcNjY0RKGWWzFU_hzY2.H2cHskBbuM62q0S2XBbOvSqBXoN1fi lH2RKk2sP4rdyJhvgbjS5AovPmebydp1BJwtEWVQT9rc8RNTTTtljiBeIdkU DX9pXnSs2.9Xk1GKbdvMQNyewMML39NvCah.kqNyKKEwDPmrAp43xiAgdg2S ITVINRk41n4aSJ5StbipgsqxLUOhDP5TytRVl6Xdc7KqS0RmCeUb3mwaiRo9 NqOCye2cJx6Nddat_IuJrnGNTSMVOPNA.ZDrHiD2N77OP09lvfse2LNT1Z6z 0LtoovGaGEQN9vAYpPs.QFD2Yz4v9u2fcj0cXn67YCQtBzAkc..xszLBUhK4 r6th9Q7sIh3n8R.qxBDP7jE6KK9EfoVLYpM.4KyMnILaRB3MYyud5Tmf2yKs 8pWKKLeUEhaFLom5FykNaJpR0zQy3Y8ahMB6nsVpeO18CO4pf8E.URJ3xIXK k6pqnGz3umVHthh407QLebFh5IS1GvuJoqkEJ.9rxlwkzpSqfWEBgU7yg.Wd TlT1WUiw-
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
To: Dan Brown <danibrown@blackberry.com>, "cfrg@irtf.org" <cfrg@irtf.org>
References: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net>
From: David Jacobson <dmjacobson@sbcglobal.net>
Message-ID: <73cec152-916a-a29f-0daa-dba70c43a7ba@sbcglobal.net>
Date: Tue, 16 May 2017 21:25:27 -0700
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:45.0) Gecko/20100101 Thunderbird/45.8.0
MIME-Version: 1.0
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/UzPbypeTJJsXo7OpNZ2O9uOFtJg>
Subject: Re: [Cfrg] ECC mod 8^91+5
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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: Wed, 17 May 2017 04:28:45 -0000

8^91+5 is provably prime.

In Mathematica I loaded the PrimalityProving module, and checked whether 
8^91+5 was prime, and got True, along with a "Certificate" that is about 
2 pages long.  I don't know the math of certificates, but if anyone in 
interested I can post the certificate.

     --David

On 5/16/17 10:35 AM, Dan Brown wrote:
> Hi all,
>
> I'm considering writing an I-D on doing ECC over the field of size
>     8^91+5    (=2^273+5),
> because it:
> - is written in just 6 symbols (=low Kolmogorov complexity, heuristically minimizing threat of NOBUS-trapdoor),
> - has easy and fast inversion, Legendre symbols, and square roots,
> - has efficient arithmetic using at most five 64-bit words (use base 2^55),
> - is at least 2^(256-epsilon),
> - is (probably) prime, so not an extension field (has no subfields for descent-type attacks on ECDLP).
> Other fields can improve on some of these properties, but might worsen the others.
>
> For ECC with this field, I am also considering the special curve
>     2y^2=x^3+x,
> because it:
> - is written in just 10 symbols (similar gains to 6-symbol field),
> - has Montgomery form (and easily converts to Weierstrass),
> - has efficient endomorphism (so it is a GLV curve),
> - is similar to curves already suggested by Miller in 1985 (well-aged),
> - is similar to sect256k1 already used in bitcoin (incentivized),
> - has an small enough cofactor 72 (over field size 8^91+5),
> - avoids the main ECDLP attacks: Pohlig-Hellman, Menezes-Okamoto-Vanstone, etc.,
> - is similar to the special curves of Koblitz-Menezes [ia.cr/2008/390, Sec 11.1, Example 5] resisting a speculative attack.
> The motivation for this special curve largely matches the motivation for the special field.
>
> The curve's risks are at least:
> - CM (endomorphism) makes it potentially weak (after 32 years of being safe) (note exactly opposing Koblitz-Menezes rationale),
> - its small coefficients are weak for some unpublished reason (continuing trend of weak small-coefficients, y^2=x^3 (singular), supersingular, etc. being weak),
> - weak twist order (so, it requires a static ECDH Montgomery ladder to use public key validation),
> - weak Cheon resistance (but this is an attack with many queries, much computation, and faulty or no KDF).
> - den Boer or Maurer-Wolf reductions are not tight as possible, so perhaps it has a big gap between DHP and DLP
> Other curves (over this field) can reduce these risks, but may also lose some of the benefits.
>
> Overall, E(GF(8^91+5)):2y^2=x^3+x might offer competitive efficiency with fairly reasonable security (for 128-bit symmetric keys). It is only an incremental change over other standard ECC curves, not anything too radical.
>
> I'd be happy to hear what CFRG thinks, or if the CFRG would welcome such an I-D as a CFRG work item.  I hope to have this topic presented briefly at an upcoming CFRG meeting.
>
> Best regards,
>
> Dan Brown
>
>
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>