How to generate random 64-bit value as decimal string in PHP

Question

Oauth requires a random 64-bit, unsigned number encoded as an ASCII string in decimal format. Can you guys help me achieve this with php? Thanks

Acerb

Answer 1

You could use two 32-bit numbers, four 16-bit numbers, etc.

PHP has rand() and and mt_rand() but how many random bits they supply isn't specified by the standard (though they can be queried with the help of getrandmax() and mt_getrandmax(), respectively.)

So your safest simplest bet would be generating 64 random bits and setting them one by one.

As for working with 64-bit integers, I'd recommend using the GMP library as it has a good range of functions to help you out.

You could create a number, call 64 gmp_setbit()s on it with successive positions then convert it to a string using gmp_strval().

Configuration

Answer 2

This was a really interesting problem (how to create the decimal representation of an arbitrary-length random number in PHP, using no optional extensions). Here's the solution:

Step 1: arbitrary-length random number

// Counts how many bits are needed to represent $value
function count_bits($value) {
    for($count = 0; $value != 0; $value >>= 1) {
        ++$count;
    }
    return $count;
}

// Returns a base16 random string of at least $bits bits
// Actual bits returned will be a multiple of 4 (1 hex digit)
function random_bits($bits) {
    $result = '';
    $accumulated_bits = 0;
    $total_bits = count_bits(mt_getrandmax());
    $usable_bits = intval($total_bits / 8) * 8;

    while ($accumulated_bits < $bits) {
        $bits_to_add = min($total_bits - $usable_bits, $bits - $accumulated_bits);
        if ($bits_to_add % 4 != 0) {
            // add bits in whole increments of 4
            $bits_to_add += 4 - $bits_to_add % 4;
        }

        // isolate leftmost $bits_to_add from mt_rand() result
        $more_bits = mt_rand() & ((1 << $bits_to_add) - 1);

        // format as hex (this will be safe)
        $format_string = '%0'.($bits_to_add / 4).'x';
        $result .= sprintf($format_string, $more_bits);
        $accumulated_bits += $bits_to_add;
    }

    return $result;
}

At this point, calling random_bits(2048) will give you 2048 random bits as a hex-encoded string, no problem.

Step 2: arbitrary-precision base conversion

Math is hard, so here's the code:

function base_convert_arbitrary($number, $fromBase, $toBase) {
    $digits = '0123456789abcdefghijklmnopqrstuvwxyz';
    $length = strlen($number);
    $result = '';

    $nibbles = array();
    for ($i = 0; $i < $length; ++$i) {
        $nibbles[$i] = strpos($digits, $number[$i]);
    }

    do {
        $value = 0;
        $newlen = 0;
        for ($i = 0; $i < $length; ++$i) {
            $value = $value * $fromBase + $nibbles[$i];
            if ($value >= $toBase) {
                $nibbles[$newlen++] = (int)($value / $toBase);
                $value %= $toBase;
            }
            else if ($newlen > 0) {
                $nibbles[$newlen++] = 0;
            }
        }
        $length = $newlen;
        $result = $digits[$value].$result;
    }
    while ($newlen != 0);
    return $result;
}

This function will work as advertised, for example try base_convert_arbitrary('ffffffffffffffff', 16, 10) == '18446744073709551615' and base_convert_arbitrary('10000000000000000', 16, 10) == '18446744073709551616'.

Putting it together

echo base_convert_arbitrary(random_bits(64), 16, 10);

Norge

+1 for the mind-blowingness of even thinking of doing that in PHP. Keep in mind that count_bits won't be able to deal with numbers larger than PHP_INT_MAX. – Ramah

@Charles: Thanks for the vote. count_bits is indeed limited, but as we 're only going to use it to measure the return value of mt_getrandmax it's adequate for the job. – Norge

Very adequate considering that mt_getrandmax usually seems to be 2^31-1 even on 64-bit platforms. – Ramah

Just FYI: sometimes number respresentation can contain leading zeros (i.e., result of hash() function), and this function obviously can't restore them after converting. So if nab = convert(n, a, b) it can be that n !== convert(nab, b, a). Be careful. – Heartburning

Interesting function base_convert_arbitrary. But why all the alphabets? Doesn't $value = $value * $fromBase + $nibbles[$i]; ensure that the operation can only be valid for base 2 to 16? – Propagandist

Interesting, I just noticed what nibbles actually has is strpos not substr. I'm still confused however at ($value >= $toBase) { $nibbles[$newlen++] = (int)($value / $toBase); $value %= $toBase; }, what exactly is happening here? Comments would be well appreciated. – Propagandist

Answer 3

Are you building an OAuth adapter yourself? If so, you might want to reconsider. There are plenty of good OAuth libraries out there, including one from PECL, one in PEAR, another from the Zend Framework, and this other one hosted on Google Code. I've worked with the first three, and they're all pretty decent.

If you really want to do this yourself, you may face an issue. PHP can't think in 64-bit numbers unless it's compiled on a 64-bit platform or you have an advanced mathematics extension installed. This is going to make presenting a 64-bit number as a decimal very difficult. It looks like many of the libraries I linked above completely ignore the format requirement and simply work with a raw MD5 hash. Here's the code from ZF's adapter:

/**
 * Generate nonce
 * 
 * @return string
 */
public function generateNonce()
{
    return md5(uniqid(rand(), true));
}

They look like they're getting away with this without interoperability issues.

Ramah