将数字ID转换为短的不同字母数字代码的算法

Question

将数字ID转换为短的不同字母数字代码的算法

pythondatabaseencryptionhashprimary-key

3

我有一个数据库中的ID，我希望它们短小，并且可以轻松地通过视觉区分（即，两个接近的数字看起来不同）。

像这样：

13892359163211 -> ALO2WE7 13992351216421 -> 52NBEK3

或类似的算法。所以就像哈希一样，但需要可逆？像AES这样的加密算法几乎是理想的，但其输出太长了（过度设计）。

我正在使用Python（3），尽管我认为这并不重要。

- retnikt

1

为什么要踩？“这个问题没有展示任何研究努力；它不清楚或者没有用”。非常清晰有用，而且我已经做了研究（见：AES和哈希）。 - retnikt

1

让它们变得更短需要右侧比仅有A-Z0-9更大的字母表。 - President James K. Polk

旁注，这并不是我的问题的答案，而是另一种方法：您可以简单地生成随机字符串并将它们附加到数据库中的行/文档。 - retnikt

那很好，但是你仍需要使用一种不会产生重复的随机技术。 - President James K. Polk

5个回答

2

这个问题很容易陈述，但要解决它却并不容易。其中一种解决方法是借鉴格式保留加密的一些思想，并简化它们，因为安全性不是目标。使用Feistel密码框架可以编写一个非常短且可逆的“混合”函数，然后是一个短的编码函数，从而实现看起来符合您要求的功能。

import hashlib
import string

mask = (1 << 22) - 1
alphabet = string.ascii_uppercase + string.digits


def func(x: int):
    return int.from_bytes(hashlib.sha256(x.to_bytes(3, 'big')).digest(), 'big') & mask


def mix(id_in: int):
    L, R = id_in >> 22, id_in & mask
    L ^= func(R)
    R ^= func(L)
    return (L << 22) | R


def unmix(mixed: int):
    L, R = mixed >> 22, mixed & mask
    R ^= func(L)
    L ^= func(R)
    return (L << 22) | R


def base_n_encode(value: int):
    digits = []
    for i in range(9):
        value, rem = divmod(value, len(alphabet))
        digits.insert(0, rem)
    return ''.join(alphabet[digit] for digit in digits)


def base_n_decode(encoded: str):
    digits = [alphabet.index(ch) for ch in encoded]
    result = 0
    for digit in digits:
        result = result * len(alphabet) + digit
    return result


def encode(id_in: int):
    return base_n_encode(mix(id_in))


def decode(encoded: str):
    return unmix(base_n_decode(encoded))


if __name__ == '__main__':
    e1 = encode(13892359163211)
    e2 = encode(13992351216421)
    print('13892359163211 -> ' + e1)
    print('13992351216421 -> ' + e2)
    print(e1 + ' -> ' + str(decode(e1)))
    print(e2 + ' -> ' + str(decode(e2)))

输出结果为：

13892359163211 -> BC33VXN8A
13992351216421 -> D1UOW6SLL
BC33VXN8A -> 13892359163211
D1UOW6SLL -> 13992351216421

请注意sha256的使用。这很慢，绝对是过度设计，但它的优点是内置于python中，因此只需要一行代码。除非您要转换数百万个ID，否则速度不应该是问题，但如果是，您可以将func替换为更快的东西，比如Murmur3。

该代码使用硬编码常量编写，以使其更容易看到正在发生的事情，但它可以通用化以处理任意长度（以位为单位）的ID和任意字母表。

这个例子的更通用版本可在GitHub上找到。

- President James K. Polk

1

要不要尝试为输入查找crc32并以十六进制形式显示结果呢？

>>> n = 13892359163211
>>> 
>>> import binascii
>>> hex(binascii.crc32(str(n).encode()))[2:]
'240a831a'

- Prem Anand

