ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничный криптунЪ и редукция
25 сообщений из 90, страница 1 из 4
  1  все
Тяпничный криптунЪ и редукция
    #39906262
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Камрады привет. С пятницей. Дима. Илья. Сидоров. Сова. Сибиряков. И все-все-все. Пытаюсь осилить статью Making a Faster Cryptanalytic Time-Memory Trade-Off Вобщем вопрос первый пока. Что за функция редукции и как ее разработать? Из текста я понял только требования.
  • Она должна на выходе иметь тот-же алфавит что и на вход функции хеширования. И одинаковой длины.
  • На различных таблицах могут быть применены разные функции редукции
Непонятна связь между хешированием и редукцией. Второе зависит от первого? Другие вопросы еще не сварились в моей голове. Но будут по мере сил... Линки по теме.
...
Рейтинг: 0 / 0
20.12.2019, 17:10
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39906544
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Update.

Поисковые сети нам сообщают примерчик.
Код: sql
1.
2.
H(nus)=0e23df0
R(0e23df0)=wef


Цепочка хешей и редукций
Код: sql
1.
2.
     H             R        H           R
nus ---> 0e23df0 --> wef ---> a3bc8aa ---> ytr
...
Рейтинг: 0 / 0
21.12.2019, 20:33
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39906596
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если внутри другой chain, появляется pwd=nus, то цепочка частично повторяется.

Код: sql
1.
2.
nus ---> 0e23df0 --> wef ---> a3bc8aa ---> ytr ---> becd2a4 ---> mng
trf ---> b983ff3 --> nus ---> 0e23df0 ---> wef ---> a3bc8aa ---> ytr
...
Рейтинг: 0 / 0
21.12.2019, 23:28
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39906597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если одну функцию редукции R заменить на набор различных функций R1,R2,R3...
то коллизий в цепочках не будет.
...
Рейтинг: 0 / 0
21.12.2019, 23:31
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39906747
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Кроме статей Филиппа Ошлина - практически ничего нет. Видео-материалы по теме на 99%
состоят либо из практического руководства по установке или использованию rt-gen, либо
из докладов Индусов которые рисуют корявые картинки на тему самих основ.
...
Рейтинг: 0 / 0
22.12.2019, 22:09
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39906832
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
С английским у меня не очень, поэтому сначала опишу как я понял принцип работы.

Подготовка
1. Выстраивается цепочка N пар Ключ-Шифр, типа
Код: sql
1.
Ключ1 -> Шифр1 -> Ключ2 -> Шифр2 -> ... -> КлючN -> ШифрN


где Шифр1 это какой-то постоянный текст зашифрованный с помощью Ключ1
Ключ2 генерируется из Шифр1 алгоритмом редукции.

2. Заполнение таблицы. Генерим цепочку для каждого значения ключа и если внутри цепочки ни один Шифр i не присутствует в таблице, то пара {Ключ1, ШифрN} добавляются в таблицу.

Таким образом происходит сжатие таблицы всех возможных пар {Ключ, Шифр} в N раз, где N длина цепочки.

Использование : берем какой-то ШифрХ и гоним его по цепочке пока не получим известный нам ШифрN из таблицы. Затем берем Ключ1 и по цепочке получаем КлючХ


Выводы
Как я понимаю задача функции редукции генерация Ключ i+1 из Шифр i .
Т.е. функция редукции может делать что угодно, например посчитать хэш/CRC/AES/XOR и привести к требуемому алфавиту ключа.
Основное требование к функции это сгенерить как можно меньше зацикленных и вырождающихся (уходящих в другую) цепочек, т.е. в идеале из каждого уникального Шифр i должен получаться уникальный Ключ i+1 . Ну и желательно чтобы функция побыстрее работала, т.к. цепочки достаточно длинные.
Я так понимаю автор проблему зацикливания решить не смог, поэтому обошел ее применив две разные функции, надеясь что для каждого конкретного значения шифра найдется цепочка хотя бы в одной таблице.

