Crossing Cryptographic Algorithm

프로젝트 개요

Feistel 암호 방식에 대한 내용을 수업시간에 들으면서 현 크로싱 암호프로그램의 영감을 받았고 본격적으로 프로젝트에 착수하였습니다.

복호화 과정은 암호화 과정의 역과정으로 구현을 시작하였으며, 암호 강도를 높일 수 있는 요소들은 유지하고 불필요한 단계는 최대한 추가되지 않도록 하였습니다. 또한 복호화 알고리즘 구현 과정에서 예상치 못한 몇몇 문제가 발생하였고, 디버깅 과정을 통해 모두 해결함으로 써 최종적인 프로그램을 완성하였습니다.

본 프로그램은 대칭키 암호화 알고리즘을 이용하였고 치환, 전치, XOR, 교차, 반복연산 등, 여러 가지 암호화 기법을 적절하게 효과적으로 이용한 복합적인 암호화 프로그램입니다. 꾸준히 충분한 검토와 피드백을 통해 암호화 강도를 조절하며 약점을 보완하였으며, 어느덧 개인이네 소규모 기업에서 충분히 상용화 가능할 정도로 완성도있는 프로그램으로 발전하였습니다.

암호화 알고리즘

1. 초기 단계

1. 평문 절단 평문을 m이라고 하면, x = m.length/2를 수행하여 배열의 인덱스 범위가 m1 =(0, x-1), m2 = (x, m.length)인 각각의 평문배열을 생성한다.

2. KEY 생성 최초 KEY를 입력받은 후 k1이라고 하면 KEY의 문자배열을 역으로 읽은 문자배열을 k2라고 한다. ex) k1 = ABC, k2 = CBA

3. 아스키코드 제어문자 치환 아스키코드에서 0~31과 127의 값은 제어문자로써 암호화시 해당 값을 가져서는 안되지만, 실제로 XOR 연산을 하면 해당 값들이 등장한다.
   그래서 본 알고리즘에서는 위와 같은 제어문자들을 아스키코드와 중복되지 않는 값, 일부 한글 문자들을 사용하기로 하였다.
   즉, 0~31, 127번 문자들을 사용자임의 한글문자로 치환하여 사용한다. 모든 XOR 연산의 결과와 XOR에 임한 문자배열은 제어문자를 치환된 문자가 된다.

4. 달팽이배열 생성 아스키코드의 문자는 0~127이다. 이 때, 2차원 배열을 16 x 8로 생성하여 아스키코드 0번부터 127번까지의 값들을 ‘달팽이 배열 알고리즘’을 적용하여 채워나간다.
   마찬가지로 0~31, 127번 값은 사용자임의 한글문자가 들어가게 된다.

2. 암호화 단계(Round 1)

1. 평문 치환 평문 m은 평문 m1과 m2로 나누어진다.
   평문 m2의 문자배열에서 한 문자씩 아스키코드 값을 산출하고 그 산출된 값을 달팽이배열을 순차배열로 탐색했을 때, 인덱스 값과 일치하는 곳을 찾고 그 인덱스의 값으로 문자를 치환한다.
   이렇게 m2 문자열을 한 문자씩 모두 치환하고 새로운 m2 문자열이 된다.

2. XOR연산 각각 나누어진 평문 m1, m2, k1, k2를 XOR 연산한다.
   m1과 k2, m2와 k1이 각각 XOR연산을 진행하는데, 평문의 한 문자와 KEY의 한 문자씩 XOR연산을 수행한다.
   만약 평문의 문자열이 KEY의 문자열보다 길 경우, XOR연산 도중 KEY의 문자인덱스가 KEY의 길이만큼 도달했을 때, 다시 0번 인덱스부터 반복하여 XOR연산을 진행한다.
   반대로 평문의 문자열이 KEY의 문자열보다 짧을 경우, 평문의 문자인덱스가 KEY의 길이만큼 도달했을 때, XOR연산을 종료한다.
   마찬가지로 m2와 k1의 XOR연산도 이와 같이 반복하여 진행한다.

3. 암호화 단계(Round2 ~ key.length)

1. 교차 암호화 라운드가 진행될 때 마다, 평문과 키를 XOR하고 나온 암호문 c1과 c2는 서로 교차하여 실행된다.
   첫 라운드에서 m1이 k2과 연산하여 암호문 c1을 생성했다면, 다음라운드에서는 반대로 달팽이배열로 치환한 후 k1과 연산하여 암호화를 진행하게 된다.
   첫 라운드에서의 평문 m2도 다음라운드에서는 교차하여 달팽이배열 치환을 하지 않고 k2와 연산한다.

