페이스텔 암호의 암호화와 복호화 증명

 

페이스텔 암호의 암호화와 복호화 증명

페이스텔 암호는 여러 암호의 기초가 되는 알고리즘이다.
특징이라면 복호화와 암호화 알고리즘이 동일하다.

요즘 네트워크 보안을 공부하고 있는데, 문제를 풀던 중 페이스텔의 복호화가 페이스텔 암호화의 복호화임을 보이라고 해서 풀어보려고 한다.

페이스텔 암호화/복호화의 기본 구조

일반식으로 표현하면 아래와 같다. 암호화와 복호화가 모두 동일하다

• REi-1 = LEi
• REi-1 = LEi-1 ⊕ F(REi-1, Ki) 암호화와 복호화가 왜 동일할까? 방식이 동일하다고 복호화라는 건 논리가 약하고 예외가 발생한다. 조금 더 생각을 해보자
  암호화 과정에서 사용 되는 함수가 self-invertible 속성을 가지고 있기 때문이라고 하는데, 아직 이해가 되지 않는다

페이스텔 암호화와 복호화가 동일하다는 것은 키를 대칭으로 사용하면 같은 값이 나온다는 거다
즉, 암호화된 메시지를 복호화하는 데 동일한 알고리즘이 사용되지만, 키의 순서가 반대로 적용된다
이러한 대칭성을 통해, 암호화 후 복호화 과정을 거치면 원래의 평문이 복원된다

아래의 암호화와 복호화 과정에서, 암호화의 좌우와 복호화의 좌우 식이 대칭으로 같으면 된다

• 암호화: (Li+1, Ri+1) = E(Li, Ri) = (Ri, Li ⊕ f(Ri, ki))
• 복호화: (Li', Ri') = D(Li+1, Ri+1) = (Ri+1 ⊕ f(Li+1, ki), Li+1)

1. Ri' = Li+1 = Ri:
   • 각 라운드에서 복호화의 오른쪽 출력이 암호화의 왼쪽 입력과 동일
2. Li' = Ri+1 ⊕ f(Li+1, ki) = Li ⊕ f(Ri, ki)
   • 각 라운드에서 복호화의 왼쪽 출력은 암호화의 왼쪽 입력과 동일

그림으로 그려서 증명해 봅시다. 예시로 암호화하자마자 복호화하는 상황을 예로 들겠습니다

암호호/복호화 과정을 그림으로 그리면 위와 같은 그림이 나옵니다.
L과 R 옆의 D는 Description의 이니셜입니다

페이스텔 구조의 경우 한 번 암호화할 경우 L과 R을 바꾸지 않습니다
아래는 복호화에 대한 증명입니다.

결국 이론상, 복호화했을 때 값이 같으면 됩니다.
R은 쭈욱 물려받기만 하니 계산이 쉬웠는데 L은 그거보다 조금 더 복잡합니다.

 

여기서 XOR을 유심히 봐야 합니다. XOR을 2번 하니 F(K, R0)이 사라지는데, XOR의 경우, 순서가 바뀌어도 성립합니다

즉 복호화 과정에서 키를 거울 모드로 입력하기만 하면, 복호화가 된다는 것이 자명합니다