Home

박스화 과정은 다음과 같이 4개의 과정을 거친다.

• ⦁ step 1. Select k - 1 bound positions for k regions
• ⦁ step 2. Sort the bound positions to decide the range of k regions
• ⦁ step 3. Select a number to decide the number of the last region, and subtract 1 to the number of regions less than or equal to the last number.
• ⦁ step 4. Choose a number randomly in a region, then the number is the cipher message and the regional number is the original message.

각 과정에 대한 세부적인 설명은 다음과 같다.

step 1은 k개의 구역을 정하기 위해 k - 1개의 경계값을 설정하는 과정이다. n개의 숫자를 무작위로 k개의 박스에 나누어 담는다면 그 정보를 키에 일일이 지정해 주어야 하므로 키의 길이가 매우 길어질 것이다. 이를 피하기 위해 {0, 1, 2, …, n - 1}의 집합 A를 k개의 구역으로 구분되도록 k - 1개의 경계값(Bound Position)만을 설정한다. 그림 1의 (a)는 k = 16이고, n = 256일 경우 k - 1에 해당하는 15개의 경계값 정보가 선택된 예시를 나타낸다. 각 숫자에 해당하는 경계값 정보는 키에 저장되며 k - 1개의 경계값은 각각 8비트(⌈ log₂n ⌉ = 8)의 크기를 가지게 된다.

Fig. 1. 
Examples to explain the boxing procedure

step 2는 선택된 k - 1개의 경계값을 오름차순 정렬 후 구간을 결정한다. 그림 1의 (b)의 예시에서 평문 13에 대응되는 암호문의 구간이 0~7이고, 12에 대응되는 암호문의 구간이 8~11인 것을 알 수 있다. 하지만 아직 암호문의 마지막 구간인 249~255에 대응되는 평문의 숫자는 결정되지 않은 상태이다.

step 3은 마지막 구간의 숫자를 결정하는 과정이다. 이 때 선택된 숫자가 0이 아니라면 기존의 숫자(1, 2, …, k - 1 )와 겹치게 된다. 이를 피하기 위해 선택된 숫자보다 작거나 같은 기존의 숫자들은 1씩 뺀 값을 최종적으로 취하게 된다. 그림 1의 (c)에서 처럼 선택된 숫자가 8일 경우 기존에 선택된 1, 2, …, 8 의 숫자들은 0, 1, …, 7 로 변환된다. 그러면 평문의 숫자에 대응되는 암호문의 구간이 최종적으로 결정된다.

step 4는 이들 구간에 속한 값들을 임의 선택하는 과정으로 원시 암호문이 결정된다.

본 방법론에서는 복호화의 복잡도를 더욱 높이기 위하여 행과 열을 각각 뒤섞는 순열 과정을 추가로 실시한다. k = 16이고, n = 256인 경우 박스화 과정을 통해 이진화하여 표현된 원시 암호문은 8비트 단위의 길이를 가지게 된다. 그림 2의 (a)는 {15, 1,⋯, 11}로 구성된 평문을 {54, 228, ⋯, 164 }의 원시 암호문으로 변환한 예시이다. 이를 이진수로 표현화면 4비트 단위의 평문이 8비트 단위의 암호문으로 변경된 것을 확인할 수 있다. 그림 2의 (b)는 8비트 단위의 이진수 암호문을 세로로 나열하여 {문자의 수}×8 크기의 행렬 형태로 나타낸 것이다.

Fig. 2. 
Examples to show the message conversion to a binary form and row/column permutation

우선 행 순열(Row Permutation)은 임의의 행 개수에 대해 순번을 교환하는 작업을 수행한다. 그림 2의 (b)는 l = 4인 경우를 예로 든 것이다. 4개의 암호문 단위로 (1, 2, 3, 4)→(3, 1, 4, 2)의 순열 과정을 거치는 것을 확인할 수 있다. 만일 l의 개수를 메시지 송수신자가 알고 있다면 마지막 순열 (4)→(2)는 저절로 결정된다. 따라서 키에 포함되는 행순열의 정보는 (3, 1, 4)로 충분하다. 이 경우 각각의 행 순열 정보를 이진화하여 표현할 경우 ⌈ log₂l ⌉ = 2비트가 필요하므로 l은 2의 거듭제곱인 경우 행 순열 과정에 필요한 키의 길이를 절약할 수 있다.

