Частотный анализ: разбираем одно из любимых заданий участников online-этапа NeoQUEST-2020

Частотный анализ: разбираем одно из любимых заданий участников online-этапа NeoQUEST-2020

Сегодня публикуем врайт-ап задания NeoQUEST-2020 , о котором наши участники писали: «4 таск мега крутой» и «Лучшая задача олимпиады».
Несмотря на внешнюю простоту, это задание прошли всего 8 человек! А теперь и ты сможешь познакомиться с ним поближе, для этого — welcome под кат!


Итак, участникам предлагается скачать аудиозапись . Минуты прослушивания вполне достаточно, чтобы понять, что азбукой Морзе здесь даже не пахнет, ровно как и осмысленные слова в аудиозаписи тоже не наблюдаются. Поэтому пытку прослушиванием мы заканчиваем и начинаем смотреть на звук более детально. Например, с помощью старой-доброй (и бесплатной) Audacity . Открываем аудиозапись и обращаем внимание на её структуру: между нажатиями клавиш – абсолютная тишина (повезло же кому-то с условиями работы, никаких тебе телефонных звонков и вечно болтающих коллег!), а, значит, не составит труда извлечь каждое отдельное нажатие, отфильтровав участки с нулевой амплитудой сигнала.



Окей, допустим, это сделали. Теперь у нас есть две вещи: «массив», в котором 100500 нажатий, и надежда, что среди этих звуков есть повторяющиеся – ведь только тогда можно будет утверждать, что «клавиша X была нажата N раз, а клавиша Y – M раз». Итак, все исходные данные проанализированы, осталось ответить на вопрос «к чему нас приведет такой набор утверждений при условии, что аудиозапись длится 10 минут?». Да, всё верно, настанет пора расчехлять классический частотный анализ . Что ж, проверяем нашу теорию с помощью python, numpy и scikits.audiolab (для обработки звука с тем же успехом можно выбрать любой другой пакет и даже язык).
Для настройки окружения можно выполнить следующие команды (точно работает на Ubuntu 19.10):

$ sudo apt-get install -y python python-dev python-pip python-setuptools libsndfile-dev python-numpy $ pip install --upgrade pip $ pip install scikits.audiolab 


Теперь воплощаем проверку нашего предположения в несколько строк кода, использующего самый примитивный способ идентификации звука нажатия – по сумме значений соответствующего numpy-массива:

get list of separated ‘clicks’ data, fs, enc = scikits.audiolab.wavread(filename) data = data.ravel() clicks = [list(g) for k, g in groupby(data, lambda x: x != 0) if k]  # calculate number of unique ‘clicks’ and their frequences freqs = dict()  cypher_test = list() for click in clicks:     value = np.sum(np.array(click), dtype = np.float32)     cypher_test.append(value)     if value not in freqs:         freqs[value] = 1     else:         freqs[value] += 1


Результат выполнения кода, показанный на диаграмме – как тепло костра посреди ядерной зимы – не может не греть по крайней мере душу: 27 уникальных нажатий, да еще и внешний вид распределения внушает уверенность в том, что частотный анализ тщетным не будет.



Согласно Википедии и другим более надежным источникам, 26 букв английского языка, отсортированные в порядке уменьшения встречаемости, образуют ряд etaoinshrdlcumwfgypbvkjxqz. Плюс, конечно же, пробел, который занимает лидирующую позицию. Ты знаешь, что делать! Вновь используем несколько строк примитивного кода для сопоставления каждого звука нажатия своей букве (по частоте встречаемости) и проведения первичной замены:

COMMON_FREQ_ALPHABET = { 0:' ', 1:'e', 2:'t', 3:'a', 4:'o', 5:'i', 6:'n', 7:'s', 8:'h', 9:'r', 10:'d', 11:'l', 12:'c', 13:'u', 14:'m',15:'w', 16:'f', 17:'g', 18:'y', 19:'p', 20:'b', 21:'v', 22:'k', 23:'j', 24:'x', 25:'q', 26:'z' }  # calculate key key = dict() index = 0 for freq in sorted(freqs.items(), key=operator.itemgetter(1),reverse=True): key[freq[0]] = COMMON_FREQ_ALPHABET[index] index +=1  # replace sounds according the key partly_plain_text = "" for elem in cypher_test: 	partly_plain_text += key[elem] 


После замены по частотному анализу получаем следующий текст:

