브루트포스 문제 복기하면서 실수한 부분 체크하기1(어디서든 시작할 수 있다)

3129번: 상범이의 은밀한 메세지

 

암호화된 메시지랑 원본 메시지의 일부가 주어질떄, 원본 메시지를 찾는 문제

 

각 메시지에서 알파벳을 0~25로 치환하고 

 

원래 메시지 + 키 = 암호화된 메시지 이기 때문에

 

암호화된 메시지 - 원래 메시지 = 키임을 알 수 있다.

 

여기서 원래 메시지의 일부분만 보여지기 때문에 암호화된 메시지랑 원래 메시지를 비교해서 가능한 모든 키를 구해야한다.

 

예를 들어 암호화된 psinottfn과 원래 메시지 most가 주어지는데 원래 메시지 most는 어디 부분인지 모르니까

 

0번부터 5번까지 most를 비교해보면서 키를 찾는다

 

psinottfn

most

 

psinottfn

  most

 

...

 

for i in range(len(a)-len(b)+1):
    
    K = []

    for j in range(i,i+len(b)):
      
        k = B[j-i] - A[j]

        if k < 0:
            
            k += 26

        K.append(k)

 

 

0~25사이로 만들어야하므로 암호 - 원래가 음수가 나오면 26을 더해줘야한다.

 

이러면 가능한 K가 len(a) - len(b)개만큼 나올텐데 조건을 만족하는 것은 어떻게 찾는가?

 

문제에서 원래 메시지의 일부분의 길이는 키의 2배이상이라고 나와있다.

 

그리고 암호화 할때는 키를 반복해서 이어 붙여서 원래 메시지와 길이를 동일하게 맞춘다고 나와있다.

 

따라서 K가 주기성을 가져야한다

 

K = [0,1,2,3]이면 주기성을 안가지니 안될 것이고 K = [0,1,0,1]은 길이가 2인 주기를 가지니 가능하고

 

K = [0,0,0,0]은 길이가 1인 주기를 가지니 가능

 

K의 길이가 키의 2배 이상이기 때문에 주기는 K의 길이의 절반까지만 가능한 부분

 

find = False

for k in range(1,len(b)//2+1): #주기의 길이

    no = False

    for w in range(len(K)-k):

        if K[w] != K[w+k]: #주기를 만족하는 부분이 하나라도 없으면 NO

            no = True
            break

    if no == False:

        find = True
        break

 

 

조건을 만족하는 K를 찾았으면 k가 키의 길이임을 알 수 있는데 

 

여기서 핵심은 키의 시작부분이 0부터 시작하는 것이 아닐 수도 있다는 점

 

key = [0,1]인데 K = [0,1,0,1]로 나오면 K[0:2] = [0,1]을 찾을 수 있긴 하지만

 

key = [0,1]인데 우연히 K = [1,0,1,0]이 나오면 K[0:2] = [1,0]이라서 이건 키가 아니다

 

그래서 가능한 모든 시작 지점에서 다 찾아봐야함

 

가능한 모든 시작 지점에 대해 K[w:w+k]를 키로 하고 복호화를 해본 다음 실제 메시지가 복호화된 메시지에 존재하면 그것이 정답

 

    if find: #키가 될 수 있는 k,K를 찾았으면
        
        for w in range(len(K)-k+1): #가능한 모든 시작점에 대해

            key = K[w:w+k] #가능한 모든 key를 찾고

            answer = []

            i = 0

            for a in A:

                x = (a + key[i]) % 26
                answer.append(r[x])
                i += 1
                i %= k
            
            answer = ''.join(answer) #키를 이용해서 복호화를 한 다음에

            if b in answer: #원래 메시지가 복호화된 메시지에 존재하는가?
                
                print(answer)
                break
        
        break