0
$\begingroup$

In elliptic curves, a private key is just a random number, and one relatively small compared to other crypto systems (256 bits for ECC vs 4096 bits for RSA for example).

Suppose I don't trust hardware random number generators (electronic ones) and I want an auditable way to generate a private key. For elliptic curves, it's feasible to flip a coin 256 times and annotate the results to form a 256 bits random number. You can switch that by an n-sided dice to speed up the process.

Now, for RSA, the key is not just simply a random number. It's a product of two random primes. I don't know the details of how these random primes are found. Are them generated by a random number? If so, how long is this number?

If this number is still long, do you know a feasible way to generate a 4096 bits RSA key manually?

PS: I know it'd take years to do the public key math manually from the private key in both cases. I just want to manually generate the key (in the case of ECC) or key seed (in the case of RSA), so I can plug into 2 completely different air gapped computers and see if the public keys match, which would be a very good signal.

$\endgroup$
  • $\begingroup$ The "standard" way to generate an $n$ bit RSA key is to generate $\frac{n}{2}$ random bits, interpret them as an integer and check for primality. Once you have two prime integers you can generate the rest of the key pretty easily manually. From the prime number theorem we can say that, using coin flips for randomness, the amount of coin flips you'll need to generate an $n$ bit RSA key is $\mathcal{O}(2n*\mathrm{log}(\frac{n}{2}))$. $\endgroup$ – puzzlepalace Apr 21 '18 at 7:31
  • $\begingroup$ @puzzlepalace so it's not feasible with coin flips. Maybe if we raise n on the n-sided dice it becomes possible. $\endgroup$ – Guerlando OCs Apr 21 '18 at 8:01
3
$\begingroup$

You can pick a 1024-bit prime more or less uniformly at random by flipping only 256 coins. But there's additional computational cost to it. Here's a naive algorithm that is deterministic after the initial coin flips:

  1. Flip 256 coins, yielding a bit string $s$.
  2. Compute $p_0 = \operatorname{SHAKE128-1024}(s) \mathbin| 1$ and interpret it as an integer in little-endian bit order. (The $\cdots \mathbin| 1$ forces it to be odd, saving you the wasted effort of testing a large even number for primality.)
  3. Compute a primality certificate for $p_0$, such as a Pratt certificate (which requires computing the prime factorization of $p_0 - 1$) or a Pocklington–Lehmer certificate (which requires computing half the prime factorization of $p_0 - 1$, up to a composite factor below $\sqrt{p_0 - 1}$) or an Atkin–Goldwasser–Kilian–Morain elliptic curve primality proof certificate (which requires a ~512-bit prime, and doing some arithmetic on an elliptic curve).
  4. If it turns out that $p_0$ is composite, then try again with $p_1 = p_0 \pm 2$, and so on. If you hit $2^{1024}$ or $2^{1023}$, you probably made a mistake.

Generating an RSA key. You can use the same 256-bit seed $s$ to pick both prime factors $p$ and $q$ of an RSA modulus $n$, e.g. by splitting the output of $\operatorname{SHAKE128-2048}(s)$ into two 1024-bit integers $p_0$ and $q_0$ instead of step (2). You will also want to try again with the next candidate if you get $\gcd(e, \operatorname{lcm}(p - 1, q - 1)) \ne 1$, where $e$ is your favorite exponent, which ought to be 3 or 65537 unless you have eclectic taste in exponents.

Efficiency. There are variations on the theme: you can use trial division to save some work, for instance, or use a fancier faster sequence of trials at small cost to uniformity of the distribution (but be careful or else you might have a billion-euro mistake on your hands).

Obviously, step (3) costs a lot more computation than generating an elliptic-curve scalar uniformly at random, even if you do the rejection sampling necessary to avoid the (negligible) modulo bias. What's the exchange rate between computation and coin flips?

You can save a lot of computation by doing a fast probabilistic primality test first, like 128 independent Rabin tests, which gives reasonably high confidence that you found a prime, but this costs a lot more coin flips.

If you believe in the extended Riemann hypothesis, you could even avoid the additional coin flips and use a deterministic variant, the Miller test (paywall-free), which is named after the person who first republished the novel result of Russian mathematician М.М. Артюхов in English. It might even perform better than finding an ECPP certificate.

Choice of prime vs. primality testing. All this will take quite a lot of effort with the computational power of pen and paper. But you could write a computer program to do everything past the coin flips in step (1), and feed that computer program the outcomes of your coin flips. Even if it uses a probabilistic primality test, the choice of the prime will be (unless the primality test goes haywire) a deterministic function of the coin flip outcomes.

With a primality certificate, as a bonus you get a verifiable proof that it is prime, which you can independently verify in case a god with a cosmic ray gun angry at your computational arrogance decided to disrupt your faster-than-pen-and-paper computer.

(You might want to keep the certificate secret too.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.