[컴퓨터 보안] 해싱과 암호화

해싱이란?

input으로 들어온 값이 해싱 함수를 거쳐 일정한 길이의 output으로 나오게 됩니다.

일정한 길이의 output이기 때문에 해싱의 종류에 따라 output으로 나오는 경우의 수는 한정됩니다.

통상적으로 비밀번호의 경우 그 길이 제한이 정해져있지만 hash함수의 input은 이론상 거의 무한합니다. (시간과 자원이 유한할 뿐..!)

그렇기 때문에 서로 다른 input 값이 우연치 않게 동일한 output 값으로 나올수 있습니다.

하지만 보통의 hash 함수는 확률적으로 널리 퍼지게끔, 한쪽으로 쏠리지 않도록 알고리즘을 구현합니다.

여기서 해싱의 중요한 점은 알고리즘 자체의 특징에서도 보았 듯이 거꾸로 되돌리는게 불가능합니다.

즉 태생적으로 여러개의 input이 같은 output으로 나올수 있으므로 그 역은 정확하게 계산할 수가 없습니다.

 

암호화 원리의 정성적인 이해

사실 암호화라는 것은 그 과정을 역으로 되돌리는 복호화 과정이 짝으로 필요하기 때문에 암호화 알고리즘과 비밀키값 등이 유출되면 원본내용(plain text)을 유추할 수 있게됩니다.

반대로 해시처럼 역으로 되돌릴 수 없는 알고리즘을 써버리면 문서를 다시 원복할 수 없으니 통신 목적으로 활용할 수 없죠.

 

해싱은 mod(나눈 나머지) 연산을 응용함으로서 a % 5 = 1 이라고 하면 수 많은 a값을 특정 할 수 없는 점을 이용합니다.

(a가 원문, 1이 해싱된 문장)

즉 알고리즘(혹은 키값)이 유출됐다 할지언정 역계산이 무의미한 알고리즘을 사용합니다. 

 

SSL에서 사용하는 RSA등,현대의 대부분의 암호화 알고리즘은 공개가 되어 있죠?

이미 알고리즘은 모두가 알고 있는 상태에서 문서를 보호하기 위한 개념이 key 입니다., (정확한 수학적 수식은 No~~)

그중 비대칭키 암호화 기법은 마치 해싱과 비슷하게 역방향 연산이 불가능한 방식을 사용합니다.

(그렇다고 해싱과 같지는 않습니다. 비대칭키 기법은 원문을 결국 찾아낼 수 있는 방법이며 성격상 직접적인 역산수가 아니라는 점입니다.)

 

i.e) 평문 <-> 암호문 이런식으로  a + 2 = 3 이니까  3-2 = 1, 거꾸로 연산하여 a(원문)를 알아내는 방식이 아닌

평문 -> 암호문 -> 평문    f(a, k) = 3 이고 f`(3, k`) = a 이런식으로 서로 다른 key값과 알고리즘을 통해 단방향성 계산으로 같은 값이 나오는 방법을 사용하여 복호화합니다. (서로 다른키를 사용하기 때문에 비대칭키 암호화라고 불리움)

 

현대 가장 강력하다고 알려진 RSA 암/복호화 알고리즘은 mod/정수론을 사용한 방식으로 매우 큰 소수의 인수분해 방식을 사용합니다.

(RSA 비/대칭키 추천 블로그)

RSA 암호화 알고리즘은 key값을 모르는 상태에서 복호화하기 위해서는 큰 소수의 조합을 찾아야하고 아직까지 bruteforce 방식으로만 해킹이 가능한 것으로 알려져있습니다. 아주큰 bit수를 암호화에 사용할 경우 슈퍼 컴퓨터로도 만년단위로 걸리기 때문에 사실상 key가 유출되지 않는 이상 보안이 뚫리지 않을 것으로 기대합니다.

(포스트 최하단에 비대칭키를 생성 예제 코드있습니다.)

 

key가 유출되면 아무리 강력한 암호화 알고리즘이더라도 무용지물이지만, 제대로된 해싱 알고리즘은 key 유출과 무관하게 원복이 거의 불가능합니다. (output 값과 key를 알더라도 원문/plaintext를 정확하게 유추할 수 없음, 특히 salt 까지 섞여있다면 사실상 어려움)

그렇기 때문에 대부분의 서비스들은 사용자의 패스워드같은 민감한 정보는 유출되더라도 해커가 원본으로 원복할 수 없도록 해싱으로 저장하고 서비스 담당자 또한 원본의 패스워드는 알 수 없습니다. (그래서 사용자가 패스워드를 잊은 경우, 운영자는 알려줄 수 없고 새로운 비밀번호로 변경만 가능합니다.)

해싱은 암/복호화에 비해 연산이 가볍고 보안성이 강력하기 때문에 원본 내용의 유출은 상관없고 내용의 위조만 판단하려는 경우 해싱을 이용하여 사인(sign)할 수 있습니다. 

