유한 상태 기계 (Finite State Machine, FSM)

유한 상태 기계(Finite State Machine, FSM)는 유한한 양의 저장 공간 또는 상태, 상태 값 간의 전이, 그리고 상태의 어떤 함수로서의 출력으로 구성된 일반적인 수학적 계산 모델입니다. FSM은 한 시점에 정해진 상태 중 하나에만 있으며, 입력이 들어오면 정해진 규칙에 따라 다음 상태로 옮겨 갑니다. nonce 또는 메시지 키 값을 위한 진정한 난수 생성기를 제외하고, 암호화의 모든 계산은 유한 상태 기계이며 따라서 완전히 결정적입니다.

장점:

• 단순성: FSM은 이해하고 구현하기 비교적 간단하여 광범위한 애플리케이션에 적합합니다.
• 예측 가능성: 동일한 입력과 초기 상태가 주어지면 FSM은 항상 동일한 출력을 생성하므로 결정적이고 예측 가능합니다.
• 분석 가능성: FSM의 동작은 공식적으로 분석할 수 있으므로 기능의 검증 및 유효성 검사가 가능합니다.

단점:

1. 제한된 메모리: FSM은 유한한 양의 메모리를 가지고 있어 광범위한 데이터 저장이 필요한 복잡한 작업을 처리하는 능력이 제한될 수 있습니다.
2. 상태 폭발: 문제의 복잡성이 증가함에 따라 FSM의 상태 수는 기하급수적으로 증가하여 설계 및 구현 문제가 발생할 수 있습니다.
3. 비결정성 처리의 어려움: FSM은 내재적인 무작위성 또는 예측 불가능한 동작을 가진 시스템을 모델링하는 데 어려움을 겪습니다.

응용 분야:

FSM은 다음과 같은 다양한 분야에서 응용됩니다.

• 디지털 회로 설계: 순차 논리 회로의 모델링 및 설계.
• 소프트웨어 엔지니어링: 상태 기반 시스템, 파서 및 정규 표현식 엔진 구현.
• 통신 프로토콜: 통신 프로토콜의 상태 및 전이 정의.
• 게임 개발: 비플레이어 캐릭터(NPC) 및 게임 상태의 동작 제어.

예시로 이해하기: 자판기

자판기는 FSM의 좋은 예입니다.

• 상태: 기계가 가질 수 있는 다양한 “모드”를 생각해 보세요. 돈을 기다리는 중, 간식을 내보내는 중, 또는 고장 난 상태입니다. 이것들이 바로 “상태”입니다.
• 전이: 동전을 넣으면 기계가 “기다리는 중”에서 “배출하는 중”으로 이동합니다. 사용자의 행동으로 일어난 전이입니다.
• 출력: 나오는 과자(또는 오류 메시지)는 현재 상태와 전이에 의해 결정되는 출력입니다.

일상 속의 FSM

일상에서 볼 수 있는 FSM의 예는 다음과 같습니다.

1. 신호등: 빨간색, 노란색, 녹색 – 각 빛은 상태를 나타내며 타이머가 전이를 결정합니다.
2. 텍스트 편집기: “Caps Lock”을 누르면 입력 방식이 바뀝니다. 입력 상태를 제어하는 FSM입니다.

이것이 왜 중요할까요?

FSM을 이해하면 컴퓨터가 정의된 상태와 전이를 기반으로 정보를 처리하고 결정을 내리는 방식에 대한 더 깊은 이해를 얻을 수 있습니다. 실제 활용 범위가 매우 넓은 컴퓨터 과학의 기본 개념입니다.

FSM과 암호화의 세계

암호화의 거의 모든 계산은 FSM에 의존합니다. 왜일까요? FSM은 본질적으로 결정적이기 때문입니다. 이는 동일한 입력과 시작 상태가 주어지면 항상 동일한 출력을 생성한다는 의미입니다. 이러한 예측 가능성은 암호화 알고리즘이 안정적으로 작동하는 데 매우 중요합니다.

예를 들어 암호화 알고리즘을 생각해 보세요. 암호화 알고리즘은 FSM을 사용하여 평문(읽을 수 있는 메시지)을 암호문(읽을 수 없게 암호화된 데이터)으로 변환합니다. 비밀 키에 의해 결정되는 FSM 내의 특정 규칙은 해당 키를 가진 사람만 과정을 되돌려 메시지를 복호화할 수 있도록 합니다.

예외: 진정한 무작위성

다만 예외가 있습니다. 대부분의 암호화 작업은 FSM을 활용하지만 일부 요소는 다음과 같은 진정한 무작위성을 필요로 합니다.

• Nonce: 재생 공격을 방지하는 데 사용되는 고유하고 예측할 수 없는 값입니다.
• 메시지 키: 보안 강화를 위해 단일 메시지를 암호화하는 데 사용되는 임시 키입니다.

이러한 임의 값은 물리적 현상에 의존하는 하드웨어 난수 생성기 등에서 얻은 엔트로피를 바탕으로 생성되므로 외부에서 예측하기 어렵습니다.

간단히 말해서…

암호화는 핵심적으로 유한 상태 기계의 힘에 크게 의존합니다. 정의된 상태와 전이를 가진 이러한 수학적 모델은 안전한 암호화·복호화 과정을 위한 결정론적 기반을 제공합니다. 진정한 무작위성이 특정 시나리오에서 역할을 하지만 암호화 계산의 대부분은 예측 가능하고 안정적인 FSM 특성에 의존하여 디지털 세계를 보호합니다.