подстановочный шифр с разной длиной алфавита - PullRequest
7 голосов
/ 19 мая 2010

Я хотел бы реализовать простой шифр замещения для маскировки частных идентификаторов в URL.

Я знаю, как будут выглядеть мои идентификаторы (комбинация букв ASCII в верхнем регистре, цифр и подчеркивания), и они будут довольно длинными, поскольку они состоят из ключей. Я хотел бы использовать более длинный алфавит для сокращения результирующих кодов (я хотел бы использовать прописные и строчные буквы ASCII, цифры и ничего больше). Так что мой входящий алфавит будет

[A-Z0-9_] (37 chars)

и мой исходящий алфавит будет

[A-Za-z0-9] (62 chars)

так что сжатие почти на 50% будет доступно в разумных пределах.

Допустим, мои URL выглядят так:

/my/page/GFZHFFFZFZTFZTF_24_F34

и я хочу, чтобы они выглядели так:

/my/page/Ft32zfegZFV5

Очевидно, что оба массива будут перетасованы, чтобы внести некоторый случайный порядок.

Это не обязательно должно быть безопасно. Если кто-то это поймет: хорошо, но я не хочу, чтобы схема была очевидной.

Мое желаемое решение состояло бы в том, чтобы преобразовать строку в целочисленное представление радиуса 37, преобразовать основание в 62 и использовать второй алфавит для записи этого числа. есть ли пример кода, который делает что-то подобное? Integer.parseInt() имеет некоторую похожую логику, но она жестко запрограммирована для использования стандартного поведения цифр.

Есть идеи?

Я использую Java для реализации этого, но, конечно, также полезен код или псевдокод на любом другом языке.

Ответы [ 3 ]

3 голосов
/ 19 мая 2010

Необъяснимо Character.MAX_RADIX - это всего 36, но вы всегда можете написать свою собственную базовую процедуру преобразования. Следующая реализация не является высокопроизводительной, но она должна быть хорошей отправной точкой:

import java.math.BigInteger;
public class BaseConvert {
    static BigInteger fromString(String s, int base, String symbols) {
        BigInteger num = BigInteger.ZERO;
        BigInteger biBase = BigInteger.valueOf(base);
        for (char ch : s.toCharArray()) {
            num = num.multiply(biBase)
                     .add(BigInteger.valueOf(symbols.indexOf(ch)));
        }
        return num;
    }
    static String toString(BigInteger num, int base, String symbols) {
        StringBuilder sb = new StringBuilder();
        BigInteger biBase = BigInteger.valueOf(base);
        while (!num.equals(BigInteger.ZERO)) {
            sb.append(symbols.charAt(num.mod(biBase).intValue()));
            num = num.divide(biBase);
        }
        return sb.reverse().toString();
    }
    static String span(char from, char to) {
        StringBuilder sb = new StringBuilder();
        for (char ch = from; ch <= to; ch++) {
            sb.append(ch);
        }
        return sb.toString();
    }
}

Тогда вы можете иметь main() испытательный комплект, подобный следующему:

public static void main(String[] args) {
    final String SYMBOLS_AZ09_ = span('A','Z') + span('0','9') + "_";
    final String SYMBOLS_09AZ = span('0','9') + span('A','Z');
    final String SYMBOLS_AZaz09 = span('A','Z') + span('a','z') + span('0','9');

    BigInteger n = fromString("GFZHFFFZFZTFZTF_24_F34", 37, SYMBOLS_AZ09_);

    // let's convert back to base 37 first...
    System.out.println(toString(n, 37, SYMBOLS_AZ09_));
    // prints "GFZHFFFZFZTFZTF_24_F34"

    // now let's see what it looks like in base 62...       
    System.out.println(toString(n, 62, SYMBOLS_AZaz09));
    // prints "ctJvrR5kII1vdHKvjA4"

    // now let's test with something we're more familiar with...
    System.out.println(fromString("CAFEBABE", 16, SYMBOLS_09AZ));
    // prints "3405691582"

    n = BigInteger.valueOf(3405691582L);
    System.out.println(toString(n, 16, SYMBOLS_09AZ));
    // prints "CAFEBABE"        
}

Некоторые наблюдения

  • BigInteger, вероятно, проще всего, если числа могут превышать long
  • Вы можете перетасовать char в символе String, просто придерживайтесь одной "секретной" перестановки

Примечание относительно "50% сжатия"

Обычно нельзя ожидать, что базовая строка 62 будет примерно вдвое короче базовой строки 36. Вот Long.MAX_VALUE в базе 10, 20 и 30:

    System.out.format("%s%n%s%n%s%n",
        Long.toString(Long.MAX_VALUE, 10), // "9223372036854775807"
        Long.toString(Long.MAX_VALUE, 20), // "5cbfjia3fh26ja7"
        Long.toString(Long.MAX_VALUE, 30)  // "hajppbc1fc207"
    );
2 голосов
/ 19 мая 2010

Это вообще не подстановочный шифр, но ваш вопрос достаточно ясен.

Посмотрите на Base85: http://en.wikipedia.org/wiki/Ascii85

Для Java (как косвенно связано со статьей Википедии):

0 голосов
/ 19 мая 2010

Теперь у меня есть рабочее решение, которое вы можете найти здесь:

http://pastebin.com/Mctnidng

Проблема была в том, что а) Я терял точность длинных кодов в этой части:

value = value.add(//
    BigInteger.valueOf((long) Math.pow(alphabet.length, i)) // error here
        .multiply(
            BigInteger.valueOf(ArrayUtils.indexOf(alphabet, c))));

(долго просто недостаточно)

и б) всякий раз, когда у меня был текст, начинающийся с символа со смещением 0 в алфавите, это было бы отброшено, поэтому мне нужно было добавить символ длины (один символ здесь подойдет, так как мои коды никогда не будут будь длиной до алфавита)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...