열 순열(Column Permutation)의 경우도 비슷하게 진행된다. 8비트(n = 256) 암호문을 선택하였으므로 열 순열을 위해 7개의 키가 필요하다. 그림 2의 (b)는 (1, 2, 3, 4, 5, 6, 7, 8) → (7, 1, 8, 2, 4, 5, 3, 6)인 순열을 나타내고 있다. 따라서 키에 포함되는 열순열의 정보는 (7, 1, 8, 2, 4, 5, 3)의 7개가 된다. 행 순열과 마찬가지로 각각의 숫자 정보를 이진화하여 표현할 경우 ⌈ log₂ ⌈ log₂n ⌉ ⌉비트가 필요하므로 ⌈ log₂n ⌉이 2의 거듭제곱인 경우 키의 길이를 절약할 수 있다. 즉 n이 2의 거듭제곱의 거듭제곱인 경우 키의 길이를 절약할 수 있는 것이다. 만일 2⁸ = 256 < n ≤ 512 = 2⁹인 경우(⌈ log₂n ⌉이 2의 거듭제곱이 아닌 경우)를 예로 들면, 박스화 과정에서 경계값을 9비트로 표현해야 한다. 그러면 9비트로 이진화된 원시 암호문의 열 순열은 ⌈ log₂9 ⌉ = 4 (= ⌈3.169... ⌉)비트 크기의 숫자 8개가 필요할 것이다. 또 다른 예로 512 < n ≤ 1024 이면 박스화 과정의 경계값을 10비트로 표현해야 한다. 위의 경우와 마찬가지로 이진화된 원시 암호문의 열 순열은 ⌈ log₂10 ⌉ = 4비트 크기의 숫자 9개가 필요할 것이다. 앞의 예처럼 열 순열을 4비트로 표현할 수 있는 n의 값은 257부터 65,636까지 가능하므로(⌈ log₂⌈ log₂n ⌉ ⌉ = 4), 열 순열을 4비트로 표현하면서도 n의 값을 65,536 미만으로 설정하는 것은 키의 길이 낭비가 발생하는 것이다. 따라서 이상적인 경우는 n의 값이 221 = 4, 222 = 16, 223 = 256, 224 = 65,536 등인 경우이다. 하지만 4나 16은 너무 작은 숫자이므로 복잡도가 낮아질 것이고, 65,536 이상인 숫자들은 너무 큰 값이라 암호화하는 데에 매우 많은 시간이 소모될 것이므로 n = 256은 가장 이상적인 선택이라 할 수 있다. 따라서 본 논문에는 n = 256으로 고정하여 기술할 것이다.

박스화 과정과 순열 과정을 통한 박스 알고리즘의 정보는 키에 포함되어 전달되며, 수신자는 공유된 키 정보를 사용하여 암호화된 메시지를 복호화 한다. 암호화는 ⌈ log₂k ⌉ 비트 단위의 평문을 ⌈ log₂n ⌉ 비트 단위의 암호문으로 변환한 후, 행순열 및 열 순열 과정을 거친다. 이 때 키의 길이는 1) k - 1개의 경계값 정보, 2) 마지막 구간의 숫자 정보, 3) 행 순열 정보, 마지막으로 4) 열 순열 정보에 의해 결정된다. 위 4가지 항목에 대한 세부적인 키의 길이는 다음과 같이 계산된다.

• 1) k - 1 bounds : (k - 1)⌈ log₂n ⌉[bit]
• 2) last digit : ⌈ log₂k ⌉[bit]
• 3) row permutation : (l - 1)⌈ log₂l ⌉[bit]
• 4) column permutation : (⌈ log₂n ⌉- 1)⌈ log₂ (⌈ log₂n ⌉) ⌉[bit]

예를 들어 n = 256, k = 16인 경우 15개의 경계 값은 8비트의 단위 길이가 필요하므로 총 120비트의 경계값 정보가 필요하다. 또한 마지막 구간의 숫자는 k = 16이므로 4비트가 필요하다. 한편, 행 순열을 위해서는 l 이내의 숫자로 구성된 l - 1개의 ⌈ log₂l ⌉비트 순열 정보가 필요하다. 비슷한 방법으로 열 순열을 위해서는 ⌈ log₂n ⌉ 이내의 숫자로 구성된 ⌈ log₂n ⌉- 1개의 ⌈ log₂⌈ log₂n ⌉ ⌉비트 순열 정보가 필요하다. 그러면 전체 키는 앞에서 언급한 4가지 항목의 키를 차례대로 나열한 값이 되며, 길이는 다음과 같이 표현된다.

