[현대 암호학] 03. 실습(3)

현대 암호학

[현대 암호학] 03. 실습(3)

Uggjjini 2021. 6. 22. 12:39

[실습] 영어 문장 감지 프로그램 분석하기

메시지 문자열이 영어인지 알아내는 한가지 방법은 각 공백마다 메시지를 작은 문자열로 나누고, 각 하위 문자열이 사전에 있는 단어인지 확인하는 것이다. 메시지의 하위 문자열이 사전 파일에 있는지 확인하는 is_english() 함수를 작성한다.

detectEnglish.py

###!/usr/bin/python3
#
# 영어 감지 모듈
#
# (0) 준비 : dictionary.txt (45,000 단어 이상이 포함된 사전파일이다.)
# (1) 입력 : message
# (2) 출력 : True|False (영어인지 확인)
# (3) 기능 :
# * 문자열을 입력 받고, 영어인지 확인(사전 파일에 존재하면)하여 맞으면 True, 틀리면 False return
# * 메시지의 하위 문자열이 사전 파일에 있는지 확인 하는 is_english() 함수을 작성한다.
# * is_english() 함수는 20% 이상의 단어가 사전 파일에 있고
# * 문자열의 85%가 영문자 또는 공백이면 영어 문자열이라고 판정한다.
# (4) 사용법 :
# import detectEnglish
# detectEnglish.is_english(someString)
# -> return True|False
 
 
UPPER_LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
# 사전 파일과 비교할 대상이 되는 대문자, 소문자, 공백문자의 종류들 구성
LETTERS_AND_SPACE = UPPER_LETTERS + UPPER_LETTERS.lower() + ' \t\n'
 
 
def load_dictionary():
# input : 사전파일(EX: dictionary.txt)
# output : dict(english_words) - 사전 파일이 들어 있는 영어 단어 dictionary
# function : 사전 파일을 입력으로 받아서 dict 객체(english_words)에 넣는다.
fd = open('dictionary.txt')
english_words = {}
for word in fd.read().split('\n'):
english_words[word] = None
fd.close()
return english_words
 
 
ENGLISH_WORDS = load_dictionary()
 
 
def remove_none_letters(message):
# input : str(message)
# * 입력받는 메시지
# output : str(''.join(letters_only))
# * 대문자, 소문자, 공백문자 인지를 확인한 문자열, 나머지 문자열은 제외된다.
# function:
# * 문자열(plaintext)를 입력 받아서 한글자씩 쪼갠 후 문자표(LETTERS_AND_SPACE)
# * 들어 있는 확인하고,
# * 맞으면 리스트(letters_only)에 넣고 string으로 변환하여 return 한다.
letters_only = [] # 대소문자 + 공백을 포함한 단어를 저장할 공간
for symbol in message: # message 안에 문자를 symbol에 넣고
if symbol in LETTERS_AND_SPACE: # 대문자, 소문자, 공백문자인지를 확인하여
letters_only.append(symbol) # 그런 종류만 letter_only list에 넣는다.
 
return ''.join(letters_only) # string으로 변환하여 return
 
 
def get_english_count(message):
# input : str(message)
# output : float(matches) / len(possible_words)
# function: 문자열(message) 입력 받아서
#
 
# 대문자로 변경한 후 점검 가능한 문자열만을 모은다.
message = message.upper() # 무조건 대문자로 변환
# 점검 가능한 문자열(대/소문자 + 공백문자)만 뽑아서 message 저장
message = remove_none_letters(message)
 
possible_words = message.split()
# 다음 코드는 0으로 나누기 에러를 회피하기 위한 코드 부분이다.
if not possible_words: # if possible_words == []:
return 0.0 # 단어가 없으면 0.0을 return 한다.
 
matches = 0
for word in possible_words:
if word in ENGLISH_WORDS:
matches += 1
 
