HackCTF Classic Cipher -3

사용해야하는 지식: affine cipher

 

공식:

val = (a*p+s) % 26 
p는 각 알파벳의 인덱스 
예를 들어 'a'인 경우 인덱스는 [0]

 

Cipher

FqyeYBX{Yv4kk1y_Y1lfgt_1k_jgti_g4ki_1x91cqx14x}

공식에 의거하여 추출한 딕셔너리

{'0': ['0, 7'], '1': ['1, 2'], '2': ['2, 23'], '3': ['3, 18'], '4': ['4, 13'], '5': ['5, 8'], '6': ['6, 3'], '7': ['7, 24'], '8': ['8, 19'], '9': ['9, 14'], '10': ['10, 9'], '11': ['11, 4'], '12': ['12, 25'], '13': ['13, 20'], '14': ['14, 15'], '15': ['15, 10'], '16': ['16, 5'], '17': ['17, 0'], '18': ['18, 21'], '19': ['19, 16'], '20': ['20, 11'], '21': ['21, 6'], '22': ['22, 1'], '23': ['23, 22'], '24': ['24, 17'], '25': ['25, 12']}

딕셔너리를 통해 Cipher 각 인덱스 찾은 결과물

플래그 형태 HackCTF임을 알고 있기 때문에 7바이트만으로 규칙을 찾을 수 있다.

upper enc value = F / a = 0 / s = 7
upper enc value = F / a = 1 / s = 2
upper enc value = F / a = 2 / s = 23
upper enc value = F / a = 3 / s = 18
upper enc value = F / a = 4 / s = 13
upper enc value = F / a = 5 / s = 8
upper enc value = F / a = 6 / s = 3
upper enc value = F / a = 7 / s = 24
upper enc value = F / a = 8 / s = 19
upper enc value = F / a = 9 / s = 14
upper enc value = F / a = 10 / s = 9
upper enc value = B / a = 10 / s = 9
upper enc value = X / a = 10 / s = 9
upper enc value = F / a = 11 / s = 4
upper enc value = F / a = 12 / s = 25
upper enc value = F / a = 13 / s = 20
upper enc value = F / a = 14 / s = 15
upper enc value = F / a = 15 / s = 10
upper enc value = F / a = 16 / s = 5
upper enc value = F / a = 17 / s = 0
upper enc value = F / a = 18 / s = 21
upper enc value = F / a = 19 / s = 16
upper enc value = F / a = 20 / s = 11
upper enc value = F / a = 21 / s = 6
upper enc value = F / a = 22 / s = 1
upper enc value = F / a = 23 / s = 22
upper enc value = Y / a = 23 / s = 22
upper enc value = B / a = 23 / s = 22
upper enc value = X / a = 23 / s = 22
upper enc value = F / a = 24 / s = 17
upper enc value = F / a = 25 / s = 12
lower enc value = q / a = 23 / s = 22
lower enc value = y / a = 23 / s = 22
lower enc value = e / a = 23 / s = 22

 

Solve

알파벳이 대문자 일 경우, 대문자로만 치환되며

알파벳이 소문자 일 경우, 소문자로만 치환된다.

#!-*-encoding:utf-8-*-
enc = "FqyeYBX{Yv4kk1y_Y1lfgt_1k_jgti_g4ki_1x91cqx14x}"
# block, { } 숫자 고정

'''
지식: affine cipher
val = (a*p+s) % 26 
p는 각 알파벳의 인덱스 
예를 들어 'a'인 경우 인덱스는 [0]
'''
import string 
target = "HackCTF"
# H의 경우 인덱스 [7]
# 즉, p는 7 