2. 배열 회전 라운드가 진행될 때 마다 달팽이배열은 시계방향으로 회전을 하게 된다.
   2라운드의 경우, m1의 암호문이 달팽이 배열로 치환되는데 배열이 1회 회전되므로 1라운드와 다른 치환 값을 가지게 된다.
   배열 회전은 라운드가 모두 실행될 때 까지 총 키의 길이 – 1번 회전하게 되며, 4개의 각기 다른 형태의 배열의 값으로 치환되게 된다.

3. 키 전치 초기단계에서 나누었던 k1과 k2에서 첫 인덱스 문자 값을 맨 뒤로 보내고 모든 값을 한 칸씩 인덱스를 앞으로 당기는 식의 전치를 하는 방식이다.
   단, 맨 처음 라운드에서는 전치를 하지 않는다. 맨 처음 초기 KEY가 ABCDE라면 k1 = ABCDE, k2 = EDCBA로 나누어지고 첫 번째 라운드에서 그대로 암호화가 진행되고 다음 라운드는 k1 = BCDEA, k2 = DCBAE가 된다.

4. XOR 연산 1회 라운드와 마찬가지로 치환된 c1, c2는 각각 전치된 해당 KEY와 XOR연산을 수행하여 다시 암호문을 도출해낸다.

5. 이후 반복적으로 KEY 전치, 배열 회전, 평문 교차를 하며 첫 라운드부터 총 KEY의 길이만큼 실행하게 된다.
   그리고 최종적으로 두 개의 암호문이 도출되며 그 암호문 문자배열을 결합하여 하나의 완벽한 암호문을 만들어낸다.

4. 암호화 흐름

암호화과정

1. 기존 프레임 유지, 기존 평문&KEY입력
2. 평문절단, 키 나눔
3. 우측 평문블럭 달팽이배열을 참조하여 치환
4. 달팽이배열 회전, KEY전치 및 블록 교차
5. 평문과 KEY의 XOR연산→ROUND 반복(KEY길이만큼)
6. 부분암호문 결합→최종암호문 도출

(3) ~ (5) 키의 길이만큼 반복 진행
(4)는 첫 루프에는 실행되지 않고 두 번째 루프부터 실행됨

5. 암호화 흐름도

복호화 알고리즘(Round2 ~ key.length)

1. 초기 단계

1. KEY를 입력받고 키를 2개로 나눈다. 복호화 알고리즘에서는 첫 라운드부터 KEY를 키의 길이만큼 역으로 전치를 시킨 후 실행한다.

2. 최종 도출된 암호문을 2개로 나누는데, KEY의 길이가 짝수이면 교차된 상태로 암호화 되었으므로 앞쪽의 블록이 뒤쪽으로, 뒤쪽의 블록이 앞으로 오게 된다. 단, 홀수는 그 반대가 된다.

3. 첫 시작 달팽이배열은 KEY의 길이로 결정한다. ((KEY length – 1) mod 4) 만큼 미리 달팽이배열을 회전시킨 후 실행된다.

4. KEY와 암호문을 XOR 연산을 수행한다.

2. 복호화 단계

• 복호화 과정은 암호화 과정의 역

1. 모든 연산을 암호화 알고리즘이 진행될 때의 역으로 실행한다.
   하나의 라운드가 진행 될 때 마다 전치 KEY 값을 뒤에서 앞으로 역으로 전치시키고, XOR 연산을 수행한 후 달팽이 배열을 역회전 시키고 배열 치환 값을 다시 치환하며 교차되며 다음 라운드를 진행해나간다.

2. KEY의 길이만큼 라운드에서 XOR 연산을 진행하고 m2 문자열만 마지막 달팽이배열 값을 치환하게 되면 결과적으로 m1, m2가 출력되게 된다.
   두 개의 문자열배열을 결합하면 평문이 도출된다.

3. 복호화 흐름

복호화과정

1. 기존 프레임 유지, 암호문&KEY입력
2. 암호문 절단, 키를 키의 길이만큼 전치하고 키 나눔
3. 달팽이배열을 (KEY.LENTH-1)mod 4 만큼 미리 회전
4. 우측 평문블럭 달팽이배열을 참조하여 역치환
5. 달팽이배열 역회전, KEY역전치 및 블록 교차
6. 평문과 KEY의 XOR연산→ROUND 반복(KEY길이만큼)
7. 부분평문 결합→최종평문 도출