Приведение к алфавиту ключа не проблема. Легко решается по аналогии с переводом из одной системы счисления в другую. Например Base64.
...
Рейтинг: 0 / 0
23.12.2019, 08:29
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907079
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, да все норм у тебя с английским. Тут вопрос не в языке а в способности оценить рациональное зерно.

Щас пригоню следующий вопрос.
...
Рейтинг: 0 / 0
23.12.2019, 15:22
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907149
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот допустим у меня есть следующая (не радужная) табличка

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
Ondertrouwd8 ad52bb899f98da83ad1a5ddd6eeae1f210757c1ef27df945f4d264ed29b9f3cd
opengewerkt8 164d5838ac1256405ae040d1f3d7a080d209c7eea87cacd7be7cb7210cfa91fb
i55po8x538if c7813fa89092f8ab358ba72abf40cc269404d5308160796db2a77bcf950b427b
jvvi5m4y36xr 5293a0f9dd3c6c8976cde75fd63b44afb4153bc46fa6fecf5701fc070b43ab70
Jichtpijnen3 65b21f7e3d196574086bdb2e808535af82a1d48e0ae4f56572c535a2c63ccbf6
j43sci9x03j3 f08604216a9950afee43a865d338bc08e69b957d152c479d35230ce9b0d2e331
hrd78ub12o2a d18ed9f7b176edefed01baacb144067fe0376de005d4cdae859ad66b0f0669e2
utkarshhanam 6b6319a93b0fae6b5a471b2beafdb09904403e5d95df7eb77768fa6c3c0d5f54



И я хочу применить данный метод. Слева - ключ (12 символов). Справа дайджест типа SHA1. Почему SHA1? Потому-что он мне нужен.
Он - меня интересует. Далее я хочу сформировать функцию редукции с учотом алфавита. Альфа-нумерик + верхний
и нижний кейс. Возьму Base64. Она - подходит. 12 символов кратно 3 и 4 тоесть отображается на base64 идеально
без padding.

И дальше ... - меня терзают смутные сомнения. Что-то здесь не то в моих рассуждениях.

 

Ключи это все 12-символьные слова которые я взял из нашего 1.2млрд текстового
файлика который использовался в топиках толстой сортировки.
...
Рейтинг: 0 / 0
23.12.2019, 17:01
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907172
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Литература по теме.

(Имена файлов - не оригинальные. Я переименовывал для своего удобства. Но легко гуглятся.)

Cryptoanalytic.Time-Memory.Tradeoff.for.Password.Hashing.Schemes.pdf
Making.a.Faster.Cryptoanalytic.Time-Memory.Trade-Off.pdf
Rainbow.Tables.explained.pdf
Reducing.Time.Complexity.in.RFID.Systems.pdf
Time-Memory.Trade-Offs.False.Alarm.Detection.Using.Checkpoints.pdf
...
Рейтинг: 0 / 0
23.12.2019, 17:24
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907230
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Твоя задача не решается этим методом. 64^12 примерно 10^21 паролей. Прикинь сколько времени уйдет на полный перебор для построения таблицы.

