Гость
Войти | Профиль | Очистить
Map
Действия ...
Форумы / Java [игнор отключен] [закрыт для гостей] / Дорогая в использовании функция. / 21 сообщений из 21, страница 1 из 1
27.03.2021, 20:50
    #40057442
mayton
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
| Ответить | Цитировать | Написать  
29.03.2021, 04:16
    #40057651
crutchmaster
crutchmaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дорогая в использовании функция.
mayton,

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

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

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



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

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

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

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

Единственный способ их ужать - использововать функцию типа divmod, которая вычисляет частное и остаток одновременно. Ну и хорошо если она будет уметь отдельно обрабатывать случаи когда делитель - степень двойки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.03.2021, 14:12
    #40057784
mayton
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
| Ответить | Цитировать | Написать  
30.03.2021, 12:00
    #40058149
mayton
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
| Ответить | Цитировать | Написать  
30.03.2021, 12:01
    #40058151
mayton
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
| Ответить | Цитировать | Написать  
30.03.2021, 12:03
    #40058152
mayton
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
| Ответить | Цитировать | Написать  
30.03.2021, 12:20
    #40058159
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дорогая в использовании функция.
Последняя идея.

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

Код: java
1.
1347d73da9d496705783af314ce992137503e649a10c3b96026b00c2922440f9



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

0x1347d73da9d496705783af314ce992137503e649a10c3b96026b00c2922440f9 / 0x10 = 0x1347d73da9d496705783af314ce992137503e649a10c3b96026b00c2922440f

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

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

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

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

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

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

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



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

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

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


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

<:o)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Java [игнор отключен] [закрыт для гостей] / Дорогая в использовании функция. / 21 сообщений из 21, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 488ms
Закрыть
start [/forum/topic.php?fid=59&mobile=1&tid=2120489]:
 0ms
get settings:
 18ms
get forum list:
 5ms
check forum access:
 1ms
check topic access:
 1ms
track hit:
 43ms
get topic data:
 3ms
get forum data:
 1ms
get page messages:
 411ms
get tp. blocked users:
 0ms
others: 5ms
total:  488ms
x
x
Закрыть


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