일반적으로 k와 n은 2의 거듭제곱으로 나타내는 것이 자연적이므로(ASCII, UTF 코드 등의 문자열은 모두 2의 거듭제곱만큼의 개수를 가진다.) 키 길이는 다음과 같이 간략하게 나타낼 수도 있다.

암호화 알고리즘에서 복호화에 대한 복잡도는 보안성의 가장 중요한 요인이다. 박스 알고리즘에서의 복잡도는 1) k - 1개의 경계값을 구하는 경우의 수, 2) 마지막 구간의 숫자를 결정하는 경우의 수, 3) 행 순열의 수, 마지막으로 4) 열 순열의 수를 구한 후 모두 곱하여 구하게 된다. 위 4가지 항목에 대한 세부적인 복잡도(경우의 수)는 다음과 같이 계산된다.

• 1) k - 1 bounds : _{n - 1}P_{k - 1}
• 2) last digit : k
• 3) row permutation : l × (l - 1) ×⋯× 1 = l!
• 4) column permutation :⌈ log₂n ⌉ !

박스화 과정에서는 n개의 숫자를 k개의 박스에 나누어 담는 경우의 수는 일렬로 나열된 n개의 숫자를 k - 1개의 경계선으로 구분하는 경우의 수와 같다. n개의 숫자 사이 경계 n - 1개 중 k - 1개를 순서를 고려하여 뽑는 경우의 수는 _{n - 1}P_{k - 1}이 된다. 또한 마지막 구간의 숫자는 0에서 k - 1 중에서 선택될 수 있으므로 k가지의 경우의 수가 있다. 한편, 길이 l의 행 순열은 l!, 길이 ⌈ log₂n ⌉의 열순열은 ⌈ log₂n ⌉!의 경우의 수를 가진다. 이를 바탕으로 각 과정의 경우의 수를 곱하면 다음과 같이 해킹 복잡도를 구할 수 있다.

암호 알고리즘의 효율성은 여러 측면에서 살펴볼 수 있다. 일반적으로 키의 길이가 q비트라면 가질 수 있는 정보의 최대량은 2^q이 된다. 따라서 복잡도는 2^q을 넘어설 수 없다. 이러한 관점에서 complexity/2^q 값은 주어진 길이의 키가 주어질 때, 허용된 정보량에 대한 전송되는 정보량의 비율이 되므로 알고리즘의 성능을 측정하는 하나의 지표가 된다. 하지만 비용 측면에서 보면 키의 길이보다는 메시지를 암호화하는데 걸리는 시간이 보다 중요할 것이다. 한편 보안성을 높이기 위해서는 복호화에 대한 복잡도가 높은 알고리즘이 선호될 것이다. 따라서 본 절에서는 암호 알고리즘의 효율성을 다음과 같이 정의한다.

암호화하는데 걸리는 시간은 컴퓨터의 성능과 암호화 프로그램에 따라 다소 차이가 나겠지만 동일한 환경 하에서 여러 경우의 결과들을 상대 비교하여 알고리즘의 우열을 판단할 수 있을 것이다.

2장에서 설명한 것과 같이, 박스 알고리즘은 이 진화한 평문을 임의의 길이로 구분한 후, 다른 길이로 암호화하는 것이 가능하다. 우리는 log₂k비트 (1, 2, 3,..., 8 bit) 단위의 평문을 log₂n비트 단위의 암호문으로 변경하고, 길이 l의 행 순열과 길이 log₂n의 열 순열을 시행한 결과를 기술할 것이다.

2.2절에서 키의 길이를 최적화 시키는 n의 값은 2의 거듭제곱의 거듭제곱인 경우(221 = 4, 222 = 16, 223 = 256, 224 = 65,536)이므로 암호화 조건을 만족하는 n의 값은 256이 이상적임을 설명하였다. 따라서 우리는 n을 256으로 고정시키고, k와 l의 값만을 2의 거듭제곱으로 변화시켜 가며 키 길이와 복잡도 변화를 분석하였다.