=> 원본정보와 해싱된 정보는 공개되어 있고 sign(해싱)시 필요한 Key는 위조를 확인하는 주체만 알고 있어야함

-> ex) JWT

=> jwt는 토큰 헤더 + payload + 해싱값을 짝으로 만듭니다.

=> jwt payload에는 해당 토큰의 권한이나 생성자, 주체 등의 중요한 정보가 있습니다. 이런 정보를 변조할 수 있으면 권한 탈취 가능

=> 토큰을 인증하는 주체는 토큰의 헤더 + 페이로드를 다시 해싱해보고, 사용자가 함께 보낸 해싱값과 비교하여 변조 여부를 확인합니다.

=> 토큰의 사용자는 헤더와 payload 값은 조작할 수 있지만, 해시 키를 모르는 상태에서 정확한 해시값을 만들어낼 수 없습니다.

 

하지만 해싱이라 할지라도 key값의 bit수가 적으면 모든 키값을 bruteforce하게 다 넣어보면서 해킹할 수 있습니다.

그래서 과거에 쓰이고 사라지는 암호화 알고리즘 대부분 적은 수의 key를 다루기 때문에 컴퓨터 속도가 빨리지면서,

bruteforce 방식으로 뚫리거나, 확률적인 통계 이론으로 bit수에 지수승이 아닌 더 나은 방법으로 시도가 가능하다는 사실이 밝혀지면

암호는 죽게 되어 있습니다.

 

흔히 암호를 뚫는다는 것은 퍼즐을 더 빨리 끼워맞추는 방식과 다름 없기 때문에 시간이 무한하다면 언젠간 뚫리게 되어 있습니다.

6개월에 한번씩 비밀번호를 바꾸도록 추천하는 이유가 요즘 일반 서비스들에서 사용하는 pri/pub key의 bit 수를 braceforce 방식으로 뚫으려면 지구 모든 컴퓨터를 동원해도 최소 6개월정도는 소요될 것으로 보기 때문이죠 (물론 날이갈수록 컴퓨터가 많아지고 좋아져서 달라졌을 수도 ㅎㅎ..)

 

+ 참고, key에 사용하는 bit수가 커질 수록 pri/pub key쌍을 생성하는 시간과 암/복호화에 걸리는 시간이 늘어나기 때문에 무작정 큰 bit를 사용할 수 없습니다.

 

---

+ 2025.05.7

일정 기간마다 사용자의 패스워드를 변경하는 것도 중요하지만, 관리자의 key 값을 변경하는 것도 매우 중요합니다.

의외로 대부분의 해킹은 관리자 PC의 관리 미흡으로 인해 관리 서버의 공격을 받는 경우가 많습니다. 무서운 점은 관리자 또한 언제 해킹 당했는지 알 수 없다는 점이죠.

 

이때 key 자체가 유출되면 존재하지도 않았던 plaintext들을 무한이 찍어내는게 가능해지는 말도 안되는 문제가 발생합니다.

 

특히 Root CA 등의 브라우저 인증서들은 탈취될 경우 심각한 인터넷 보안 문제를 만들기 때문에 계속해서 유효기간을 줄이자는 구글과 애플의 입김이 많아지고 있습니다..ㅎㅎ..

(인증서 교체를 자동화하라는데.. 어험~)

 

jwt 등을 운영하는 서비스에서도 해싱키를 주기적으로 교체하는 것이 좋습니다.

저장소에 활성화된 토큰 정보(jti)를 저장하고 있다면 그나마 다행이지만 그 또한 다른 유출된 정보와 함께 변조를 통해 예상치 못한 약점을 파고들 수 있습니다. (만료기한을 늘린다거나)

 

이 모든 건 키 변경을 통해 예방할 수 있습니다.

jwt를 사용하는 서비스라면 이런 키 교체를 고려하여 키 버저닝(versioning)을 구현하는 것이 좋습니다.

  => 해시키로 교체후 새롭게 발급되는 jwt는 신규 키로 해싱

  => 과거 발급된 jwt는 만료기한까지 예전 해싱키로 동작하여 하위호환성 보장

 

---

비대칭키 생성/사용 예제 코드

from math import lcm, gcd


def print_rsa_key(p, q, max_count=None, filter_e_key_count=1):
    L = lcm(p-1,q-1)
    count = 0
    
    key_dict = {}
    
    for i in range(2,L):
        if max_count != 0 and type(max_count) == int and count >= max_count:
            break
        
        if gcd(i,90) == 1:
            d_key = i
            e_keys = []
            for j in range(2,L):
                if d_key*j%L == 1:
                    e_keys.append(j)
            
            if len(e_keys) > 0 and filter_e_key_count <= len(e_keys):
                count += 1
                key_dict[d_key] = e_keys
    
    return {
        'count': count,
        'p': p,
        'q': q,
        'N': p*q,
        'L': L,
        'key':key_dict
    }

