KR101493212B1

KR101493212B1 - 아이디 기반 암호화, 복호화 방법 및 이를 수행하기 위한 장치

Info

Publication number: KR101493212B1
Application number: KR20120122508A
Authority: KR
Inventors: 윤효진; 천정희; 이선영; 이형태; 손정훈
Original assignee: 삼성에스디에스 주식회사; 서울대학교산학협력단
Priority date: 2012-10-31
Filing date: 2012-10-31
Publication date: 2015-02-23
Also published as: US9379891B2; CN103795533B; US20140192976A1; WO2014069778A1; KR20140055509A; CN103795533A

Abstract

아이디 기반 암호화, 복호화 방법 및 이를 수행하기 위한 장치가 개시된다. 본 발명의 일 실시예에 따른 아이디 기반 암호화 방법은, 송신 단말에서, 키 발급 서버로부터 송신측 아이디에 대응되는 송신측 개인키(a)를 발급받는 단계; 상기 송신 단말에서, 상기 송신측 아이디, 수신측 아이디 및 상기 송신측 개인키를 이용하여 세션키(S)를 생성하는 단계; 상기 송신 단말에서, 상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및 상기 송신 단말에서, 기 설정된 암호화 알고리즘 및 상기 비밀키를 이용하여 메시지를 암호화하는 단계를 포함한다.

Description

아이디 기반 암호화, 복호화 방법 및 이를 수행하기 위한 장치{METHOD AND SYSTEM FOR ID-BASED ENCRYPTION AND DECRYPTION}

본 발명은 메시지의 암호화 및 복호화 기술과 관련된다.

아이디 기반 암호 기술은 최근 빅 데이터 트렌드(big data trend)와 사물 인터넷(internet of things) 환경에서 새롭게 주목을 받고 있다. 또한 클라우드 환경에서 다양한 보안 이슈들이 대두됨에 따라 아이디 기반 암호 기술의 활용에 대한 니즈가 증가하고 있으며, 특히 기존 PC나 서버 환경이 아닌 모바일 등의 소형 단말에서 동작이 가능한 아이디 기반 암호 기술이 필요하게 되었다. 그러나, 기존 아이디 기반 암호 기술은 대부분 페어링(pairing)을 이용한 기술인 바, 클라이언트 단의 모바일 등 소형 단말에서 동작하기에는 그 계산량이 지나치게 많고 복잡한 문제가 있었다. 또한 이를 해결하기 위하여 래티스(lattice)를 이용한 방법이 도입되었으나, lattice를 이용한 방법은 계산 성능은 뛰어나지만 공개키 크기, 암호문의 크기 등의 파라미터의 크기가 너무 크다는 단점을 지닌다.

본 발명의 실시예들은 적은 계산량 및 작은 암호문 사이즈로도 충분한 안정성을 확보할 수 있는 메시지 암호화 및 복호화 알고리즘을 제공하는 데 그 목적이 있다.

본 발명의 일 실시예에 따른 아이디 기반 암호화 방법은, 송신 단말에서, 키 발급 서버로부터 송신측 아이디에 대응되는 송신측 개인키(a)를 발급받는 단계; 상기 송신 단말에서, 상기 송신측 아이디, 수신측 아이디 및 상기 송신측 개인키를 이용하여 세션키(S)를 생성하는 단계; 상기 송신 단말에서, 상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및 상기 송신 단말에서, 기 설정된 암호화 알고리즘 및 상기 비밀키를 이용하여 메시지를 암호화하는 단계를 포함한다.

한편, 본 발명의 일 실시예에 따른 아이디 기반 복호화 방법은, 수신 단말에서, 키 발급 서버로부터 수신측 아이디에 대응되는 수신측 개인키(b)를 발급받는 단계; 상기 수신 단말에서, 송신측 아이디, 상기 수신측 아이디 및 상기 수신측 개인키(b)를 이용하여 세션키(S)를 생성하는 단계; 상기 수신 단말에서, 상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및 상기 수신 단말에서, 기 설정된 복호화 알고리즘 및 상기 비밀키를 이용하여 암호화된 메시지를 복호화하는 단계를 포함한다.

한편, 본 발명의 일 실시예에 따른 장치는, 하나 이상의 프로세서; 메모리; 및 하나 이상의 프로그램을 포함하는 장치로서, 상기 하나 이상의 프로그램은 상기 메모리에 저장되고 상기 하나 이상의 프로세서에 의해 실행되도록 구성되며, 상기 프로그램은, 키 발급 서버로부터 송신측 아이디에 대응되는 송신측 개인키(a)를 발급받는 단계; 상기 송신측 아이디, 수신측 아이디 및 상기 송신측 개인키를 이용하여 세션키(S)를 생성하는 단계; 상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및 기 설정된 암호화 알고리즘 및 상기 비밀키를 이용하여 메시지를 암호화하는 단계를 실행하기 위한 명령어들을 포함한다.