return float(matches) / len(possible_words)
 
 
def is_english(message, word_percentage=20, letter_percentage=85):
# input : str(messages), int(word_percentage), int(letter_percentage)
# output : bool(words_match and letters_match)
# function :
# * is_english() 함수는 20% 이상의 단어가 사전 파일에 있고
# * 문자열의 85%가 영문자 또는 공백이면 영어 문자열이라고 판정한다.
 
# (1) message의 20% 이상의 단어가 사전 파일에 있으면 True, 아니면 False
# 결과가 word_percentage 패러미터보다 크거나 같으면 word_match에 True 저장
# 그렇지 않으면 word_match에는 False 저장
words_match = bool(get_english_count(message) * 100 >= word_percentage)
 
# (2) 문자열의 85%가 영문자 또는 공백이면 True, 아니면 False
num_letters = len(remove_none_letters(message))
message_letters_percentage = float(num_letters) / len(message) * 100
# 결과가 letter_percentage 패러미터보다 크거나 같은면 message_match에는 True 저장
# 그렇지 않으면 message_match에는 False 저장
letters_match = bool(message_letters_percentage >= letter_percentage)
 
# (3) 둘다 참일때만 True, 그렇지 않으면 False return
return words_match and letters_match

[참고] detectEnglish.py 파일을 가지고 디버깅하는 방법

<F8>

[실습] 아핀 암호(Affine Cipher)를 구현하기 위한 모듈러 연산 모듈

시저 암호(Caesar Cipher) : C = (P + K) mod 26

곱셈 암호(Multiplication Cipher) : C = (P * K) mod 26

아핀 암호(Affine Cipher) : C = (P * K1 + K2) mod 26

여러 실습에서 사용할 cryptomath.py 파일을 작성해 보자.

아핀(Affine) 암호 = 곱셈암호 + 시저 암호(카이사르 암호)

아핀 암호 구현을 위한 필요 지식

나머지 연산(modular)
최대 공약수(GCD, Greatest Common Divisor)

1) 나머지 연산

(수 학) 10 mod 3 : 10을 3으로 나눈 나머지

(파이썬) 10 % 3

2) 최대 공약수를 찾는 유클리드 알고리즘

용어: 약수, 공약수, 최대공약수

2000년 전의 수학자 유클리드(Euclid)는 나머지 연산을 통해 두 수의 GCD를 찾는 간단한 알고리즘을 고안했다.

파이썬으로 유클리드 알고리즘 구현 => 복수 할당문 사용

-------------------------------------

def gcd(a, b):

while a != 0:

a, b = b % a, a

return b

-------------------------------------

(예) 유클리드 알고리즘 확인(손으로 풀어 보기)

만약 a = 24, b =32 라면,

a의 약수 : 1, 2, 3, 4, 6, 8, 12, 24

b의 약수 : 1, 2, 4, 8, 16, 32

a, b의 공약수 : 1, 2, 8

a, b의 최대 공약수 : 8

(예) 유클리드 알고리즘 확인(프로그램으로 확인)

만약 a = 24, b =32 라면,

첫번째 loop 돌 때(a != 0)

a , b = b % a , a

a , b = 32 % 24 , 24

a , b = 8 , 24

두번째 loop 돌 때(a != 0)

a , b = b % a , a

a , b = 24 % 8 , 8

a , b = 0 , 8

따라서, return 8

아핀 암호(Affine Cipher)의 암호화

C = (P * K1 + K2) mod len(symbols)

(조건) K1, len(symbols)는 서로소 관계이어야 한다.

암호화 과정

(ㄱ) 평문을 K1으로 곱셈

(ㄴ) K2를 더함

(ㄷ) 심볼 집합 크기로 나머지 연산

아핀 암호(Affine Cipher)의 복호화

P = {(C - K2) * K1-1} mod len(symbols)

(조건) K1, len(symbols)는 서로소 관계이어야 한다.

복호화 과정

