BELFRY
Week-1: 작은 문제: 피보나치 수열과 암호화
DSA-알고리즘 스터디
Jan 5, 2022

피보나치 수열

1

1, 1, 2, 3, 5, ...

재귀 (Recursion)

자기 자신을 호출하는 방법이다.

1
2
3
4

def fib2(n:int) -> int:
    if n < 2:
        return n
    return fib2(n - 1) + fib2(n - 2)

재귀를 사용하면 같은 인자에 대한 호출이 중복으로 발생한다. 이는 인자가 커질수록 기하급수적으로 증가한다.

기저 조건(또는 종료 조건)을 설정하지 않으면 무한 재귀 호출의 굴레에 빠질 수 있으므로 조심해야 한다!

메모이제이션 (Memoization)

사전 자료형에 함수의 리턴값을 저장하면 불필요한 호출을 줄일 수 있다.

1
2
3
4
5

memo:dict[int:int] = {0: 0, 1: 1}
def fib3(n:int) -> int:
    if n not in memo:
        memo[n] = fib3(n - 1) + fib3(n - 2)
    return memo[n]

내장 데코레이터인 @lru_cache는 함수의 리턴값을 자동으로 캐싱(저장)할 수도 있다. 데코레이터를 추가하면 최초 호출이 아닌 모든 함수 호출은 캐싱된 결과를 대신 반환한다. maxsize는 캐시할 수 있는 최대 개수를 의미하며, None으로 설정 시 캐싱의 제한이 사라진다.

1
2
3
4
5
6

from functools import lru_cache
@lru_cache(maxsize=None)
def fib4(n:int) -> int:
    if n < 2:
        return n
    return fib4(n - 1) + fib4(n - 2)

기존 재귀 함수와 구조는 같다.

lru : last recently used

튜플 언패킹 (Tuple unpacking)

재귀적으로 해결할 수 있는 문제는 반복문으로 해결할 수도 있다. 튜플 언패킹은 시간적, 공간적 효율의 두 마리 토끼를 모두 잡는 방법이다.

1
2
3
4
5
6
7

def fib5(n:int) -> int:
    if n == 0: return n
    last:int = 0
    next:int = 1
    for _ in range(1, n):
        last, next = next, last + next
    return next

제네레이터 (Generator)

1
2
3
4
5
6
7
8
9

from typing import Generator
def fib6(n:int) -> Generator[int, None, None]:
    yield 0
    if n > 0: yield 1
    last:int = 0
    next:int = 1
    for _ in range(1, n):
        last, next = next, last + next
        yield next

피보나치 함수를 for 반복문에서 사용하는 range와 같은 제네레이터로 만든다면, 이전까지의 모든 결과를 yield할 수 있다.

1
2

for i in fib6(20):
    print(i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

0
1   
1   
2   
3   
5   
8   
13  
21  
34  
55  
89  
144 
233 
377 
610 
987 
1597
2584
4181
6765

처음에는 0과 1을 생성, 이후 튜플 언패킹 방식으로 구한 값을 차례로 yield한다.

깨지지 않는 암호화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from secrets import token_bytes
from typing import Tuple

def random_key(length:int) -> int:
    tb:bytes = token_bytes(length)
    return int.from_bytes(tb, "big")

def encrypt(original:str) -> Tuple[int, int]: # 암호화
    original_bytes:bytes = original.encode()
    original_key:int = int.from_bytes(original_bytes, "big")
    dummy:int = random_key(len(original_bytes))
    encrypted:int = original_key ^ dummy
    return dummy, encrypted

def decrypt(key1:int, key2:int) -> str:
    decrypted:int = key1 ^ key2
    temp:bytes = decrypted.to_bytes((decrypted.bit_length() + 7) // 8, "big")
    return temp.decode()

  • random_key는 secrets 모듈의 token_bytes메서드를 사용해 원본 데이터와 같은 길이의 더미 데이터를 생성한다.

  • encrypt는 두 데이터를 종합해 암호화한다. 결과물로 두 개의 키를 반환한다. (dummy, encrypted)

    original_key, dummy, encrypted중 두 값을 알고 있으면 XOR 연산을 통해 나머지 하나의 값을 알 수 있다.

    1
2
3

    original_key ^ dummy = encrypted
dummy ^ encrypted = original_key
encrypted ^ original_key = dummy

  • 이 성질을 이용해 decrypt로 두 개의 키를 종합해 복호화한다.

    일련의 과정을 거친 반환값이 원래의 값과 같으면, OTP 알고리즘이 정상적으로 작동함을 알 수 있다.

1
2
3
4
5

if __name__ == "__main__":
    original = "One Time Pad!"
    key1, key2 = encrypt(original)
    result:str = decrypt(key1, key2)
    print(original == result)

1

True

Reference