[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