Easyelectronics.ru

Электроника для всех
Текущее время: 23 сен 2019, 18:36

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/10pcs (Любой цвет!)
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 17:42 
Старожил
Аватара пользователя

Зарегистрирован: 13 май 2010, 01:32
Сообщения: 1354
Откуда: Из сказки.
Есть файл с данными от регистратора логического.
Регистратор данных подключен как попало и надо в данных найти символы или слово например: передача

вот: п (207 число)
11001111 - так оно выглядит при правильном раскладе бит
при неправильных может выглядеть так:

10101111
01101111
11111100
...

Как вариант, пусть вот так 11111100 записано в файле.Тоесть перепутаны 0,1,7,5 биты.
В итоге надо чтобы программа умела искать в наборе байт последовательность искомую.

_________________
Береги планету.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 17:52 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 6156
И еще десяток тем?
viewtopic.php?f=56&t=36868


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 18:26 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3287
тупо перебрать все 8! = 40320 возможных перестановок и проверить strstr()?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 20:10 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3619
Ладно, а как мы узнаем, какой порядок битов - именно правильный, по которому и надо искать? Потому что, грубо говоря, практически из любого числа путем перестановок битов можно получить такой байт, который будет равен искомому байту.
Ну, не из любого конечно, но искомый байт будет получаться из многих вариантов.
Чем длиннее искомое слово (как строгий набор байтов), тем больше исключается вариант случайных совпадений, больше отсеивается заведомо неподходящих вариантов. Но это длинная цепочка перестановок и проверок.
В принципе, да. Допустим, искомое слово у нас длиной 12 символов (12 байт). Во всех этих 12 байтах одинаково и одновременно переставляем биты, до тех пор, пока не обнаружим искомое слово. Причем, это надо проделывать по всей длине строки, сдвигаясь на один байт и повторяя перестановки по 12 байт с каждым вновь включенным байтом. Выше там написали, сколько максимум нужно выполнить перестановок для каждого 12-байтного слова.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 20:45 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 6156
Гм. Вообще-то, с вероятностью, близкой к "1", всё можно найти и определить за один единственный проход поиска.
Неее, глупость написал. Достаточно ровно 1 прохода.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 20:48 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2012, 20:35
Сообщения: 2471
u37 писал(а):
Неее, глупость написал. Достаточно ровно 1 прохода.

А можно подробнее?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 20:51 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3619
За один проход? Ну да, если известно, что и сколько перепутано, то да, за 1 проход. Вначале переставляем биты в байтах искомого слова так, чтобы они соотвествовали тому порядку, что записан в массиве. Ну и вперед.
А если правильный порядок битов не известен и нам надо разгадать его? Тогда за 1 проход мы либо угадаем (если очень-очень повезет), либо не угадаем (что чаще всего и случается).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 20:55 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 6156
Да ни вопрос.
Вариант зачеркнутый - шаблон переводится из ASCII символов в "кол-во бит в байте", получается "строка" поиска. Этим "шаблоном" по такому-же принципу проходится по файлу. Результат - с высокой вероятностью найденное место и есть оригинальный шаблон. Остальное декодирование тривиально.
Вариант два - берется первый ASCII символ шаблона и 0 байт файла, сравниваются с морфированием байта. Если совпадение обнаружено - по этому принципу проверяется i+1 и шаблон+1. При ошибке морфировать первый байт дальше. При переборе всех значений (а их не много), перейти к следующему элементу ...
Варианты можно комбинировать (для ускорения), но для PC это "не задача".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 21:00 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 6156
Если вопрос в полной угадайте, сааавсем без шаблона, то один бит я угадаю сразу (подсказка - d5), еще 3 - чуть сложнее. ))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 21:08 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3619
Да угадать то вы угадаете, да вдруг неправильно угадаете, и то, что вы получили для одного байта, не подойдет для другого байта.
Судя по написанному в первом посте, там как раз "угадайка". ТС предположил, что перепутаны биты (номера такие-то). Хорошо, если это так. Но все равно, просто число неизвестных битов максимальных 8 в байте до числа перепутанных битов.

