発端

ケース1

とあるサービスで, ユーザ ID を整数の連番で採番しており, ユーザにユーザ ID を見せる際, そのままユーザに見せてしまうと, ユーザ数が予測されてしまう.
そこで, ユーザ ID を別の整数に可逆変換し, その値をユーザに見せたい.

ケース2

雑誌などに, 整数のみで構成されたシリアルキーを掲載する際, ランダムでシリアルキーを生成したいが, 件数が増えると重複チェックで大量にリソースを消費する.
そこで連番の整数を別の整数に可逆変換し, その値をシリアルキーとしたい.

解決策

偉大な先人の知恵を借りる

整数を可逆スクランブルする - C Sharpens you up

数値を変換する関数を Python で実装

先人の知恵を拝借し, 全単射な変換関数を Python で実装する.

scramble.py

def scramble(number, salt, inverse_salt):

    """
    数値を相互変換する.

    :param int number: 変換する整数
    :param int salt: 変換のキーとなる整数
    :param int inverse_salt: 変換のキーとなる整数の 2^32 を法とする逆数
    :return: 変換後の整数
    """

    _assert_number(number)
    _assert_salt(salt, inverse_salt)
    return _trim32bit(_reverse32bit(_trim32bit(number * salt)) * inverse_salt)


def _assert_number(number):
    assert 1 <= number <= 0xFFFFFFFF


def _assert_salt(salt, inverse_salt):
    assert _trim32bit(salt * inverse_salt) == 1


def _reverse32bit(number):
    number = ((number >> 1) & 0x55555555) | ((number & 0x55555555) << 1)
    number = ((number >> 2) & 0x33333333) | ((number & 0x33333333) << 2)
    number = ((number >> 4) & 0x0F0F0F0F) | ((number & 0x0F0F0F0F) << 4)
    number = ((number >> 8) & 0x00FF00FF) | ((number & 0x00FF00FF) << 8)
    number = (number >> 16) | (number << 16)
    return number


def _trim32bit(number):
    return number & 0xFFFFFFFF

変換キーと, その逆数を得る関数を Python で実装

逆数の簡単な算出方法が判らず, 社内チャットで @melponn に相談したら, 次の記事を紹介された.
Modular multiplicative inverse function in Python - Stack Overflow

変換キーはランダムで決定し, その逆数を拡張ユークリッド互除法で算出する.

generate.py

import random


class InverseDoesNotExist(Exception):
    pass


def generate_salt():

    """
    scramble で使用する salt と inverse_salt を生成する.

    :return: salt, inverse_salt
    """

    salt = _gen_salt()
    return salt, _modinv(salt, 0x100000000)


def _gen_salt():
    salt = random.randint(3, 0xFFFFFFFF)
    if salt % 2 == 0:
        salt += 1
    return salt


def _egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = _egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def _modinv(a, m):
    g, x, y = _egcd(a, m)
    if g != 1:
        raise InverseDoesNotExist()
    else:
        return x % m

動作確認

test.py

salt, inverse_salt = generate_salt()

def f(number):
    return scramble(number, salt, inverse_salt)

for n in xrange(1, 0xFFFFFFFF):
    assert f(f(n)) == n

注意点

雑誌のシリアルコードなどで使用する場合, 下記を考慮すること.

連番を避けるため, 2^32 個発行しない
CRC 値を混ぜ, もう一段, 別の可逆変換を行う

Python で整数を可逆スクランブルする

発端