Убедитесь, что пароль не содержит слов в словаре

Question

Я планирую реализовать решение на Java, которое проверяет, не содержит ли пароль пользователя слова из словаря, будь то английский, испанский, немецкий или французский.

У меня есть список слов отсюда: FTP: //ftp.openwall.com/pub/wordlists/languages/English/

Я думаю использовать HashMap или использовать кеш, такой как redis, который будет содержать все слова из словаря в качестве слов. Хотя это может быть неэффективно.

Какой будет лучший способ имплементации?

Answer 1

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

Вы можете получить реализацию дерева в org.apache.commons.collections4. Смотри https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/Trie.html

С помощью trie вам нужно будет собрать его из словаря и сохранить в памяти. Затем вам нужно будет пройти строку справа налево и посмотреть, сможете ли вы найти результаты в дереве. Если результатов не найдено, то в словаре нет частей пароля, которые есть в словаре.

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

Если вы хотите использовать три Apache Commons в проекте Maven, используйте эту зависимость импорта:

<!-- https://mvnrepository.com/artifact/org.apache.commons/commons-collections4 -->
<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-collections4</artifactId>
    <version>4.0</version>
</dependency>

Вот простой игрушечный пример, который находит слова словаря в строке "hellothere":

import com.google.common.collect.ImmutableMap;
import org.apache.commons.collections4.Trie;
import org.apache.commons.collections4.trie.PatriciaTrie;
import org.apache.commons.collections4.trie.UnmodifiableTrie;

import java.util.ArrayList;
import java.util.Map;
import java.util.stream.IntStream;

public class TrieDict {

    public static void main(String[] args) {
        Trie<String, String> trie = new UnmodifiableTrie<>(new PatriciaTrie<>(fillMap()));
        String pwd = "hellothere";
        System.out.println(extractDictMatches(trie, pwd));
    }

    // Provides a dictionary
    private static Map<String, String> fillMap() {
        return ImmutableMap.<String, String>builder().
                put("there", "there").
                put("is", "is").
                put("word", "word").
                put("here", "here").
                put("hell", "hell").
                build();
    }

    private static ArrayList<String> extractDictMatches(Trie<String, String> trie, String pwd) {
        return IntStream.range(0, pwd.length()).collect(ArrayList::new, (objects, i) -> {
            String suffix = pwd.substring(i);
            IntStream.rangeClosed(0, suffix.length()).forEach(j -> {
                String suffixCut = suffix.substring(0, j);
                if (suffixCut.length() > 2) {
                    if (trie.containsKey(suffixCut)) {
                        objects.add(suffixCut);
                    }
                }
            });
        }, (objects, i) -> {
        });
    }
}

Это распечатает:

[hell, there, here]