PS Пишу с телефона, подробности позже
...
Рейтинг: 0 / 0
23.12.2019, 18:56
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907231
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот такая вот туфта получается. Ну и где тут экономия? Какой болт мне с таких редукций?
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
Ondertrouwd8 --> rVK7iZ+Y2oOtGl3dburh8hB1fB7yfflF9NJk7Sm5880= --> rVK7iZ+Y2oOt --> BNkMNQC1RjQfhHqypziEyQbo1rEJ8ZrEvKgWGlBZ7HY= --> BNkMNQC1RjQf --> PwMeGzPPJmZjtIR+GnUxfJWfMf2Fdecl389+1hPNTZY= --> PwMeGzPPJmZj
opengewerkt8 --> Fk1YOKwSVkBa4EDR89eggNIJx+6ofKzXvny3IQz6kfs= --> Fk1YOKwSVkBa --> 8am0ewI3QtPeJAtR3X9n6rLjRz/ymVO3Ej/BoWpztDw= --> 8am0ewI3QtPe --> EwYnLJPzRxY8VTfCA7VwuwcwjAddQYeGiRP5IljrMzY= --> EwYnLJPzRxY8
i55po8x538if --> x4E/qJCS+Ks1i6cqv0DMJpQE1TCBYHltsqd7z5ULQns= --> x4E/qJCS+Ks1 --> pqegxH1QZhSQ3ejEpHcfhEp18ouDLrbT7WoHxfCEpa4= --> pqegxH1QZhSQ --> Bo1E1K3WHBj15kHI6qlukNoQnZjO9kFn2E40TSL3yGU= --> Bo1E1K3WHBj1
jvvi5m4y36xr --> UpOg+d08bIl2zedf1jtEr7QVO8Rvpv7PVwH8BwtDq3A= --> UpOg+d08bIl2 --> 3umAPYI28DnUqk486TDC6ocfyu6ihgm3nlDBBzKXRQo= --> 3umAPYI28DnU --> SVdwyTfmrNoU8MUIKo7zyBROgjNpgdr0r2rffEdwfSw= --> SVdwyTfmrNoU
Jichtpijnen3 --> ZbIffj0ZZXQIa9sugIU1r4Kh1I4K5PVlcsU1osY8y/Y= --> ZbIffj0ZZXQI --> 3rZenHYQuJA8P4+4FGgvrJAzlGmbWDr+trusIl1z2xg= --> 3rZenHYQuJA8 --> XJc2EF8LGdzoJVy8E73wLJ8shf7n2ajXC55b72dEftI= --> XJc2EF8LGdzo
j43sci9x03j3 --> 8IYEIWqZUK/uQ6hl0zi8COablX0VLEedNSMM6bDS4zE= --> 8IYEIWqZUK/u --> Z7TwKfWTt9j6nj9Lh1GKcFoilX+TArO6bLVmpQPZoPI= --> Z7TwKfWTt9j6 --> L8jJpZURw+UA5rIv0jFux3F/4Q+jW3dIT7nGxxHgQVI= --> L8jJpZURw+UA
hrd78ub12o2a --> 0Y7Z97F27e/tAbqssUQGf+A3beAF1M2uhZrWaw8GaeI= --> 0Y7Z97F27e/t --> zLn+viyMF4eOgYA7gZO6wa218Tbfgx4TPRHugikkL3I= --> zLn+viyMF4eO --> n5VIeAcRXDUtlgQ5Vx6nK7h5RGphs61oAQt3j1BzyCI= --> n5VIeAcRXDUt
utkarshhanam --> a2MZqTsPrmtaRxsr6v2wmQRAPl2V3363d2j6bDwNX1Q= --> a2MZqTsPrmta --> Q0CtMITCEjiMw1mnKtM1uZ4tccvbiHCQhuSdPiM2R/Q= --> Q0CtMITCEjiM --> tCm9zGawH4IXgAKi66f+CDM0sihofnnUoaYXFmnwyk8= --> tCm9zGawH4IX
j52604s03l0f --> 7NNMNKfLkUA62I7DmHXRUp+OqbSnWGSqKOo9rv82p54= --> 7NNMNKfLkUA6 --> 81z5nmk+0yV4nRU17wzO7OI3DtqlChrNHRwYJ5FOIz0= --> 81z5nmk+0yV4 --> 8X9GAyWFc4Q2eOBwxVEjEa6IoMdzE+TylNtXJnGJfwY= --> 8X9GAyWFc4Q2
gccxu98o9ag8 --> Yx0MA5tFxW9GNhmr4XC2TpVuRLz/dJBQQTuYKmlIAGs= --> Yx0MA5tFxW9G --> qGzY7UK5ZHfXsNaVWqypB2XCqI5KIDZUZ6gcbFx9q48= --> qGzY7UK5ZHfX --> To9WowujkJ8zJRn7DQzgEisswQn5604SkNclUyqnEWo= --> To9WowujkJ8z
kj8i6i4pe4y4 --> 6LiBLP54S3YBCIiR1qOYYGNIi3WA1/ZuDfPx7LzanuQ= --> 6LiBLP54S3YB --> 8BlsQPZtDPWmxF9pqm7wssx9jQ5R9PWrZTRLIcFoaIk= --> 8BlsQPZtDPWm --> M9bTudPa7DtCgZYOku3Xgcu60qt7ZUW7Z51f8xp8jt4= --> M9bTudPa7DtC
h7d49lc5m71f --> 2PHKUEk0MGIDR7C/Rs2wYsWKnQ9YY1GaZj5Y88yVpNc= --> 2PHKUEk0MGID --> mqAfdJhdLIKf/5ak8Q3kbhTtEQ2FTw/jqtqj1k1byN4= --> mqAfdJhdLIKf --> QxBZvzvhIimnNMwVI6djEY+/m5DHR61JNld5l+JwpUE= --> QxBZvzvhIimn
Arcticdrizzt --> noOMKjVrR+KFvrR3yN15goTysh8dzi9NnkvkRXvfIpw= --> noOMKjVrR+KF --> fZjVGMVqOwH7xdWlD0tQveNqwqh9uhsl4nTyPwfhxd4= --> fZjVGMVqOwH7 --> /BBkBz8IyXYBFvKmVRij9kYh58AysOaeSTkj7cxam40= --> /BBkBz8IyXYB
Aarontrident --> PMRQGuCB91eXMMLJk/5goWGR1NuOzK+5+URdUaRLL4o= --> PMRQGuCB91eX --> q6AmPK0tlC5RqNhv2WHzy44F936xIODTi2+yMlhb1Ng= --> q6AmPK0tlC5R --> UDCBFxAlGMhxyEkXga5mY6HUZ/LF0VWcrpuK8K6Lazs= --> UDCBFxAlGMhx
unanimityses --> yUEwVhTuCa7jm2FvZCiIbD/W+pdQ4om1PoLEEi6ya10= --> yUEwVhTuCa7j --> Ak7ai1HiWw72sVcj22Rpw2qvZ04toqr/HcO0BKxsk20= --> Ak7ai1HiWw72 --> MiL6drJJElxzFlrkcsZFPECg5NHfHBeTCX3Mvp3EEO8= --> MiL6drJJElxz
yticangupped --> re53JBaQa2XOCSYLxc+RNnniawVNJmCwrCcPATxGbH8= --> re53JBaQa2XO --> YbqNEA6mqmEhenOk//0TwqMZSya1oS6BOvsLJwSxFkk= --> YbqNEA6mqmEh --> w/68YAtORyQ6Gm5r16roXpspg54mu4RuNSm8X2Xz/sU= --> w/68YAtORyQ6


