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

Recommended Posts

Reversible scrambling of integers in Python
Prime factorization of integers entered in Python ver.1
Prime factorization ver.2 of integers input in Python
Equivalence of objects in Python
Implementation of quicksort in Python
Pixel manipulation of images in Python
Division of timedelta in Python 2.7 series
MySQL-automatic escape of parameters in python
Handling of JSON files in Python
Implementation of life game in Python
Waveform display of audio in Python
Law of large numbers in python
Implementation of original sorting in Python
Conversion of string <-> date (date, datetime) in Python
Check the behavior of destructor in Python
(Bad) practice of using this in Python
General Theory of Relativity in Python: Introduction
Output tree structure of files in Python
Display a list of alphabets in Python 3
Summary of various for statements in Python
Gang of Four (GoF) Patterns in Python
The basics of running NoxPlayer in Python
Bulk replacement of strings in Python arrays
Project Euler # 16 "Sum of Powers" in Python
Traffic Safety-kun: Recognition of traffic signs in Python
Summary of built-in methods in Python list
Non-logical operator usage of or in python
In search of the fastest FizzBuzz in Python
Practical example of Hexagonal Architecture in Python
Project Euler # 17 "Number of Characters" in Python
Double pendulum equation of motion in python
Get rid of DICOM images in Python
Status of each Python processing system in 2020
Project Euler # 1 "Multiples of 3 and 5" in Python
Meaning of using DI framework in Python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
Introduction of Python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
Basics of Python ①
Basics of python ①
Plink in Python
Constant in python
Copy of python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python