powered by simpleCommunicator - 2.0.30     © 2024 Programmizd 02
Map
Форумы / Java [игнор отключен] [закрыт для гостей] / Дорогая в использовании функция.
21 сообщений из 21, страница 1 из 1
Дорогая в использовании функция.
    #40057442
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В продолжение радужных табличек и прочее.

Функция преобразует хеш в ключевое слово в заданном алфавите и заданной длине.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
    public static String reverseKeyword(String hexEncodedHash, String alphabet, int max) {
        BigInteger numericOfHash = new BigInteger(hexEncodedHash, 16); // radix = [2..36]
        BigInteger divider = BigInteger.valueOf(alphabet.length());
        StringBuilder sb = new StringBuilder(max);
        for(int i = 0; i < max; i++) {
            int mod = numericOfHash.mod(divider).intValue();
            sb.append(alphabet.charAt(mod));
            numericOfHash = numericOfHash.divide(divider);
        }
        return sb.toString();
    }



И тест к ней.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
    @Test
    void testRevPwd1() {
        // dbeead -> ddddbb
        String hash1 = PwdProcessor.hashPwd("dbeead"); // SHA-1
        assertEquals("1347d73da9d496705783af314ce992137503e649a10c3b96026b00c2922440f9", hash1);
        String revPwd1 = PwdProcessor.reverseKeyword("1347d73da9d496705783af314ce992137503e649a10c3b96026b00c2922440f9", "abcdefghjklmnopqrstvwxyz0123456789", 6);
        assertEquals("ky9aew", revPwd1);
    }



Так вот. Что-то мне кажется что деление и остаток от деления - дороговатая операция для такого длинного целого числа.
Надо-бы "ужать". Но как? Дорогие в расчетах строки я отметил маркером.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057651
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

alphabet.length() сделать кратным двум и делить сдвигом. Остаток находить маской + побитовое и.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057652
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
*кратным степени двойки
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057676
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Алфавит изменить невозможно. Он - задан извне. И может иметь вид самого неудобного числа. Например 127.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057690
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот думаю... что если max во много раз меньше чем длина хеша то можно хеш отсекать. Надо только
посчитать сколько символов. Тогда деление длинных целых станет дешевле.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057699
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
>Алфавит изменить невозможно. Он - задан извне. И может иметь вид самого неудобного числа. Например 127.
Тогда использовать не весь. Так можно?
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057703
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Еще можно брать на 1 бит больше чем нужно. Только я не придумал, что делать с пустотами.

Еще вариант, берешь на 1 бит больше чем, надо. К начальному индексу прибавляешь то, что взял. Получившийся индекс, берешь из алфавита. Если "перепрыгнул" алфавит, отнимаешь от индекса его длину. Сдвигаешь переменную хеша, повторяешь. Криво, но тут надо смотреть, как у тебя будет с распределением и устроит ли всё это.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057708
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Идея такая. Цепочка применений

Код: java
1.
reverseKeyword(hashPwd(reverseKeyword(.....))) 



должна давать линейное распределение символов на выходе не только для хешей но и для keyworkd
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057716
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Цепочка применений

Там оверхед будет больше, чем от делений:)
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057720
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
crutchmaster
mayton
Цепочка применений

Там оверхед будет больше, чем от делений:)

Технологически там может быть и 100 и 1000 таких применений. В этом и суть.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057778
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Но как? Дорогие в расчетах строки я отметил маркером.

Единственный способ их ужать - использововать функцию типа divmod, которая вычисляет частное и остаток одновременно. Ну и хорошо если она будет уметь отдельно обрабатывать случаи когда делитель - степень двойки.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40057784
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
mayton
Но как? Дорогие в расчетах строки я отметил маркером.

Единственный способ их ужать - использововать функцию типа divmod, которая вычисляет частное и остаток одновременно. Ну и хорошо если она будет уметь отдельно обрабатывать случаи когда делитель - степень двойки.

Это мысль. Я смотрю что в некоторых либах поддержки arbitrary precission такая функция есть

https://sites.google.com/site/indy256/algo_cpp/bigint

Есть похожая реализация в Java11 https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/math/BigInteger.html#divideAndRemainder(java.math.BigInteger)

попробую ее. Хотя интерфейс не выглядит удачным. Возврат массива. Фу-фу...
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40058149
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сделал 2 реализации и бенчмарк. Вот с цифрой два это улучшенная версия

