Reversible scrambling of integers in Python

Origin

case 1

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.

Case 2

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.

solution

Borrow the wisdom of great ancestors

Reversible scrambling of integers --C Sharpens you up

Implement a function to convert numbers in Python

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

Implement in Python a function to get the conversion key and its reciprocal

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

Operation check

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

important point

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