한편, 본 발명의 다른 실시예에 따른 장치는, 하나 이상의 프로세서; 메모리; 및 하나 이상의 프로그램을 포함하는 장치로서, 상기 하나 이상의 프로그램은 상기 메모리에 저장되고 상기 하나 이상의 프로세서에 의해 실행되도록 구성되며, 상기 프로그램은, 키 발급 서버로부터 수신측 아이디에 대응되는 수신측 개인키(b)를 발급받는 단계; 송신측 아이디, 상기 수신측 아이디 및 상기 수신측 개인키(b)를 이용하여 세션키(S)를 생성하는 단계; 상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및 기 설정된 복호화 알고리즘 및 상기 비밀키를 이용하여 암호화된 메시지를 복호화하는 단계를 실행하기 위한 명령어들을 포함한다.

본 발명의 실시예들에 따를 경우 종래에 비해 현저히 적은 연산량을 가지면서도 충분한 수준의 보안성을 유지할 수 있게 되므로, 컴퓨팅 파워 및 메모리 용량 등이 제한된 모바일 단말 등에서도 용이하게 적용 가능한 암복호화 알고리즘을 제공할 수 있게 된다. 예를 들어, 기존의 공개키 기반 암호에서는　랜덤 값을 매번 생성하여야 하므로, 암호화/복호화 시마다 지수승　연산이 필요하였으나, 본 발명의 실시예에서는 개인키 발급 시점에서 지수승 연산을 한 번만 수행하고 나면 이후부터는 지수승 연산 없이 동일한 session key로　암호화만　수행하게 되므로 기존에 비해 현저히 적은 연산량을 가지게 된다.

또한, 본 발명의 실시예들에 따를 경우 종래의 암호문에 비해 현저히 작은 암호문 사이즈를 가지게 되므로, 이를 송수신하기 위한 네트워크 트래픽 또한 절감할 수 있는 장점이 있다.

도 1은 본 발명의 일 실시예에 따른 아이디 기반 암복호화 시스템(100)을 설명하기 위한 블록도이다.
도 2는 본 발명의 일 실시예에 따른 아이디 기반 암복호화 알고리즘(200)의 전체 단계를 설명하기 위한 도면이다.
도 3은 본 발명의 일 실시예에 따른 송신 단말(102)에서의 아이디 기반 암호화 과정(206)을 나타낸 순서도이다.
도 4는 본 발명의 일 실시예에 따른 송신 단말(102)에서의 아이디 기반 암호화 과정(208)을 나타낸 순서도이다.

이하, 도면을 참조하여 본 발명의 구체적인 실시형태를 설명하기로 한다. 그러나 이는 예시에 불과하며 본 발명은 이에 제한되지 않는다.

본 발명을 설명함에 있어서, 본 발명과 관련된 공지기술에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략하기로 한다. 그리고, 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다.

본 발명의 기술적 사상은 청구범위에 의해 결정되며, 이하의 실시예는 본 발명의 기술적 사상을 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 효율적으로 설명하기 위한 일 수단일 뿐이다.

도 1은 본 발명의 일 실시예에 따른 아이디 기반 암복호화 시스템(100)을 설명하기 위한 블록도이다. 도시된 바와 같이, 본 발명의 일 실시예에 따른 아이디 기반 암복호화 시스템(100)은 송신 단말(102), 수신 단말(104), 인증 서버(106) 및 키 발급 서버(108)를 포함한다.

송신 단말(102)은 메시지를 암호화하여 수신 단말(104)로 전송하기 위한 단말이다. 송신 단말(102)은 자신의 아이디(즉, 송신측 아이디), 수신측 아이디 및 상기 송신측 아이디로부터 계산된 송신측 개인키를 이용하여 메시지 암호화를 위한 비밀키를 생성하고, 상기 비밀키 및 기 설정된 암호화 알고리즘을 이용하여 메시지를 암호화한 뒤 이를 수신 단말(104)로 전송한다. 수신 단말(104)은 수신된 메시지를 복호화하여 메시지를 추출하기 위한 단말이다. 또한 수신 단말(102)은 송신 단말(102)로부터 암호화된 메시지를 수신하고, 송신측 아이디, 수신측 아이디 및 상기 수신측 아이디로부터 계산된 수신측 개인키를 이용하여 암호화된 메시지의 복호화를 위한 비밀키를 생성하며, 상기 비밀키 및 기 설정된 복호화 알고리즘을 이용하여 암호화된 메시지를 복호화한다. 이때, 상기 송신측 아이디 및 수신측 아이디는 각각 송신 단말(102) 및 수신 단말(104)을 식별하기 위한 식별 정보로서, 예를 들어 각 단말의 맥 어드레스, 단말에 부여된 고유 식별 번호, 각 단말 사용자의 아이디, 또는 전화 번호 등, 특정 단말을 타 단말과 구별 가능하도록 할 수 있는 다양한 정보들이 제한 없이 사용될 수 있다. 그리고 상기 송신측 개인키 및 수신측 개인키는 후술할 키 발급 서버(108)를 통하여 발급되며, 상기 송신측 개인키 및 수신측 개인키의 발급을 위하여 인증 서버(106)를 통한 인증 과정을 거칠 수 있다. 또한, 본 발명의 실시예에서 상기 암호화 알고리즘 및 복호화 알고리즘은 암호학적으로 안전한 대칭키 기반 알고리즘이 사용될 수 있다. 대칭키 기반 알고리즘이란 암호화에 사용되는 암호키 및 복호화에 사용되는 복호키가 동일한 알고리즘을 의미하는 것으로서, 일반적으로 대칭키 기반 알고리즘에서 복호화는 암호화의 역순이 된다.