onlineayvinf saty stw vltn selg kird moaher csctl ncmertl we tnswer utn metscre gtll saory retl enocfh worb ltrfe tvvetr tftin vltue scn satra zero gtua t gew rotd sveuitl vroklem etsa ketcay idet who lef ipere saone retuh vrodcua uca fipe reuord scre aoob jcesaion oca dcrinf vtss dry ahen show low lisa kltub okxeuas low lifha old frow wtauh aowtrd suhool my frow well heta norah mile mcsa resa tdd tmonf yocnf kesa kird beev kird gooa smtll wts bnow oca utme uca vltna some when bnow awo how dripe tftin vca while oaher some ocr letrn satr mincae digger men scrgtues infor retd hetrd lisa rtin utll vora yes whta idet ftme bind new him old deev eta keftn keftn or socah ahe some mtv tkle sonf i metn saory yetr fold mile dtrb eqtmvle world gish tfe geel ahocstnd one mile his ky ahe tkope ahose uhildren rtin gcll gtll tnimtl ury vocnd vltue ahose shora jciub where ahocfh saood fopern sorry i gorfoa i vromised ao lend yoc my uode fea ia grom my fiahck neoscveruoder htnd ahese binf wind utrb new vossikle tdd grom saood lifha down lipe mincae rotd foa satra gire ahocfh ahose some scn aia iaeai aet iaeai aia iaeai aet iaeai aia iaeai aet iaeai aia iaeai aet iaeai aia iaeai aet iaeai aia iaeai aet iaeai ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa ucn shoa shtbe wtpe ltke nibe shtbe wtpe ltke nibe shtbe wtpe ltke nibe shtbe wtpe ltke nibe shtbe wtpe ltke nibe shtbe wtpe htn mtd dou htn mtd dou htn mtd dou htn mtd dou htn mtd dou htn mtd dou htn mtd dou htn mtd dou htn mtd dou htn dou gipe yet gipe yet gipe yet gipe yet gipe yet gipe yet gipe yet gipe yet gipe yet gipe yet gipe yet gipe yet gipe

На что-то осмысленное он похож мало, но отдельные слова определенно угадываются. Последовательно поищем слова, в которых очевидно, какую замену следует провести:
  1. moaher → mother и tnswer → answer, т.е. a и t надо поменять местами;
  2. larfe → large и selg → self, т.е. f и g надо поменять местами;
  3. kird → bird, т.е. k заменим на b и onlinetyving → onlinetyping, т.е. v заменим на p;
  4. meascre → measure и enocgh → enough, т.е. u и c надо поменять местами.

В результате этих манипуляций текст разительно преображается, а его первое слово объясняет отсутствие связности: аудиозапись была записана во время отработки скоропечатания на клавиатурном тренажере. Эх, владелец ключа явно не к апокалипсису готовился!.. Можем за него порадоваться, вероятно сейчас он очень быстро перебирает пальцами, разгребая снег, заваливший выход из его убежища. Но нам-то что с этого? Пробежимся глазами по тексту, может всё-таки найдется что-то полезное.

onlinetyping stay saw plan self bird mother usual numeral we answer can measure fall story real enough worb large appear again place sun start zero fact a few road special problem east beauty idea who leg ipere stone reach product cut gipe record sure toob juestion out during pass dry then show low list blacb obxects low light old grow watch toward school my grow well heat north mile must rest add among young best bird beep bird foot small was bnow out came cut plant some when bnow two how dripe again put while other some our learn star minute differ men surfaces ingor read heard list rain call port yes what idea game bind new him old deep eat began began or south the some map able song i mean story year gold mile darb eqample world fish age feel thousand one mile his by the abope those children rain full fall animal cry pound place those short juicb where though stood gopern sorry i forgot i promised to lend you my code get it from my github neosupercoder hand these bing wind carb new possible add from stood light down lipe minute road got start fire though those some sun tit iteti tea iteti tit iteti tea iteti tit iteti tea iteti tit iteti tea iteti tit iteti tea iteti tit iteti tea iteti cun shot cun shot cun shot cun shot cun shot cun shot cun shot cun shot cun shot cun shot cun shot cun shot cun shot shabe wape labe nibe shabe wape labe nibe shabe wape labe nibe shabe wape labe nibe shabe wape labe nibe shabe wape han mad doc han mad doc han mad doc han mad doc han mad doc han mad doc han mad doc han mad doc han mad doc han doc fipe yea fipe yea fipe yea fipe yea fipe yea fipe yea fipe yea fipe yea fipe yea fipe yea fipe yea fipe yea fipe

Похоже нам повезло: во время тренировки некто отвлекся и написал спасительное сообщение своему знакомому, вероятно, в какой-нибудь мессенджер: sorry i forgot i promised to lend you my code get it from my github neosupercoder. Читать чужую переписку, конечно, нехорошо, но тут стопроцентное исключение, за эту информацию мы заплатили более чем достаточно. Переходим на github и ищем репозиторий по имени пользователя:



Успех! Остается лишь прочитать единственный файл из репозитория «neo-medicine»:



Ура! Теперь мы — счастливые обладатели ключа!
Впереди — разборы других заданий NeoQUEST-2020 — мы же не дадим нашим читателям скучать на самоизоляции!
Alt text
Комментарии для сайта Cackle