해싱이란?
input으로 들어온 값이 해싱 함수를 거쳐 일정한 길이의 output으로 나오게 됩니다.
일정한 길이의 output이기 때문에 해싱의 종류에 따라 output으로 나오는 경우의 수는 한정됩니다.
통상적으로 비밀번호의 경우 그 길이 제한이 정해져있지만 통상적으로 hash함수의 input은 거의 무한합니다.
그렇기 때문에 서로 다른 input 값은 우연치 않게 동일한 output 값으로 나올수 있습니다.
하지만 보통의 hash 함수는 확률적으로 널리 퍼지게끔, 한쪽으로 쏠리지 않도록 해싱 알고리즘을 만듭니다.
여기서 해싱의 중요한 점은 알고리즘 자체의 특징에서도 봤듯이 거꿀로 되돌리는게 불가능합니다.
즉 태생적으로 여러개의 input이 같은 output으로 나올수 있으므로 그 역은 정확하게 계산할 수가 없습니다.
그렇기 때문에 되돌릴 필요가 없거나, 복화되서는 안되는 값들 혹은 일정한 Output이라는 장점 때문에
고유값이면서 크기를 한정시키고 싶을 때 사용합니다.(정확하게는 해싱은 고유값을 만들지 않습니다. 가능한 만드는 것 일뿐)
암호화 원리의 정성적인 이해
사실 암호화라는 것은 그 과정을 역으로 되돌리는 것이 복호화기 때문에 암호화 알고리즘(혹은 비밀키값)이 유출되면 역으로 되돌리면 내용이 유출될 수 있습니다.
반대로 해싱처럼 역으로 되돌릴 수 없는 알고리즘을 써버리면 문서를 다시 원복할 수 없으니 통신 목적으로 활용할 수 가 없죠.
해싱은 mod(나눈 나머지) 연산을 응용함으로서 a % 5 = 1 이라고 하면 수 많은 a값을 특정 할 수 없는 점을 이용합니다.
(a가 원문, 1이 해싱된 문장)
즉 알고리즘(혹은 키값)이 유출됬다 할지언정 역계산이 무의미한 알고리즘을 사용합니다.
SSL에서 사용하는 RSA등,현대의 대부분의 암호화 알고리즘은 공개가 되어 있죠?
이미 알고리즘은 모두가 알고 있는 상태에서 문서를 보호하기 위한 개념이 key 입니다., (정확한 수학적 수식은 No~~)
그중 비대칭키 암호화 기법은 마치 해싱과 비슷하게 역방향 연산이 불가능한 방식을 사용합니다.
e.i) 평문 <-> 암호문 이런식으로 a + 2 = 3 이니까 3-2 = 1, 거꾸로 연산하여 a(원문)를 알아내는 방식이 아닌
평문 -> 암호문 -> 평문 f(a, k) = 3 이고 f`(3, k`) = a 이런식으로 key값을 통한 단방향성 계산으로 같은 값이 나오는 방법을 사용하여 복호화 하게됩니다.
현대 가장 강력하다고 알려진 RSA 암/복호화 알고리즘은 mod/정수론을 사용한 방식으로 매우 큰 소수의 인수분해 방식을 사용합니다.
RSA 암호화 알고리즘은 key값을 모르는 상태에서 복호화하기 위해서는 큰 소수의 조합을 찾아야하고 아직까지 bruteforce 방식으로만 해킹이 가능한 것으로 알려져있습니다. 아주큰 bit수를 암호화에 사용할 경우 슈퍼 컴퓨터로도 만년단위로 걸리기 때문에 사실상 key가 유출되지 않는 이상 보안이 뚫리지 않을 것으로 기대합니다.
(포스트 최하단에 비대칭키를 생성 예제 코드있습니다.)
key가 유출되면 아무리 강력한 암호화 알고리즘이더라도 무용지물이지만, 제대로된 해싱 알고리즘은 key 유출과 무관하게 원복이 거의 불가능합니다.
그렇기 때문에 대부분의 서비스들은 사용자의 패스워드같은 민감한 정보는 유출되더라도 해커가 원본으로 원복할 수 없도록 해싱으로 저장하고 서비스 담당자 또한 원본의 패스워드는 알 수 없습니다. (그래서 사용자가 패스워드를 잊은 경우, 운영자는 알려줄 수 없고 새로운 비밀번호로 변경만 가능합니다.)
해싱은 암/복호화에 비해 연산이 가볍고 보안성이 강력하기 때문에 원본 내용의 유출은 상관없고 내용의 위조만 판단하려는 경우 해싱을 통해 sign을 할 수 있습니다. (원본, 해싱본은 공개되어 있고 sign(해싱)시 필요한 Key는 sign하고 위조를 확인하는 주체만 알고 있어야함)
-> ex) JWT
하지만 해싱이라 할지라도 key값의 bit수가 적으면 모든 키값을 bruteforce하게 다 넣어보면서 해킹이 가능할 순 있습니다.
그래서 과거에 쓰이고 사라지는 암호화 알고리즘 대부분 적은 수의 key를 다루기 때무에 컴퓨터 속도가 빨리지면서,
bruteforce 방식으로 뚫리거나, 확률적인 통계 이론으로 bit수에 지수승이 아닌 더 나은 방법으로 try이가 가능하다는 사실이 밝혀지면
암호는 죽게 되어 있습니다.
흔히 암호를 뚫는다는 것은 퍼즐을 더 빨리 끼워맞추는 방식과 다름 없기 때문에 시간이 무한정이라면 언젠간 뚫리게 되어 있습니다.
6개월에 한번씩 비밀번호를 바꾸도록 추천하는 이유가 요즘 일반 서비스들에서 사용하는 pri/pub key의 bit 수를 braceforce 방식으로 뚫으려면 아무리 좋은 컴퓨터를 가져와도 평균 6개월을 써야하기 때문이죠.
(참고, key에 사용하는 bit수가 커질 수록 pri/pub key쌍을 생성하는 시간과 암/복호화에 걸리는 시간이 늘어나기 때문에 무작정 큰 bit를 사용할 수 없습니다.)
비대칭키 생성/사용 예제 코드
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
'Security' 카테고리의 다른 글
| 패스워드 암호화/인증(해싱) 과정 & 중간 패킷 탈취에 대한 오해 (2) | 2021.04.29 |
|---|
댓글