Биективная функция "Integer <-> String"

Question

Вот проблема, для которой я пытаюсь найти лучшее решение.У меня есть конечный набор неотрицательных целых чисел в диапазоне [0 ... N] .Мне нужно иметь возможность представлять каждое число в этом наборе в виде строки и иметь возможность преобразовать такую ​​строку обратно в исходное число.Так что это должна быть биективная функция.

Дополнительные требования:

1. Строковое представление числа должно запутывать исходное число хотя бы в некоторой степени.Таким образом, простое решение типа f (x) = x.toString () не будет работать.
2. Важна длина строки: чем меньше, тем лучше.
3. Если известно строковое представление K , я бы хотел, чтобы оно было нетривиальным (в некоторой степени) угадать строковое представление K + 1 .

Для стр. 1 и стр. 2 очевидным решением является использование чего-то вроде Base64 (или любого другого BaseXXX, подходящего для всехзначения) обозначения.Но можем ли мы вписаться в п.3 с минимальными дополнительными усилиями?Здравый смысл подсказывает мне, что мне дополнительно нужна биективная функция «String <-> String» для значений BaseXXX.Какие-либо предложения?Или, может быть, есть что-то лучше, чем BaseXXX, чтобы соответствовать всем 3 требованиям?

Answer 1

Составьте таблицу длины M. Эта таблица должна отображать числа от 0 до M-1 в разные короткие строки со случайным порядком. Выразите целое число как число - M, используя строки таблицы для представления цифр в числе. Расшифруйте с помощью простого обращения.

С M=26 вы можете просто использовать букву для каждой из цифр. Или возьмите M=256 и используйте байт для каждой цифры.

Даже удаленно хороший криптографический подход!

Answer 2

Этот метод соответствует требованиям 1-3, но, возможно, он слишком дорог для вычислений:

1. найти простое число p > N+2, не слишком большое
2. найти первообразный корень g по модулю p, то есть число, порядок умножения которого по модулю p равен p-1
3. для 0 <= k <= N, пусть enc(k) = min {j > 0 : g^j == (k+2) (mod p)}
4. f(k) = enc(k).toString()

Answer 3

Если вам не нужно, чтобы он был слишком защищенным, вы можете просто использовать простой симметричный шифр после кодирования в BaseXXX. Например, вы можете выбрать последовательность ключей из целых чисел [n₁, n₂, n₃ ...], а затем использовать Vigenere шифр .

Основная идея шифра проста - кодировать каждый символ C как C + K (mod 26), где K - элемент ключа. По мере продвижения, просто получите следующий номер из ключа для следующего символа, оборачиваясь, как только у вас заканчиваются значения в ключе.

У вас действительно есть два варианта: вы можете сначала преобразовать число в строку в baseXXX, а затем зашифровать, или вы можете использовать ту же идею, чтобы просто зашифровать каждое число как один символ. В этом случае вы хотели бы изменить его с mod 26 на mod N + 1.

Если подумать, еще более простым вариантом будет просто xor элемент из ключа и значения. (В отличие от использования формулы Vigenere.) Я думаю, что это будет работать так же хорошо для запутывания.

Answer 4

р. 1 и р. 3 немного противоречат и тоже немного расплывчаты.

Я бы предложил использовать шестнадцатеричное представление целых чисел.

17 => 0x11
123123 => 1E0F3

Answer 5

Итак, вам нужна строка, которая затемняет исходное число, но позволяет определить str (K + 1), когда str (K) известна?

Как насчет просто сделать f(x) = (x + a).toString(), где a является секретом? Тогда внешний пользователь не может определить x из f(x), но он может быть уверен, что если у него есть строка «1234», скажем, для неизвестного x, то «1235» отображается на x+1.