인증 서버(106)는 송신 단말(102) 및 수신 단말(104)을 인증하기 위한 서버이다. 본 발명에서는 메시지의 암호화 및 복호화를 위하여 송신 단말(102) 및 수신 단말(104)에 할당된 아이디를 이용하므로, 암호화 및 복호화 과정을 수행하기 이전에 각 단말들이 해당 아이디의 적법한 소유자인지의 여부를 인증할 필요가 있다. 이에 따라 인증 서버(106)는 송신 단말(102) 또는 수신 단말(104)로부터 각 단말들의 아이디를 포함하는 인증 요청을 수신하고, 수신된 상기 인증 요청에 따라 송신 단말(102) 또는 수신 단말(104)을 인증한다. 상기 인증 결과는 실시예에 따라 송신 단말(102) 또는 수신 단말(104)로 전송될 수도 있고, 후술할 키 발급 서버(108)로 전송될 수도 있으며, 이들 모두로 전송될 수도 있다.

키 발급 서버(108)는 송신 단말(102) 및 수신 단말(104)로부터 각각 송신측 아이디 및 수신측 아이디를 수신하고, 수신된 상기 송신측 아이디 및 수신측 아이디에 대응되는 송신측 개인키 및 수신측 개인키를 송신 단말(102) 및 수신 단말(104)로 발급해준다. 이를 위하여 키 발급 서버(108)는 개인키 생성자 (PKG; Private Key Generator)를 포함하며, 상기 개인키 발급 장치는 키 발급 서버(108)의 일 구성요소로서 존재하거나, 또는 키 발급 서버(108)와 별도의 구성요소로서 키 발급 서버(108)와 통신망 등을 통하여 데이터를 교환하도록 구성될 수도 있다. 상기 개인키 발급 장치는 기 설정된 시스템 파라미터와 자신의 마스터키, 그리고 트랩도어 이산 로그(Trapdoor discrete logarithm) 군에 해당하는 사전계산 데이터를 기반으로 수신된 아이디에 대응되는 개인키를 계산한다. 상기 개인키 발급과 관련된 상세한 사항은 후술하기로 한다.

전술한 바와 같이, 키 발급 서버(108)는 인증된 단말에 대해서만 개인키를 발급하도록 구성될 수 있으며, 이를 위하여 키 발급 서버(108)는 인증 서버(106)로부터 단말의 인증 결과를 전달받을 수 있다. 또한, 도시된 실시예에서는 인증 서버(106)와 키 발급 서버(108)가 별도의 주체를 구성하는 것으로 도시되었으나, 실시예에 따라 인증 서버(106) 및 키 발급 서버(108)는 동일한 컴퓨터 장치 내의 구성요소로서 형성될 수도 있다. 이는 전술한 개인키 생성자(PKG) 또한 마찬가지임은 전술하였다.

이하에서는 상술한 구성을 가지는 아이디 기반 암복호화 시스템(100)에서의 암호화 및 복호화의 구체적인 사항을 설명한다. 본 발명의 실시예에서는 트랩도어 이산 로그(TDL)군에서 효율적인 암복호화가 가능한 아이디 기반 핵심 암호 알고리즘을 제안한다. 도 2에 도시된 바와 같이, 본 알고리즘은 셋업(Setup, 202), 개인키 발급(Key extract, 204), 암호화(Encryption, 206) 및 복호화(Decryption, 208)의 4 과정으로 구성된다. 이 중, 셋업 단계(202)에서는 시스템 전체의 구성 요소를 정의하고, 개인키 발급 단계(204)에서는 개인키 생성자(Private key generator - PKG)가 마스터 키를 기반으로 사용자의 아이디에 대응되는 개인키들을 생성해준다. 암호화 단계(206)에서는 송신자가 수신자의 아이디를 이용하여 전송하고자 하는 메시지를 암호화하며, 복호화 단계(208)에서는 수신자가 자신의 아이디에 대응되는 개인키를 이용하여 수신된 암호문을 복호화하는 과정을 설명한다.

셋업 (202)

본 발명의 실시예에서 셋업 단계는 메시지의 암호화 및 복호화에 사용되는 파라미터들을 정의하는 단계이다. 먼저, 주어진 안전성 파라미터 (security parameter) l에 대해 각각 p≡1 (mod 4), q≡3 (mod 4)를 만족하는 비슷한 크기의 두 소수로부터 N = pq 를 계산한다. 이 때, p와 q는 주어진 안전성 파라미터에 해당하는 보안 강도 (security level)를 만족하고 암호학적으로 안전한 소수이다. 안정성 파라미터란 암호화 알고리즘에 대한 기본공격의 시간과 비용을 결정짓는 알고리즘의 요소를 의미한다. 이때 기본 공격이란 주어진 데이터(평문과 암호문)를 만족시키는 키를 발견할 때까지 모든 가능한 키 후보를 검색하는 전수조사(Exhaustive Search) 방식의 공격을 의미한다. 전수 조사에 걸리는 시간은 가능한 키의 개수에 의존하고 키의 개수는 키의 길이에 의해 결정되므로, 이 경우 안전성 파라미터는 키의 길이를 의미한다.