(ㄱ) 암호문에서 K2를 뺀다.

(ㄴ) K1의 모듈러 역수 연산

(ㄷ) 심볼 집합 크기로 나머지 연산

[참고] 두 숫자(a mod m)의 모듈러 역수란?

a, b의 모듈러(modular)

= a mod m

= a % m

a, m : 두 숫자, i : 모듈러 역수

두 숫자 (a mod m)의 모듈러 역수는 (a * i) % m == 1 만족하는 i 값이다.

(예) 두 숫자 (5 % 7) 의 모듈러 역수는

(5 * i) % 7 == 1 식을 만족하는 i 값이다.

i = 1 (5 * 1) % 7 != 1

i = 2 (5 * 2) % 7 != 1

i = 3 (5 * 3) % 7 == 1

따라서, (5 % 7)의 모듈러 역수 3이다.

유클리드 확장 알고리즘을 이용한 모듈러 역수 구하기

findModInverse(a, m) 함수를 반드시 이해할 필요는 없다.

------------------------------------------------------------------------------------------------

def findModInverse(a, m):

if gcd(a, m) != 1:

return None # a, m 두수가 서로소 관계가 아니면 모듈러 역수가 없다.

u1, u2, u3 = 1, 0, a

v1, v2, v3 = 0, 1, m

while v3 != 0:

q = u3 // v3 # (주의) //은 정수 난눗셈 연산자이다.