Пока я только проиграл в размере.

Я так понимаю что самый правый редукт (в последней колонке) должен оказать мне помощь в поиске keys?
Но как? На вход поступает к примеру хешик UDCBFxAlGMhxyEkXga5mY6HUZ/LF0VWcrpuK8K6Lazs=.
Что дальше? Какова логика поиска?

Кому интересно поломать дальше - вот сорц.

Вобщем в топик призываются все криптуны, математики, маги и колдуны и прочие книжники и фарисеи.

 
Код: 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.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
import org.apache.commons.codec.binary.Base64;
import org.apache.commons.codec.binary.Hex;

import java.io.FileInputStream;

import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.security.MessageDigest;
import java.util.Arrays;
import java.util.Properties;
import java.util.stream.Stream;
import static mayton.crypto.Utils.*;

public class RainbowGen {

    public static void main(String[] args) throws Exception {
        int t = 7; // Chain length
        int m = 16; // Chains in table
        int pwdLength = 12; // chars (by modulo 3)
        int limitHash = 3 * pwdLength / 4; // (by modulo 4)
        Properties properties = new Properties();
        properties.load(new FileInputStream("sensitive.properties"));
        String pwds = properties.getProperty("pwds");
        try (Stream<String> stream = Files.lines(Paths.get(pwds))) {
            stream.limit(m).forEach(line -> {
                print(line);
                print(" --> ");
                byte[] hash = getShaFromLine(line);
                for (int i = 0; i < ( t / 2 ); i++) {
                    //print(Hex.encodeHexString(hash));
                    print(Utils.encodeBase64(hash));
                    print(" --> ");
                    String reduct = Utils.encodeBase64(subArray(hash, 0, limitHash));
                    print(reduct);
                    if (i < t / 2 - 1) {
                        print(" --> ");
                        hash = getShaFromLine(reduct);
                    }
                }
                print("\n");
            });
        }
    }

}


