将递增的整数范围映射到最大六位数26,但不可预测

Question

我想为特定用例和我所针对的最终用户类型设计URL缩短器.我已经决定要根据自动递增的整数键在内部存储URL.然而,还需要将密钥表示给URL中的用户作为六位数的基数26(az*6)并且不可能基于递增的整数密钥来预测基本26 url密钥是什么.换句话说,第一个url键不应该是aaaaaa然后在下次有人创建url时它不应该是aaaaab等,并且没有循环生成随机的并且捕获到数据库中以查看它是否已经重复存在.

要求的第二部分(外部人员难以预测的基础26中的网址)是更有趣的部分.理想情况下,我希望将26 ^ 6范围内的所有数字的某种算法1-1映射到相同范围内的另一个数字,然后我可以在基数26中打印,并且我可以在算法上撤消而不是当我想查找网址时,需要存储在单独的表中.我怎么能做到这一点？

Answer 1

为什么不在转换为基数26值之前按特定顺序对位进行洗牌？例如,位0变为位5,位1变为位2等.要解码,只需执行相反操作.

这是Python中的一个例子.(现在编辑也包括转换基地.)

import random

# generate a random bit order
# you'll need to save this mapping permanently, perhaps just hardcode it
# map how ever many bits you need to represent your integer space
mapping = range(28)
mapping.reverse()
#random.shuffle(mapping)

# alphabet for changing from base 10
chars = 'abcdefghijklmnopqrstuvwxyz'

# shuffle the bits
def encode(n):
    result = 0
    for i, b in enumerate(mapping):
        b1 = 1 << i
        b2 = 1 << mapping[i]
        if n & b1:
            result |= b2
    return result

# unshuffle the bits
def decode(n):
    result = 0
    for i, b in enumerate(mapping):
        b1 = 1 << i
        b2 = 1 << mapping[i]
        if n & b2:
            result |= b1
    return result

# change the base
def enbase(x):
    n = len(chars)
    if x < n:
        return chars[x]
    return enbase(x/n) + chars[x%n]

# go back to base 10
def debase(x):
    n = len(chars)
    result = 0
    for i, c in enumerate(reversed(x)):
        result += chars.index(c) * (n**i)
    return result

# test it out
for a in range(200):
    b = encode(a)
    c = enbase(b)
    d = debase(c)
    e = decode(d)
    while len(c) < 7:
        c = ' ' + c
    print '%6d %6d %s %6d %6d' % (a, b, c, d, e)

此脚本的输出,显示编码和解码过程:

   0            0       a            0    0
   1    134217728  lhskyi    134217728    1
   2     67108864  fqwfme     67108864    2
   3    201326592  qyoqkm    201326592    3
   4     33554432  cvlctc     33554432    4
   5    167772160  oddnrk    167772160    5
   6    100663296  imhifg    100663296    6
   7    234881024  ttztdo    234881024    7
   8     16777216  bksojo     16777216    8
   9    150994944  mskzhw    150994944    9
  10     83886080  hbotvs     83886080   10
  11    218103808  sjheua    218103808   11
  12     50331648  egdrcq     50331648   12
  13    184549376  pnwcay    184549376   13
  14    117440512  jwzwou    117440512   14
  15    251658240  veshnc    251658240   15
  16      8388608   sjheu      8388608   16
  17    142606336  mabsdc    142606336   17
  18     75497472  gjfmqy     75497472   18
  19    209715200  rqxxpg    209715200   19

请注意,零映射为零,但您可以跳过该数字.

这很简单,有效,应该足够好用于您的目的.如果你真的需要安全的东西,我显然不会推荐这个.它基本上是一个天真的分组密码.不会有任何碰撞.

可能最好确保位N不会映射到位N(无变化),并且通常最好是输入中的某些低位映射到输出中的较高位.换句话说,您可能希望手动生成映射.实际上,一个不错的映射就是简单地颠倒位顺序.(这就是我为上面的示例输出所做的.)

Answer 2

这取决于你所说的不可预测是什么意思。如果您想要加密安全，您可能对Blum Blum Shub算法感兴趣，但您可能不感兴趣。

我实现了一个线性反馈移位寄存器，目的是提供随机的唯一标识符。LFSR 实现起来很简单，并且它们循环遍历所有可能的组合，尽管可以根据给定的前一个数字计算下一个数字（这不是直接的，但可以完成）。

如果您使用 LFSR，我不确定如何使用整个 26^6 空间。LFRS 具有一定的位长度，并循环遍历这些位的每种可能的组合（我认为 00...0 除外）。您可以使用 28 位 LFSR，但您会丢失前 4000 万个组合（约占其中的 13%）。

看起来可以用序数来映射 LFSR 的状态（即 LFSR 的第 n 个状态是 x），但它有一个专利......但无论如何你都想反过来。