데이터 은닉을 위한 부호화/복호화 방법 및 그 방법을이용한 부호화기/복호화기 document_id A220623007462

본 발명은 데이터의 은닉을 위한 부호화 및 복호화에 관한 것으로, 보다 상세하게는 원본 데이터의 손실이나 왜곡을 초래하지 않으면서 데이터를 은닉 및 복원할 수 있고 이러한 은닉과 동시에 데이터의 압축을 수행할 수 있는 데이터 은닉을 위한 부호화/복호화 방법 및 이를 이용한 복호화기/복호화기에 관한 것이다. 일반적으로 데이터 은닉이라 알려져 있는 방법은 크게 스테가노그라피(Steganography)와 워터마킹(watermarking)으로 나눌 수 있다. 전자는 데이터가 은닉되었는지의 여부조차 제 삼자에게 노출하지 않는 것을, 후자는 데이터의 은닉 여부가 알려져 있다고 생각하고, 잠재적인 제 삼자의 공격에 강인하여야 한다는 철학을 가지기 때문에 그 목적에 있어 상이할 뿐, 그 은닉을 위한 알고리듬은 상당히 유사하다고 할 수 있다. 데이터 은닉은 원본 데이터에 사용자의 메시지를 은닉하는 것인데, 추가적인 메시지가 원본에 더해지기 때문에 원본 데이터에 약간의 왜곡을 가져오게 된다. 원본 데이터는 그 파일 크기가 크기 때문에 일반적으로 압축 과정을 거치게 되며, 그러한 이유로 압축 방식을 이용한 알고리듬이 원본을 이용한 방법에 비해 효율적이라 할 수 있다. 압축 방식에는 여러 가지가 있으나, 현재 많이 사용되는 압축 방식으로는 렘펠 지브 웰치(Lempel-Ziv-Welch; 이하 "LZW"라 약칭한다) 압축 방식을 들 수 있다. LZW는 현재 모뎀 통신 CCITT V.42 비스 스탠다드, GIF, TIFF 영상 포맷의 압축 모듈, adobe사의 pdf 포맷에서의 영상 압축 등을 위해 사용되고 있다. LZW의 압축 방식은 압축할 전체 데이터에 대한 확률 분포를 사전 조사할 필요 없이, 각 문자 스트림들이 입력되는 대로 바로 부호화 할 수 있는 적응적인 무손실 데이터 압축 방식이다. 또한 동일한 코드 테이블이 동적으로 부호화기와 복호화기에 의해 생성되어 별도의 전송을 필요치 않는 딕셔너리(dictionary)를 기반으로 한 압축 방식이다. LZW 압축에 사용되는 주요 용어는 다음과 같이 정리할 수 있다. - 문자(character) : 압축하고자 하는 데이터의 기본적인 처리단위로서, 오디오, 텍스트, 영상 등을 포괄하는 것으로 알파벳과 같은 글자 그 자체에 국한되는 것은 아니다. 예를 들어 영문 문서 파일에서는 알파벳 하나하나 또는 소정개수의 집합들을 각각 문자라 할 수 있으며, 영상에서는 각 픽셀 또는 소정개수의 픽셀들을 문자로 생각할 수 있다. - 문자열(string) : 하나 또는 연속되는 문자들의 열을 지칭한다. - 문자 스트림(character stream) : 입력으로 주어지는 일련의 문자들로서 입력 데이터 전체를 의미한다. - 코드 (code) : 인덱스라고도 하며, 문자열이 각각 배정되어 있으며 압축된 데이터들에 대한 LZW 부호화기의 출력이 된다. - 딕셔너리(dictionary) : 코드 테이블(code table)이라고도 하며, 딕셔너리에 있는 문자열 각각에 대해 코드(또는 인덱스)가 배정되어 있다. - 엔트리(entry) : 딕셔너리 내부에 존재하는 각 문자열과 그 문자열을 지칭하는 코드를 말한다. - 은닉 코드 스트림(code stream) : 압축 후에 출력되는 일련의 코드들로 은닉메시지를 포함하여 압축된 데이터를 말한다. 도1은 일반적인 LZW 부호화기에 대한 기능 블록 구성도이고, 도 2는 일반적인 LZW 부호화의 동작 흐름을 도시한 것이다. 도 1 및 도 2를 참조하여 일반적인 LZW 부호화기 및 LZW 부호화에 대하여 설명하기로 한다. 우선, 제어부(20)는 입력 문자 스트림에 존재 할 수 있는 모든 문자들에 대하여 각각의 문자에 대한 코드를 정의하는 딕셔너리(40) 초기화 과정을 수행한 다음(단계 S100), 압축을 위하여 입력버퍼(10)에 입력되는 입력 문자 스트림에서 하나의 문자를 읽어와 저장부(30)의 프리픽스 저장영역(30A)에 프리픽스로 저장한다(단계 S101). 이어, 상기 제어부(20)는 상기 입력버퍼(10)에 저장된 입력 문자 스트림에서 다음 문자를 읽어와 저장부(30)의 서픽스 저장영역(30B)에 서픽스로 저장한다(단계 S102). 그 후, 상기 제어부(20)는 상기 단계 S101 및 S102에서 읽어와 저장한 프리픽스와 서픽스를 합한 문자열이 딕셔너리(40)내의 엔트리와 매치(match)하는 것이 있는지 확인한다(단계 S103). 상기 단계 S103의 확인 결과, 매치가 있는 경우에는 상기 제어부(20)는 현재의 문자열(프리픽스+서픽스)을 상기 저장부(30)의 프리픽스 저장영역(30A)에 프리픽스로 저장한다(단계 S104). 여기서, 프리픽스 저장영역(30A)에는 기 저장된 프리픽스가 상기 단계 S104에서 새로운 프릭픽스(즉, 기존 프리픽스 + 서픽스)로 갱신 저장된다. 그 후, 상기 제어부(20)의 제어가 단계 S109로 진행하여, 상기 제어부(20)는 입력되어 입력버퍼(10)에 저장된 입력 문자 스트림으로부터 더 이상 읽을 문자가 있는지 확인한다. 상기 단계 S109에서 읽을 문자가 남아 있는 것으로 확인된 경우, 상기 제어부(20)의 제어는 상기한 S102로 되돌아가서, 입력되어 상기 입력버퍼(10)에 저장된 입력 문자 스트림으로부터 다음 문자를 읽어와 상기한 단계 S102부터의 제어 과정을 반복하여 수행한다. 상기 단계 S109에서 읽을 문자가 남아 있지 않은 것으로 확인된 경우, 상기 제어부(20)는 맨 마지막에 남게 되는 저장부(30)의 프리픽스 저장영역(30A)에 저장된 프리픽스에 해당하는 코드를 딕셔너리(40)에서 찾아서 출력버퍼(50)를 통해서 출력신호로서 출력하고(단계 S110), 모든 부호화 제어를 종료한다. 한편, 상기한 단계 S103에서, 현재의 프리픽스와 서픽스를 합한 문자열과 매치되는 문자열이 딕셔너리(40)내에 존재하지 않는 것으로 확인된 경우, 상기 제어부(20)는 현재 저장부(30)의 프리픽스 저장영역(30A)에 저장된 프리픽스에 대응하는 코드를 딕셔너리(40)에서 찾아서 출력버퍼(50)를 통해서 출력신호로서 출력한다(단계 S106). 그 후, 상기 제어부(20)는 상기 저장부(30)의 프리픽스 저장영역(30A)과 서픽스 저장영역(30B)에 각각 현재 저장되어 있는 프리픽스와 서픽스를 합하고 이를 딕셔너리(40)내에 새로운 엔트리로 추가하여, 딕셔너리(40)를 업데이트한다(단계 S107). 이어, 상기 제어부(20)는 상기 저장부(30)의 프리픽스 저장영역(30A)에 서피스 저장영역(30B)에서 읽어낸 값을 프리픽스로 갱신 저장하여 다음의 압축에 사용하도록 한다(단계 S108). 그 후, 상기 제어부(20)의 제어는 상기한 단계 S109로 진행하여, 입력되어 입력버퍼(10)에 저장된 입력 문자 스트림으로부터 더 이상 읽을 문자가 있는지 확인한다. 상기 단계 S109에서 읽을 문자가 남아 있는 것으로 확인된 경우, 상기 제어부(20)의 제어는 상기한 S102로 되돌아가서, 입력되어 상기 입력버퍼(10)에 저장된 입력 문자 스트림으로부터 다음 문자를 읽어와 상기한 단계 S102부터의 제어 과정을 반복하여 수행한다. 한편, 단계 S109에서 읽을 문자가 남아 있지 않는 것으로 확인된 경우, 상기 제어부(20)는 상기 단계 S108에서 저장부(30)의 프리픽스 저장영역(30A)에 갱신 저장된 프리픽스(즉, 서픽스)에 해당하는 코드를 딕셔너리(40)에서 찾아 출력버퍼(50)를 통해서 출력하고(단계 S110), 모든 부호화 제어를 종료한다. 도 3은 일반적인 LZW 복호화기의 기능 블록 구성도이고, 도 4는 일반적인 LZW 복호화의 동작 흐름을 도시한 것이다. 도 3 및 도 4를 참조하여 일반적인 LZW 복호화기 및 LZW 복호화에 대하여 설명하기로 한다. 우선, 제어부(25)는 부호화된 문자 스트림에 존재 할 수 있는 모든 문자들에 대하여 각각의 문자에 대한 코드를 정의하는 딕셔너리(45) 초기화 과정을 수행한 다음(단계 S300), 부호화기로부터 전송되어온 입력 신호 스트림을 입력버퍼(15)에 저장하여 이로부터 하나의 코드를 읽어와 저장부(35)의 이전 코드 저장영역(35B)에 OCODE(old code)로 저장한 후(단계 S301), 그 코드에 해당하는 문자열을 딕셔너리(45)에서 찾아서 출력버퍼(55)를 통해서 출력한다(단계 S302). 어어, 상기 제어부(25)는 그 다음의 코드를 상기 입력버퍼(15)에서 읽어와 저장부(35)의 신규 코드 저장영역(35C)에 NCODE(new code)로 저장한다(단계 S303). 그 다음, 제어부(25)는 NCODE가 딕셔너리(45)내에 존재하는가를 확인한 후(단계 S304), 존재하는 경우 딕셔너리(45)에서 NCODE에 해당하는 문자열을 읽어 출력버퍼(55)의 스트링영역(STRING)(55A)에 저장하고(단계 S307), 상기 제어부(25)의 제어는 하기의 단계 S308로 진행한다. 여기서, 상기 스트링 저장영역(55A)은 임시적 버퍼로 사용된다. 이후, 단계 S308에서 상기 제어부(25)는 상기 스트링 저장영역(55A)에 저장된 STRING을 출력하도록 제어하고(단계 S308), 상기 제어부(25)는 상기 출력된 STRING의 첫 문자를 서픽스로 하여 상기 저장부(35)의 서픽스 저장영역(35A)에 저장한다(단계 S309). 이어, 상기 제어부(25)는 상기 이전 코드 저장영역(35B)에 저장된 OCODE에 해당하는 문자열과 상기 서픽스 저장영역(35A)에 저장된 서픽스를 합쳐서 딕셔너리(45)에 추가하여 딕셔너리(45)를 업데이트한다(단계 S310). 이렇게 딕셔너리 업데이트 과정이 끝나면 다음 과정을 위해 상기 제어부(25)는 저장부(35)의 이전 코드 저장영역(35B)에 신규 코드 저장영역(35C)에서 읽어낸 값을 OCODE로서 갱신 저장한다(단계 S312). 그 후, 상기 제어부(25)는 상기 입력버퍼(15)에서 읽어올 더 이상의 코드가 있는 가를 확인한 후(단계 S313), 코드가 남아 있을 경우 다시 상기한 단계 S303부터의 과정을 반복하여 수행하고, 그 반면 상기 단계 S313에서 더 이상 코드가 남아 있지 않은 것으로 확인되면 모든 복호화 과정의 제어를 종료한다. 한편, 상기한 단계 S304에서 NCODE가 딕셔너리에 존재하지 않는 경우는 특별한 경우로 딕셔너리(45)에 추가되는 것이 인코딩되는 코드보다 늦다는 것을 의미한다. 이 경우에는 상기 제어부(25)는 상기 저장부(35)의 이전 코드 저장영역(35B)에 저장된 OCODE에 해당하는 문자열을 딕셔너리에서 읽어내어 STRING으로서 출력버퍼(55)의 스트링 저장영역(55A)에 저장하고(단계 S305), 상기 스트링 저장영역(55A)에 저장된 STRING에 이 STRING의 첫 문자와 합하여 그 합한 것을 상기 출력버퍼(55)의 스트링 저장영역(55A)에 새로운 STRING으로 갱신 저장하게 된다(단계 S306). 이후, 상기 제어부(25)는 상기 스트링 저장영역(55A)에 저장된 STRING을 출력하도록 제어하고(단계 S308), 상기한 바와 같이 단계 S309~S313의 과정을 수행한다. 한편, 현재 워터마크나 스테가노그라피(Steganography) 등 여러 가지 데이터 은닉 방법들이 제안되어 있는데, 전술한 바와 같이, 이들은 주로 압축 등 신호처리 과정 전에 원본 데이터에 수정을 가하여 데이터 은닉을 수행하며, 결과적으로 원본 정보에 대한 왜곡을 초래하게 되는 단점을 가진다. 이와 같은 기존 방법에는 LZW 압축 방식을 사용하여 GIF 이미지에 데이터를 은닉하는 방법과 색상 정보에 대한 정의(definition)인 팔레트(palette)를 이용하여 데이터를 은닉하는 방법이 있다. 이러한 방법들은 『Ogihara, T. and Kaneda, Y., "Data Embedding into Compressed Data of GIF Images," Proceedings of Pacific Rim Workshop on Digital Steganography 2003』과, 『Fridrich, J., and Du Dui, "A new steganographic methods for palette-based images," IS0026#T PICS Conference, pp.285-389, 1999』 등에 개시되어 있다. LZW 압축 방식을 이용한 방법은 일반적인 LZW 과정에서 코드의 패리티(parity)와 은닉하고자 하는 데이터의 패리티를 일치 시키는 방법이다. 주어진 데이터를 LZW 방식을 이용하여 압축하기 위해 앞서 기술한 바와 같이 입력 문자 스트림에서 딕셔너리내의 엔트리와 가장 긴 길이의 문자열로 매치할 때까지 문자를 하나씩 읽어와, 읽어온 문자열에 해당하는 코드를 출력하게 된다. 이 때, 코드의 패리티가 은닉하고자 하는 데이터의 패리티와 일치한다면 원래의 코드를 그대로 출력하고 그렇지 않다면 읽어온 문자열의 가장 마지막 문자를 이와 가장 유사한 문자로 바꾸게 된다. 만약 마지막 문자를 변경한 문자열과 매치하는 엔트리가 딕셔너리내에 존재하며 이에 해당하는 코드의 패리티와 은닉하고자 하는 데이터의 패리티가 일치한다면 해당 코드를 출력한다. 그러나 변경된 문자열과 매치하는 엔트리가 존재하지 않는다면 마지막 문자열을 제거한 문자열과 일치하는 엔트리의 코드를 찾아 해당 코드의 패리티와 은닉하고자 하는 데이터의 패리티의 일치 여부를 조사한다. 만약 패리티가 서로 일치 한다면 해당 코드를 출력하고, 일치하지 않는다면 마지막 문자를 가장 유사한 문자로 수정하여 이와 같은 과정을 문자열의 길이가 3이 될 때까지 반복한다. 문자열의 길이가 3보다 작아지게 되면 데이터를 은닉하지 않게 된다. 예를 들어, 은닉하고자 하는 데이터가 ‘0’이며, 읽어온 문자열이 ‘01 01 33 11 02’ 이고 이와 일치하는 엔트리의 코드가 ‘130’일 경우, 은닉하려는 메시지의 패리티와 출력하고자하는 코드의 패리티가 일치하므로 코드 ‘130’을 그대로 출력한다. 하지만 읽어온 문자열과 일치하는 엔트리의 코드가 ‘131’로 은닉하고자 하는 데이터의 패리티와 일치 하지 않을 경우 읽어온 문자열의 맨 마지막 문자인 ‘02’를 이와 가장 유사한 문자로 대체시킨다. 만약 ‘02’와 가장 유사한 문자가 ‘44’이면 기존의 문자열 ‘01 01 33 11 02’를 ‘01 01 33 11 44’로 변경하게 되는 것이다. 이러한 방법으로 변경된 문자열과 매치하는 엔트리가 딕셔너리내에 존재하며, 이에 대한 코드의 패리티가 원하는 값을 갖는다면 해당 코드를 출력하고, 그렇지 않을 경우 마지막 문자를 제거한 ‘01 01 33 11’에 대해 동일한 과정을 반복한다. 그러나 이와 같은 방법의 경우 입력 문자의 강제적인 변형으로 인해 원래의 입력 신호를 왜곡하는 결과를 초래하게 된다. 팔레트를 이용하여 데이터를 은닉하는 방법은 다음과 같다. 팔레트내의 모든 색에 대하여 가장 유사한 색과 서로 짝을 이루도록 한 후, 각 쌍 내의 두 가지 색에 대하여 서로 다른 패리티를 부여한다. 은닉하고자 하는 데이터의 패리티와 입력 문자의 패리티가 동일하다면 입력 문자를 그대로 사용하고, 그렇지 않다면 입력 문자와 가장 유사한 색을 가지며 다른 패리티를 갖도록 앞서 짝을 이룬 색으로 변경한다. 예를 들어, 팔레트의 ‘120’에 해당하는 색과 ‘30’에 해당하는 색이 가장 유사할 경우 서로 짝을 이루도록 하며, ‘120’에는 ‘0’ 을 ‘30’에는 ‘1’이란 패리티를 부여한다. 만약 입력 문자의 값이 ‘120’이며 은닉하고 하는 데이터가 ‘0’이라면 입력 문자를 그대로 사용하고, 은닉하고자 하는 데이터가 ‘1’이라면 이와 동일한 패리티를 가지며 본래의 입력 문자와 가장 유사한 색을 갖는 ‘30’으로 입력 문자를 변경하게 된다. 그러나 이와 같은 방법을 사용할 경우 수신자가 전송측에서 사용한 테이블인, 가장 유사한 색끼리 서로 짝을 이루며 각 색에 패리티를 부여한 테이블과 동일한 가지고 있어야 한다. 뿐만 아니라 앞서 서술한 LZW 압축 방식을 이용한 방법과 마찬가지로 색상 정보의 변형으로 인해 원본 영상에 왜곡이 발생하게 되는 단점을 가지고 있다. 현재 LZW와 같은 압축 방식 자체를 데이터 은닉 기술에 응용하는 예는 없는데, 이는 LZW로 압축 이후 데이터의 중복성(redundancy)이 거의 존재하지 않기 때문이다. 그러한 이유로 현존하는 대부분의 알고리듬은 압축 이전 데이터 자체에 데이터 은닉을 수행하게 되므로 데이터의 왜곡을 초래하는 결과를 낳게 된다.