CRC32仅适用于小于4字节的值（作为int的4294967296或字符串的9999（您的方法）是如此）。这对于长数据库ID来说过于小了。如果有一个理论上的CRC128，它的输出将会太长。 - retnikt

0

您可以使用CrypII的思路将整数转换为base64编码。这是最短的方法。

13892359163211 对应的base64编码是 4LWL
13992351216421 对应的base64编码是 64yl

- kelalaka

0

将数字ID转换为二进制形式（3），并使用编码器（4、5）。

In [1]: import struct, base64

In [2]: i = 13892359163211
Out[2]: 13892359163211

In [3]: struct.pack('L', i)
Out[3]: b'K\r"\x91\xa2\x0c\x00\x00'

In [4]: base64.b85encode(struct.pack('L', i)).decode('ascii')
Out[4]: 'OAR8Cq6`24'

In [5]: base64.b64encode(struct.pack('L', i)).decode('ascii')[:-1]
Out[5]: 'Sw0ikaIMAAA'

使用哪种编码器取决于您想允许哪些字符。

- Roland Smith

这也解决不了问题！！！长度需要固定，并且不同的ID需要有实质性的差异！ - retnikt

长度是固定的，因为转换为8字节二进制。我能想到的唯一会产生“显著不同”结果的算法是哈希函数... - Roland Smith

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nitzel · Accepted Answer

“关闭” 数字看起来不同的新答案 您可以使用 RSA 加密（和稍后解密）您的数字。这肯定是过度设计的 - 但是...以下是示例：安装 https://github.com/sybrenstuvel/python-rsa（pip install rsa）。

import rsa
import rsa.core
# (pubkey, privkey) = rsa.newkeys(64) # Generate key pair
pubkey = rsa.PublicKey(n=9645943279888986023, e=65537)
privkey = rsa.PrivateKey(n=9645943279888986023, e=65537, d=7507666207464026273, p=9255782423, q=1042153201)

print("1st", rsa.core.encrypt_int(13892359163211, pubkey.e, pubkey.n))
print("2nd", rsa.core.encrypt_int(13992351216421, pubkey.e, pubkey.n))
print("1st", hex(rsa.core.encrypt_int(13892359163211, pubkey.e, pubkey.n))[2:])
print("2nd", hex(rsa.core.encrypt_int(13992351216421, pubkey.e, pubkey.n))[2:])

# If you want to compare a couple of numbers that are similar
for i in range (13892359163211, 13892359163251):
  encrypted = rsa.core.encrypt_int(i, pubkey.e, pubkey.n)
  # decrypted = rsa.core.decrypt_int(encrypted, privkey.d, privkey.n)
  print (i, hex(encrypted)[2:], encrypted)

请注意，您不能加密大于pubkey.n的数字。这是RSA相关的限制。通过生成一个不同的具有更高n的密钥对，可以绕过此问题。如果要使所有生成的数字具有相同的长度，请在前面加上前导零。您还可以考虑将它们大写以提高可读性。为了使显示的字符串更短，请考虑使用我早期答案中提到的base62编码。

输出

1st 5427392181794576250
2nd 7543432434424555966
1st 4b51f86f0c99177a
2nd 68afa7d5110929be

input          hex(encrypted)   encrypted
13892359163211 4b51f86f0c99177a 5427392181794576250
13892359163212 2039f9a3f5cf5d46 2322161565485194566
13892359163213 173997b57918a6c3 1673535542221383363
13892359163214 36644663653bbb4  244958435527080884
13892359163215 c2eeec0c054e633  877901489011746355
...

旧版答案与数字的显示方式有关，不知道它们应该看起来显着不同

您想将数字的基数从10更改为更大的数字，以使用更少的字符。请参见https://dev59.com/M3NA5IYBdhLWcg3wBpHs#1119769，其中有一个使用62进制（a-zA-Z0-9）的示例。

或者可以使用16进制(0-9A-F)进行快速且简单的转换。

hex(13892359163211)[2:] # -> 'ca291220d4b'