How to generate random 64-bit value as decimal str

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

Answer 1

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);

Answer 2

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.

Answer 3

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().