Увеличение целочисленного диапазона карты до шестизначного 26 макс., Но непредсказуемо
Я хочу спроектировать сокращение URL для конкретного варианта использования и типа конечного пользователя, на которого я нацелился. Я решил, что я хочу, чтобы URL-адреса были сохранены внутри в соответствии с автоматически увеличивающимся целочисленным ключом. Однако также необходимо, чтобы ключ был представлен пользователям в URL-адресе как шестизначное основание 26 (az * 6), и невозможно предсказать, что основа 26-го URL-ключа основана на увеличивающемся целочисленном ключе. Другими словами, первый ключ URL-адреса не должен быть aaaaaa, затем в следующий раз, когда кто-то создает URL-адрес, это не должен быть aaaaab и т. Д., И не должно быть цикла, генерирующего случайный ключ и отправляющего данные в базу данных, чтобы увидеть, существует ли он уже неоднократно.
Вторая часть требований (URL-адреса в базе 26, которые посторонний предсказать сложно) является более интересной. В идеале я хотел бы получить какое-то алгоритмическое 1-1 отображение всех чисел в диапазоне 26^6 на другое число в том же диапазоне, которое я могу просто затем распечатать в базе 26, и которое я могу отменить алгоритмически и не нужно хранить в отдельной таблице, когда я хочу посмотреть URL. Как я могу сделать это?
8 ответов
Почему бы просто не перемешать биты в определенном порядке перед преобразованием в базовое значение 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 (без изменений), и, вероятно, лучше всего, если в целом некоторые младшие биты на входе отображаются в старшие биты на выходе. Другими словами, вы можете создать отображение вручную. Фактически, приличное отображение просто изменило бы порядок битов. (Это то, что я сделал для примера вывода выше.)
Использование функции Hash с семенем должно сделать его непредсказуемым.
Безопасность, очевидно, не является проблемой (иначе вы бы использовали криптографию).
На самом деле, вы можете сразу использовать MD5 и выбрать фиксированные 6 символов для простого решения, которое будет хорошо работать. Он доступен на большинстве языков и генерирует буквенно-цифровой хеш 128-битный хеш, который легко записывается в виде 32 шестнадцатеричных. Это на самом деле всего 16 символов (сводится к базе 16).
Создание собственного алгоритма непредсказуемого хеширования не рекомендуется.
Вот запись в блоге Coding Horror, которую вы тоже должны прочитать.
Я явно дважды цитирую упоминание Джеффа "Кодирующий ужас", чтобы подчеркнуть.
Предположим, вы используете что-то вроде MD5 (БОГ ХАШ). MD5 принимает любую длину строки входных байтов и выводит 128 бит. Биты постоянно случайные, в зависимости от входной строки. Если вы отправите одну и ту же строку дважды, вы получите точно такие же случайные 16 байтов. Но если вы сделаете даже небольшое изменение во входной строке - даже одно-битное изменение - вы получите совершенно другой выходной хеш.
Итак, когда вам нужно беспокоиться о столкновениях? Рабочее правило здесь происходит из парадокса дня рождения. По сути, вы можете ожидать первого столкновения после хэширования 2n/2 элементов или 2^64 для MD5.
2^64 - это большое число. Если в сети 100 миллиардов URL, а мы все их MD5, увидим ли мы столкновение? Ну, нет, так как 100 000 000 000 намного меньше, чем 2^64:
2^64 18,446,744,073,709,551,616
2 ^ 37 100 000 000 000
Обновление на основе комментариев.
- При шестнадцатеричном представлении из 6 символов, как я предлагаю выше, вероятность столкновений уменьшается до
2^12- это всего 4096! (прочитайте всю статью Coding Horror для нюансов). - Если вы не хотите повторения при сокращении (одна и та же сокращенная форма для URL-адреса каждый раз), случайное число должно подойти.
Это зависит от того, что вы подразумеваете под непредсказуемым. Если вам нужна криптографическая защита, вам может быть интересен алгоритм Blum Blum Shub, но, вероятно, нет.
Я реализовал регистр сдвига с линейной обратной связью, чтобы дать случайным образом выглядящие уникальные идентификаторы. LFSR просты в реализации и циклически перебирают все возможные комбинации, хотя можно вычислить следующее число, учитывая предыдущее число (это не просто, но это можно сделать).
Я не уверен, как использовать все пространство 26^6, если вы используете LFSR. LFRS имеет определенную битовую длину и циклически перебирает каждую возможную комбинацию этих битов (за исключением 00...0, я думаю). Вы можете использовать 28-битный LFSR, но вы потеряете 40 миллионов лучших комбинаций (что составляет около 13% из них).
Похоже, что можно сопоставить состояния LFSR с порядковыми номерами (т. Е. N-е состояние LFSR равно x), но на это есть патент... Но вы все равно хотите пойти в обратном направлении.
Как насчет LFSR? Регистр сдвига с линейной обратной связью используется для генерации псевдослучайных чисел в диапазоне - операция является детерминированной, учитывая начальное значение, но она может посещать каждое значение в диапазоне с длинным циклом.
Вы хотите изменить свой первоначальный автоинкрементный идентификационный номер в сети Feistel. Это сообщение (которое находится в списках PostgreSQL, но на самом деле не имеет ничего общего с PostgreSQL) описывает простую сеть Фейстеля. Конечно, существует множество вариаций, но в целом это правильный подход.
Недавно я задавал в основном тот же вопрос, и решением было увеличить его на простое число (по модулю max), чтобы получить красивую, казалось бы, случайную последовательность без повторения любых чисел: уникальный код в стиле Tinyurl: потенциальный алгоритм для предотвращения столкновений
26^6 составляет около 300 миллионов.
Проще всего использовать генератор случайных чисел, и, если у вас есть коллизия (то есть, если ваш случайно сгенерированный 6-буквенный идентификатор уже занят), увеличивать, пока у вас не будет свободного идентификатора.
Я имею в виду, конечно, что вы будете получать коллизии довольно рано (около 17 тысяч записей), но приращение, пока у вас не будет свободного идентификатора, будет достаточно быстрым, по крайней мере, до тех пор, пока ваше пространство ключей не начнет насыщаться (около 12 миллионов записей), и к тому времени вы все равно должны перейти на 7-буквенные идентификаторы.
Вам нужен блочный шифр с "Block Space" из 266.
Выберите произвольный ключ для шифра, и теперь у вас есть преобразование, которое вы обратимо, но непредсказуемо для всех остальных.
Ваш размер блока немного необычен, так что вы, вероятно, не найдете готовый хороший блочный шифр для вашего размера. Но, как предлагает kquinn, вы можете создать один самостоятельно, который имитирует другие шифры.