D. J. Bernstein

Authenticators and signatures

A state-of-the-art public-key signature system
# The constant c

The constant c is the integer with 309-digit decimal expansion
179870286739608110908793986433779282952709437186980111027634886806680
105430306203504772087724415765187628536569403357866962021859070432575
840490938673081114568020802801572639107433385488013533823889359543365
805739639724297106495248013808227417948954846716576431759705516797612
912096782118234207449553394447817

in the range {2^1024,2^1024+1,...,2^1024+10^306-1}.
## How c was selected

I chose c by adding 306 random digits to 2^1024.
Choosing c at random,
and then choosing pq at random in {2^512 c,...,2^512 c+2^512-1},
has the same effect as choosing pq at random from the wide interval
{2^1536,...,2^1536+2^512 10^306-1}.
It is conjectured, and consistent with all available experiments,
that a uniform distribution of c
produces an almost uniform distribution of pairs (p,q).
Instead of generating my own random digits,
I took the first 306 digits from the RAND tables published in 1955:

10097 32533 76520 13586 34673 54876 80959 09117 39292 74945
37542 04805 64894 74296 24805 24037 20636 10402 00822 91665
08422 68953 19645 09303 23209 02560 15953 34764 35080 33606
99019 02529 09376 70715 38311 31165 88676 74397 04436 27659
12807 99970 80157 36147 64032 36653 98951 16877 12171 76833
66065 74717 34072 76850 36697 36170 65813 39885 11199 29170
31060 1

This selection strategy means that anyone can verify that I didn't cheat.
Of course,
it's conceivable that the creators of the RAND tables cheated
and constrained their digits.
However,
it isn't conceivable that
anyone in 1955 knew so much about factorization and public-key cryptography
to be able to (or want to!)
choose a weak value of c for this application.