How to generate a cryptographically secure random integer within a given range in PostgreSQL?

57 Views Asked by At

Problem

I want to write a PL/pgSQL function that generates a cryptographically secure random integer within a given range.

Context

Many languages used for the application layer provide a built-in function to generate cryptographically secure random integers, which are useful for generating secrets or codes. For example, Node.js and Python have methods to produce such integers.

However, PostgreSQL does not have a built-in function for this purpose.

Challenges

A proper implementation has to avoid introducing modulo bias to the results. Otherwise, the generated integers may not be uniformly distributed. Some relevant PostgreSQL posts on StackOverflow appear to have solutions that do not account for modulo bias.

Attempt

I based my attempt on the Node.js implementation of its crypto.randomInt function. pgTAP tests for the below function pass, and I plotted the results of 2 million random integers between various ranges to check for modulo bias. However, I want to be cautious in case I overlooked any flaws or mistakes.

Does the below function require any tweaking? It takes two integer inputs, low and high, and returns a random integer in the range [low, high).

CREATE EXTENSION pgcrypto;

CREATE FUNCTION random_int(low INT, high INT)
    RETURNS INT
    LANGUAGE plpgsql
    STRICT
    AS $$
DECLARE
    -- The maximum value of a 4-byte signed integer.
    RAND_MAX INT := 2147483647; 
    rand_range INT;
    rand_limit INT;
    rand_bytes BYTEA;
    x INT;
BEGIN
    IF low >= high THEN
        RAISE EXCEPTION 'Low must be less than high';
    END IF;

    -- The range of random integers that can be generated.
    rand_range := high - low;

    -- The maximum value that can be divided evenly by rand_range.
    rand_limit := RAND_MAX - (RAND_MAX % rand_range);

    LOOP
        -- Generate 4 random bytes.
        rand_bytes := gen_random_bytes(4);

        -- Convert the 4 random bytes to a 4-byte signed integer, masking the sign bit to ensure a positive integer.
        -- 127 is '01111111' in binary, so the bitwise AND operation drops the sign bit from the first byte.
        x := ((get_byte(rand_bytes, 0) & 127) << 24)
            | (get_byte(rand_bytes, 1) << 16)
            | (get_byte(rand_bytes, 2) << 8)
            | get_byte(rand_bytes, 3);

        -- Accept the random integer if it is less than rand_limit to avoid modulo bias.
        -- We accept up to, but not including, rand_limit, to ensure x % rand_range is evenly distributed.
        -- For any x >= rand_limit, x % rand_range will be biased.
        -- Consider the contrived example where rand_range = 5, RAND_MAX = 12, and rand_limit = 12 - (12 % 5) = 10.
        -- x             : | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10       | 11        | 12       |
        -- x % rand_range: | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 0 (bias) | 1  (bias) | 2 (bias) |
        -- The numbers 0, 1, and 2 are more likely to be generated than 3 and 4.
        -- To avoid this bias, we only accept x < rand_limit
        -- x             : | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
        -- x % rand_range: | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 |
        -- Adding low to the result ensures the random integer is in the range [low, high).
        IF x < rand_limit THEN
            RETURN (x % rand_range) + low;
        END IF;
    END LOOP;

    -- If rand_range exceeds what can be represented by a 4-byte signed integer, PostgreSQL will raise an integer out of range error.
    -- Catch this error and raise a more informative exception.
    EXCEPTION WHEN numeric_value_out_of_range THEN
        RAISE EXCEPTION 'The difference between high and low cannot exceed the maximum value of a 4-byte signed integer';
END;
$$;

Results

SELECT random_int(1, 4);

-- Returns a random integer in the range [1, 4)
SELECT random_int(-4, 1);

-- Returns a random integer in the range [-4, 1)
SELECT random_int(-2, 2);

-- Returns a random integer in the range [-2, 2)
SELECT random_int(0, 2147483647);

-- Returns a random integer in the range [0, 2147483647)
SELECT random_int(-1, 2147483647);

-- Raises an exception
-- (high - low) > the maximum value for a 4-byte signed integer
0

There are 0 best solutions below