tmp_upper = string.ascii_uppercase
tmp_lower = string.ascii_lowercase
p = 7
offset = 0
flag = -1
'''
while(offset < len(target)):
    for a in range(0,26):
        for s in range(0,26):
            #print(f'test = {type(ord(target[offset]))}')
            #exit(0)
            if(ord(enc[offset]) >= 65 and ord(enc[offset]) <= 90):
                val = (a*tmp_upper.find(enc[offset])+s) % 26
                flag = 0 # upper 
            elif(ord(enc[offset]) >= 97 and ord(enc[offset]) <= 122):
                val = (a*tmp_lower.find(enc[offset])+s) % 26
                flag = 1 # lower 
            elif(ord(enc[offset]) == 95 or ord(enc[offset]) == 123 or ord(enc[offset]) == 125):
                offset += 1
                continue
            elif(ord(enc[offset]) == 49 and ord(enc[offset]) == 57):
                offset += 1
                continue
            if(val > 26):
                val %= 26
            
            try:
                if(flag==0): # upper 
                    if(tmp_upper[val] == target[offset]): # 하나 만족하는게 있다면 
                        print(f'enc\'s index = {tmp_upper.find(enc[offset])} / enc val = {tmp_upper[tmp_upper.find(enc[offset])]} / a = {a} / s = {s} / decode = {target[offset]}') # 0 / 5
                        offset += 1
                    else:
                        #print(f'[fail] a = {a} / s = {s}')
                        continue
                if(flag==1): # lower
                    if(tmp_lower[val] == target[offset]): # 하나 만족하는게 있다면 
                        print(f'enc\'s index = {tmp_lower.find(enc[offset])} / enc val = {tmp_lower[tmp_lower.find(enc[offset])]} / a = {a} / s = {s}  / decode = {target[offset]}') # 0 / 5
                        offset += 1
                    else:
                        continue
            except IndexError as e:
                break
'''
'''
enc's index = 5 / enc val = F / a = 0 / s = 7 / decode = H
enc's index = 16 / enc val = q / a = 1 / s = 10  / decode = a
enc's index = 24 / enc val = y / a = 2 / s = 6  / decode = c
enc's index = 4 / enc val = e / a = 3 / s = 24  / decode = k
enc's index = 24 / enc val = Y / a = 4 / s = 10 / decode = C
enc's index = 1 / enc val = B / a = 4 / s = 15 / decode = T
enc's index = 23 / enc val = X / a = 4 / s = 17 / decode = F
'''
# round 2 
a = 0
s = 0 
t = 0
dict = {}
while(a < 26):
    for s in range(26):
        if(ord(enc[offset]) >= 65 and ord(enc[offset]) <= 90):
            val = (a*tmp_upper.find(enc[offset])+s) % 26
            flag = 0 # upper 
        elif(ord(enc[offset]) >= 97 and ord(enc[offset]) <= 122):
            val = (a*tmp_lower.find(enc[offset])+s) % 26
            flag = 1 # lower 
        elif(ord(enc[offset]) == 95 or ord(enc[offset]) == 123 or ord(enc[offset]) == 125):
            continue
        elif(ord(enc[offset]) == 49 and ord(enc[offset]) == 57):
            continue
        if(val > 26):
            val %= 26
            
        if(flag==0):
            if(tmp_upper[val] == target[offset]): # 하나 만족하는게 있다면 
                dict[str(t)] = [f'{a}, {s}']
                a += 1
                s = 0
                t += 1
            else:
                continue
        if(flag==1):
            if(tmp_lower[val] == target[offset]): # 하나 만족하는게 있다면 
                dict[str(t)] = [f'{a}, {s}']
                a +=1 
                s = 0
                t += 1
            else:
                continue
            
print(dict)
result = 0
cnt = 0
f = open("affine_parse","w")
for key,value in dict.items():
    tmp = value[cnt]
    a= int(tmp.split(",")[0])
    s= int(tmp.split(",")[1].replace(" ",""))
    
    # formula
    # a * 문자인덱스 + s % 26
        # enc= FqyeYBX
        # target = HackCTF
    for i in range(8):
        if(enc[i] >= 'A' and enc[i] <= 'Z'):
            p = tmp_upper.find(enc[i])
            tmp = (a * p + s) % 26
            if(tmp > 26):
                tmp %= 26
            if(tmp_upper[tmp] == target[i]):
                f.writelines(f'upper enc value = {enc[i]} / a = {a} / s = {s}' + "\n")
                
for key,value in dict.items():
    tmp = value[cnt]
    #print(tmp)
    a= int(tmp.split(",")[0])
    s= int(tmp.split(",")[1].replace(" ",""))            
    for i in range(8):
        if(enc[i] >= 'a' and enc[i] <= 'z'):
            p = tmp_lower.find(enc[i])
            tmp = (a * p + s) % 26
            if(tmp > 26):
                tmp %= 26
            
            if(tmp_lower[tmp] == target[i]):
                f.writelines(f'lower enc value = {enc[i]} / a = {a} / s = {s}' + "\n")
        
f.close()
# result : affine_parse를 통해 찾음
a= 23
s= 22

dec = ""
for i in range(len(enc)):
    if(enc[i] >= 'a' and enc[i] <= 'z'):
        tmp = ( a * tmp_lower.find((enc[i])) + s ) % 26
        if(tmp > 26):
            tmp %= 26
        dec += tmp_lower[tmp]
    elif(enc[i] >= 'A' and enc[i] <= 'Z'):
        tmp = ( a * tmp_upper.find((enc[i])) + s ) % 26
        if(tmp > 26):
            tmp %= 26
        dec += tmp_upper[tmp]
    else:
        dec += enc[i]
print(dec)