За один проход угадать можно, для этого надо составить энное количество слов, содержащие все варианты перестановок, и сравнивать с каждым из этих слов. Да, так можно. Но при 8! слов очень уж много.


Последний раз редактировалось BusMaster 16 окт 2018, 21:12, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 21:11 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2012, 20:35
Сообщения: 2471
u37 писал(а):
Да ни вопрос.

Спасибо.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 21:15 
Старожил
Аватара пользователя

Зарегистрирован: 30 мар 2015, 23:56
Сообщения: 737
selevo писал(а):
Есть файл с данными.... В итоге надо чтобы программа умела искать в наборе байт последовательность искомую.

Подсказка иррациональные числа + миксер данных = самый совершенный на данный момент алгоритм шифрования. Базовый алгоритм простой как валенок, но число вариаций последовательностей - практически бесконечно. Случаев взлома подобного алгоритма - не зарегистрировано. Даже самых простых - по модулю 12.
Его кстати уже стали применять в мк и системах связи. Использование в открытом виде запрещено практически везде, кроме диких племён Африки - у тех просто компьютеров нет. Однако, можно сверху добавить ещё один известный и разрешённый тип шифрования. Для которого у спец служб есть ключи. Прикол в том что они не занимаются дешифровкой всего и вся, ну а если найдут - их проблемы.

Предлагать изобрести механизм взлома подобного алгоритма здесь на форуме - это просто максимальное зло на которое способен selevo.

_________________
Потоковая OS


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 21:17 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 6156
Так, ладно, не интересно.
В текстовом файле, написанном на английском, точно известны два бита - d7=0 (легко находится глазами) и d5=1 (см. самый известный символ " ").
За этим вычисляются символы перевода строки (0D/0A --- один из них может отсутствовать) и разделяются тетрады - d6 и d4 там =0, остается лишь их перестановка. Если в тексте есть цифры (а это заранее известно), по ним (и определенным пробелам и переводам строки) определяется значения d4 и d6. Остается младшая часть байта, которую проще определить по "числам". Например, если выдается время или дата в структуированном формате.
Короче, и без "программы" за пару часов.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 21:21 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3287
https://ideone.com/eiICKo


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 22:16 
Старожил

Зарегистрирован: 23 мар 2017, 14:45
Сообщения: 5787
AVI-crak писал(а):
самый совершенный на данный момент алгоритм шифрования. Базовый алгоритм простой как валенок, но число вариаций последовательностей - практически бесконечно. Случаев взлома подобного алгоритма - не зарегистрировано.
Этот алгоритм еще во времена Великой Отечественной использовался немецкой "Энигмой", и давно уже взломан.

u37 писал(а):
переводится из ASCII символов в "кол-во бит в байте"
А где ТС сказал, что там ASCII? Если у него П=207, то это 1251.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 22:40 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3619
А кто знает, какой речевой текст - правильный? Может там АБЫРВАЛГ или $GPGSA,A,1,,,,,,,,,,,,,9.9,9.9,9.9*30. Между прочим, последнее - это из GPS приемника


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 22:56 
Старожил

Зарегистрирован: 23 мар 2017, 14:45
Сообщения: 5787
Словарь и знает. Вносим в него самые употребительные слова, без которых не может обойтись речь.
Как только стало находиться по словарю больше 50% слов - значит перестановка правильная.
А если не правильная - ну найдется один АБЫРВАЛГ случайно, и всё.
Но, кстати, да, нужно знать на каком языке текст.
Если не знаем, то дело осложняется.
Придется брать статистику кодов: распределение самых употребительных знаков. В каждом языке этот "спектр" свой. По нему можно с некоторой вероятностью определить, какой язык и какие слова, и от этого плясать.
Поэтому в настоящее время такие шифры простых перестановок не используются: их сравнительно легко расколоть для профессиональных криптоаналитиков.
Кстати, чтобы избежать этого способа раскрытия, США во время Второй Мировой перед шифрованием сообщения переводили его на язык навахо, который и среди лингвистов-то мало кто знал :))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 16 окт 2018, 23:56 
Старожил