다음으로, 메시지의 암호화 및 복호화에 사용되는 제1해시함수(H₁) 및 제2해시함수(H₂)를 정의한다. 유한한 군 Z_N = {0, 1, 2, ..., N-1}의 최대 순환 부분군(maximal cyclic subgroup) G의 생성원(generator)을 g라 하자. 이로부터 제1해시함수(H₁)는 다음과 같이 정의된다.

H₁: {0,1}^* -> G

(이때, {0,1}^*은 0 또는 1 중 임의의 비트를 의미)

상기 제1해시함수(H₁)로는 예를 들어, SHA1, SHA-256, SHA-512 등의 랜덤 해시함수를 사용할 수 있으며, 상기 랜덤 해시함수의 출력값인 임의의 문자열(bit string)을 군 G로 매핑하기 위하여 위하여 자코비 심볼(Jacobi symbol) 등을 이용할 수 있다.

또한, 제2해시함수(H2)는 다음과 같이 정의된다.

H₂: {0,1}^* -> {0,1}ⁿ

(이때, {0,1}ⁿ은 0 또는 1 중 임의의 비트로 구성된 n비트의 문자열을 의미)

상기 제2해시함수(H₂) 또한 예를 들어, SHA1, SHA-256, SHA-512 등의 랜덤 해시함수가 사용될 수 있으며, 그 출력값은 랜덤한 n-bit string이 된다. 이때 상기 n 값은 후술할 암호화 과정에서 사용되는 대칭키 기반 암호화 알고리즘의 종류에 따라 128bit, 160bit, 512bit 등의 값을 가질 수 있다.

다음으로, 메시지의 암호화 및 복호화에 사용되는 대칭키 기반 암호 알고리즘 E_sym: {0,1}^k -> {0,1}^k 을 정의하고 이와 같이 사용할 동작 모드(modes of operation, MoO)도 정의한다. 이 때, 상기 대칭키 기반 암호 알고리즘의 메시지 사이즈 k는 n과 같을 수도 있고, n과 관련된 값(예를 들어, k=1/2*n)을 가질 수도 있다.

이와 같은 과정을 거쳐 도출되는 시스템 파라미터(param_R) 및 마스터키(mk_root)는 다음과 같다.

param_R = (N, G, g, H₁, H₂, E_sym, MoO)

mk_root = (p, q)

개인키 발급(204)

본 단계는 키 발급 서버(108)에서 수신된 송신측 아이디 또는 수신측 아이디를 기반으로 송신측 또는 수신측 개인키를 발급하는 단계이다. 키 발급 서버(108)의 개인키 생성자(PKG)는 상기 시스템 파라미터(param_R) 및 마스터키(mk_root), 그리고 트랩도어 이산 로그(TDL) 군에 해당하는 사전계산 데이터를 기반으로 주어진 아이디에 대응되는 개인키를 계산한다. 수학적으로, 트랩도어라 불리우는 특정 정보를 가지고 있는 경우에는 상대적으로 쉽게 이산 로그를 계산할 수 있으나 그렇지 않은 경우에는 이산 로그 계산이 매우 어려운 군이 존재하며 이를 트랩도어 이산 로그 군이라 한다. 본 발명에서는 이와 같은 트랩도어 이산 로그군의 특성을 이용하여 각 아이디에 대응되는 개인키를 계산한다. 즉, 상기 개인키 생성자는 상기 트랩도어 이산 로그군에 해당하는 각 값들에 대한 사전 계산 데이터를 예를 들어 테이블 등의 형태로 저장해 두었다가 수신되는 아이디와 상기 테이블에 저장된 사전 계산 데이터를 이용하여 수신된 아이디에 대응되는 개인키를 계산한다. 구체적으로, 개인키 생성자(PKG)는 수신되는 아이디(ID)를 제1해시함수(H₁)를 이용하여 TDL 군 G의 원소로 변환하고, 전술한 사전계산 데이터를 이용하여 H₁(ID)의 밑 g에 대한 이산로그 값을 계산한다. 즉, 다음과 같다.

개인키 x = log_g(H₁(ID))

전술한 바와 같이, 개인키 발급 과정 수행 전, 사용자는 본인의 ID에 대한 소유권 및 사용자 인증 과정을 먼저 수행하여야 한다. 또한 개인키 발급을 위한 온라인 또는 오프라인 연결 및 데이터 전송은 암호학 및 정보 통신 보안 관점에서 안전하게 보호되어야 한다.

암호화(206)

본 단계는 송신 단말(102)에서 수신 단말(104)로 전송할 메시지(m)를 암호화하는 단계이다. 이때 송신 단말(102)의 아이디를 A, 수신 단말(104)의 아이디를 B라 하자. 전술한 개인키 발급 과정을 통하여, 송신 단말(102)은 자신의 아이디 A에 대응되는 송신측 개인키 a = log_g(H₁(A))를 갖고 있다.

도 3은 본 발명의 일 실시예에 따른 송신 단말(102)에서의 아이디 기반 암호화 과정(206)을 나타낸 순서도이다.

먼저 송신 단말(102)은 제1해시함수(H₁)를 이용하여 송신측 아이디(A) 및 수신측 아이디(B)를 해싱함으로써 제1 세션키 엘리먼트(h_A) 및 제2 세션키 엘리먼트(h_B)를 생성한다(302). 이를 수식으로 표현하면 다음과 같다.

h_A = H₁(A)

h_B = H₁(B)

