In a certain service, user IDs are numbered sequentially with integers, and when showing the user ID to the user, if it is shown to the user as it is, the number of users will be predicted. Therefore, we want to convert the user ID to another integer and show the value to the user.
When publishing a serial key consisting only of integers in a magazine etc., I want to generate a serial key at random, but as the number increases, a large amount of resources are consumed by duplicate check. Therefore, we want to reversibly convert a serial number integer to another integer and use that value as the serial key.
Reversible scrambling of integers --C Sharpens you up
Borrowing the wisdom of our predecessors, we implement a bijective conversion function in Python.
scramble.py
def scramble(number, salt, inverse_salt):
"""
Convert numbers to each other.
:param int number:Integer to convert
:param int salt:Integer that is the key to conversion
:param int inverse_salt:2 of integers that are the key to conversion^Reciprocal modulo 32
:return:Integer after conversion
"""
_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
I didn't know how to calculate the reciprocal easily, so when I consulted with @melponn via in-house chat, the following article was introduced. Modular multiplicative inverse function in Python - Stack Overflow
The conversion key is randomly determined, and its reciprocal is calculated by the extended Euclidean algorithm.
generate.py
import random
class InverseDoesNotExist(Exception):
pass
def generate_salt():
"""
Salt and inverse used in scramble_Generate 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
When using it with a serial code of a magazine, consider the following.
--Do not issue 2 ^ 32 to avoid serial numbers --Mix CRC values and perform another reversible conversion
Recommended Posts