How do we pick random elements in cryptography?

Question

While reading papers on cryptography, a lot of time I have seen that people pick random elements $x\in \mathbb{Z}^*_q$ to do something (like setting secret key and all). How does one randomly pick elements in reality. I mean in practical implementation, what procedure do we follow? Do we use some CSPRNG?

Answer 1

In practice, in order to pick a uniformly random $x\in \mathbb{Z}^*_q$, we reduce that task to the problem of picking uniformly random and independent bits. On a modern computer system, there will be some operating system service supplying such bits, e.g. /dev/urandom on many Unix derivatives (we'll get back to the problem of how such bits have been obtained in the second section).

The simplest method to pick a uniformly random $x\in \mathbb{Z}^*_q$, that is an integer in $[0,q)$, sometime called rejection sampling, goes:

1. As a preliminary performed once no matter how many $x$ we want to generate: as a (deterministic) function of $q$, choose some $k$ with $2^k\ge q$, e.g. $k$ a little over the number of bits in the binary expression of $q$.
2. Draw $k$ uniformly random and independent bits $b_i$, for $0\le i<k$
3. Assemble the $k$ bits into integer $y=\sum b_i\,2^i$
4. If $y<(2^k\bmod q)$, proceed at 2.
5. Compute and output $x=y\bmod q$.

The probability that $x$ is any particular integer in $[0,q)$ is exactly $1/q$ under the hypothesis the bits $b_i$ are uniformly random and independent.

Common variations:

• Producing the bits $b_i$ grouped in a computer word, and/or $k$ forced to be a multiple of some words size.
• Big endianness at 2: $y=\sum b_i\,2^{k-i-1}$; this also allows $y$ to be built as we draw the $b_i$ as $y_0=0$, $y_{i+1}=y_i+y_i+b_i$ for $0\le i<k$, $y=y_k$.
• Different test condition at 4, e.g. $y\ge2^k-(2^k\bmod q)$.

We can also remove step 4 (in which case the method is no longer rejection sampling). Unless $q$ is a power of two, this leaves integers in $[0,2^k\bmod q)$ more likely than those in $[(2^k\bmod q), q)$, with probability $\lceil 2^k/q\rceil/2^k$ rather than $\lfloor 2^k/q\rfloor/2^k$. But if $k$ is suitably larger than the number of bits in $q$ (say, $k\>\lceil\log_2 q\rceil+64$ ), or/and if $\min(2^k\bmod q,-2^k\bmod q)/q$ is smaller than some suitable limit (e.g. $2^{-128}$ ), then this bias is experimentally undetectable.

(There are better characterizations of when we can remove step 4, and more complex methods to minimize the number of $b_i$ generated when making many $x$, but their use is uncommon).

---

We are back to the problem of picking uniformly random and independent bits, or perhaps computer words consisting of such bits.

Recommendable methods all use the same broad principle: source(s) of imperfect randomness are post-processed into bits hopefully indistinguishable (indeally, including for arbitrarily powerful adversaries; or as a fallback, computably) from the desired uniformly random and independent bits.

Example sources:

• Inputs including keystrokes, mouse position, microphone, camera input.
• Time when keystrokes occur, mouse position changes, disk blocks or Ethernet/Wifi/Bluetooth/USB packet reaches the motherboard, measured e.g. in clock cycles since computer started
• A dedicated device. One method compares the instantaneous voltage across a Zener diode to it's mean, and samples the outcome at regular intervals. Another samples an hopefully chaotic oscillator using another hopefully independent one.

A lot of effort should go into surveillance of the source(s), to ensure it/they operate properly (or if we combine several, to estimate a minimum entropy we can be confident they collectively deliver).

One of the most simple effective postprocessing mean is hashing: a number of bits from the source(s) are hashed, and the outcome (or a portion thereof) form the conditioned output. That's secure for a hash computationally indistinguishable from a random oracle (for the input length used), and a large enough (min-)entropy of the hash input.

If we need many random bits, we can make them at low cost by seeding a Cryptographically Secure Pseudo Random number Generator with randomness obtained as in the last paragraph. However, if the state of the CSPRNG is compromised (e.g. by side channels), all it's output is. For this reason there are more elaborate methods to obtain highly secure random bits at high rate, in a way that recovers nicely from compromise of their internal state.

Addition: on modern CPUs, there often is an on-die source (that was sometime in the chipset). Often, it's output is not accessible in a well-documented way. Excuses for that are that people would use it directly, or/and brag about detecting some bias in it even though that's expected. The programmer is supposed to use a mysteriously conditioned output thru some instruction (e.g. RDRAND). How the source's health is monitored is often left poorly documented, and/or not supportedin the software/OS. Other possible issues with CPU-based RNGs include poorly protecting the confidentiality of their output, see e.g. this. Draw (pun intended) your own conclusions about if they should be trusted as the sole source or randomness in crypto.