[Cryptography] Need a list of Solinas/pseudo Mersene Primes.

[Phillip Hallam-Baker]

On Thu, Aug 30, 2018 at 11:39 AM Phillip Hallam-Baker <phill at hallambaker.com>
wrote:

> I am using Shamir secret sharing as a recovery mechanism for private keys
> and would like to extend this to recover quantum resistant keys. As a
> result, I need a nice round prime greater than 2^256.
>
> Finding a nice round prime smaller than 2^256 is easy, 2^255-2^19-1. But I
> need 2^256-x. I was looking for lists of Solinas primes but can't find one
> with what I need.
>
> Anyone got a pointer?
>

Thanks to everyone who responded. I could have spent the time to learn the
tools but that would be pointless as I would have never trusted my result.

The answer from three sources is 2^257-93

The way that I drafted the spec, it requires the number of bits to be a
multiple of 8 and the prime to be the largest prime that is smaller than
the next power of two. Thus, folk can apply the spec to secrets of any
length without re-writing the spec.

I am considering changing this to require the number of bits to be a
multiple of 32 and giving the primes for use with up to 512 bits.


The reason for this change is my strategy for introducing an XMSS key into
the scheme to provide a bridge to a QRC world. The basic idea is that the
user creates a master secret of at least 256 bits and then uses that and a
HKDF to generate an XMSS tree that can be used to sign at least 16
messages. That should be enough to make a bootstrap possible. They then
calculate the corresponding public key and put the fingerprint of that
public key in their Mesh profile.

The design choice I am now having to make is whether to put the XMSS
parameters in the secret record or the profile. I will probably need to
implement the spec first before I decide.

Like the second card slot on the Z7, I do not expect anyone will ever
seriously need the Quantum Recovery stuff. My experience of the particle
physics field suggests to me that keeping a machine running for the time it
would take to factor Ed448 or RSA2048 is prohibitive. But like the second
slot, considering these possibilities is something that we absolutely had
to do if a proposal isn't going to get pecked to death. [If you are not
following slotgate, see my podcast later on.]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180831/442bd088/attachment.html>