(19) 대한민국특허청(KR) (12) 공개특허공보(A)
(11) 공개번호 10-2009-0055846 (43) 공개일자 2009년06월03일 (51) Int. Cl.
H04L 9/28 (2006.01)
(21) 출원번호 10-2007-0122687 (22) 출원일자 2007년11월29일 심사청구일자 2007년11월29일
(71) 출원인
한국전자통신연구원
대전 유성구 가정동 161번지 (72) 발명자
박태준
서울 송파구 가락1차 현대아파트 17동 402호 이승민
대전 대덕구 송촌동 선비마을 301동 502호 (뒷면에 계속)
(74) 대리인 한양특허법인 전체 청구항 수 : 총 8 항
(54) 베타 전개를 이용한 순서 보존 수치 데이타 암호화 시스템및 방법 (57) 요 약
본 발명은 베타 전개를 이용한 순서 보존 수치 데이타 암호화 시스템 및 방법에 관한 것이다. 베타 전개를 이용 한 순서 보존 수치 데이타 대칭키 암호화 시스템은 비밀키 방식의 암호화 키를 생성하는 비밀키 생성부; 비밀키 생성부에 의해 생성된 암호화 키로 베타 전개를 이용하여 수치 데이타를 암호화하고, 서버로 저장하는 수치 데이 타 암호화부; 임의의 수 n을 가지고 데이타를 검색할 경우, 비밀키를 이용하여 임의의 수 n을 베타 전개한 후, 베타 전개의 결과 값을 서버로 전송하여, 서버로부터 베타 전개의 결과값에 의해 검색된 암호화된 수치 데이타를 수신받는 검색부; 및 베타 전개를 이용하여 복호화 키로 서버로부터 수신된 검색 결과인 암호화된 수치 데이타를 복호화하는 수치 데이타 복호화부를 포함한다. 따라서, 베타 전개를 이용한 수치 데이타 암호화 시스템은 암호화 된 수치 데이타의 크기 순서가 보존되기 때문에 검색이 용이하고 와일드 카드검색 및 구간 검색이 가능하여 효율 적으로 암호화된 수치 데이타를 검색할 수 있다.
대 표 도 - 도4
(72) 발명자 홍도원
대전 유성구 전민동 엑스포아파트 212-1704
조현숙
대전 유성구 어은동 한빛아파트 131-1306
이 발명을 지원한 국가연구개발사업 과제고유번호 2005-Y-001-03
부처명 정보통신부 및 정보통신연구진흥원 연구사업명 유비쿼터스원천기술개발
연구과제명 차세대 시큐리티 기술 개발 주관기관 한국전자통신연구원 연구기간 2007-04-01 ~ 2007-12-31
특허청구의 범위 청구항 1
베타 전개를 이용한 순서 보존 수치데이타 암호화 시스템에 있어서, 비밀키 방식의 암호화 키를 생성하는 비밀키 생성부;
상기 비밀키 생성부에 의해 생성된 암호화 키로 베타 전개(beta expansion)를 이용하여 수치 데이타를 암호화하 고, 서버로 저장하는 수치 데이타 암호화부;
임의의 수 n을 가지고 있는 데이타를 검색할 경우, 비밀키를 이용하여 상기 임의의 수 n을 베타 전개한 후, 베 타 전개의 결과 값을 서버로 전송하여, 서버로부터 베타 전개의 결과값에 의해 검색된 암호화된 수치 데이타를 수신받는 검색부; 및
상기 베타 전개를 이용하여 복호화 키로 암호화된 수치 데이타를 복호화하는 수치 데이타 복호화부;
를 포함하는 베타 전개를 이용한 순서 보존 수치데이타 암호화 시스템.
청구항 2
제 1 항에 있어서,
상기 암호화된 수치 데이타는,
크기 순서가 보존되는 것을 특징으로 하는 베타 전개를 이용한 순서 보존 수치데이타 암호화 시스템.
청구항 3
제 2 항에 있어서, 상기 검색부는,
특정 수보다 작은 값의 데이타를 검색하는 와일드카드 검색을 제공하는 것을 특징으로 하는 베타 전개를 이용한 순서 보존 수치데이타 암호화 시스템.
청구항 4
제 2 항에 있어서, 상기 검색부는,
특정 숫자 범위에 해당하는 값의 데이타를 검색하는 구간 검색을 제공하는 것을 특징으로 하는 베타 전개를 이 용한 순서 보존 수치데이타 암호화 시스템.
청구항 5
베타 전개를 이용한 순서 보존 수치데이타 암호화 방법에 있어서, (a) 비밀키 생성부에 의해 비밀키 방식의 암호화 키를 생성하는 단계;
(b) 수치 데이타 암호화부에 의해 상기 비밀키 생성부에 의해 생성된 암호화 키로 베타 전개(beta expansion)를 이용하여 수치 데이타를 암호화하고, 서버로 저장하는 단계;
(c) 검색부에 의해 임의의 수 n을 가지고 있는 데이타를 검색할 경우, 비밀키를 이용하여 상기 임의의 수 n을 베타 전개한 후, 베타 전개의 결과 값을 서버로 전송하여, 서버로부터 베타 전개의 결과값에 의해 검색을 수행 하여 암호화된 수치 데이타를 수신받는 단계; 및
(d) 수치 데이타 복호화부에 의해 상기 베타 전개를 이용하여 복호화 키로 암호화된 수치 데이타를 복호화하는 단계;
를 포함하는 베타 전개를 이용한 순서 보존 수치데이타 암호화 방법.
청구항 6
제 5 항에 있어서,
상기 암호화된 수치 데이타는,
크기 순서가 보존되는 것을 특징으로 하는 베타 전개를 이용한 순서 보존 수치데이타 암호화 방법.
청구항 7
제 5 항에 있어서, 상기 검색부는,
특정 수보다 작은 값의 데이타를 검색하는 와일드카드 검색을 제공하는 것을 특징으로 하는 베타 전개를 이용한 순서 보존 수치데이타 암호화 방법.
청구항 8
제 5 항에 있어서, 상기 검색부는,
특정 숫자 범위에 해당하는 값의 데이타를 검색하는 구간 검색을 제공하는 것을 특징으로 하는 베타 전개를 이 용한 순서 보존 수치데이타 암호화 방법.
명 세 서
발명의 상세한 설명 기 술 분 야
본 발명은 수치 데이타 암호화 시스템 및 방법에 관한 것으로, 특히 정보보호를 위해 비밀키 방식의 암호화 키
<1>
로 수치 데이타를 암호화하여 저장할 경우 이에 대한 검색을 빠르게 할 수 있도록 베타 전개(beta expansion)를 이용하여 수치 데이타의 순서를 보존하고, 와일드 카드검색 및 구간 검색 기능을 제공하며, 복호화 키로 검색된 암호화된 수치 데이타를 복호화하는, 베타 전개를 이용한 순서 보존 수치 데이타 암호화 시스템 및 방법에 관한 것이다.
본 발명은 정보통신부 및 정보통신연구진흥원의 유비쿼터스원천기술개발 사업의 일환으로 수행한 연구로부터 도
<2>
출된 것이다[과제관리번호: 2005-Y-001-03, 과제명:차세대 시큐리티 기술 개발(Developments of next generation security technology)].
<3>
배 경 기 술
사용자의 정보보호 및 프라이버시 보호를 위해 중요정보가 저장된 서버는 접근제어(Access Control)를 통해 사
<4>
용권한이 있는 사람을 판단하고 즉 비밀 번호 등 사용자를 확인할 수 있는 방법을 통해 서버이용 권한을 주도록 하는 방식을 사용한다. 하지만, 이런 방식은 서버 관리자, 즉 내부자의 배임행위에 대해서는 대처할 수가 없다.
내부자는 접근제어를 뚫고 들어가는 것이 용이하기 때문에 저장된 데이타에 쉽게 접근할 수 있다. 이때, 저장된 문서가 평문(plaintext)인 경우, 사용자의 중요한 정보가 외부로 유출되어 오용될 우려가 있다.
이를 막기 위해 중요한 정보는 암호화하여 데이타베이스에 저장한다. 하지만, 문서를 암호화할 경우, 검색 및
<5>
데이타에 대한 효율적인 처리가 불가능해졌다. 그러므로, 암호화된 데이타 검색시, 시스템은 암호화된 데이타를 전부 수신받아 복호화한 후에 검색 및 처리를 해야만 한다.
이에 대한 불편함은 데이타의 크기가 커질수록 감당할 수 없는 수준이 된다. 특히, 숫자로 된 데이타의 경우,
<6>
시스템은 수치 데이타의 크기 비교를 통해 데이타 처리를 용이하게 할 수 있다. 또한, 와일드카드 검색과 구간 검색은 검색의 효율을 높여주는 기본 검색으로써 암호화된 데이타에 대하여 이런 검색을 할 수 있는 기술은 실 용적인 측면에서 매우 중요한 문제이다.
그러나, 기존의 암호화 기술은 수치데이타의 순서를 보존하지 않는다. 따라서, 기존의 암호화 기술은 암호화된
<7>
데이타는 복호화하지 않으면 비교, 검색 등 데이타에 대한 처리가 불가능하다.
발명의 내용
해결 하고자하는 과제
본 발명은 상기한 문제점을 해결하기 위해 제안된 것으로, 정보보호를 위해 비밀키 방식의 암호화 키로 수치 데
<8>
이타를 암호화하여 저장할 경우 이에 대한 검색을 빠르게 할 수 있도록 베타 전개(beta expansion)를 이용하여 수치 데이타의 순서를 보존하고, 검색후 복호화 키로 검색된 암호화된 수치 데이타를 복호화하는, 베타 전개를 이용한 순서 보존 수치 데이타 암호화 시스템 및 방법을 제공하는데 그 목적이 있다.
본 발명이 이루고자 하는 또 다른 기술적 과제는 제안된 베타 전개를 이용한 순서 보존 수치 데이타 대칭 암호
<9>
화 기술이 암호화된 수치 데이타의 크기 순서를 보존하므로 와일드카드 검색 및 구간 검색 기능을 제공하는 것 이다.
본 발명의 다른 목적 및 장점들은 하기의 설명에 의해서 이해될 수 있으며, 본 발명의 실시예에 의해 보다 분명
<10>
하게 알게 될 것이다. 또한, 본 발명의 목적 및 장점들은 특허 청구 범위에 나타낸 수단 및 그 조합에 의해 실 현될 수 있음을 쉽게 알 수 있을 것이다.
과제 해결수단
본 발명의 목적을 달성하기 위하여, 본 발명은 베타 전개를 이용한 순서 보존 수치데이타 암호화 시스템으로서,
<11>
비밀키 방식의 암호화 키를 생성하는 비밀키 생성부; 상기 비밀키 생성부에 의해 생성된 암호화 키로 베타 전개 (beta expansion)를 이용하여 수치 데이타를 암호화하고, 서버로 저장하는 수치 데이타 암호화부; 임의의 수 n 을 가지고 있는 데이타를 검색할 경우, 비밀키를 이용하여 상기 임의의 수 n을 베타 전개한 후, 베타 전개의 결 과 값을 서버로 전송하여, 서버로부터 베타 전개의 결과값에 의해 검색된 암호화된 수치 데이타를 수신받는 검 색부; 및 상기 베타 전개를 이용하여 복호화 키로 암호화된 수치 데이타를 복호화하는 수치 데이타 복호화부를 포함한다.
상기 암호화된 수치 데이타는, 크기 순서가 보존되는 것을 특징으로 한다.
<12>
상기 검색부는, 특정 수보다 작은 값의 데이타를 검색하는 와일드카드 검색을 제공하는 것을 특징으로 한다.
<13>
상기 검색부는, 특정 숫자 범위에 해당하는 값의 데이타를 검색하는 구간 검색을 제공하는 것을 특징으로 한다.
<14>
본 발명의 다른 목적을 달성하기 위하여, 본 발명은 베타 전개를 이용한 순서 보존 수치데이타 암호화 방법으로
<15>
서, (a) 비밀키 생성부에 의해 비밀키 방식의 암호화 키를 생성하는 단계; (b) 수치 데이타 암호화부에 의해 상 기 비밀키 생성부에 의해 생성된 암호화 키로 베타 전개(beta expansion)를 이용하여 수치 데이타를 암호화하고, 서버로 저장하는 단계; (c) 검색부에 의해 임의의 수 n을 가지고 있는 데이타를 검색할 경우, 비밀 키를 이용하여 상기 임의의 수 n을 베타 전개한 후, 베타 전개의 결과 값을 서버로 전송하여, 서버로부터 베타 전개의 결과값에 의해 검색을 수행하여 암호화된 수치 데이타를 수신받는 단계; 및 (d) 수치 데이타 복호화부에 의해 상기 베타 전개를 이용하여 복호화 키로 암호화된 수치 데이타를 복호화하는 단계를 포함한다.
상기 암호화된 수치 데이타는, 크기 순서가 보존되는 것을 특징으로 한다.
<16>
상기 검색부는, 특정 수보다 작은 값의 데이타를 검색하는 와일드카드 검색을 제공하는 것을 특징으로 한다.
<17>
상기 검색부는, 특정 숫자 범위에 해당하는 값의 데이타를 검색하는 구간 검색을 제공하는 것을 특징으로 한다.
<18>
효 과
이상에서 설명한 바와 같이, 본 발명에 따른 베타 전개를 이용한 순서 보존 수치 데이타 암호화 시스템 및 방법
<19>
은, 비밀키 방식의 암호화 키로 수치 데이타를 암호화하여 저장할 경우, 이에 대한 검색을 빠르게 할 수 있도록 베타 전개(beta expansion)를 이용하여 수치 데이타의 크기 순서를 보존하여 암호화, 검색, 복호화하기 때문에 검색이 용이하고 와일드카드 검색 및 구간 검색이 가능하여 효율적으로 암호화된 수치 데이타의 검색이 이루어 질 수 있다.
또한, 본 발명은 암호화하지 않은 데이타베이스의 보안 결점을 해소하여 데이타베이스 위탁에 대한 위험성을 낮
<20>
추고 이에 대한 신뢰도를 높일 수 있으며, 암호화된 데이타의 효율적인 검색을 통해 데이타베이스 사업에 대한
실용가능성을 높여 산업 활성화를 기대할 수 있다.
발명의 실시를 위한 구체적인 내용
이하, 본 발명의 바람직한 실시예를 첨부된 도면을 참조하여 상세하게 설명한다.
<21>
도 1은 본 발명에 따른 베타 전개를 이용한 순서 보존 수치데이타 대칭키 암호화 및 복호화 시스템의 구성도이
<22>
다. 도 2는 본 발명의 일실시예에 따른 베타 전개를 이용한 순서 보존 수치데이타 대칭키 암호화 및 복호화 방 법을 설명한 흐름도이다.
베타 전개를 이용한 순서 보존 수치데이타 대칭키 암호화 및 복호화 클라이언트 시스템은 비밀키 생성부(11),
<23>
수치 데이타 암호화부(12), 검색부(13), 및 수치 데이타 복호화부(14)로 구성된다.
비밀키 생성부(11)는 비밀키 방식의 암호화 키를 생성한다(S10).
<24>
수치 데이타 암호화부(12)는 비밀키 생성부(11)에 의해 생성된 암호화 키로 베타 전개(beta expansion)를 이용
<25>
하여 크기 순서를 보장하는 수치 데이타를 암호화하고, 암호화된 수치 데이타를 서버의 저장부(23)로 저장한다 (S11).
검색부(13)는 임의의 수 n을 가지고 데이타를 검색할 경우, 암호화 파라미터로 충분히 큰 소수 p 보다 작은 수
<26>
n개를 무작위(random)로 를 선택한 후, 를 이라고
하고 마지막 정수 은 이 되는 임의의 정수를 선택하고, 베타 전개 함수에 의해 비밀키 을 이용하여 임의의 수 n을 베타 전개한 후, 베타전개의 결과 값 을 서버(20)로 전송하면, 서버(20)에서 베타 전개의 결과값에 의해 암호화된 수치 데이 타를 검색하여 서버(20)로부터 그 검색결과를 사용자의 클라이언트(10)의 검색부(13)로 수신받는다(S12).
상기 검색부(13)는 특정 수보다 작은 값의 데이타를 검색하는 와일드카드 검색을 제공하고, 특정 숫자 범위에
<27>
해당하는 값의 데이타를 검색하는 구간 검색을 제공한다.
수치 데이타 복호화부(14)는 상기 베타 전개를 이용하여 복호화 키로 서버로부터 수신된 검색 결과인 암호화된
<28>
수치 데이타를 복호화한다(S13).
이하, 본 발명은 암호화 및 복호화 방법의 몇 가지 필요한 개념을 설명한다.
<29>
진법 표현은 컴퓨터 산술의 한 분야로서 radix 표현은 컴퓨터 산술에서 가장 많이 사용되고 있는 숫자 표기법이
<30>
다. 라딕스(radix) 표현은 base 와 digit 집합 을 이용하여 행해진다. 1보다 큰 정수 z에 대 한 진법 표현은 으로 표기되며, 이는 을 의미하며, 여기서 모든 이다. 예를 들어 이라고 하면, digit 집합은 이 되며, 이라고 표현된다.
진법 표현은 보통 정수에 대해 하지만 실수범위로 확장이 가능하다. 이를 베타 표현이라고 하며, 본 발명은 베
<31>
타 표현을 이용하여 암복호화를 행한다. 베타 표현에 대해 알아보자. 우선, 예를 들면, 를 2진법으로 표현 하는 방법은
<32>
이므로, 의 등식이 성립하게 되며 이라고 표현할 수 있다.
<33>
이에 대한 일반화하여 수리적인 설명을 하면 다음과 같다. 는 에 대한 정수부분을 나타내고 는 의
<34>
소수부분을 나타낸다. 로 놓고 에 대해, , 라고 하면, 의
등식이 성립하며 형식으로 표현된다.
베타 전개는 다음과 같은 함수를 이용하여 설명할 수도 있다.
<35>
<36>
이 함수는 로 나타낼 수 있다. 이 함수를 이용한 베타 전개는 도 3과 같은 그림으로 표현될
<37>
수 있다.
도 3은 인 경우, 베타 전개를 이용한 수치 데이타 암호화를 위한 인덱스를 설정하는 방법에 대한 개념도
<38>
이다.
은 사전적인 순서(lexicographic order)를 줄 수 있다. 사전적인 순서란,
<39>
에 대하여 적당한 k>1가 존재하여 이고, 인 에 대하여 이 면, 으로 하는 것을 말한다. 사전적인 순서는 쉽게 말하면 사전을 배열할 때 사용 하는 순서이다. 예를 들면, a를 prefix로 하는 단어가 나온 후 b를 prefix로 하는 단어가 나오는 식이다.
베타 전개를 하면, 그 결과는 다음과 같은 성질을 만족한다.
<40>
베타 전개는 이고 일 때 이면 가 성립
<41>
하고, 역으로 이면 가 성립하게 된다.
이하, 베타 전개를 이용한 암호화 방법을 설명한다. 암호 파라미터로 충분히 큰 소수 p를 선택한다. p 보다 작
<42>
은 수 n개를 무작위(random)로 선택한다. 무작위로 택한 수를 라고 하고, 마지막 값 은
이 되는 임의의 실수를 선택한다(도면에서 이고 는 를 함수값으로 하는 x 축의 점이다).
이에 대한 일반화하여 수리적인 설명을 하면 다음과 같다
<43>
는 를 p로 나눴을 때의 몫을 나타내고 는 의 나머지부분을 나타낸다. 로 놓고 에 대
<44>
해, 라고 하면, 의 등식이 성립하며 형식으로 표현
된다(단, 는 와 대응되는 로서 가운데 하나의 값임).
확장된 진법 표현은 순서가 보존된다. 이고 일 때 이면
<45>
가 성립하고, 역으로 이면 가 성립하게 된다.
도 4는 베타 전개를 이용한 암호화된 수치 데이타를 검색하기 위한 개념도이다.
<46>
사용자가 임의의 수 n을 가지고 있는 데이타를 검색하고 싶다고 하자. 사용자는 비밀키
<47>
을 이용하여 임의의 수 n을 베타 전개한 후, 그 결과 값 을 서버(20)에 전송하면, 서버 (20)를 이를 이용하여 검색을 수행하고 해당되는 검색 결과를 사용자의 클라이언트(10)로 전송한다.
이후, 베타 전개를 이용하여 복호화 키로 암호화된 수치 데이타를 복호화한다.
<48>
베타 전개(beta expansion)를 이용함 암호화 기술은 수치 데이타의 크기 순서가 보존되기 때문에 임의의 수 n보
<49>
다 작은 수를 모두 찾는 와일드카드 검색과, 를 만족하는 모든 n을 찾는 구간 검색이 모두 가능하여 효율적으로 암호화된 수치 데이타의 검색이 이루어질 수 있다.
즉, 비밀키 방식의 암호화 키로 수치 데이타를 암호화하여 저장할 경우, 이에 대한 검색을 빠르게 할 수 있도록
<50>
베타 전개(beta expansion)를 이용하여 수치 데이타의 크기 순서를 보존하기 때문에 검색이 용이하고, 와일드카 드 검색 및 구간 검색이 가능하다.
이상에서 설명한 바와 같이, 본 발명의 바람직한 실시예를 참조하여 설명하였지만, 본 발명이 속하는 기술 분야
<51>
에서 통상의 지식을 가진자가 하기의 특허청구범위에 기재된 본 발명의 기술적 사상 및 영역으로부터 벗어나지 않는 범위 내에서 본 발명을 다양하게 수정 또는 변형하여 실시할 수 있다.
도면의 간단한 설명
도 1은 본 발명에 따른 베타 전개를 이용한 순서 보존 수치데이타 대칭키 암호화 및 복호화 시스템의 구성도.
<52>
도 2는 본 발명의 일실시예에 따른 베타 전개를 이용한 순서 보존 수치데이타 대칭키 암호화 및 복호화 방법을
<53>
설명한 흐름도.
도 3은 인 경우, 베타 전개를 이용한 수치 데이타 암호화를 위한 인덱스를 설정하는 방법에 대한 개념도.
<54>
도 4는 베타 전개를 이용한 암호화된 수치 데이타를 검색하기 위한 개념도.
<55>
<도면의 주요 부분에 대한 부호의 설명>
<56>
10: 클라이언트 11: 비밀키 생성부
<57>
12: 수치 데이타 암호화부 13: 검색부
<58>
14: 수치 데이타 복호화부 20: 서버
<59>
23: 저장부
<60>
도면 도면1
도면2
도면3
도면4