Код: 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.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
import org.apache.commons.codec.binary.Base64;
import org.jetbrains.annotations.NotNull;
import javax.annotation.concurrent.NotThreadSafe;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;

@NotThreadSafe
public class Utils {

    static MessageDigest messageDigest = null;
    static Base64 base64encoder = new Base64();

    static {
        try {
            messageDigest = MessageDigest.getInstance("SHA-256");
        } catch (NoSuchAlgorithmException ex) {
            throw new RuntimeException(ex);
        }
    }

    private Utils() {}

    @NotNull
    public static byte[] subArray(byte[] array, int beg, int end) {
        return Arrays.copyOfRange(array, beg, end);
    }

    public static void print(@NotNull String arg) {
        System.out.print(arg);
    }

    @NotNull
    public static byte[] getShaFromLine(@NotNull String line) {
        messageDigest.reset();
        messageDigest.update(line.getBytes(StandardCharsets.UTF_8));
        return messageDigest.digest();
    }

    @NotNull
    public static String encodeBase64(@NotNull byte[] arr) {
        return base64encoder.encodeAsString(arr);
    }

}

...
Рейтинг: 0 / 0
23.12.2019, 19:01
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907247
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ага. Сам допёр. Тоесть если их так расписать. И потом развернуть левое и правое и проиндексировать.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
j43sci9x03j3 -->  L8jJpZURw+UA
hrd78ub12o2a -->  n5VIeAcRXDUt
utkarshhanam -->  tCm9zGawH4IX
j52604s03l0f -->  8X9GAyWFc4Q2
gccxu98o9ag8 -->  To9WowujkJ8z
kj8i6i4pe4y4 -->  M9bTudPa7DtC
h7d49lc5m71f -->  QxBZvzvhIimn
Arcticdrizzt -->  /BBkBz8IyXYB
Aarontrident -->  UDCBFxAlGMhx
unanimityses -->  MiL6drJJElxz
yticangupped -->  w/68YAtORyQ6



Тогда подсвеченное - и будет искомой строкой.
...
Рейтинг: 0 / 0
23.12.2019, 19:13
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907249
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А с этим как быть?

Код: sql
1.
Fk1YOKwSVkBa4EDR89eggNIJx+6ofKzXvny3IQz6kfs=



Маги и колдуны. Помогайте.
...
Рейтинг: 0 / 0
23.12.2019, 19:14
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907296
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Этот инструмент тут не подходит. Это алгоритм ускорения массового подбора паролей. Тут это запрещено обсуждать, но тема тупиковая, поэтому продолжим. Этот алгоритм оптимизирует подбор конкретного пароля, у автора ускорилось в 7 раз по сравнению с тупым перебором, но перебор не исчез, просто перебор происходит заранее, но в более тяжелой форме для построения таблицы цепочек 22046586 , т.е. польза будет если только массово подбирать, получить один пароль перебором будет быстрее.

У тебя 10 21 вариантов паролей, лень считать точно, но прикинув на глаз могу сказать что построение таблицы может занять годы, а может и десятилетия, может еще больше...
...
Рейтинг: 0 / 0
23.12.2019, 20:57
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907298
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я не хочу обсуждать такие темы как перебор паролей. Поэтому в дальнейшем я буду использовать такие
термины как ключ. И хеш.

И применение я искал не в атаках на несчастных владельцев Windows а для других задач. Хотя-бы для подписывания
блоков блокчейна. Как вариант. Да. Вот тема топика. Оптимизация подписывания блокчейна. За это и буду топить.

А таблицы эти уже построены. Проект называется http://project-rainbowcrack.com/

Поэтому к той теме я ничего нового не добавлю. Просто сижу. Разбираюсь.
...
Рейтинг: 0 / 0
23.12.2019, 21:04
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907301
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Я не хочу обсуждать такие темы как перебор паролей.

