[Cfrg] Malicious pseudoprimes versus 2y^2=x^3+x/GF(8^91+5)

Dan Brown <danibrown@blackberry.com> Fri, 17 August 2018 18:36 UTC

From: Dan Brown <danibrown@blackberry.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: Malicious pseudoprimes versus 2y^2=x^3+x/GF(8^91+5)
Thread-Index: AdQ2VMdWVX1NUjMzSXiTpolIdEeqpg==
Date: Fri, 17 Aug 2018 18:36:52 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501CBD808@XMB116CNC.rim.net>
Accept-Language: en-US, en-CA
Content-Language: en-US
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="----=_NextPart_000_0176_01D43637.BC0E1E10"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/XU3YyNOo0GnTe3hduV2CSgINnlw>
Subject: [Cfrg] Malicious pseudoprimes versus 2y^2=x^3+x/GF(8^91+5)
Precedence: list

Hi CFRG,

Because the recent report of Albrecht, Massimo, Paterson and Somorovsky (AMPS) 
raised real-world attacks with malicious pseudoprimes https://ia.cr/2018/749 - 
and also mentioned that SageMath (via PARI) resists this attack - I thought it 
appropriate for me to provide a short sage script about the primes in the 
recently proposed elliptic curve 2y^3=x^3+x/GF(8^91+5):

p=8^91+5
E=EllipticCurve(GF(p),[-1,0]) # justifiable since 2y^2=x^3+x isomorphic (over 
GF(p)) to y^2=x^3-x
n=E.cardinality()
proof.arithmetic(True) # default, but just in case
mod(n,72),is_prime(p),is_prime(n//72)  # // needed to get integer division

Output (0,True,True) should indicate success, apparently in terms of provable 
primes (although I'm not sure what SageMath does with the "proof").  This 
requires trusting the code above and SageMath.  However, SageMath is very 
large, so maybe there is a smaller software that can do a similar job (PARI?). 
In any case, some kind of software would be needed ...

I would say a primality proof here is defense in the depth, since the AMPS 
attack seems to require extensive searching, since the malicious pseudoprime 
are rare, etc., and the AMPS attack depends on the vagaries the primality test 
mechanism (IIUC).  So, under a reasonable heuristic assumptions, these 
malicious pseudoprimes are likely have high Kolmogorov complexity, much higher 
than 8^91+5, etc.  Well, at least, that's my main excuse for not trying to run 
provable primality tests before now (real reason, I was too lazy to read the 
manuals on software I already had that could do this for me).

I recall that others on the list mentioned finding primality proofs for 
8^91+5, but I don't recall if provable primality tests were reported for the 
curve order's large prime factor.  So, I seem to have replicated some of the 
previous findings.  Thanks.

For other curves, I presume that previous work has already been done to find 
primality proofs for most other standard curves, so have not bothered to run 
any myself ...

Best regards,

Dan

Attachment: smime.p7s

[Cfrg] Malicious pseudoprimes versus 2y^2=x^3+x/G… Dan Brown

[Cfrg] Malicious pseudoprimes versus 2y^2=x^3+x/GF(8^91+5)

Attachment: smime.p7s