def print_rsa_result(rsa_rs: dict):
    print(f"-------- START D/E keys --------")
    for d_key, e_key_list in rsa_rs['key'].items():
        print(f"D_key: {d_key}")
        print(f" >> E/key({len(e_key_list)}):", *e_key_list, end="\n\n")
    print(f"--------  END D/E keys  --------")
    print("p =", rsa_rs['p'])
    print("q =", rsa_rs['q'])
    print("N = p*q =", rsa_rs['N'])
    print("L = lcm(p-1,q-1) =", rsa_rs['L'])
    
def help():
    print("Usage: python3 rsa.py <prime number1> <prime number2> [filter_ekey_count/default 1] [max_count]")

if __name__ == "__main__":
    import sys
    if len(sys.argv) < 3:
        help()
        exit(1)
    
    try:
        p = int(sys.argv[1])
        q = int(sys.argv[2])
        
        if len(sys.argv) >= 4:
            filter_e_key_count = int(sys.argv[3])
        else:
            filter_e_key_count = 0
            
        if len(sys.argv) >= 5:
            max_count = int(sys.argv[4])
        else:
            max_count = None
            
    except Exception:
        help()
        exit(1)
    
    rs = print_rsa_key(p, q, max_count=max_count, filter_e_key_count=filter_e_key_count)
    print_rsa_result(rs)

    print()
    print("# 비대칭키 공식(평문은 N보다 작은 수)")
    print(f"평문 ^ D_key % N = 암호문")
    print(f"암호문 ^ E_key % N = 평문(복호화)")
    
    print("\n")
    print("# 예제")
    last_key = list(rs['key'].items())[-1]
    d_key = last_key[0]
    e_key = last_key[1][-1]
    N = rs['N']
    
    import random
    plain = random.randrange(2, N)
    cipher = plain**d_key%N
    print(f"{plain} ^ {d_key}(D) % {N}(N) =", cipher)
    print(f"{cipher} ^ {e_key}(E) % {N}(N) =", cipher**e_key%N)
    print()
    print(f"plain_text(random): {plain}")
    print(f"cipher_text: {cipher}")

 

출력

$ python3 rsa.py 13 19

-------- START D/E keys --------
D_key: 7
 >> E/key(1): 31

D_key: 11
 >> E/key(1): 23

D_key: 13
 >> E/key(1): 25

D_key: 17
 >> E/key(1): 17

D_key: 19
 >> E/key(1): 19

D_key: 23
 >> E/key(1): 11

D_key: 29
 >> E/key(1): 5

D_key: 31
 >> E/key(1): 7

--------  END D/E keys  --------
p = 13
q = 19
N = p*q = 247
L = lcm(p-1,q-1) = 36

# 비대칭키 공식(평문은 N보다 작은 수)
평문 ^ D_key % N = 암호문
암호문 ^ E_key % N = 평문(복호화)


# 예제
29 ^ 31 % 247 = 146
146 ^ 7 % 247 = 29
plain_text(random): 29
cipher_text: 146
➜  Desktop python3 rsa.py 13 19
-------- START D/E keys --------
D_key: 7
 >> E/key(1): 31

D_key: 11
 >> E/key(1): 23

D_key: 13
 >> E/key(1): 25

D_key: 17
 >> E/key(1): 17

D_key: 19
 >> E/key(1): 19

D_key: 23
 >> E/key(1): 11

D_key: 29
 >> E/key(1): 5

D_key: 31
 >> E/key(1): 7

--------  END D/E keys  --------
p = 13
q = 19
N = p*q = 247
L = lcm(p-1,q-1) = 36

# 비대칭키 공식(평문은 N보다 작은 수)
평문 ^ D_key % N = 암호문
암호문 ^ E_key % N = 평문(복호화)


# 예제
108 ^ 31 % 247 = 186
186 ^ 7 % 247 = 108

plain_text(random): 108
cipher_text: 186
➜  Desktop python3 rsa.py 13 19
-------- START D/E keys --------
D_key: 7
 >> E/key(1): 31

D_key: 11
 >> E/key(1): 23

D_key: 13
 >> E/key(1): 25

D_key: 17
 >> E/key(1): 17

D_key: 19
 >> E/key(1): 19

D_key: 23
 >> E/key(1): 11

D_key: 29
 >> E/key(1): 5

D_key: 31
 >> E/key(1): 7

--------  END D/E keys  --------
p = 13
q = 19
N = p*q = 247
L = lcm(p-1,q-1) = 36

# 비대칭키 공식(평문은 N보다 작은 수)
평문 ^ D_key % N = 암호문
암호문 ^ E_key % N = 평문(복호화)


# 예제
78 ^ 31(D) % 247(N) = 117
117 ^ 7(E) % 247(N) = 78

plain_text(random): 78
cipher_text: 117