Зачем тогда ее поднял?

Ничего криминального тут нет, раз все обсуждают, то почему нам не обсудить? Эта тема старье и об этом давно всем известно, в т.ч. тебе, т.к. ты не спроста сделал 12 символов в пароле.
...
Рейтинг: 0 / 0
23.12.2019, 21:19
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907303
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну. Дык. Где рациональное зерно? Радужка оптимизирует хранение за счет более медленного доступа.
По сути это торговля. Мы продаем диск. Но покупаем CPU. Вместо верчения циклом - итеративный
поиск по дисковому файлу.

Я так перевожу себе trace-off. Как сделка. Обмен. Торг.

А где в моём случае сделка? Редукция? Да работает. А как двигаться по чейну справа налево? Я не знаю.
...
Рейтинг: 0 / 0
23.12.2019, 21:29
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907304
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Ну. Дык. Где рациональное зерно?

Нет его тут, совсем.
...
Рейтинг: 0 / 0
23.12.2019, 21:31
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907307
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton, подробнее свою задачу опиши, может я вижу совсем не то что тебе надо
...
Рейтинг: 0 / 0
23.12.2019, 21:34
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907309
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Представь что я ищу ключ по SHA1. Обратная операция по отношению к хешированию.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
Ondertrouwd8 ad52bb899f98da83ad1a5ddd6eeae1f210757c1ef27df945f4d264ed29b9f3cd
opengewerkt8 164d5838ac1256405ae040d1f3d7a080d209c7eea87cacd7be7cb7210cfa91fb
i55po8x538if c7813fa89092f8ab358ba72abf40cc269404d5308160796db2a77bcf950b427b
jvvi5m4y36xr 5293a0f9dd3c6c8976cde75fd63b44afb4153bc46fa6fecf5701fc070b43ab70
Jichtpijnen3 65b21f7e3d196574086bdb2e808535af82a1d48e0ae4f56572c535a2c63ccbf6
j43sci9x03j3 f08604216a9950afee43a865d338bc08e69b957d152c479d35230ce9b0d2e331
hrd78ub12o2a d18ed9f7b176edefed01baacb144067fe0376de005d4cdae859ad66b0f0669e2
utkarshhanam 6b6319a93b0fae6b5a471b2beafdb09904403e5d95df7eb77768fa6c3c0d5f54



По сути мне надо найти любую символьную последовательность которая удовлетворяет первому
хешу ad52bb899f98da83ad1a5ddd6eeae1f210757c1ef27df945f4d264ed29b9f3cd. Не обязательно она должна
быть ключом Ondertrouwd8. Это может быть любая другая последовательность. Не суть.

Я хочу сэкономить. Я не хочу вращать циклы. Я заранее знаю формулу которая порождает ключи.
Например ключи - это всегда даты 2015-01-01. Или некие комбинации даты и суммы.

Я хочу выиграть время. Я хочу находить ключ менее чем за 10 минут. Большее время - я потерял деньги.
Уложился в 9 минут - заработал.

Я могу использовать железо на базе видеокарт. Но я ищу альтернативные векторы развития.
Зачем вкладываться только в вычислительные модули? Когда есть модули хранения которые
дешевы и их много. И есть принцип memory trade-off о котором так долго пишет несчастный французик.

Впрочем всё это поток моего сознания.

Можете критиковать.
...
Рейтинг: 0 / 0
23.12.2019, 21:49
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907329
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
И функции редукции у меня неправильные. Одинаковые.
...
Рейтинг: 0 / 0
24.12.2019, 00:21
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907347
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
mayton
Я заранее знаю формулу которая порождает ключи.
Например ключи - это всегда даты 2015-01-01. Или некие комбинации даты и суммы.
За использование "осмысленного" ключевого материала полагается расстрел из рогатки.
Ключ должен быть (псевдо)случайным "и здесь нет темы для обсуждения".
Как надёжно зашифровать ключ на коротком пароле - отдельная тема.
...
Рейтинг: 0 / 0
24.12.2019, 07:02
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907364
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
По сути мне надо найти любую символьную последовательность которая удовлетворяет первому
хешу ad52bb899f98da83ad1a5ddd6eeae1f210757c1ef27df945f4d264ed29b9f3cd. Не обязательно она должна
быть ключом Ondertrouwd8. Это может быть любая другая последовательность. Не суть.

