発端
ケース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 値を混ぜ, もう一段, 別の可逆変換を行う