Python - генерирует отклонения от string.ascii_lowercase

Question

Python - генерирует отклонения от string.ascii_lowercase

1

Я нашел некоторые алгоритмы онлайн, чтобы генерировать нарушения в Python, но они все экспоненциальны по сложности, и в результате я не могу заставить их сходиться с набором из 26 элементов (алфавита)!

Итак, я пытаюсь найти способ улучшить следующий код (источник здесь):

def derangement(vs):
    l = [None for x in vs]
    sol = set()
    sol.add(tuple(l))
    for v in vs:
        sol1 = set()
        for s in sol:
            for (i, v1) in enumerate(s):
                if not v1 and v != vs[i]:
                    s1 = list(s)
                    s1[i] = v
                    sol1.add(tuple(s1))
        sol = sol1
    return list(sol)

Если кому-то интересно, это для решателя шифрования подстановки. Я пытаюсь понять, сколько времени требуется для шифрования шифрования!

2rs2ts 15 июнь 2011, в 04:25

Источник

0

Число перестановок растет экспоненциально (или, точнее, факториально). Каждый алгоритм, генерирующий все перестановки из n объектов, является Ω (n!).
Sven Marnach 15 июнь 2011, в 02:17
0

Вы проверили модуль itertools ?
JBernardo 15 июнь 2011, в 02:18
0

Sven, itertools.permutations создает список всех перестановок практически мгновенно.
2rs2ts 15 июнь 2011, в 02:18
0

У меня Бернардо, он ничего не дает за невменяемость. Просто перестановки. Это недействительно для шифров замещения.
2rs2ts 15 июнь 2011, в 02:19
0

@user: itertools.permutations() возвращает ленивый итератор. Попробуйте list(itertools.permutations(string.lowercase)) .
Sven Marnach 15 июнь 2011, в 02:21
3

да, но вы можете сделать помехи из permutations с помощью одной строки кода
JBernardo 15 июнь 2011, в 02:26
1

Свен, ты мог предположить, что мое окружение защитило бы меня, но это на самом деле сломало мой компьютер.
2rs2ts 15 июнь 2011, в 02:34
1

@user: Очень жаль. Это не сломало мой (я тоже пытался), и это определенно не должно разбить любой компьютер.
Sven Marnach 15 июнь 2011, в 02:47
0

Это сожрало всю мою память и процессор, и я даже не был в состоянии ctrl-alt-del, поэтому я бы не сказал «любой» компьютер;)
2rs2ts 15 июнь 2011, в 02:54

Показать ещё 7 комментариев

Теги:

python

encryption

cryptography

brute-force

2 ответа

1

Не обязательно, это зависит от того, какой шифр вы используете. Если вы используете Caesar cypher, который, я уверен, вы этого не сделали, вам нужно всего лишь попробовать все 26! Перестановки, а затем найдите один * (s) с реальными словами, но я уверен, что вы имеете в виду для vigenere cypher, и в этом случае вы берете весь первый набор перестановок, и вы кладете их в ряды аналогичной фракции и находите эти перестановки, а затем перекрестная проверка словарных слов, и тогда вы, вероятно, получите очень длинный список возможных сообщений, и вам придется сортировать те, которые имеют смысл.

Justin 02 фев. 2012, в 19:01

0

это сдвиговые шифры, подстановочный шифр - это шифр, в котором ключ представляет собой отображение алфавита на перестановку алфавита, то есть A = C, B = Q, C = T ...
2rs2ts 08 фев. 2012, в 17:49

Ещё вопросы

Число перестановок растет экспоненциально (или, точнее, факториально). Каждый алгоритм, генерирующий все перестановки из n объектов, является Ω (n!).
Sven, itertools.permutations создает список всех перестановок практически мгновенно.
У меня Бернардо, он ничего не дает за невменяемость. Просто перестановки. Это недействительно для шифров замещения.
@user: itertools.permutations() возвращает ленивый итератор. Попробуйте list(itertools.permutations(string.lowercase)) .
да, но вы можете сделать помехи из permutations с помощью одной строки кода
Свен, ты мог предположить, что мое окружение защитило бы меня, но это на самом деле сломало мой компьютер.
@user: Очень жаль. Это не сломало мой (я тоже пытался), и это определенно не должно разбить любой компьютер.
Это сожрало всю мою память и процессор, и я даже не был в состоянии ctrl-alt-del, поэтому я бы не сказал «любой» компьютер;)
это сдвиговые шифры, подстановочный шифр - это шифр, в котором ключ представляет собой отображение алфавита на перестановку алфавита, то есть A = C, B = Q, C = T ...

JBernardo · Accepted Answer · 2011-06-14T23-40-00.000Z

Поскольку алгоритмы перестановок - это Ω (n!), ничто не приведет к сближению вашего кода. Это может быть быстрее, но это ничего не значит для вещей такой сложности:

import itertools
def derangement(x):
    p = itertools.permutations(x)
    return (i for i in p if not any(i[k] == x[k] for k in range(len(x))))

Это ленивый итератор. Если вам нужны все значения (я сомневаюсь, что вам нужно) просто list() it

Я не знал, что это ленивый итератор, так что спасибо за поддержку и оптимизацию. Я полагаю, что с помощью универсального компьютера брутфорс заменительного шифра - это выстрел в темноте!