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

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

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

dnaoyt
cinuertdso
bda
haey
tolpap
...

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

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 ответа

Решение

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

Ваше тело цикла выполняется 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;
   }
}

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

Источник

Я бы сделал что-то подобное с 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
Источник

Вот бесплатное решение, которое я придумал, используя 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"
Источник

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

#!/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, Этот способ "только" ~10k раз называется.

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

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

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

Источник
Другие вопросы по тегам