Код: java
1.
2.
3.
4.
Benchmark                                Mode  Cnt        Score       Error  Units
PwdProcessorBenchmark.testHash          thrpt   10  1549404.249 ± 41868.835  ops/s
PwdProcessorBenchmark.testReverseHash   thrpt   10   229683.377 ±  5370.196  ops/s
PwdProcessorBenchmark.testReverseHash2  thrpt   10   313369.002 ±  6880.737  ops/s
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40058151
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
    public static String hashPwd(String pwd) {
        sha256.reset();
        sha256.update(pwd.getBytes(StandardCharsets.UTF_8));
        return Hex.encodeHexString(sha256.digest());
    }

    public static String reversePwd(String hexEncodedHash, String alphabet, int max) {
        BigInteger numericOfHash = new BigInteger(hexEncodedHash, 16); // radix = [2..36]
        BigInteger divider = BigInteger.valueOf(alphabet.length());
        StringBuilder sb = new StringBuilder(max);
        for(int i = 0; i < max; i++) {
            int mod = numericOfHash.mod(divider).intValue();
            sb.append(alphabet.charAt(mod));
            numericOfHash = numericOfHash.divide(divider);
        }
        return sb.toString();
    }

    public static String reversePwd2(String hexEncodedHash, String alphabet, int max) {
        BigInteger numericOfHash = new BigInteger(hexEncodedHash, 16); // radix = [2..36]
        BigInteger divider = BigInteger.valueOf(alphabet.length());
        StringBuilder sb = new StringBuilder(max);
        for(int i = 0; i < max; i++) {
            BigInteger[] res = numericOfHash.divideAndRemainder(divider);
           int mod = res[1].intValue();
            sb.append(alphabet.charAt(mod));
            numericOfHash = res[0];
        }
        return sb.toString();
    }
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40058152
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Бенчмарк.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
    private String randomStringGen(String alphabet, int maxPwdLength) {
        StringBuilder sb = new StringBuilder(maxPwdLength);
        for (int i = 0; i < maxPwdLength; i++) {
            sb.append(alphabet.charAt(random.nextInt(alphabet.length())));
        }
        return sb.toString();
    }

    @Setup(value = Level.Iteration)
    public void setup() {
        random = new Random();
    }

    @Benchmark
    @Warmup(iterations = 1, time = 10, timeUnit = TimeUnit.SECONDS)
    @Measurement(iterations = 2, batchSize = 2)
    public void testHash() {
        PwdProcessor.hashPwd(randomStringGen(ALPHABET, MAX_PWD_LENGTH));
    }

    @Benchmark
    @Warmup(iterations = 1, time = 10, timeUnit = TimeUnit.SECONDS)
    @Measurement(iterations = 2, batchSize = 2)
    public void testReverseHash() {
        PwdProcessor.reversePwd(randomStringGen(HEX_ALPHABET, SHA256_LENGTH_BITS / 4), ALPHABET, MAX_PWD_LENGTH);
    }

    @Benchmark
    @Warmup(iterations = 1, time = 10, timeUnit = TimeUnit.SECONDS)
    @Measurement(iterations = 2, batchSize = 2)
    public void testReverseHash2() {
        PwdProcessor.reversePwd2(randomStringGen(HEX_ALPHABET, SHA256_LENGTH_BITS / 4), ALPHABET, MAX_PWD_LENGTH);
    }

...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40058159
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Последняя идея.

Отсечь лишние буквы от хеша. Допустим для 12 символьного ключевого слова при алфавите в 34
мы сделаем 12 делений этого хеша.

Код: java
1.
1347d73da9d496705783af314ce992137503e649a10c3b96026b00c2922440f9



Целочисленное деление + мод это тяжелая операция. И облегчить ее можно разве что уменьшением
самого числа. Грубо говоря. Если 12 заменить на 16 то деление - в BinHex кодировке это сдвиг на 1
hex символ. Тоесть

0x1347d73da9d496705783af314ce992137503e649a10c3b96026b00c2922440f9 / 0x10 = 0x1347d73da9d496705783af314ce992137503e649a10c3b96026b00c2922440f

Тогда после 34 делений у нас остается число 0x1347d73da9d496705783af314ce992.

И это шлак который не влияет на результат.

Вот мне надо такую-же формулу только не кратную двоичной и hex системе.

Отсечь шлак еще до деления.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40058221
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Вот мне надо такую-же формулу только не кратную двоичной и hex системе.

Увы, не существует в природе. У двойки с десяткой нет общих степеней.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40058231
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я не это имел в виду. Это - функция-шумелка. Чем лучше она шумит - тем лучше. Но мне достаточно того
шума который создает часть хеша SHA-256 (уже переделал).

Вот щас думаю как сделать

Код: java
1.
PwdProcessor.reverseKeyword(cropLetters(sha256value, 256, 36)); // 256 bits per hash, and 34 symbols (divider)



Здесь что-то будет с логарифмом вместо икса.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40058243
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В теле функции cropLetters.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40058605
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тут еще другая проблема. Хеш функции бывают разные. От 32бит CRC до SHA-512, и функция реверсного
отображения будет иметь ограничения. Я уже думаю что это не функция. А некий объект. У которого есть
инициализация. Там идут проверки на всякие границы. Максимальная длина хеша и ключа. Есть
смысл вынести проверки в некую общую часть наподобие init().

Или например хеш функция может быть экзотическая. Какой-нибудь mur-mur. Или сложная где
хеш применяется рекурсивно тыщу раз.
...
Рейтинг: 0 / 0
Дорогая в использовании функция.
    #40059624
mad_nazgul
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton

Так вот. Что-то мне кажется что деление и остаток от деления - дороговатая операция для такого длинного целого числа.
Надо-бы "ужать". Но как? Дорогие в расчетах строки я отметил маркером.


Использовать сдвиги?!

<:o)
...
Рейтинг: 0 / 0
21 сообщений из 21, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Дорогая в использовании функция.
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]