무작위 문자 생성 - 무작위 출력!

위기를 모방하다

이와 같은 것은 3개 문자열 길이의 {a,b} 집합의 모든 순열을 생성하고 섞인 출력을 사용합니다 shuf.

$ printf "%s\n" {a..b}{a..b}{a..b} | shuf
bbb
aab
abb
bba
baa
aba
bab
aaa

이것은 실제로 를 사용하는 것과 관련이 있습니다 sort -R.

숨겨진 무작위화

scriptX인수 목록이 주어지면 와 같은 임의의 목록을 반환하도록 인터페이스를 숨기려는 의도인 경우 crunch별칭이나 쉘 스크립트로 래핑하면 작업이 수행됩니다. 다음을 라는 쉘 스크립트에 넣을 수 있습니다 mycrunch.bash.

#!/bin/bash

crunch "$1" "$2" "$3" | sort -R

실행 가능으로 표시하십시오.

$ chmod +x mycrunch.bash

다음과 같이 실행하세요.

$ ./mycrunch.bash 3 3 ab

스퓨리어스 크런치 출력 필터링

위 스크립트의 명령을 사용하여 grep다음과 같이 이러한 줄을 필터링할 수 있습니다.

crunch "$1" "$2" "$3" | grep -vE "Crunch|0" | sort -R

그러면 "Crunch" 또는 "0" 문자열이 포함된 모든 줄이 무시됩니다.

분석하다

당신이 하고 싶은 일에는 근본적인 어려움이 있습니다.

crunch가능한 모든 줄을 무작위 순서로 출력하려면(모든 줄을 미리 생성하고 OR로 작동하지 않고 ) sort -R이미 shuf인쇄된 줄을 기억해야 합니다. 이 정보를 저장하려면 궁극적으로 모든 행을 저장하는 것만큼 많은 공간이 필요합니다. 아직 인쇄되지 않은 전체 컬렉션에서 행을 무작위로 선택하는 데 필요한 총 계산 노력은 전체 컬렉션을 작업하는 데 필요한 계산 노력과 sort -R비슷합니다 shuf.

crunch엄격한 순서로 행을 생성하기 때문에 이러한 부담 없이 행을 생성할 수 있습니다. 다음 줄을 알려면 명령줄 인수와 현재 줄(그리고 사용된 알고리즘)을 아는 것만으로도 crunch충분합니다 . 내 요점은 crunch이전 줄을 기억할 필요가 없고, 비교하거나 검색할 필요가 없다는 것입니다. 해당 줄이 무엇인지 이미 알고 있고 아직 인쇄하지 않았기 때문에 다음 줄로 빠르게 이동합니다.

직접 시도해 보세요. 0부터 26까지의 모든 숫자를 무작위 순서로(또는 적어도 무작위로 보이는 순서로) 큰 소리로 말해보세요. 반복이나 누락이 없으며 각 숫자는 한 번만 수행됩니다. 서둘러요! 이제 0부터 26까지의 모든 숫자를 자연스럽게 소리내어 말해보세요.

이론적으로 위의 부담 없이 무작위로 보이는 시퀀스를 얻는 방법은 최소한 두 가지가 있습니다.

1. 현재 줄과 명령줄 인수만 알면 내부 알고리즘은 crunch어떻게든 이전 줄(대규모 컬렉션의 경우: 수백만 줄)과 다른 다음 줄을 생성할 수 있으므로 최종 결과는 무작위로 정렬된 것처럼 보입니다. .

2. 사용된 명령줄 인수를 알면 crunch외부 필터는 현재 줄을 가져와 crunch(정렬된 방식으로 작동) 어떤 방식으로든 변환할 수 있으므로 crunch완료되면 최종 결과가 무작위로 정렬된 것처럼 보입니다.

필터 내 또는 필터 내의 알고리즘은 crunch중복이나 누락 없이 가능한 모든 행을 생성해야 합니다. 시드를 제공하여 다음 전체 실행 시 결과가 무작위로 섞이는 것처럼 보이도록 할 수 있습니다. 그런 알고리즘을 만드는 것은 (가능하다면 알고리즘 자체의 부담을 숨기지 않고) 쉽지 않은 작업이라고 생각합니다.