이때, 송신 단말(102)은 자신의 아이디에 대응되는 제1해시함수(H₁)의 출력값인 h_A를 사전에 계산하여 저장해놓을 수 있다. 또한, 상기 수신측 아이디(B)의 해시값 또한 저장해 놓을 경우, 이후 동일한 수신 단말(104)로의 메시지 전송 시 이를 중복하여 계산할 필요 없이 저장된 값을 이용할 수 있다.

다음으로, 송신 단말(102)은 상기 제2 세션키 엘리먼트에 대한 송신측 개인키(a)의 지수승을 계산하여 제3 세션키 엘리먼트((h_B)^a)를 생성하며(304), 이후 상기 제1 세션키 엘리먼트, 상기 제2 세션키 엘리먼트 및 상기 제3 세션키 엘리먼트를 포함하는 세션키 생성 문자열을 생성하고, 제2해시함수(H₂)를 이용하여 상기 세션키 생성 문자열을 해싱함으로써 세션키(S)를 생성한다(306). 먼저, 상기 세션키 생성 문자열은 다음과 같이 앞서 계산된 h_A, ((h_B)^a), h_B 값을 연접하여 생성될 수 있다.

세션키 생성 문자열 = (h_A || (h_B)^a || h_B)

이때, 상기 세션키 생성 문자열을 구성하는 각 세션키 엘리먼트의 연접 순서는 특별히 제한되지 않으나, 송신 단말(102)과 수신 단말(104) 사이에는 동일한 순서로 세션키 엘리먼트를 연접하여야 함은 자명하다.

한편, 이와 같은 방식으로 세션키 생성 문자열을 생성할 경우, 동일한 송신자와 수신자 사이에는 매번 동일한 세션키 생성 문자열이 생성되는 문제가 존재한다. 따라서 이를 해결하기 위하여 상기 세션키 생성 문자열에 별도의 추가 문자열(제1추가 문자열을) 더 포함시킬 수 있다. 예를 들어, 다음과 같다.

세션키 생성 문자열 = (h_A || (h_B)^a || h_B || 제1추가 문자열)

이때, 상기 제1추가 문자열은 예를 들어, 메시지 생성 날짜, 또는 시각, 메시지의 일련번호 등 매번 다른 값을 가질 수 있으며, 송신 단말(102) 및 수신 단말(104) 사이에서 공유 가능한 정보가 될 수 있다. 이와 같이 세션키 생성 문자열에 별도의 추가 문자열을 덧붙일 경우 매번 다른 세션키 생성 문자열을 생성할 수 있으며, 이에 따라 후술할 세션키 또한 매번 달라지게 된다.

이와 같이 세션키 생성 문자열이 구성되면, 송신 단말(102)은 이를 제2해시함수(H₂)를 이용하여 해싱함으로써 세션키를 생성한다. 즉, 다음과 같다.

S = H₂(세션키 생성 문자열)

다음으로, 송신 단말(102)은 생성된 상기 세션키(S)의 적어도 일부로부터 비밀키(S_key)를 추출한다(308). 예를 들어, 상기 세션키는 그 자체로 비밀키가 될 수 있다(즉, S = S_key). 또는, 세션키(S)를 구성하는 이진 문자열 중 일부를 비밀키(S_key)에 할당하고, 비밀키에 할당된 이진 문자열을 제외한 나머지 문자열을 메시지 암호화를 위한 초기화 벡터(IV, Initialization Vector)에 할당할 수도 있다. 예를 들어, 제2해시함수(H₂)로 SHA-256을 사용하는 경우, S는 256bit 랜덤 이진 문자열이 되며, 이 중 하위 (또는 상위) 128bit를 비밀키(S_key)에, 상위 (또는 하위) 128bit는 CBC mode 등의 IV에 할당함으로써 128bit의 비밀키를 갖는 대칭키 기반 암호 알고리즘 (예를 들어, AES-128 등)에 적용할 수 있다. 즉, 이 경우 S = S_key||IV 또는 IV||S_key 가 된다. 다만, 이 방법은 매 번 다른 IV 값이 필요한 CTR 모드 등에는 적용될 수 없으며, 이 경우에는 별도의 IV 생성 알고리즘이 필요하게 된다.

다음으로, 송신 단말(102)은 기 설정된 대칭키 기반 암호화 알고리즘(E_sym) 및 상기 비밀키를 이용하여 메시지를 암호화하여 암호문(C)을 생성한다(310)(즉, C = MoO(E_sym(S_key, m), IV)). 예를 들어, H₂로 SHA-256, 대칭키 기반 암호화 알고리즘(E_sym)으로 AES-128, MoO로 CBC 모드를 사용하는 경우, 만약 S = S_key||IV로 사용할 경우 C = AES - CBC₍ _skey _, _IV ₎(m)이 된다.