표 1은 기준 수 k 값과 순열 길이 l 값의 변화에 따른 키 길이의 변화를 나타낸 표이고, 이를 k 와 l에 대해 별도의 경향성을 살펴본 것이다. 표 1에서 k = 2⁸인 경우는 n의 값과 같으므로 박스 알고리즘은 사실상 일대일대응을 이루는 변환을 거친다. 표 2는 기준 수 k 값과 순열 길이 l 값의 변화에 따른 복잡도 변화를 나타낸 표이다. 이 때 복잡도는 2를 밑으로 하는 로그값을 취하였다. 표에서 추정할 수 있듯이 키의 길이와 복잡도는 k와 l에 대해 비교적 정확한 선형성을 나타낸다. 즉, k와 l의 값이 커질수록 그에 비례하는 키의 길이와 복잡도를 지니는 것이다.

표 1과 2는 비슷한 경향성을 지니는데, 이는 3.3절에서 언급한 바와 같이 주어진 길이의 키에 저장할 수 있는 최대 정보량 대비 실제 저장된 정보량의 비가 0.8~0.95 범위에서 유지되는 것을 의미하며 박스 알고리즘이 안정된 성능을 지니고 있음을 보여주는 것이다.

박스 알고리즘의 성능을 추정하기 위해 메시지 길이 변화에 따른 암/복호화 시간을 측정하였다. 본 실험에는 i5-4570 3.2GHz Quad Core CPU, 4GB 메모리 성능의 사무용 컴퓨터를 이용하였으며, 암호화를 위한 프로그램은 매트랩(Matlab) 2012를 사용하였다.

표 3은 메시지의 용량을 1MB로 고정하였을 때 기준 수 k 값과 순열 길이 l 값의 변화에 따른 암호화 및 복호화 시간을 나타낸 표이다. 메시지 용량이 고정되어 있으므로 기준 수 k 값이 커지면 암호화하는 문자의 수는 반비례하여 줄어든다는 점에 유의해야 한다.

따라서 k가 늘어나면 오히려 CPU 시간이 줄어들 수 있는 것이다. 각각의 k와 l 값에 따라 암호화 및 복호화에 걸리는 시간은 9.4 ~ 59.8초 범위를 가지고 있는 것을 확인할 수 있다. 흥미로운 점은 기준 수가 늘어감에 따라 소모 시간의 극소값들이 존재한다는 것이다. 주어진 메시지를 암호화시키는데 걸리는 시간은 곧 비용과 관련되는데, n = 256인 경우 k = 64 (= 2⁶ )일 때 가장 적은 시간으로 암호화가 가능하다는 사실을 알 수 있다. l에 대해서는 16 (= 2⁴ ) 이상인 경우 뚜렷한 감소를 나타내지는 않고 있다. 따라서 고려 대상이 오직 소모 시간일 경우에는, k = 64, l ≧ 16인 값을 택해 암호화할 경우 가장 적은 시간에 암호화 및 복호화를 시행할 수 있는 것이다.

암호 알고리즘의 성능은 여러 가지 기준으로 측정할 수 있을 것이다. 우리는 3.3절 식 (4)~(6)의 정의를 바탕으로 앞서 측정한 키의 길이와, 복잡도, CPU 시간을 조합하여 효율성을 계산하였다. 키의 길이는 정보 전송의 효과성을, 복잡도는 해킹에 대비한 안정성을, 그리고 CPU 시간은 암호화 비용의 경제성과 관련되어 있다.

표 4 및 그림 3은 3.3절의 식 (4)에서 정의한 것과 같이 키의 길이와 CPU 시간 대비 복잡도를 바탕으로 한 효율성을 나타낸 표와 그래프이다.

Fig. 3. 
Plot of the efficiency as functions of base digit and permutation length

그래프를 보면 모든 l에 대해 k = 64 (= 2⁶ )일 때 효율성이 극대화 되는 것을 알 수 있다. 이 때 l의 값은 2³~2⁴ 범위일 때 효율성이 높게 나타난다. 따라서 우리의 박스 알고리즘은 n = 256, k = 64, l = 2³~2⁴인 값을 선택하는 것이 효율성을 높이는 합리적인 선택이라 할 수 있다.