---

그런데 왜?

crunch무차별 대입을 통해 비밀번호를 추측하기 위해 단어 목록을 생성하는 데 일반적으로 사용됩니다. 다음을 통해 생성된 목록을 원한다고 가정합니다.

crunch 9 9

무작위 시퀀스가 ​​정렬된 시퀀스보다 나을 수 있습니까? 실제 비밀번호에 다른 문자가 포함되어 있거나 길이가 다른 경우 목록에 없으며 두 순서 모두 똑같이 나쁩니다. 비밀번호가 다른 것임을 알아내려면 목록 중 하나를 완전히 소모해야 합니다.

실제 비밀번호가 목록에 있으면 운이 좋게도 일찍 목록에 올라올 수도 있고 그렇지 않을 수도 있습니다. 이는 비밀번호 소유자(작성자)가 사용자가 crunch기본 az 순서 문자 세트를 사용할 것이라고 예측하는 경우 의도적으로 az로 시작하는 "영리한" 비밀번호를 선택할 수 z있으며 성공을 지연시킬 뿐이라는 의미입니다. 목록을 어지럽히면 이 전략이 무효화됩니다. 실제 비밀번호는 목록의 앞부분에 가까울 수도 있고 목록의 끝부분에 가까울 수도 있으므로 평균적으로 목록의 절반을 다 소모해야 합니다. 평균적으로 이 작업을 수행하면 로 시작하는 "스마트" 비밀번호를 추측하는 데 약 절반의 시간이 소요됩니다 z.

그렇습니다. 이 경우에는 목록을 다시 정렬하는 것이 도움이 될 것입니다.

하지만 "스마트" 비밀번호 소유자를 속이기 위해 za를 사용하는 것은 어떨까요?

crunch 9 9 zyxwvutsrqponmlkjihgfedcba

이를 통해 비교적 빠르게 "스마트" 비밀번호를 추측할 수 있습니다 z. 하지만 포스터가 예측한다면이것특정 공격을 할 경우에는 차라리 비밀번호를 생성하는 편이 나을 것입니다 a!

수행하는 방법:동전을 던지고 az(앞면) 또는 za(뒷면)를 사용하세요..

모든 비밀번호(정책을 사용하거나 정책 없이 생성됨)에 대해 az는 운이 좋지 않으며 az는 운이 좋지 않고 za는 운이 좋습니다. 따라서 목록에 비밀번호만 있는 경우 더 운이 좋은 순서를 사용할 확률은 50%입니다.일반적으로목록의 절반을 소진해야 합니다.목록을 섞는 것처럼. 동전을 한 번 던지면 어떤 전략도 쓸모 없게 됩니다.

글쎄요, sort -R을 통해 "Crunch will now"로 시작하는 출력 줄 뒤의 모든 내용을 파이프할 수 있습니다. 이와 같이:

crunch 3 3 ab| sed -e '0,/^Crunch will now/d' | sort -R

그래도 이것이 "즉시"로 간주되는지 확실하지 않습니다.

하지만 무작위 출력 라인만 다를 뿐 크런치와 동일한 솔루션이 있을까요?

아니요.

이 문제는 다음 두 단계만으로 해결할 수 있습니다.

1. 가능한 모든 조합 만들기
2. 결과의 무작위 순열 생성

적어도 단일 알고리즘을 사용하여 조합을 생성하지 않는 한 동시에 두 가지를 모두 수행할 수는 없습니다. 다양한 알고리즘이 있어야 하며 프로그램 시작 시 무작위로 하나를 선택하고 이러한 다양한 알고리즘의 최종 결과가 고르게 분포된다는 점에 유의하세요.

어쨌든, 당신이 아무것도 찾을 수 없을 것 같아요단순한, crunch이는 + 와 매우 다릅니다 sort -R.