Я хочу сэкономить. Я не хочу вращать циклы. Я заранее знаю формулу которая порождает ключи.
Например ключи - это всегда даты 2015-01-01. Или некие комбинации даты и суммы.

Тут ты сам себе противоречишь. Или у тебя хэш от 12 символов любых буквоцифр или дата. В первом случае 64^12 вариантов, во втором 737 300 (365*2020). Второй элементарно перебирается без всяких оптимизаций.

mayton
Я заранее знаю формулу которая порождает ключи.

Если ее знаешь, то хэш обратим и проблемы нет, взял и посчитал по формуле, получил ключ.

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

mayton
Я хочу выиграть время. Я хочу находить ключ менее чем за 10 минут. Большее время - я потерял деньги.
Уложился в 9 минут - заработал.

Считаем:

Размер одной записи таблицы 9 (ключ) + 32 (хэш) = 43 байта
Допустим таблица 4.3 Тб (4.3*10 12 ), т.е. 10 11 записей
Всего у тебя 4.7*10 21 (64 12 ) вариантов ключа, следовательно в одной записи цепочка из 4.7*10 10 пар {ключ, хэш}

Для получения ключа по хэшу требуется пройти всю цепочку (движение возможно только слева направо, а надо сделать шаг назад), поэтому прикидываем минимальную скорость: 4.7*10 10 / 600 сек. = 78 млн. раз в секунду делать редукцию и считать хэш. Плюс по-началу еще надо каждый хэш искать в таблице пока не найдем.

В принципе скорость 7.8*10 7 вполне достижимая, т.е. можно получить ключ менее чем за 10 минут, но давай прикинем время построения таблицы с такой же скоростью. Допустим мы изобрели супер оптимальный алгоритм когда хэш каждого ключа считается однократно: 4.7*10 21 / 7.8*10 7 = 6*10 13 секунд = 694.4 млн дней = 1.9 млн лет. И это идеальный алгоритм, реальный будет намного хуже, т.к. потребует повторных рассчетов, кроме того при распараллеливании Закон Амдала сработает.
...
Рейтинг: 0 / 0
24.12.2019, 08:56
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907366
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Нужен перерыв.
...
Рейтинг: 0 / 0
24.12.2019, 09:07
| Ответить | Цитировать | Написать  
Тяпничный криптунЪ и редукция
    #39907406
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Пока надо отъехать назад. Короткий брейншторм.

Alpha-num - множество символов латиницы + цифры. 26 + 26 + 10 = 62

Пишу на псевдо-языке.

Код: sql
1.
2.
3.
$ alpha-num-generator length=6 >> alphanum-keys.csv

$ select column(1) from csvfile(alphanum-keys.csv) order by SHA1(column(1)) >> alphanum-keys-ordered-sha1.csv


Я получил файл ключей ранжированных по хешу. И возможность вести поиск любого ключа
или доказать что в базе нет ключа соотвевтвующего данному хешу.

Длина файла:

Код: sql
1.
62^6 = 56 800 235 584 ~ 52Гб.



52 Гигабайта сортированных по хешу ключей. Грубо говоря за 36 итераций дихотомического поиска
я в этом файле нахожу любой ключ либо доказываю что его нет.

Теперь - размер. Для 6 символьных ключей - да. Еще можно понять. Но для 12 символьных размер
этого файла получается неподъемным.
...
Рейтинг: 0 / 0
24.12.2019, 11:09
| Ответить | Цитировать | Написать  
25 сообщений из 90, страница 1 из 4
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничный криптунЪ и редукция
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39907347&tid=1339856]:
 0ms
get settings:
 10ms
get forum list:
 16ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 37ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 66ms
get tp. blocked users:
 1ms
others: 237ms
total:  389ms
созд. / загр.: 389ms
x
x
Закрыть


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