Расшифруй слова Challenge - улучшай мое решение - PullRequest
Новая
       8

Расшифруй слова Challenge - улучшай мое решение

0 голосов
/ 14 сентября 2018

Есть вызов Захватить флаг

У меня есть два файла; один с зашифрованным текстом примерно с 550 записями 

dnaoyt
cinuertdso
bda
haey
tolpap
...

Второй файл представляет собой словарь с около 9 000 записей 

radar
ccd
gcc
fcc
historical
...

Цель состоит в том, чтобы найти правильную, расшифрованную версию слова, содержащегося в файле словаря.

Мой подход состоит в том, чтобы отсортировать символы из первого слова из первого файла и затем посмотреть, имеет ли первое слово из второго файла ту же длину. Если так, то рассортируйте их и сравните.

Это мой полнофункциональный bash-скрипт, но он очень медленный. 

#!/bin/bash

while IFS="" read -r p || [ -n "$p" ]
do
    var=0
    ro=$(echo $p | perl -F -lane 'print sort @F')
    len_ro=${#ro}
    while IFS="" read -r o || [ -n "$o" ]
    do
        ro2=$(echo $o | perl -F -lane 'print sort @ F')
        len_ro2=${#ro2}
        let "var+=1"
        if [ $len_ro == $len_ro2 ]; then
            if  [ $ro == $ro2 ]; then
                echo $o >> new.txt
                echo $var >> whichline.txt
            fi
        fi
    done < dictionary.txt
done < scrambled-words.txt

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

[править] Для записей: - в словаре нет анаграмм - чтобы получить флаг, вам нужно экспортировать расшифрованные слова как один большой двоичный объект и сделать из него SHA-хэш (это флаг) - ссылка на ctf для парня, который хотел файлы https://challenges.reply.com/tamtamy/user/login.action

Ответы [ 4 ]

0 голосов
/ 14 сентября 2018

Вам лучше создать словарь поиска (набираемый отсортированным словом) из файла словаря.

Ваше тело цикла выполнено 550 * 9 000 = 4950 000 раз (O (N * M)).

Предлагаемое мною решение выполняет два цикла максимум по 9 000 проходов каждый (O (N + M)).

Бонус: он находит все возможные решения бесплатно. 

#!/usr/bin/perl

use strict;
use warnings qw( all );
use feature qw( say );

my $dict_qfn      = "dictionary.txt";
my $scrambled_qfn = "scrambled-words.txt";

sub key { join "", sort split //, $_[0] }

my %dict;
{
   open(my $fh, "<", $dict_qfn)
      or die("Can't open \"$dict_qfn\": $!\n");

   while (<$fh>) {
      chomp;
      push @{ $dict{key($_)} }, $_;
   }
}

{
   open(my $fh, "<", $scrambled_qfn)
      or die("Can't open \"$scrambled_qfn\": $!\n");

   while (<$fh>) {
      chomp;
      my $matches = $dict{key($_)};
      say "$_ matches @$matches" if $matches;
   }
}

Я не удивлюсь, если это займет всего одну миллионную часть времени вашего решения для предоставленных вами размеров (и оно масштабируется намного лучше, чем ваше, если вы увеличите размеры).

0 голосов
/ 14 сентября 2018

Я бы сделал что-то подобное с gawk 

gawk '
NR == FNR {
    dict[csort()] = $0
    next
}

{
    print dict[csort()]
}

function csort(    chars, sorted) {
    split($0, chars, "")
    asort(chars)
    for (i in chars)
        sorted = sorted chars[i]

    return sorted
}' dictionary.txt scrambled-words.txt
0 голосов
/ 14 сентября 2018

Вот решение без Perl, которое я придумал, используя sort и join: 

sort_letters() {
    # Splits each letter onto a line, sorts the letters, then joins them
    #   e.g. "hello" becomes "ehllo"
    echo "${1}" | fold-b1 | sort | tr -d '\n'
}


# For each input file...
for input in "dict.txt" "words.txt"; do
    # Convert each line to [sorted] [original]
    #  then sort and save the results with a .sorted extension
    while read -r original; do
        sorted=$(sort_letters "${original}")
        echo "${sorted} ${original}"
    done < "${input}" | sort > "${input}.sorted"
done

# Join the two files on the [sorted] word
#   outputting the scrambled and unscrambed words
join -j 1 -o 1.2,2.2 "words.txt.sorted" "dict.txt.sorted"
0 голосов
/ 14 сентября 2018

Я пробовал что-то очень похожее, но немного другое. 

#!/bin/bash

exec 3<scrambled-words.txt
while read -r line <&3; do
   printf "%s" ${line} | perl -F -lane 'print sort @F'
done>scrambled-words_sorted.txt
exec 3>&-

exec 3<dictionary.txt
while read -r line <&3; do
   printf "%s" ${line} | perl -F -lane 'print sort @F'
done>dictionary_sorted.txt
exec 3>&-

printf "" > whichline.txt
exec 3<scrambled-words_sorted.txt
while read -r line <&3; do
   counter="$((++counter))"
   grep -n -e "^${line}$" dictionary_sorted.txt | cut -d ':' -f 1 | tr -d '\n' >>whichline.txt   printf "\n" >>whichline.txt
done   
exec 3>&-

Как видите, я не создаю файл new.txt; вместо этого я создаю whichline.txt только с пустой строкой, где слово не совпадает. Вы можете легко вставить их, чтобы создать new.txt.

Логика, стоящая за сценарием, почти совпадает с логикой вашей, за исключением того, что я звонил perl меньше раз и сохраняю два файла поддержки. Я думаю (но я не уверен), что их создание и циклическое выполнение только одного файла будет лучше, чем ~ 5kk вызовов perl. Этот способ называется "только" ~ 10 000 раз.

Наконец, я решил использовать grep, потому что это (возможно) самый быстрый метод сопоставления регулярных выражений, и при поиске всей строки длина присуща регулярному выражению.

Обратите внимание, что то, что сказал @ benjamin-w, остается в силе, и в этом случае grep ответит плохо, а мне это не удалось!

Надеюсь, это может помочь [:

...