v1, v2, v3, u1, u2, u3 = (u1 -q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3

return u1 % m

---------------------------------------------------------------------------------------------------

cryptomath.py

def gcd(a, b):
    # 유클리드 알고리즘으로 a와 b의 GCD(최대 공약수)를 return 한다.
    while a != 0:
        a, b = b % a, a

    return b


def find_mod_inverse(a, m):
    # "a * x % m = 1"을 만족하는 a와 m의 모듈러 역수를 return 한다.

    if gcd(a, m) != 1:
        return None     # a와 m이 서로소 관계가 아니면 모듈러 역수가 없다.

    # 확장 유클리디안 알고리즘으로 계산한다.
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3    # "//"은 정수 나눗셈 연산자이다.
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3

    return u1 % m

[실습] 아핀 암호 암호화/복호화 프로그램 제작

아핀 암호의 암호화

C = (P * K1 + K2) mod len(symbols)

(조건) K1, K2에 대한 몇가지 조건

K1 = 1 이면 안된다. 곱셈하는 의미가 없어지기 때문이다.

K2 = 0 이면 안된다. 덧셈하는 의미가 없어지기 때문이다.

K2 < len(symbols)

곱셈 암호 방식은 K1, len(symobs)는 서로소 관계이어야 한다.(ex: gcd(K1, len(symbols) == 1)

아핀 암호의 복호화

P = {(C - K2) * K1(-1)} mod len(symbols)

(조건) K1, K2에 대한 몇가지 조건(암호화 조건과 같다.)

K1 = 1 이면 안된다. 곱셈하는 의미가 없어지기 때문이다.

K2 = 0 이면 안된다. 덧셈하는 의미가 없어지기 때문이다.

K2 < len(symbols)

곱셈 암호 방식은 K1, len(symobs)는 서로소 관계이어야 한다.(ex: gcd(K1, len(symbols) == 1)

아핀 암호의 키의 범위

왜 K2 < len(symbols) 관계이어야 하는가? 다음 실습을 통해 확인한다.

아핀 암호의 K2의 범위는 len(symbols) 이어야 한다.

이것은 K2가 심볼의 크기를 넘게 되면 모듈러 연산 때문에 다시 처음으로 돌아 오게 되기 때문이다.

=> K2 > len(SYMBOLS) - 1

아핀 암호에서 K1과 len(SYMBOLS)는 최대 공약수가 1이어야 한다.

affineCipher.py

#!/usr/bin/python3
#
# 아핀 암호
#
# (0) 준비 : cryptomath.py
# (1) 입력 : 평문 메시지, 암호화 키, 모드(encrypt|decrypt)
# (2) 출력 : 암호화문 또는 복호화문
# (3) 기능 : 아핀 암호를 사용하여 암호화하고 복호화 할 수 있는 프로그램을 제작한다.

import sys

try:
    import cryptomath
except Exception as e:
    print("Error: % s" %e)
    sys.exit(1)

SYMBOLS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890 !?.'

def main():
    # Affine Cipher :
    #   * Encryption: C = ((P * K1) + K2) mod len(symbols)
    #   * Decryption: P = ((C -K2) * K(-1)) mod len(symbols)
    mymessages = "A computer would deserve to be called intelligent if it could deceive a human into believing that it was human. -Alan Turing"
    mykey = 2894

    myencrypted = affine_cipher_encrypt('encrypt', mymessages, mykey)
    mydecrypted = affine_cipher_decrypt('decrypt', myencrypted, mykey)

    print("My massages :", mymessages)
    print("MY Encrypted:", myencrypted)
    print("My Decrypted:", mydecrypted)


def affine_cipher_decrypt(mode, msgs, key):
    # input : str(mode==encrypt|decrypt), str(msgs), int(key)
    # output: decrypted
    # function:
    # * P = ((C -K2) * K1(-1)) mod len(symbols)
    key_a, key_b = get_key_parts(key)
    check_keys(key_a, key_b, mode)

    mod_inverse_of_key_a = cryptomath.find_mod_inverse(key_a, len(SYMBOLS))
    # print(key_a, key_b, mod_inverse_of_key_a)
    decrypted = ''
    if mod_inverse_of_key_a is not None:
        for char in msgs:
            # print(char)
            if char in SYMBOLS:
                # P = ((C -K2) * K1(-1)) mod len(symbols)
                char_index = SYMBOLS.find(char)
                plain_index = ((char_index - key_b) * mod_inverse_of_key_a) % len(SYMBOLS)
                decrypted += SYMBOLS[plain_index]
            else:
                decrypted += char

    return decrypted

def affine_cipher_encrypt(mode, msgs, key):
    # input : str(msg), int(key)
    # output: encryption_str(encrypted)
    # function:
    #   * C = ((P * K1) + K2) mod len(symbols)
    key_a, key_b = get_key_parts(key)
    # print(key_a, key_b)
    check_keys(key_a, key_b, mode)
    # print(key_a, key_b)

    decrypted = ''
    for char in msgs:
        # print(char)
        if char in SYMBOLS:
            # C = ((P * K1) + K2) mod len(symbols)
            char_index = SYMBOLS.find(char)
            cipher_index = (char_index * key_a + key_b) % len(SYMBOLS)
            decrypted += SYMBOLS[cipher_index]
        else:
            decrypted += char

    return decrypted

def check_keys(a, b, m):
    # input : int(a), int(b), str(m=encrypt|decrypt)
    # output: error messages
    # function: 취약한 키 점검
    if m == 'encrypt' and a == 1:
        sys.exit('Cipher is weak if key A is 1. Choose a different key.')
    if m == 'encrypt' and b == 0:
        sys.exit('Cipher is weak if key B is 0. Choose a different key.')
    if a < 0 or b < 0 or b > len(SYMBOLS)-1:
        sys.exit('Key A must be greater than 0 and key B must be between 0 and %d' % (len(SYMBOLS) - 1))
    if cryptomath.gcd(a, len(SYMBOLS)) !=1:
        sys.exit('key A (%s) and the symbol set size (%s) are not relatively prime. Choose a different key.' % (a, len(SYMBOLS)))



def get_key_parts(key):
    # input : int(key)
    # output: tuple(key_a, key_b)
    # function: 하나의 키를 입력 받아서 2개의 키(아핀암호에서 사용할 2개의 키)를 생성한다.
    key_a = key // len(SYMBOLS)     # 10 / 3 = 3 ... 1
    key_b = key % len(SYMBOLS)

    return key_a, key_b

if __name__ == '__main__':
    main()

[실습] 아핀 암호 크랙 프로그램

시저 암호(Caesar Cipher) : C = (P + K) mod 26

곱셈 암호(Multiplication Cipher) : C = (P * K) mod 26

아핀 암호(Affine Cipher) : C = (P * K1 + K2) mod 26

아핀 암호 = 곱셈 암호 + 시저 암호

아핀 암호는 키가 수천개로 제한되기 때문에 무차별 대입법으로 쉽게 공격할 수 있다.

affineHacker.py

#!/usr/bin/python3
#
# 2. 아핀 암호 해킹
#
# (0) 준비 : dictionary.txt, affineCiper.py, detectEnglish.py, cryptomath.py
# (1) 입력 : 아핀 암호을 이용한 암호화된 메시지(my_message)
# (2) 출력 : 아핀 암호 해킹을 통해 얻은 평문
# (3) 기능 : 암호문을 입력으로 받아서 아핀 암호 해킹을 통해 평문을 얻는다.

import sys

try:
    import affineCipher
    import detectEnglish
    import cryptomath
except Exception as e:
    print("Error:", e)
    sys.exit(1)

def main():
    mymessages = """5QG9ol3La6QI93!xQxaia6faQL9QdaQG1!!axQARLa!!AuaRLQADQALQG93!xQxaGaAfaQ1QX3o1RQARL9Qda!AafARuQLX1LQALQI1iQX3o1RNQ-5!1RQP36ARu"""

    mydecrypted = hack_affine(mymessages)
    if mydecrypted is not None:
        print('hacked messages output: ')
        print(mydecrypted)
    else:
        print('Fail to hack encryption')


def hack_affine(msgs):
    print('Hacking started.')
    print('Press <CTRL + C> or <CTRL + D> to quit at any time.')

    for key in range(len(affineCipher.SYMBOLS)+1, len(affineCipher.SYMBOLS)**2):
        # print(key)
        key_a, key_b = affineCipher.get_key_parts(key)
        if cryptomath.gcd(key_a, len(affineCipher.SYMBOLS)) != 1:
            continue
        # print(key_a)
        decrypted = affineCipher.affine_cipher_decrypt('decrypt', msgs, key)
        print('Tried key %s |%s|' % (key, decrypted[:40]))

        if detectEnglish.is_english(decrypted):
            print()
            print('Possible encryption hack:')
            print('Key: %s' % key)

            print('Decrypted plaintext: ' + decrypted[:200])
            print()
            print('Enter D for done, or just press Enter to continue hacking.')
            response = input('> ')

            if response.strip().upper().startswith('D'):
                return decrypted


if __name__ == '__main__':
    main()

'현대 암호학' 카테고리의 다른 글

[현대 암호학] 04. 대칭(Symmetric) 암호 -1. 문자 암호에서 비트열 암호로 (0)	2021.06.22
[현대 암호학] 03. 실습(4) (0)	2021.06.22
[현대 암호학] 03. 실습(2) (0)	2021.06.22
[현대 암호학] 03. 실습(1) (0)	2021.06.21
[현대 암호학] 03-4. 전치 암호와 치환 암호 (0)	2021.06.21

현재글[현대 암호학] 03. 실습(3)

Ugg's White hat

해당 블로그는 순수 공부 목적으로 만들어졌습니다.

피싱, it보안, 워게임, 출입인증, njRAT, 타이포 스쿼팅, webhacking.kr, 사이버보안, 모바일 출입카드, 사건사고, IT 보안, ASEC 분석팀, 정보보안, challenge(old), 스미싱, 해킹, 성형외과, 정보보호, 해킹 이메일, challenge (old),

Today :
Yesterday :

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Ugg's White hat