[Cryptography] What type of nearest prime is most likely to be useful?

Phillip Hallam-Baker phill at hallambaker.com
Thu Aug 6 14:13:15 EDT 2020


A while back, I asked about next prime generation for use with Shamir
secret sharing.

I have since revised my spec after discovering that my previous approach of
rounding up secrets to a multiple of 32 bits was a bad plan. So I now have
a list of offsets that are to be used to deterministically generate a list
of primes p such that:

2^n < p < 2^(n+8)

I am using these for Shamir secret sharing which is information theoretic
secure so there are two obvious choices:

p = Nextprime (2^n)  or   p = PreviousPrime (2^(n+8))

I have generated both tables (attached in case someone feels like
checking). Question is which is the better choice for other applications?

I am inclined to pick  p = Nextprime (2^n) because that results in the
least bias when selecting a random number in the interval 0 <= r < p using
the modulo reduction approach:

Select n+8 bits of randomness, reduce modulo p.

So for an 8 bit value p = 257. Generate a 2^16 bit value and the
probability the result is 0 will be 1/256 and the probability it will be
1-256 will be 1/255. Which is not completely flat but near enough for most
purposes. And we can get the result as flat as we like using n+32 or such.

So what to pick or doesn't it matter?


        public readonly static int[] PrimeOffsetNext = new int[] {
            1,            1,         43,          15,
            15,          21,         81,          13,
            15,          13,          7,          61,
            111,         25,        451,          51,
            85,         175,        253,           7,
            87,         427,         27,         133,
            235,        375,        423,         735,
            357,        115,         81,         297,
            175,         57,         45,         127,
            61,          37,         91,          27,
            15,         241,        231,          55,
            105,        127,        115,         231,
            207,        181,         37,         235,
            163,       1093,        187,         211,
            21,         841,        445,         165,
            777,        583,        133,          75
            };

        public readonly static int[] PrimeOffsetPrevious = new int[] {
            5,           15,          3,           5,
            87,          59,          5,          59,
            93,          65,        299,          17,
            17,          75,        119,         159,
            113,         83,         17,          47,
            257,        233,         33,         237,
            75,         299,        377,          63,
            567,        467,        237,         189,
            275,        237,         47,         167,
            285,         75,        203,         197,
            155,          3,        119,         657,
            719,        315,         57,         317,
            107,        593,       1005,         435,
            389,        299,         33,         203,
            627,        437,        209,          47,
            17,         257,        503,         569
            };
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20200806/ad31c4cb/attachment.htm>


More information about the cryptography mailing list