Зарегистрирован: 27 мар 2015, 01:22
Сообщения: 1432
Кто знает что это?


Вложения:
5004.jpg
5004.jpg [ 111.2 Кб | Просмотров: 649 ]
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 17 окт 2018, 00:08 
Старожил

Зарегистрирован: 23 мар 2017, 14:45
Сообщения: 5787
Сигнатурный анализатор?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 17 окт 2018, 00:42 
Старожил
Аватара пользователя

Зарегистрирован: 13 май 2010, 01:32
Сообщения: 1354
Откуда: Из сказки.
так ,че, ко программу напишет ?
или мне может как-то правильно вопрос гуглу задать ?

ту реально всё примитивно, как уже было отмечено, сначала идет перебор первого байта на соответствие шаблону - числу 207 кодировка не важна в данном случае.
затем, с уже "правильно проставленными битами" сравнивается второй байт со вторым байтом в шаблоне,и дальше..
При записи обычно не меняют проводки на регистраторе, так что постоянно все.
Вся задача сводится к перебору первых двух символов.

_________________
Береги планету.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 17 окт 2018, 01:02 
Старожил
Аватара пользователя

Зарегистрирован: 30 мар 2015, 23:56
Сообщения: 737
Кот495 писал(а):
Этот алгоритм еще во времена Великой Отечественной использовался немецкой "Энигмой", и давно уже взломан.

Ну во первых в энигме использовалось перетасовка букв, а во вторых - механика (барабаны) с конечным количеством вариантов на один оборот!!! При полном цикле всех трёх барабанов - алгоритм повторялся.
С миксером на иррациональных числах повтора не существует чисто физически. Каждая новая точка замены - уникальная. Почитай как это вообще работает, ужаснись.

_________________
Потоковая OS


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 17 окт 2018, 01:09 
Старожил

Зарегистрирован: 27 мар 2015, 01:22
Сообщения: 1432
selevo писал(а):
так ,че, ко программу напишет ?
или мне может как-то правильно вопрос гуглу задать ?

ту реально всё примитивно, как уже было отмечено, сначала идет перебор первого байта на соответствие шаблону - числу 207 кодировка не важна в данном случае.
затем, с уже "правильно проставленными битами" сравнивается второй байт со вторым байтом в шаблоне,и дальше..
При записи обычно не меняют проводки на регистраторе, так что постоянно все.
Вся задача сводится к перебору первых двух символов.

Это скучно, я думал ты брейн-ринг тут устраиваешь
Не надо там никаких переборов, давай файл с данными и последовательность которую искать, чтоб было на чём проверить


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 17 окт 2018, 03:17 
Старожил

Зарегистрирован: 17 дек 2014, 04:38
Сообщения: 677
vt340 писал(а):
Это скучно, я думал ты брейн-ринг тут устраиваешь
Не надо там никаких переборов, давай файл с данными и последовательность которую искать, чтоб было на чём проверить


Честно говоря я не понял, чего хочет ТС, но исходя из его условий - бери любой файл и считай его содержимое "ошибочными битами" и вместо них ставь биты из образца. Для меня задача звучит как - "если в слове ХЛЕБ сделать четыре ошибки, то получится слово ПИВО !".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 17 окт 2018, 07:43 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3619
selevo писал(а):
так ,че, ко программу напишет ?.

О, узнаю Селево, он в своем репертуаре :))) А то по началу, по первому посту я даже усомнился, он ли это, может после длительного отпуска подменили. Ан нет, он :))) Ну что, 500 рублей, как всегда? :))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Ищу прогу поиска слов с перетасовкой бит
СообщениеДобавлено: 17 окт 2018, 09:33 
Старожил

Зарегистрирован: 05 фев 2013, 00:58
Сообщения: 3519
:)


Последний раз редактировалось iev91 19 май 2019, 18:49, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB