학교 과제로 개발한 RSA 프로그램이 있으므로, 이것을 개선하는 쪽으로 개발을 진행할 것이다.
코드는 깃허브에 모두 올려져있다.
개발에 참고한 코드는 여기있다. 많은 부분을 카피했다.
파일명은 encript.py이고 내용은 아래와 같다.
from argparse import ArgumentParser
from util import get_random_prime, get_random_coprime, mod_exp
parser = ArgumentParser(description='RSA암호화')
parser.add_argument('-f', '--file_path', action="store", dest="file_path", type=str, help="file path", default=None)
parser.add_argument('-s', '--str', action="store", dest="str", type=str, default=None)
parser.add_argument('-b', '--block_size', action="store", dest="block_size", type=int, default=2)
def encript_block(data:bytes, e, n, block_size=2):
int_val = int.from_bytes(data, 'big') # 바이트 형식인 data를 int형으로 변환
if int_val >= n: # 값이 n 보다 큰 경우엔 아래와 같이 수행
encripted_int_val = mod_exp(int_val, e, n) + (int(int_val / n) * n)
else:
encripted_int_val = mod_exp(int_val, e, n) # int_val^e % n
return encripted_int_val.to_bytes(block_size, byteorder='big')
def generate_keys(block_size):
# n, O, e, d 값 결정
limit = 256**(block_size/3)
p = get_random_prime(limit) # p는 block^1/3를 넘지 않는 소수
q = get_random_prime(limit) # q는 block^1/3를 넘지 않는 소수
n = p*q
O = (p-1)*(q-1)
e = get_random_coprime(val=O, limit=n) # e는 n보다 작은 O의 서로소
# d는 (e*d) % O == 1인 수
d = 0
for d_tmp in range(1, O):
if (e*d_tmp) % O == 1:
d = d_tmp
break
return (e, n), (d, n) # 개인키, 공개키
def encript(data:bytes, block_size=2):
pri_key, pub_key = generate_keys(block_size)
e = pri_key[0]
d = pub_key[0]
n = pri_key[1]
# data의 길이가 블록사이즈에 맞지 않으면 더미데이터(\x00)을 붙힘
if len(data) % block_size != 0:
data += bytes([0]*(block_size - len(data) % block_size))
encripted_data = bytes() # 암호화된 데이터
for i in range(0, len(data), block_size): # 블럭단위로 반복
encripted_data += encript_block(data[i:i+block_size], e, n, block_size)
return encripted_data, (e, n), (d, n)
def encript_file(path, block_size=2):
pri_key, pub_key = generate_keys(block_size)
try:
rf = open(path, 'rb')
wf = open(path+'.dat', 'wb')
data = 1
while data != b"":
data = rf.read(block_size)
encripted_data = encript_block(data, pri_key[0], pri_key[1], block_size)
wf.write(encripted_data)
finally:
rf.close()
wf.close()
return pri_key, pub_key
if __name__ == '__main__':
args = parser.parse_args()
if args.str:
encripted_val, private_key, public_key = encript(args.str.encode('utf-8'), args.block_size)
print(f'암호화된 값 : {encripted_val}, 개인키 : {private_key}, 공개키 : {public_key}')
elif args.file_path:
private_key, public_key = encript_file(args.file_path, args.block_size)
print(f'개인키 : {private_key}, 공개키 : {public_key}')
위의 코드를 함수별로 하나하나 뜯어보며 개선을 해보자
generate_keys
def generate_keys(block_size):
# n, O, e, d 값 결정
limit = 256**(block_size/3)
p = get_random_prime(limit) # p는 block^1/3를 넘지 않는 소수
q = get_random_prime(limit) # q는 block^1/3를 넘지 않는 소수
n = p*q
O = (p-1)*(q-1)
e = get_random_coprime(val=O, limit=n) # e는 n보다 작은 O의 서로소
# d는 (e*d) % O == 1인 수
d = 0
for d_tmp in range(1, O):
if (e*d_tmp) % O == 1:
d = d_tmp
break
return (e, n), (d, n) # 개인키, 공개키먼저 키값을 생성하는 코드이다.
이전 포스트에서 설명한 수식이 그대로 있지만, 눈 여겨 볼 것이 몇가지 있다.
먼저, get_random_prime과 limit이다.
get_random_prime은 util.py이란 파일에 따로 선언을 해 두었고, 소수를 랜덤으로 가져오는 함수이다.(아래에서 자세히)
여기서 limit은 소수의 한계크기로, p값과 q값이 너무 커지면 n이 한 블럭의 크기(block_size)보다 큰 공간이 필요하므로, 오류가 발생한다.
그래서 limit을 정해 둔 것이다. 처음에는 256*block_size/2 으로 정했지만, 이렇게 하면 다른부분(C > n 인 경우)에서 오류가 생겨서 더 줄였다.
-> 위의 코드에선 block_size에 따라 p, q값을 달리 했지만, 다른 코드를 많이 보니, 그냥 키 길이를 독립적으로 정했고,
bytes길이 단위로 코드를 구성했다.
그래서, generate_keys 함수를 encript.py에서 빼서 따로 key.py 파일을 만든 뒤, block_size가 아닌 키 길이 값을 인자로 받는 함수로 수정한다.
그리고, get_random_prime함수는 다음과 같다.
limit크기보다 작은 소수를 랜덤으로 구해준다.
def get_random_prime(limit):
global prime_list
limit_idx = 0
while limit_idx < len(prime_list):
if prime_list[limit_idx] >= limit:
break
limit_idx+=1
return prime_list[random.randrange(limit_idx)]prime_list는 프로그램 시작시에 미리 '에라토스테네스의 채'로 소수들을 구해놓은 배열이다.
이 함수의 문제점은 실행시간이 오래걸리고, 키 길이가 길어질수록 저장해야 하는 소수도 많아지므로, 메모리도 많이 잡아먹을 것이다.
따라서, '밀러-라빈 소수 판정법'을 이용해서 수정한다.
밀러-라빈 소수 판정법은 완벽하진 않지만, 매우 적은 확률의 오류를 가지고 소수가 아닌지 맞는지 판별해준다.
다음은 d를 구하는 코드이다. 이 코드는 역 모듈러 연산으로 충분히 간소화 시킬 수 있다.
generate_keys(수정 후)
def generate_keys(nbytes: int) -> typing.Turple[PrivateKey, PublicKey]:
""" n, O, e, d 값 결정
p = prime number
q = prime number
n = p * q
O = Phi_n = (p-1)*(q-1)
e = O의 서로소
d, (d*e)%O = 1인 수. (d<O)
-> d%O = (1/e)%O
-> d = e^(O-2)%O
-> d = e^(O-2)%O
"""
p = get_random_prime(nbytes) # p는 nbytes/2길이의 소수
q = get_random_prime(nbytes) # q는 nbytes/2길이의 소수
n = p*q
O = (p-1)*(q-1)
e = get_random_coprime(val=O, limit=n) # e는 n보다 작은 O의 서로소
d = pow(e, O-2, O)
del p, q, O
return PrivateKey(d, n), PublicKey(e, n) # 개인키, 공개키개인키, 공개키를 객체단위로 만들었다.
d를 구하는 식을 단순화 하니 코드가 훨씬 간결해지도 보기 편해졌다.
get_random_prime함수는 다음과 같이 수정했다.
def get_random_prime(nbytes: int) -> int:
assert nbytes > 0 # the loop wil hang on too small numbers
while True:
int_val = get_random_odd_int(nbytes)
# Test if it is a prime number
if is_prime(int_val):
return int_val
# If not, retry간단히 소수인지 아닌지 계속 반복하며 구하는 방식인데, 소수판정 함수는 아래와 같다.
def is_prime(int_val: int) -> int:
# Check for small numbers.
if int_val < 10:
return int_val in [2, 3, 5, 7]
# Check for even numbers.
if not (int_val & 1):
return False
k = get_primality_testing_rounds(int_val)
return miller_rabin_primality_testing(int_val, k)
k값을 구하는 get_primality_testing_rounds함수는 이글을 참고해서 만들었다.
miller_rabin_primality_testing함수는 소수인지 아닌지 k번 반복해서 판정해준다.
* 새로운 함수를 만들면서 알게 된 것인데, 파이썬은 pow함수가 인자를 세개나 받을 수 있다. 마지막 인자는 나머지를 구할때, 쓰는 값으로 modpow같은 함수를 굳이 만들지 않아도 된다.
encrypt, encrypt_block, encrypt_file
def encript_block(data:bytes, e, n, block_size=2):
int_val = int.from_bytes(data, 'big') # 바이트 형식인 data를 int형으로 변환
if int_val >= n: # 값이 n 보다 큰 경우엔 아래와 같이 수행
encripted_int_val = mod_exp(int_val, e, n) + (int(int_val / n) * n)
else:
encripted_int_val = mod_exp(int_val, e, n) # int_val^e % n
return encripted_int_val.to_bytes(block_size, byteorder='big')
def encript(data:bytes, block_size=2):
pri_key, pub_key = generate_keys(block_size)
e = pri_key[0]
d = pub_key[0]
n = pri_key[1]
# data의 길이가 블록사이즈에 맞지 않으면 더미데이터(\x00)을 붙힘
if len(data) % block_size != 0:
data += bytes([0]*(block_size - len(data) % block_size))
encripted_data = bytes() # 암호화된 데이터
for i in range(0, len(data), block_size): # 블럭단위로 반복
encripted_data += encript_block(data[i:i+block_size], e, n, block_size)
return encripted_data, (e, n), (d, n)
def encript_file(path, block_size=2):
pri_key, pub_key = generate_keys(block_size)
try:
rf = open(path, 'rb')
wf = open(path+'.dat', 'wb')
data = 1
while data != b"":
data = rf.read(block_size)
encripted_data = encript_block(data, pri_key[0], pri_key[1], block_size)
wf.write(encripted_data)
finally:
rf.close()
wf.close()
return pri_key, pub_key먼저, 이 함수의 이름부터 좀 수정해야 겠다.
encript가 아니라 encrypt이다.... 내가 코딩했지만 진짜 어이가 없다.
아무튼 넘어가서 encript_block을 주로 설명하겠다.
암호화를 할 값이 n보다 크거나 같은 경우, 암호화시 데이터가 소실되어 버린다.
그래서, 기존에는 n으로 나눈 값을 다시 곱셈해서 암호화된 값에 더해주었다.
이렇게 번거로운 과정을 n을 크게 만들어서 수정한다.
encript함수를 보면 더미데이터를 추가하는 과정이 있다.
복호화를 하고 더미데이터를 구분하기 위해 데이터 끝에 \x00를 붙였다.
하지만, 이런방식은 보안에 좋지 않다.
블럭마다 마크를 달아서 수정한다.
블럭 앞에 \x00x02[더미데이터]\x00[데이터] 순으로 붙이면
복호화 검증도 할 수 있고, 더미데이터도 랜덤한 값으로 할 수 있다. (물론 \x00은 삼가야한다.)
encrypt, encrypt_block, encrypt_file(수정 후)
def encrypt_int(int_val:int, key:PublicKey) -> int:
return pow(int_val, key.e, key.n)
def _pad_data(data: bytes, key_len: int) -> bytes:
max_data_len = key_len - 11
data_len = len(data)
if data_len > max_data_len:
raise OverflowError('%i bytes needed for data, but there is only '
' space for %i' % (data_len, max_data_len))
# Get random padding
padding_len = key_len - data_len - 3
padding = b''
# Padding에 \x00은 넣지 않는다.
# \x00이 나올 경우 지운채로 붙인다.
while len(padding) < padding_len:
needed_padding_len = padding_len - len(padding)
new_padding = os.urandom(needed_padding_len)
new_padding = new_padding.replace(b'\x00', b'')
padding += new_padding
assert len(padding) == padding_len
return b''.join([b'\x00\x02',
padding,
b'\x00',
data])
def encrypt_block(data: bytes, key: PublicKey) -> bytes:
"""data를 암호화한다.
- overflow를 방지하기 위해 다음을 만족해야 한다.
len(data) <= len(key) + 11
- 11인 이유는
(오버플로우 방지 1바이트)8 + (패딩 비트)3
"""
key_len = get_bytes_length(key.n)
padded = _pad_data(data, key_len)
int_data = int.from_bytes(padded, byteorder='big')
encrypted = encrypt_int(int_data, key)
block = encrypted.to_bytes(key_len, byteorder='big')
return block
def encrypt(data: bytes, key: PublicKey) -> bytes:
key_len = get_bytes_length(key.n)
max_data_len = key_len-11
encrypted = b''
for i in range(0, len(data), max_data_len):
encrypted += encrypt_block(data[i:i+max_data_len], key)
return encrypted
def encrypt_file(src: str, dest: str, key: PublicKey):
key_len = get_bytes_length(key.n)
max_data_len = key_len-11
try:
rf = open(src, 'rb')
wf = open(dest, 'wb')
data = 1
while data != b"":
data = rf.read(max_data_len)
encrypted_data = encrypt_block(data, key)
wf.write(encrypted_data)
finally:
rf.close()
wf.close()더미데이터를 붙이는 부분은 _pad_data함수를 만들어서 코딩했다.
전체적으로 더이상 block_size를 인자로 받지 않으며, key값을 외부로 부터 받아서 암호화를 진행한다.
decript.py도 수정하였다. (어자피 encrypt와 많이 유사하니 수정한 것만 올리겠다)
import os
from util import get_bytes_length
from key import PrivateKey, PublicKey
def decrypt_int(int_val:int, key:PrivateKey) -> int:
return pow(int_val, key.d, key.n)
def decrypt_block(block: bytes, key: PrivateKey) -> bytes:
"""data를 복호화한다.
:overflow를 방지하기 위해 다음을 만족해야 한다.
:len(data) <= len(key) + 11
"""
block_len = get_bytes_length(key.n)
encrypted = int.from_bytes(block, byteorder='big')
decrypted = decrypt_int(encrypted, key)
clear = decrypted.to_bytes(block_len, byteorder='big')
if len(block) > block_len:
raise Exception('Decryption failed')
# 시작 기호를 찾을 수 없으면 오류
if clear[0:2] != b'\x00\x02':
raise Exception('Decryption failed')
# 두번째 기호를 찾을 수 없으면 오류
try:
origin_idx = clear.index(b'\x00', 2)
except ValueError:
raise Exception('Decryption failed')
return clear[origin_idx + 1:]
def decrypt(data: bytes, key: PrivateKey) -> bytes:
block_len = get_bytes_length(key.n)
decrypted = b''
for i in range(0, len(data), block_len):
decrypted += decrypt_block(data[i:i+block_len], key)
return decrypted
def decrypt_file(src: str, dest: str, key: PrivateKey):
block_len = get_bytes_length(key.n)
try:
rf = open(src, 'rb')
wf = open(dest, 'wb')
data = 1
while data != b"":
data = rf.read(block_len)
decrypted = decrypt_block(data, key)
wf.write(decrypted)
finally:
rf.close()
wf.close()짜잔~ 1차 수정은 끝났다.
'프로그래밍 > 암호화 프로그램' 카테고리의 다른 글
| 디피-헬만 키 생성 프로그램(2) - 고민 (0) | 2020.11.06 |
|---|---|
| 디피-헬만 키 생성 프로그램(1) - 이론 (0) | 2020.11.06 |
| RSA 암호화 프로그램(1) - 이론 (0) | 2020.11.02 |