한편, 대칭키 암호화 알고리즘의 특성 상 입력 정보인 원본 메시지(m)와 비밀키(S_key)가 동일하면 출력값인 암호문(C) 또한 동일하게 나오게 된다. 따라서 이를 방지하기 위하여 상기 암호화 단계에서는 송신 단말(102) 및 수신 단말(104)간에 기 설정된 추가 문자열(제2 추가 문자열)을 상기 메시지에 부가함으로써 입력값(원본 메시지)이 같아도, 매번 다른 출력값(암호메시지)을 얻을 수 있도록 구성될 수 있다. 이 경우, 수신 단말(1040은 암호문에 대한 복호화 이후 상기 제2 추가 문자열을 삭제함으로써 원본 메시지를 그대로 얻을 수 있다. 상기 제2 추가 문자열은 제1추가 문자열과 마찬가지로, 예를 들어 메시지 생성 날짜, 또는 시각, 메시지의 일련번호 등 매번 다른 값을 가질 수 있으며, 송신 단말(102) 및 수신 단말(104) 사이에서 공유 가능한 값으로 구성될 수 있다.

이와 같은 과정을 거쳐 암호문이 생성되면, 송신 단말(102)은 생성된 암호문 C 및 송신 단말의 아이디 A를 수신 단말(104)로 전송한다.

복호화(208)

본 단계는 수신 단말(102)에서 송신 단말(102)로부터 전송된 암호문(C)를 복호화하는 단계이다. 이때 송신 단말(102)의 아이디를 A, 수신 단말(104)의 아이디를 B라 하자. 전술한 개인키 발급 과정을 통하여, 수신 단말(104)은 자신의 아이디 B에 대응되는 수신측 개인키 b = log_g(H₁(B))를 갖고 있다.

도 4는 본 발명의 일 실시예에 따른 송신 단말(102)에서의 아이디 기반 암호화 과정(208)을 나타낸 순서도이다.

먼저 수신 단말(104)은 제1해시함수(H₁)를 이용하여 송신측 아이디(A) 및 수신측 아이디(B)를 해싱함으로써 제1 세션키 엘리먼트(h_A) 및 제2 세션키 엘리먼트(h_B)를 생성한다(402). 이를 수식으로 표현하면 다음과 같다.

h_A = H₁(A)

h_B = H₁(B)

이때, 수신 단말(104)은 자신의 아이디(B)에 대응되는 제1해시함수(H₁)의 출력값인 h_B를 사전에 계산하여 저장해놓을 수 있다. 또한, 상기 송신측 아이디(A)의 해시값 또한 저장해 놓을 경우, 이후 동일한 송신 단말(102)로부터의 메시지 전송 시 이를 중복하여 계산할 필요 없이 저장된 값을 이용할 수 있다.

다음으로, 수신 단말(104)은 상기 제1 세션키 엘리먼트에 대한 수신측 개인키(b)의 지수승을 계산하여 제3 세션키 엘리먼트((h_A)^b)를 생성한다(404). 이때, 다음의 수식에서 알 수 있는 바와 같이 상기 404 단계에서 생성된 수신측 제3 세션키 엘리먼트는 304 단계에서 생성된 송신측 제3 세션키 엘리먼트와 동일하다. 즉, 본 발명의 실시예들에 따를 경우 별도의 키 교환 과정을 거치지 않고도 송신측과 수신측 사이에서 동일한 비밀키를 얻을 수 있게 된다.

(h_A)^b = (h_B)^a = g^ab

다음으로, 수신 단말(104)은 상기 제1 세션키 엘리먼트, 상기 제2 세션키 엘리먼트 및 상기 제3 세션키 엘리먼트를 포함하는 세션키 생성 문자열을 생성하고, 제2해시함수(H₂)를 이용하여 상기 세션키 생성 문자열을 해싱함으로써 세션키(S)를 생성한다(406). 이때, 상기 세션키 생성 문자열 생성 규칙은 송신 단말(102)과 동일한 것을 사용하며, 필요한 경우 사전에 송신 단말(102)과의 사이에서 약속된 제1추가 문자열을 부가할 수 있다. 이와 같은 과정을 거치게 되면 송신 단말(102)과 동일한 세션키가 생성된다.

다음으로, 수신 단말(104)은 생성된 상기 세션키(S)의 적어도 일부로부터 비밀키(S_key)를 추출한다(408). 즉, 본 단계에서는 상기 308 단계에서와 동일한 방법으로 비밀키 또는 비밀키/초기화 벡터 쌍을 추출하게 된다.

마지막으로, 수신 단말(104)은 기 설정된 대칭키 기반 암호화 알고리즘(E_sym), 상기 비밀키 및 동작 모드에 따라 공유된 초기화 벡터를 이용하여 수신된 암호문을 복호화함으로써 메시지를 복원한다. 이때, 만약 복호화된 메시지에 제2추가 문자열이 부가되어 있는 경우에는 이를 삭제하는 과정을 추가적으로 거치게 된다.

한편, 본 발명의 실시예는 본 명세서에서 기술한 방법들을 컴퓨터상에서 수행하기 위한 프로그램을 포함하는 컴퓨터 판독 가능 기록매체를 포함할 수 있다. 상기 컴퓨터 판독 가능 기록매체는 프로그램 명령, 로컬 데이터 파일, 로컬 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체는 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 분야에서 통상의 지식을 가진 자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체, CD-ROM, DVD와 같은 광 기록 매체, 플로피 디스크와 같은 자기-광 매체, 및 롬, 램, 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함할 수 있다.

이상에서 대표적인 실시예를 통하여 본 발명에 대하여 상세하게 설명하였으나, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 상술한 실시예에 대하여 본 발명의 범주에서 벗어나지 않는 한도 내에서 다양한 변형이 가능함을 이해할 것이다.

그러므로 본 발명의 권리범위는 설명된 실시예에 국한되어 정해져서는 안 되며, 후술하는 특허청구범위뿐만 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.

100: 아이디 기반 암복호화 시스템
102: 송신 단말
104: 수신 단말
106: 인증 서버
108: 키 발급 서버

Claims

송신 단말에서, 키 발급 서버로부터 송신측 아이디에 대응되는 송신측 개인키(a)를 발급받는 단계;
상기 송신 단말에서, 상기 송신측 아이디 및 수신측 아이디로부터 각각 제1 세션키 엘리먼트(h_A) 및 제2 세션키 엘리먼트(h_B)를 생성하는 단계;
상기 송신 단말에서, 제2 세션키 엘리먼트(h_B)로부터 제3 세션키 엘리먼트(h_C)를 생성하는 단계;
상기 송신 단말에서, 상기 제1 세션키 엘리먼트(h_A), 상기 제2 세션키 엘리먼트(h_B) 및 상기 제3 세션키 엘리먼트(h_c)를 포함하는 세션키 생성 문자열을 생성하고, 상기 세션키 생성 문자열로부터 세션키(S)를 생성하는 단계;
상기 송신 단말에서, 상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및
상기 송신 단말에서, 기 설정된 암호화 알고리즘 및 상기 비밀키를 이용하여 메시지를 암호화하는 단계를 포함하는 아이디 기반 암호화 방법.
삭제
청구항 1에 있어서,
상기 제1 세션키 엘리먼트(h_A) 및 제2 세션키 엘리먼트(h_B)는 제1해시함수(H₁)를 이용하여 상기 송신측 아이디 및 상기 수신측 아이디를 각각 해싱함으로써 생성되고,
상기 제3 세션키 엘리먼트(h_c)는 상기 제2 세션키 엘리먼트(h_B)에 대한 상기 송신측 개인키(a)의 지수승을 계산함으로써 생성되며,
상기 세션키(S)는 제2해시함수(H₂)를 이용하여 상기 세션키 생성 문자열(S)을 해싱함으로써 생성되는, 아이디 기반 암호화 방법.
청구항 3에 있어서,
상기 송신측 개인키는 다음의 수학식
a = log_g(H₁(A))
(이때, a는 송신측 개인키, H₁은 제1해시함수, A는 송신측 아이디, g는 군 Z_N의 최대 순환 부분군 G의 생성원, N = pq를 만족하는 정수, p 및 q는 각각 p≡1 (mod 4), q≡3 (mod 4)를 만족하는 소수)
에 의하여 계산되는, 아이디 기반 암호화 방법.
청구항 4에 있어서,
상기 제1해시함수는 임의의 이진 문자열을 상기 최대 순환 부분군 G 내의 임의의 원소로 매핑시키도록 설정되는, 아이디 기반 암호화 방법.
청구항 1에 있어서,
상기 세션키 생성 문자열은, 상기 송신 단말 및 상기 수신 단말간에 기 설정된 제1추가 문자열을 더 포함하는, 아이디 기반 암호화 방법.
청구항 1에 있어서,
상기 비밀키를 추출하는 단계는,
상기 세션키를 구성하는 이진 문자열 중 일부를 추출하여 상기 비밀키에 할당하는 단계; 및
상기 비밀키에 할당된 이진 문자열을 제외한 나머지 문자열을 상기 메시지 암호화를 위한 초기화 벡터에 할당하는 단계를 더 포함하는, 아이디 기반 암호화 방법.
청구항 7에 있어서,
상기 메시지를 암호화하는 단계는, 상기 암호화 알고리즘, 상기 암호화 알고리즘의 동작 모드, 상기 비밀키 및 상기 초기화 벡터를 이용하여 상기 메시지를 암호화하는, 아이디 기반 암호화 방법.
청구항 8에 있어서,
상기 메시지를 암호화하는 단계는, 상기 송신 단말 및 상기 수신 단말간에 기 설정된 제2 추가 문자열을 상기 메시지에 부가하는 단계를 더 포함하는, 아이디 기반 암호화 방법.
수신 단말에서, 키 발급 서버로부터 수신측 아이디에 대응되는 수신측 개인키(b)를 발급받는 단계;
상기 수신 단말에서, 송신측 아이디 및 상기 수신측 아이디로부터 각각 제1 세션키 엘리먼트(h_A) 및 제2 세션키 엘리먼트(h_B)를 생성하는 단계;
상기 수신 단말에서, 제2 세션키 엘리먼트(h_B)로부터 제3 세션키 엘리먼트(h_C)를 생성하는 단계;
상기 수신 단말에서, 상기 제1 세션키 엘리먼트(h_A), 상기 제2 세션키 엘리먼트(h_B) 및 상기 제3 세션키 엘리먼트(h_C)를 포함하는 세션키 생성 문자열을 생성하고, 상기 세션키 생성 문자열로부터 세션키(S)를 생성하는 단계;
상기 수신 단말에서, 상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및
상기 수신 단말에서, 기 설정된 복호화 알고리즘 및 상기 비밀키를 이용하여 암호화된 메시지를 복호화하는 단계를 포함하는 아이디 기반 복호화 방법.
삭제
청구항 10에 있어서,
상기 제1 세션키 엘리먼트(h_A) 및 제2 세션키 엘리먼트(h_B)는 제1해시함수(H₁)를 이용하여 상기 송신측 아이디 및 상기 수신측 아이디를 각각 해싱함으로써 생성되고,
상기 제3 세션키 엘리먼트(h_C)는 상기 제1 세션키 엘리먼트(h_A)에 대한 상기 수신측 개인키(b)의 지수승을 계산함으로써 생성되며,
상기 세션키(S)는 제2해시함수(H₂)를 이용하여 상기 세션키 생성 문자열을 해싱함으로써 생성되는, 아이디 기반 복호화 방법.
청구항 12에 있어서,
상기 수신측 개인키는 다음의 수학식
b = log_g(H₁(B))
(이때, b는 수신측 개인키, H₁은 제1해시함수, B는 수신측 아이디, g는 군 Z_N의 최대 순환 부분군 G의 생성원, N = pq를 만족하는 정수, p 및 q는 각각 p≡1 (mod 4), q≡3 (mod 4)를 만족하는 소수)
에 의하여 계산되는, 아이디 기반 복호화 방법.
청구항 13에 있어서,
상기 제1해시함수는 임의의 이진 문자열을 상기 최대 순환 부분군 G 내의 임의의 원소로 매핑시키도록 설정되는, 아이디 기반 복호화 방법.
청구항 10에 있어서,
상기 세션키 생성 문자열은, 상기 송신 단말 및 상기 수신 단말간에 기 설정된 제1추가 문자열을 더 포함하는, 아이디 기반 복호화 방법.
청구항 10에 있어서,
상기 비밀키를 추출하는 단계는,
상기 세션키를 구성하는 이진 문자열 중 일부를 추출하여 상기 비밀키에 할당하는 단계; 및
상기 비밀키에 할당된 이진 문자열을 제외한 나머지 문자열을 상기 메시지 암호화를 위한 초기화 벡터에 할당하는 단계를 더 포함하는, 아이디 기반 복호화 방법.
청구항 16에 있어서,
상기 메시지를 복호화하는 단계는, 상기 복호화 알고리즘, 상기 복호화 알고리즘의 동작 모드, 상기 비밀키 및 상기 초기화 벡터를 이용하여 상기 메시지를 복호화하는, 아이디 기반 복호화 방법.
청구항 17에 있어서,
상기 메시지를 복호화하는 단계는, 상기 송신 단말 및 상기 수신 단말간에 기 설정된 제2 추가 문자열을 복호화된 메시지로부터 제거하는 단계를 더 포함하는, 아이디 기반 복호화 방법.
청구항 1, 청구항 3 내지 청구항 10 및 청구항 12 내지 청구항 18 중 어느 한 항에 기재된 방법을 컴퓨터상에서 수행하기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.
하나 이상의 프로세서;
메모리; 및
하나 이상의 프로그램을 포함하는 장치로서,
상기 하나 이상의 프로그램은 상기 메모리에 저장되고 상기 하나 이상의 프로세서에 의해 실행되도록 구성되며,
상기 프로그램은,
키 발급 서버로부터 송신측 아이디에 대응되는 송신측 개인키(a)를 발급받는 단계;
상기 송신측 아이디 및 수신측 아이디로부터 각각 제1 세션키 엘리먼트(h_A) 및 제2 세션키 엘리먼트(h_B)를 생성하는 단계;
제2 세션키 엘리먼트(h_B)로부터 제3 세션키 엘리먼트(h_C)를 생성하는 단계;
상기 제1 세션키 엘리먼트(h_A), 상기 제2 세션키 엘리먼트(h_B) 및 상기 제3 세션키 엘리먼트(h_c)를 포함하는 세션키 생성 문자열을 생성하고, 상기 세션키 생성 문자열로부터 세션키(S)를 생성하는 단계;
상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및
기 설정된 암호화 알고리즘 및 상기 비밀키를 이용하여 메시지를 암호화하는 단계를 실행하기 위한 명령어들을 포함하는 장치.
하나 이상의 프로세서;
메모리; 및
하나 이상의 프로그램을 포함하는 장치로서,
상기 하나 이상의 프로그램은 상기 메모리에 저장되고 상기 하나 이상의 프로세서에 의해 실행되도록 구성되며,
상기 프로그램은,
키 발급 서버로부터 수신측 아이디에 대응되는 수신측 개인키(b)를 발급받는 단계;
송신측 아이디 및 상기 수신측 아이디로부터 각각 제1 세션키 엘리먼트(h_A) 및 제2 세션키 엘리먼트(h_B)를 생성하는 단계;
제2 세션키 엘리먼트(h_B)로부터 제3 세션키 엘리먼트(h_C)를 생성하는 단계;
상기 제1 세션키 엘리먼트(h_A), 상기 제2 세션키 엘리먼트(h_B) 및 상기 제3 세션키 엘리먼트(h_C)를 포함하는 세션키 생성 문자열을 생성하고, 상기 세션키 생성 문자열로부터 세션키(S)를 생성하는 단계;
상기 세션키의 적어도 일부로부터 비밀키를 추출하는 단계; 및
기 설정된 복호화 알고리즘 및 상기 비밀키를 이용하여 암호화된 메시지를 복호화하는 단계를 실행하기 위한 명령어들을 포함하는 장치.