• 복호화 과정은 암호알고리즘의 역과 같다.
• (10) ~ (12) 키의 길이만큼 반복 진행
• (9) 에서 암호문 절단은 키의 길이가 짝수이고 암호문의 길이가 홀수이면 최종 평문배열이 교차로 합쳐진것이기 때문에 왼쪽 암호문블럭을 한 단어만 늘리고, 오른쪽 암호블럭을 한 단어만큼 줄여서 암호문을 절단한다.
• (11) 는 첫 루프에 실행되지 않고 두 번째 루프부터 실행됨

4. 복호화 흐름도

피드백 및 디버그

평문과 KEY의 입력글자가 맞지 않을 때 정상동작하지 않는 문제

절단된 평문이 KEY 길이보다 길 때는 원활하게 동작하나, KEY 길이가 절단된 각각의 평문 길이보다 길 경우에는 암호화-복호화 과정이 달라지는 심각한 버그 발견

1. XOR연산을 할 때 KEY 뒷부분이 생략되어 전치함수와 역전치함수가 정상적으로 동작하지 않는 사실을 확인
2. 복호화 과정에서 역전치하기전 초기 값을 달팽이 배열처럼 미리 전치시켜놓는 것으로 변경
3. 전치 후 XOR연산시 어떠한 KEY값이 생략되더라도 복호화 과정에서 해당 KEY 값을 복원하면서 정상적으로 암호문이 복호화 되는 것을 확인

특정 상황에서의 복호화 알고리즘이 제대로 동작하지 않는 상황

1. 평문의 문자배열중 한 문자씩 값이 다르게 나오고 있음을 확인 현재까지 원인은 단순 오타 or 제어문자 치환 과정에서 문제로 추정.
2. 제어문자 치환 과정에서 오타로 확인

여러 가지 상황에서의 입력

1. 아무리 긴 숫자를 입력하든 긴 키를 입력하든 문자가 아스키코드에 포함되는 값 이라면 암호화 복호화 연산이 이상없이 진행되는 것을 확인.

결론

동작 확인

자바 GUI를 활용하여 암호화 및 복호화 로직이 정상적으로 동작하는지 확인

특징

1. 무작위 공격에 강함
   • 한 문자와 키 문자 하나당 128bit인 문자 배열을 지니고 있음
2. 빈도 수 공격에 강함
   • 회전하는 배열으로의 치환과 전치가 평문배열을 교차로 진행하면서 반복적으로 실행됨
3. XOR 연산
   • XOR연산의 반복으로 평문 진위성을 판별하기 어려워 공격자 입장에서 키 값을 알아내기가 힘듦
4. 호환성이 좋음
   • ASKII 기반이기 때문에 영문 대, 소문자를 구분하지 않고 숫자와 대부분의 특수문자를 입력받을 수 있음
5. 길이 제한이 없음
   • 자바 StringBuffer 객체를 사용하고 있으므로 일반적인 경우, 키과 평문의 길이제한을 두지않음.

상용화 가능성

개요에서 언급했듯이 이 프로그램의 알고리즘 속에는 특별히 강력한 알고리즘 기법이 담겨있지 않습니다. 하지만 알고리즘 속에는 다양한 알고리즘 기법들이 서로 연관되어 스며들어있습니다.

전치, 치환, 교차, 달팽이배열, XOR, 반복 연 산 등의 여러 가지 기법들이 전부 따로따로 연산을 진행되는 것이 아닌 모든 기 법들이 조화를 이루며 기법들 간에 시너지를 발생하여 연산이 진행되고 있고 그 결과, 더욱 강력한 알고리즘이 되었습니다.

비록 특정한 독창적인 기술을 창조 해 내지는 못했지만 이렇게 알고리즘의 기법들이 손실없이 조화를 이루었기 때 문에 어떠한 알고리즘과도 대적 할 만한 프로그램이 되었다고 생각합니다.

커다 란 대규모 기업에서는 활용하기엔 약할 수 있으나 개인이나 스타트업, 중규모의 기업들을 타겟으로는 충분히 상용화 될 가능성이 있고 그 만한 강력한 프로그램 임을 우리는 자부합니다.