[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

KR101599144B1 - 키 생성 장치 및 방법 - Google Patents

키 생성 장치 및 방법 Download PDF

Info

Publication number
KR101599144B1
KR101599144B1 KR1020140093303A KR20140093303A KR101599144B1 KR 101599144 B1 KR101599144 B1 KR 101599144B1 KR 1020140093303 A KR1020140093303 A KR 1020140093303A KR 20140093303 A KR20140093303 A KR 20140093303A KR 101599144 B1 KR101599144 B1 KR 101599144B1
Authority
KR
South Korea
Prior art keywords
symbol
symbols
key
permutation
candidate
Prior art date
Application number
KR1020140093303A
Other languages
English (en)
Other versions
KR20160011956A (ko
Inventor
윤효진
Original Assignee
삼성에스디에스 주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 삼성에스디에스 주식회사 filed Critical 삼성에스디에스 주식회사
Priority to KR1020140093303A priority Critical patent/KR101599144B1/ko
Priority to US14/561,641 priority patent/US9479327B2/en
Priority to CN201410737927.3A priority patent/CN105281898B/zh
Publication of KR20160011956A publication Critical patent/KR20160011956A/ko
Application granted granted Critical
Publication of KR101599144B1 publication Critical patent/KR101599144B1/ko

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
    • H04L9/0618—Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
    • H04L9/0631—Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
    • H04L12/40—Bus networks
    • H04L12/40052—High-speed IEEE 1394 serial bus
    • H04L12/40104—Security; Encryption; Content protection
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords
    • H04L9/0866—Generation of secret information including derivation or calculation of cryptographic keys or passwords involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
    • H04L9/3073—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3226—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using a predetermined code, e.g. password, passphrase or PIN

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Signal Processing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • General Physics & Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Mathematical Optimization (AREA)
  • Mathematical Analysis (AREA)
  • Physics & Mathematics (AREA)
  • Algebra (AREA)
  • Mobile Radio Communication Systems (AREA)
  • Storage Device Security (AREA)

Abstract

예시적인 실시예에 따르면, 사용자 아이디 정보로부터 복수의 심볼을 식별하고, 상기 복수의 심볼로부터 적어도 하나의 순열(permutation)을 도출하도록 구성되는 입력 분석기; 및 상기 복수의 심볼에 각각 대응하는 복수의 제1 사전 계산된 키 및 상기 적어도 하나의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키를 포함하는 복수의 사전 계산된 키를 획득하고, 상기 복수의 사전 계산된 키로부터 상기 사용자 아이디 정보에 대응하는 암호 키를 생성하도록 구성되는 키 생성기를 포함하는 키 생성 장치가 제공된다.

Description

키 생성 장치 및 방법{APPARATUS AND METHOD FOR GENERATING KEY}
개시되는 실시예들은 키 생성 및 발급에 관한 것으로서, 더욱 상세하게는 사용자 아이디 정보를 기반으로 사용자의 개인 키(private key)와 같은 암호 키(cryptographic key)를 생성하기 위한 기술과 관련된다.
통상적인 공개 키(public key) 기반 암호 기법들과 달리, 대부분의 아이디 기반 암호(Identity Based Cryptography: IBC) 기법들은 암호화 및 복호화를 위해 페어링(pairing) 연산이 필요하다. 대안으로서, 트랩도어 이산로그(Trapdoor Discrete Logarithm: TDL) 군을 활용하는 IBC 기법들이 소개되었다. 이러한 TDL-IBC 방식은 클라이언트 측에서 암호화/복호화가 수행될 때 페어링 연산보다 간단한 연산을 수반하므로, 가령 이동통신 단말과 같은 장치에 적용되기에 다른 IBC 방식들보다 유용할 수 있다.
TDL-IBC 방식은 트랩도어에 대한 정보가 알려져 있지 않으면 실제적으로 풀기 어려운 이산로그 문제를 활용하여 키를 생성한다. 다만, 이 방식에 따르면, 사용자의 아이디에 대응하는 개인 키를 추출하는 과정에서 막대한 양의 리소스가 요구될 수 있고, 개인 키의 발급에 소요되는 시간 역시 지나치게 길 수 있다. 이는 사용자의 수가 증가함에 따라 더욱 과다한 비용이 발생할 것임을 의미한다. 따라서, TDL 군과 같은 이산로그 순환군을 이용한 IBC 기법을 실제적으로 적용하기 위한 새로운 접근법이 필요하다.
대한민국 등록특허공보 제10-1166129호 (2012. 07. 10. 등록)
개시되는 실시예들은 사용자 아이디 정보를 기반으로 암호 키를 생성하고 이에 필요한 특정 정보를 미리 계산하기 위한 향상된 기법을 제공한다.
예시적인 실시예에 따르면, 사용자 아이디 정보로부터 복수의 심볼을 식별하고, 상기 복수의 심볼로부터 적어도 하나의 순열(permutation)을 도출하도록 구성되는 입력 분석기; 및 상기 복수의 심볼에 각각 대응하는 복수의 제1 사전 계산된 키 및 상기 적어도 하나의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키를 포함하는 복수의 사전 계산된 키를 획득하고, 상기 복수의 사전 계산된 키로부터 상기 사용자 아이디 정보에 대응하는 암호 키를 생성하도록 구성되는 키 생성기를 포함하는 키 생성 장치가 제공된다.
상기 복수의 사전 계산된 키 각각은 이산로그 순환군 내 원소의 이산로그 값을 나타낼 수 있다.
상기 키 생성기는 또한 상기 암호 키를 생성하기 위해 상기 복수의 사전 계산된 키를 합산하도록 구성될 수 있다.
상기 복수의 심볼 각각은 복수의 후보 심볼 중 하나일 수 있고, 상기 적어도 하나의 순열 각각은 복수의 후보 순열 중 하나일 수 있으며, 상기 복수의 후보 순열 각각은 상기 복수의 후보 심볼의 적어도 일부로부터 도출 가능할 수 있다.
상기 키 생성 장치는 복수의 서브 키가 저장되어 있는 저장부를 더 포함할 수 있고, 상기 복수의 서브 키는 미리 설정된 제1 개수의 서브 키 그룹으로 배열될 수 있고, 상기 키 생성기는 또한 상기 복수의 제1 사전 계산된 키 및 상기 적어도 하나의 제2 사전 계산된 키를 상기 저장부로부터 획득하기 위해 상기 미리 설정된 제1 개수의 서브 키 그룹 중 하나 또는 복수의 서브 키 그룹을 검색하도록 구성될 수 있으며, 상기 미리 설정된 제1 개수의 서브 키 그룹 각각은 복수의 제1 서브 키 및 복수의 제2 서브 키를 포함할 수 있고, 상기 복수의 제1 사전 계산된 키가 상기 저장부로부터 획득 가능하도록 상기 복수의 제1 서브 키 중 각각의 제1 서브 키는 상기 복수의 후보 심볼 중 각자의 후보 심볼에 대응할 수 있고, 상기 적어도 하나의 제2 사전 계산된 키가 상기 저장부로부터 획득 가능하도록 상기 복수의 제2 서브 키 중 각각의 제2 서브 키는 상기 복수의 후보 순열 중 각자의 후보 순열에 대응할 수 있다.
상기 복수의 후보 순열 각각은 미리 설정된 제2 개수의 심볼 인덱스의 적어도 일부의 순열일 수 있고, 상기 입력 분석기는 또한 상기 적어도 하나의 순열로서 상기 미리 설정된 제2 개수의 심볼 인덱스 중 복수의 심볼 인덱스의 순열을 도출하기 위해 상기 복수의 심볼을 상기 복수의 심볼 인덱스와 각각 연관시키도록 구성될 수 있다.
상기 미리 설정된 제1 개수는 1일 수 있다.
상기 복수의 후보 순열 각각은 미리 설정된 제2 개수의 심볼 인덱스 중 적어도 일부의 순열일 수 있고, 상기 입력 분석기는 또한 상기 복수의 심볼을 복수의 심볼 그룹으로 파티셔닝(partitioning)하도록 구성될 수 있으며, 상기 적어도 하나의 순열은 상기 복수의 심볼 그룹에 각각 대응하는 복수의 순열을 포함할 수 있고, 상기 복수의 심볼 그룹 중 각각의 심볼 그룹은 상기 복수의 심볼 중 적어도 하나의 심볼을 포함할 수 있으며, 상기 입력 분석기는 또한 상기 각각의 심볼 그룹에 대하여 상기 복수의 순열 중 대응하는 순열로서 상기 미리 설정된 제2 개수의 심볼 인덱스 중 적어도 하나의 심볼 인덱스의 순열을 도출하기 위해 상기 적어도 하나의 심볼을 상기 적어도 하나의 심볼 인덱스와 각각 연관시키도록 구성될 수 있다.
상기 미리 설정된 제1 개수는 2 이상일 수 있고, 상기 키 생성기는 또한 상기 각각의 심볼 그룹에 대하여 상기 복수의 서브 키 그룹 중 대응하는 서브 키 그룹을 검색하여 상기 복수의 제1 사전 계산된 키 중 적어도 하나의 제1 사전 계산된 키 및 상기 적어도 하나의 제2 사전 계산된 키 중 하나의 제2 사전 계산된 키를 상기 저장부로부터 획득하기 위해 상기 대응하는 서브 키 그룹을 식별하도록 구성될 수 있으며, 상기 적어도 하나의 제1 사전 계산된 키는 상기 적어도 하나의 심볼에 각각 대응할 수 있고, 상기 하나의 제2 사전 계산된 키는 상기 적어도 하나의 심볼 인덱스의 상기 순열에 대응할 수 있다.
상기 키 생성 장치는, 상기 입력 분석기가 상기 복수의 심볼을 식별하기 전에 상기 복수의 서브 키를 계산하여 상기 저장부에 저장하도록 구성된 사전 계산기를 더 포함할 수 있다.
상기 각각의 제1 서브 키는 이산로그 순환군 내 제1 원소의 제1 이산로그 값을 나타낼 수 있고, 상기 각각의 제2 서브 키는 상기 이산로그 순환군 내 제2 원소의 제2 이산로그 값을 나타낼 수 있으며, 상기 사전 계산기는 또한 상기 제1 이산로그 값을 계산하기 위해 상기 각자의 후보 심볼로부터 상기 제1 원소를 생성하고 상기 제2 이산로그 값을 계산하기 위해 상기 각자의 후보 순열로부터 상기 제2 원소를 생성하도록 구성될 수 있다.
상기 사전 계산기는 또한 상기 제1 원소를 생성하기 위해 상기 각자의 후보 심볼에 해쉬 함수를 적용하고 상기 제2 원소를 생성하기 위해 상기 각자의 후보 순열에 상기 해쉬 함수를 적용하도록 구성될 수 있다.
다른 예시적인 실시예에 따르면, 사용자 아이디 정보로부터 복수의 심볼을 식별하는 단계; 상기 복수의 심볼로부터 적어도 하나의 순열을 도출하는 단계; 상기 복수의 심볼에 각각 대응하는 복수의 제1 사전 계산된 키 및 상기 적어도 하나의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키를 포함하는 복수의 사전 계산된 키를 획득하는 단계; 및 상기 복수의 사전 계산된 키로부터 상기 사용자 아이디 정보에 대응하는 암호 키를 생성하는 단계를 포함하는 키 생성 방법이 제공된다.
상기 복수의 사전 계산된 키 각각은 이산로그 순환군 내 원소의 이산로그 값을 나타낼 수 있다.
상기 키 생성 방법은, 상기 암호 키를 생성하기 위해 상기 복수의 사전 계산된 키를 합산하는 단계를 더 포함할 수 있다.
상기 복수의 심볼 각각은 복수의 후보 심볼 중 하나일 수 있고, 상기 적어도 하나의 순열 각각은 복수의 후보 순열 중 하나일 수 있으며, 상기 복수의 후보 순열 각각은 상기 복수의 후보 심볼의 적어도 일부로부터 도출 가능할 수 있다.
상기 키 생성 방법은 복수의 서브 키를 저장부에 저장하는 단계를 더 포함할 수 있고, 상기 복수의 서브 키는 미리 설정된 제1 개수의 서브 키 그룹으로 배열될 수 있고, 상기 키 생성 방법은 상기 복수의 제1 사전 계산된 키 및 상기 적어도 하나의 제2 사전 계산된 키를 상기 저장부로부터 획득하기 위해 상기 미리 설정된 제1 개수의 서브 키 그룹 중 하나 또는 복수의 서브 키 그룹을 검색하는 단계를 더 포함할 수 있으며, 상기 미리 설정된 제1 개수의 서브 키 그룹 각각은 복수의 제1 서브 키 및 복수의 제2 서브 키를 포함할 수 있고, 상기 복수의 제1 사전 계산된 키가 상기 저장부로부터 획득 가능하도록 상기 복수의 제1 서브 키 중 각각의 제1 서브 키는 상기 복수의 후보 심볼 중 각자의 후보 심볼에 대응할 수 잇고, 상기 적어도 하나의 제2 사전 계산된 키가 상기 저장부로부터 획득 가능하도록 상기 복수의 제2 서브 키 중 각각의 제2 서브 키는 상기 복수의 후보 순열 중 각자의 후보 순열에 대응할 수 있다.
상기 복수의 후보 순열 각각은 미리 설정된 제2 개수의 심볼 인덱스의 적어도 일부의 순열일 수 있고, 상기 키 생성 방법은 상기 적어도 하나의 순열로서 상기 미리 설정된 제2 개수의 심볼 인덱스 중 복수의 심볼 인덱스의 순열을 도출하기 위해 상기 복수의 심볼을 상기 복수의 심볼 인덱스와 각각 연관시키는 단계를 더 포함할 수 있다.
상기 미리 설정된 제1 개수는 1일 수 있다.
상기 복수의 후보 순열 각각은 미리 설정된 제2 개수의 심볼 인덱스 중 적어도 일부의 순열일 수 있고, 상기 키 생성 방법은 상기 복수의 심볼을 복수의 심볼 그룹으로 파티셔닝하는 단계를 더 포함할 수 있으며, 상기 적어도 하나의 순열은 상기 복수의 심볼 그룹에 각각 대응하는 복수의 순열을 포함할 수 있고, 상기 복수의 심볼 그룹 중 각각의 심볼 그룹은 상기 복수의 심볼 중 적어도 하나의 심볼을 포함할 수 있으며, 상기 키 생성 방법은 상기 각각의 심볼 그룹에 대하여 상기 복수의 순열 중 대응하는 순열로서 상기 미리 설정된 제2 개수의 심볼 인덱스 중 적어도 하나의 심볼 인덱스의 순열을 도출하기 위해 상기 적어도 하나의 심볼을 상기 적어도 하나의 심볼 인덱스와 각각 연관시키는 단계를 더 포함할 수 있다.
상기 미리 설정된 제1 개수는 2 이상일 수 있고, 상기 키 생성 방법은 상기 각각의 심볼 그룹에 대하여 상기 복수의 서브 키 그룹 중 대응하는 서브 키 그룹을 검색하여 상기 복수의 제1 사전 계산된 키 중 적어도 하나의 제1 사전 계산된 키 및 상기 적어도 하나의 제2 사전 계산된 키 중 하나의 제2 사전 계산된 키를 상기 저장부로부터 획득하기 위해 상기 대응하는 서브 키 그룹을 식별하는 단계를 더 포함할 수 있으며, 상기 적어도 하나의 제1 사전 계산된 키는 상기 적어도 하나의 심볼에 각각 대응할 수 있고, 상기 하나의 제2 사전 계산된 키는 상기 적어도 하나의 심볼 인덱스의 상기 순열에 대응할 수 있다.
상기 키 생성 방법은, 상기 식별하는 단계 전에 상기 복수의 서브 키를 상기 저장부에 저장하기 위해 상기 복수의 서브 키를 계산하는 단계를 더 포함할 수 있다.
상기 각각의 제1 서브 키는 이산로그 순환군 내 제1 원소의 제1 이산로그 값을 나타낼 수 있고, 상기 각각의 제2 서브 키는 상기 이산로그 순환군 내 제2 원소의 제2 이산로그 값을 나타낼 수 있으며, 상기 키 생성 방법은 상기 제1 이산로그 값을 계산하기 위해 상기 각자의 후보 심볼로부터 상기 제1 원소를 생성하는 단계; 및 상기 제2 이산로그 값을 계산하기 위해 상기 각자의 후보 순열로부터 상기 제2 원소를 생성하는 단계를 더 포함할 수 있다.
상기 키 생성 방법은 상기 제1 원소를 생성하기 위해 상기 각자의 후보 심볼에 해쉬 함수를 적용하는 단계; 및 상기 제2 원소를 생성하기 위해 상기 각자의 후보 순열에 상기 해쉬 함수를 적용하는 단계를 더 포함할 수 있다.
다른 예시적인 실시예에 따르면, 하드웨어와 결합되어, 사용자 아이디 정보로부터 복수의 심볼을 식별하는 단계; 상기 복수의 심볼로부터 적어도 하나의 순열을 도출하는 단계; 상기 복수의 심볼에 각각 대응하는 복수의 제1 사전 계산된 키 및 상기 적어도 하나의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키를 포함하는 복수의 사전 계산된 키를 획득하는 단계; 및 상기 복수의 사전 계산된 키로부터 상기 사용자 아이디 정보에 대응하는 암호 키를 생성하는 단계를 실행시키기 위하여 매체에 저장된 컴퓨터 프로그램이 제공된다.
소정의 실시예들에 따르면, 사용자 아이디를 기반으로 개인 키와 같은 암호 키를 생성하는 데 요구되는 시간이 현격히 줄어들 수 있고, 그러한 키가 실시간으로 발급될 수 있다.
소정의 실시예들에 따르면, 기존의 TDL-IBC에서 요구되는 상당한 양의 사전 계산이 감소될 수 있다.
소정의 실시예들에 따르면, 저 비용으로 효율적인 키 발급 서버를 구축할 수 있다.
도 1은 예시적인 실시예에 따른 키 생성 시스템을 도시한 도면,
도 2는 예시적인 실시예에 따라 사용자 아이디 정보 내 심볼들로부터 순열을 도출하는 것을 설명하기 위한 도면,
도 3은 예시적인 실시예에 따라 사용자 아이디 정보 내 심볼들을 심볼 그룹들로 파티셔닝하고 각 심볼 그룹에 대하여 순열을 도출하는 것을 설명하기 위한 도면,
도 4는 예시적인 실시예에 따라 사용자 아이디 정보에 대응하는 개인 키를 생성하기 위한 과정을 도시한 도면.
이하, 도면을 참조하여 본 발명의 구체적인 실시형태를 설명하기로 한다. 이하의 상세한 설명은 본 명세서에서 기술된 방법, 장치 및/또는 시스템에 대한 포괄적인 이해를 돕기 위해 제공된다. 그러나 이는 예시에 불과하며 본 발명은 이에 제한되지 않는다.
본 발명의 실시예들을 설명함에 있어서, 본 발명과 관련된 공지기술에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략하기로 한다. 그리고, 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다. 상세한 설명에서 사용되는 용어는 단지 본 발명의 실시예들을 기술하기 위한 것이며, 결코 제한적이어서는 안 된다. 명확하게 달리 사용되지 않는 한, 단수 형태의 표현은 복수 형태의 의미를 포함한다. 본 설명에서, "포함" 또는 "구비"와 같은 표현은 어떤 특성들, 숫자들, 단계들, 동작들, 요소들, 이들의 일부 또는 조합을 가리키기 위한 것이며, 기술된 것 이외에 하나 또는 그 이상의 다른 특성, 숫자, 단계, 동작, 요소, 이들의 일부 또는 조합의 존재 또는 가능성을 배제하도록 해석되어서는 안 된다.
도 1은 예시적인 실시예에 따른 키 생성 시스템을 도시한다.
예시적인 키 생성 시스템(100)은 사용자 아이디 정보(102)로부터 암호 키(104)를 생성하도록 구성된다. 이러한 키 생성 시스템(100)은 아이디 기반 암호 기법(예컨대, TDL-IBC 기법)을 적용하여 사용자에게 개인 키를 발급하는 데 사용될 수 있다.
키 생성 시스템(100)에 제공되는 사용자 아이디 정보(102)는 사용자 아이디를 구성하는 복수의 심볼을 포함할 수 있다. 사용자 아이디에 이용 가능한 심볼의 전형적인 예는 알파벳(대문자 및/또는 소문자), 숫자, 마침표(".")와 같은 특수 문자 또는 다른 다중 비트 문자와 같은 문자(character)이다. 그러한 심볼의 다른 예는 소정의 개수의 비트의 스트링(string)이다.
사용자 아이디 정보(102)는 추가적인 심볼을 더 포함할 수 있다. 몇몇 실시예들에서, 사용자 아이디 정보(102)는 사용자 아이디를 나타내는 심볼들 및 이에 연접된 패딩(padding)의 형태를 가질 수 있다. 예컨대, 패딩은 날짜를 나타내는 심볼(가령, 연(year), 월, 일 및/또는 분기를 나타내는 적어도 하나의 문자의 집합) 및/또는 버전(version)을 나타내는 심볼을 포함할 수 있다.
키 생성 시스템(100)은 다음과 같이 사용자의 아이디를 기반으로 사용자의 개인 키를 생성할 수 있다. 이산로그 순환군(예컨대, TDL 군) 내의 특정 원소 H = gx mod q(g는 생성자, q는 소수)가 사용자 아이디에 대응하는 일종의 공개 키인 경우, 원소 H의 이산로그 값 x를 나타내도록 생성된 키는 암호학적으로 충분히 안전하다. 따라서, 이 키는 사용자에게 개인 키로서 발급될 수 있다. 키 생성 시스템(100)에서는 사용자 아이디 정보(102)를 나타내는 데에 이용 가능한 모든 심볼들(각각은 이하에서 "후보 심볼"이라고도 지칭될 수 있음)에 각각 대응하는 이산로그 값들이 미리 계산되어 있다. 사용자 아이디 정보(102)가 주어지면, 키 생성 시스템(100)은 미리 계산된 몇몇 이산로그 값들을 이용하여 원소 H의 이산로그 값 x를 사용자 아이디 정보(102)에 대응하는 개인 키로서 생성할 수 있다. 이에 따라, 키 생성 시스템(100)은 매우 짧은 시간 내에(예컨대, 실시간으로) 사용자 아이디 정보(102)에 대응하는 개인 키를 생성하여 이를 사용자에게 발급할 수 있다. 또한, 후보 심볼들에 각각 대응하는 이산로그 값들을 적은 양의 사전 계산으로도 마련될 수 있다. 나아가, 사용자 아이디 정보(102)에 이용 가능한 후보 심볼들의 총 개수가 매우 크지 않은 경우에도 암호학적으로 충분한 안전성이 확보될 수 있도록, 키 생성 시스템(100)은 사용자 아이디 정보(102) 내 심볼들에 대한 순열(permutation)을 활용하거나, 사용자 아이디 정보(102) 내 심볼들의 파티셔닝(partitioning) 및 각 파티션 내 심볼들에 대한 순열을 활용할 수 있다.
더욱 구체적으로, 도 1에 도시된 바와 같이, 예시적인 키 생성 시스템(100)은 입력 분석기(120), 키 생성기(140), 사전 계산기(160) 및 저장부(180)를 포함할 수 있다. 키 생성 시스템(100)의 각 컴포넌트는 하드웨어(예컨대, 프로세서, 메모리, 입출력 인터페이스 등)에 의해 구현될 수 있다.
입력 분석부(120)는 심볼들을 포함하는 사용자 아이디 정보(102)를 수신할 수 있다. 설명의 편의상, 이하에서 하나의 심볼은 "a"부터 "z"까지의 영문자 소문자, "A"부터 "Z"까지의 영문자 대문자, "0"부터 "9"까지의 한 자리 숫자 및 마침표 "."로 구성된 총 63개의 문자 중 하나라고 가정한다. 다시 말해, 아래의 설명에서 위 63개의 문자 각각은 후보 심볼이고, 사용자 아이디 정보(102)에 포함되는 복수의 심볼 각각은 63개의 후보 심볼 중 하나이다. 다만, 이하의 설명은 어디까지나 예시적이고, 다른 개수 및/또는 형태의 후보 심볼들(가령, 26개의 영문자 소문자와 10개의 한 자리 숫자로 구성된 총 36개의 후보 심볼들이 주어진 경우나 둘 이상의 문자가 하나의 후보 심볼을 구성하는 경우)을 이용하는 것을 배제하지 않는다.
몇몇 실시예들에서, 사용자 아이디 정보(102) 내 심볼들의 총 개수는 제한될 수 있다. 추가적으로, 그 총 개수는 보안 누수를 방지하기 위해 하한을 가질 수 있다. 예컨대, 사용자 아이디 정보(102)는 8개 이상 20개 이하의 심볼을 포함할 것이 요구될 수 있다.
입력 분석부(120)는 수신된 사용자 아이디 정보(102)로부터 심볼들을 식별하고, 식별된 심볼들로부터 적어도 하나의 순열을 도출할 수 있다. 식별된 심볼들 각각이 후보 심볼들 중 하나이므로, 도출된 적어도 하나의 순열 각각은 후보 심볼들의 적어도 일부로부터 도출 가능한 순열들(각각은 이하에서 "후보 순열"이라고도 지칭될 수 있음) 중 하나일 수 있다.
키 생성기(140)는 사전 계산된 키들을 획득하고, 획득된 사전 계산된 키들로부터 사용자 아이디 정보(102)에 대응하는 암호 키(104)를 생성할 수 있다. 각각의 사전 계산된 키는 이산로그 순환군 내 원소의 이산로그 값을 나타낼 수 있다. 사전 계산된 키들은 식별된 심볼들에 각각 대응하는 제1 사전 계산된 키들을 포함할 수 있다. 또한, 사전 계산된 키들은 도출된 적어도 하나의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키를 포함할 수 있다.
입력 분석기(120)가 사용자 아이디 정보(102) 내 심볼들을 식별하기 전에, 사전 계산기(160)는 암호 키(104)를 생성하는 데 이용 가능한 사전 계산된 키들(각각은 이하에서 "서브 키"라고도 지칭될 수 있음)을 미리 계산하여 저장부(180)에 저장할 수 있다. 각 후보 심볼은 이 서브 키들 중 적어도 하나에 대응할 수 있고 각 후보 순열은 이 서브 키들 중 적어도 하나에 대응할 수 있는바, 키 생성기(140)는 암호 키(104)를 생성하는 데 필요한 사전 계산된 키들을 저장부(180)로부터 획득할 수 있다.
저장부(180)에 저장된 서브 키들은 하나 이상의 서브 키 그룹으로 배열될 수 있다. 서브 키 그룹의 총 개수는 소정의 정책(예컨대, 사용자 아이디 정보(102)에 파티셔닝을 적용할 것인지 여부, 그러한 파티셔닝이 적용된다면 각 파티션 내 심볼들의 최대 개수는 무엇인지, 또한 사용자 아이디 정보(102) 내 심볼들의 총 개수의 상한이 무엇인지 등)에 따라 미리 설정될 수 있다. 각 서브 키 그룹은 후보 심볼들에 일대일로 대응하는 제1 서브 키들을 포함할 수 있고, 이에 따라 암호 키(104)를 생성하는 데 필요한 제1 사전 계산된 키들이 저장부(180)로부터 획득 가능할 수 있다. 또한, 각 서브 키 그룹은 후보 순열들에 일대일로 대응하는 제2 서브 키들을 포함할 수 있고, 이에 따라 암호 키(104)를 생성하는 데 필요한 적어도 하나의 제2 사전 계산된 키가 저장부(180)로부터 획득 가능할 수 있다.
이하에서 키 생성 시스템(100)의 예시적인 구현들에 관해 더욱 상세히 기술된다.
순열을 이용하여 키를 생성하는 예시적인 접근법
설명을 위한 예로서, 입력 분석기(120)는 도 2의 사용자 아이디 정보(201)(즉, 11개의 심볼을 포함하는 "hj1230.yoon")를 수신할 수 있고, 수신된 사용자 아이디 정보(201)로부터 그 심볼들을 식별할 수 있다. 도 2에 도시된 바와 같이, 사용자 아이디 정보(201)는 동일한 심볼들(2개의 "o")이 나타날 수 있는 심볼 시퀀스로 표현될 수도 있다.
입력 분석기(120)는 식별된 심볼들을 동일한 개수의 심볼 인덱스와 각각 연관시킬 수 있다. 이와 같이 사용자 아이디 정보(201) 내 심볼들과 일대일로 대응하는 심볼 인덱스들은 미리 설정된 개수의 심볼 인덱스들 중 적어도 일부일 수 있다. 예를 들어, 입력 분석기(120)에 입력되는 어떠한 사용자 아이디 정보라도 최대 20개, 최소 8개의 심볼들을 포함할 것이 요구되는 경우, 입력 분석기(120)는 "1"부터 "20"까지의 20개의 심볼 인덱스 중에서 심볼 인덱스 "1"부터 그 사용자 아이디 정보 내 심볼들의 총 개수를 나타내는 심볼 인덱스까지의 심볼 인덱스들을 선택할 수 있고, 선택된 심볼 인덱스들과 그 심볼들을 각각 연관시켜 인덱싱(indexing)할 수 있다. 이에 따라, 도 2에 도시된 바와 같이, 사용자 아이디 정보(201)는 자신의 심볼 인덱스 세트(231)를 가질 수 있다. 도 2를 참조하면, 사용자 아이디 정보(201) 내 11개의 심볼들("h", "j", "1", "2", "3", "0", ".", "y", "o", "o" 및 "n")은 심볼 인덱스 세트(231) 내 11개의 심볼 인덱스들("1", "2", "3", "4", "5", "6", "7", "8", "9", "10" 및 "11")에 각각 대응한다는 것을 알 수 있다.
이어서, 입력 분석기(120)는 심볼 인덱스 세트(231) 내 11개의 심볼 인덱스들의 모든 가능한 순열들 중 하나를 도출할 수 있다. 몇몇 실시예들에서, 입력 분석기(120)는 사용자 아이디 정보(201) 내 11개의 심볼들을 특정한 순서에 따라 정렬할 수 있다. 가령, 숫자, 영문자 대문자, 영문자 소문자 및 마침표 순으로 우선순위가 높고 숫자와 영문자는 올림 차순으로 정렬되는 경우, 입력 분석기(120)는 도 2에 도시된 바와 같이 심볼 인덱스 세트(231) 내 11개의 심볼 인덱스들의 순열(251)(즉, {"6", "3", "4", "5", "1", "2", "11", "9", "10", "8", "7"})을 도출할 수 있다. 배열(241)은 순열(251)에 따라 사용자 아이디 정보(201) 내 심볼들의 위치 관계를 도식적으로 나타낸다.
앞서 언급된 바와 같이, 키 생성기(140)는 사용자 아이디 정보(102)에 대응하는 암호 키(104)를 사전 계산된 키들로부터 생성할 수 있다. 예시적인 설명을 위해, 암호 키(104)는 다음의 수학식에 따라 주어지는 해쉬 값 H(ID)의 이산로그 값 x로 정의된다고 가정한다.
Figure 112014069384795-pat00001
여기서, ID는 사용자 아이디 정보(102), n은 사용자 아이디 정보(102)에 포함된 심볼들의 총 개수, si(단, 1≤i≤n)는 사용자 아이디 정보(102)에 포함된 심볼들, π는 사용자 아이디 정보(102)에 포함된 심볼들로부터 도출된 순열, 그리고 hi(단, 1≤i≤n) 및 h'는 이산로그 순환군에서 정의된 해쉬 함수들(예컨대, 암호학적으로 안전한 SHA1, SHA-256, SHA-512 등)일 수 있다.
몇몇 실시예들에서, 각각의 hi 및 각각의 h'는 동일한 해쉬 함수 h이고 f는 각 인자의 곱셈으로 정의될 수 있다. 그러한 경우, H(ID)는 다음의 수학식과 같이 주어질 것이다.
Figure 112014069384795-pat00002
이제, 이산로그 순환군 내 원소인 해쉬 함수 값 h(z)의 이산로그 값을 x(z)라고 할 때, 사용자 아이디 정보(102)에 대응하는 암호 키(104)는 다음의 수학식과 같이 주어질 것이다.
Figure 112014069384795-pat00003
위 수학식에서 알 수 있듯이, x는 이산로그 값들(x(s1), ... , x(sn), x(π))로부터 산출될 수 있는데, 이 이산로그 값들 각각은 사용자 아이디 정보(102)에 포함된 심볼들 중 하나 또는 사용자 아이디 정보(102) 내 심볼들로부터 도출된 순열에 대응하는 키라고 볼 수 있다. 이러한 이산로그 값들은 사용자 아이디 정보(102)가 입력 분석기(120)에 입력되기 전에 사전 계산기(160)에 의해 계산될 수 있고, 저장부(180)에 미리 저장될 수 있다. 키 생성기(140)는 저장부(180)를 액세스하여 필요한 이산로그 값들을 획득할 수 있고, 획득된 이산로그 값들을 이용하여 암호 키(104)를 생성할 수 있다.
이러한 경우, 도 2의 사용자 아이디 정보(201)에 대응하는 H(ID)는 다음 수학식으로 나타낼 수 있다.
Figure 112014069384795-pat00004
그러면, 도 2의 사용자 아이디 정보(201)에 대응하는 개인 키 x는 다음 수학식에 따라 도출될 수 있다.
Figure 112014069384795-pat00005
여기서, x(z)는 해쉬 값 h(z)의 이산로그 값이다(단, z는 심볼 또는 순열). 이를 위해, 키 생성기(140)는 저장부(180)로부터 이산로그 값 x(z)을 획득할 수 있고, 획득된 이산로그 값들을 합산하여 x를 산출할 수 있다. 산출된 x는 암호 키(104)로서 발급될 수 있다.
이를 위하여, 몇몇 실시예들에서, 사전 계산기(160)는 다음과 같은 동작들을 수행할 수 있다.
사전 계산기(160)는 63개의 후보 심볼들에 각각 대응하는 제1 서브 키들을 계산할 수 있다. 예를 들어, 사전 계산기(160)는 (가령 심볼 "A"에 해쉬 함수를 적용하여) 그 심볼로부터 이산로그 순환군 내 특정 원소를 생성할 수 있다. 이어서, 사전 계산기(160)는 그 원소의 이산로그 값을 계산할 수 있다. 사전 계산기(160)는 계산된 이산로그 값을 심볼 "A"에 대응하는 제1 서브 키로서 저장부(180)에 저장할 수 있다.
또한, 사전 계산기(160)는 후보 순열들에 각각 대응하는 제2 서브 키들을 계산할 수 있다. 예를 들어, 사전 계산기(160)는 (가령 순열 {"2", "1", "3", "4", "5", "6", "7", "8"}에 해쉬 함수를 적용하여) 그 순열로부터 이산로그 순환군 내 특정 원소를 생성할 수 있다. 이어서, 사전 계산기(160)는 그 원소의 이산로그 값을 계산할 수 있다. 사전 계산기(160)는 계산된 이산로그 값을 심볼 {"2", "1", "3", "4", "5", "6", "7", "8"}에 대응하는 제2 서브 키로서 저장부(180)에 저장할 수 있다.
앞서 언급된 바와 같이, 사용자 아이디 정보(102) 내 심볼들은 "1"부터 "20"까지의 20개의 심볼 인덱스 중 적어도 일부에 각각 대응할 수 있다. 예를 들어, 심볼들에 일대일로 대응하는 심볼 인덱스들은 "1"부터 심볼들의 총 개수 N(단, 8≤N≤20)를 나타내는 심볼 인덱스까지의 N개의 순차적인 심볼 인덱스들일 수 있다. 이에 따라, 후보 순열들은 20개의 심볼 인덱스들("1" 내지 "20")의 20!개의 순열들 외에도, 8개의 심볼 인덱스들("1" 내지 "8")의 순열들부터 19개까지의 심볼 인덱스들("1" 내지 "19")의 순열들을 포함할 수 있다. 따라서, 후보 순열들이 위와 같이 설정되었다면, "bacdefghi"이라는 사용자 아이디 정보에 대한 순열 {"2", "1", "3", "4", "5", "6", "7", "8", "9"})과 "bacdefgh"라는 다른 사용자 아이디 정보에 대한 순열 {"2", "1", "3", "4", "5", "6", "7", "8"}은 각각 상이한 해쉬 값에 대응할 것이고, 그 해쉬 값들로부터 도출되는 이산로그 값들도 서로 상이할 것이다.
사전 계산기(160)에 의해 미리 계산되어 저장부(180)에 저장된 서브 키들은 미리 설정된 개수의 서브 키 그룹으로 배열될 수 있다. 예를 들어, 앞서 언급된 제1 서브 키들 및 제2 서브 키들은 하나의 서브 키 그룹에 포함될 수 있다. 이에 따라, 키 생성기(140)는 암호 키(104)를 생성하는 데 필요한 사전 계산된 키를 저장부(180)로부터 획득하기 위해 그 서브 키 그룹을 검색할 수 있다.
순열 및 파티셔닝을 이용하여 키를 생성하는 예시적인 접근법
도 3에 도시된 바와 같이, 입력 분석기(120)는 도 2와 마찬가지로 사용자 아이디 정보(201)(즉, 11개의 심볼을 포함하는 "hj1230.yoon")를 수신할 수 있고, 수신된 사용자 아이디 정보(201)로부터 그 심볼들을 식별할 수 있다. 또한, 입력 분석기(120)는 식별된 심볼들을 복수의 심볼 그룹으로 파티셔닝할 수 있다. 각 심볼 그룹은 사용자 아이디 정보(102)에 포함된 심볼들 중 적어도 하나를 포함할 수 있다. 각 심볼 그룹 내 심볼의 최대 가능 개수는 미리 설정될 수 있다. 만일 각 심볼 그룹 내 심볼의 최대 가능 개수가 4개라고 미리 설정된 경우, 입력 분석기(120)는 도 3에 도시된 바와 같이 사용자 아이디 정보(201)를 3개의 심볼 그룹(321, 322, 323)으로 파티셔닝할 수 있다. 이와 같이, 어떤 심볼 그룹(예컨대, 심볼 그룹(323))에 포함되는 심볼의 개수는 위 최대 가능 개수보다 작을 수 있다.
입력 분석기(120)는 각 심볼 그룹 내 적어도 하나의 심볼을 동일한 개수의 심볼 인덱스와 각각 연관시킬 수 있다. 이와 같이 각 심볼 그룹 내 적어도 하나의 심볼에 일대일로 대응하는 적어도 하나의 심볼 인덱스는 미리 설정된 개수의 심볼 인덱스들 중 적어도 일부일 수 있다. 예를 들어, 어떠한 심볼 그룹이라도 최대 4개의 심볼을 포함할 것이 요구되는 경우, 입력 분석기(120)는 "1"부터 "4"까지의 4개의 심볼 인덱스 중에서 심볼 인덱스 "1"부터 그 심볼 그룹 내 심볼의 총 개수를 나타내는 심볼 인덱스까지의 적어도 하나의 심볼 인덱스를 선택할 수 있고, 선택된 적어도 하나의 심볼 인덱스와 그 심볼 그룹 내 적어도 하나의 심볼을 각각 연관시켜 인덱싱할 수 있다. 이에 따라, 도 3에 도시된 바와 같이, 심볼 그룹들(321, 322, 323) 각각은 자신의 심볼 인덱스 세트(331, 332, 333)를 가질 수 있다. 도 3을 참조하면, (i) 심볼 그룹(321) 내 심볼들("h", "j", "1" 및 "2")은 심볼 인덱스 세트(331) 내 심볼 인덱스들("1", "2", "3" 및 "4")에 일대일로 대응하고, (ii) 심볼 그룹(322) 내 심볼들("3", "0", "." 및 "y")은 심볼 인덱스 세트(332) 내 심볼 인덱스들("1", "2", "3" 및 "4")에 일대일로 대응하며, (iii) 심볼 그룹(323) 내 심볼들("o", "o" 및 "n")은 심볼 인덱스 세트(333) 내 심볼 인덱스들("1", "2" 및 "3")에 일대일로 대응한다는 것을 알 수 있다.
이어서, 입력 분석기(120)는 심볼 그룹들(321, 322, 323) 각각에 대하여 각자의 심볼 인덱스 세트(331, 332, 333) 내 심볼 인덱스들의 모든 가능한 순열들 중 하나를 도출할 수 있다. 이와 같이, 도출된 순열들은 심볼 그룹들(321, 322, 323)에 각각 대응할 수 있다. 예를 들어, 입력 분석기(120)는 심볼 그룹(321) 내 4개의 심볼들을 특정한 순서에 따라 정렬할 수 있다. 가령, 숫자, 영문자 대문자, 영문자 소문자 및 마침표 순으로 우선 순위가 높고 숫자와 영문자는 올림 차순으로 정렬되는 경우, 입력 분석기(120)는 도 3에 도시된 바와 같이 심볼 인덱스 세트(331) 내 심볼 인덱스들의 순열(351)(즉, {"3", "4", "1", "2"})을 도출할 수 있다. 배열(341)은 순열(351)에 따라 심볼 그룹(321) 내 심볼들의 위치 관계를 도식적으로 나타낸다. 마찬가지로, 배열(342) 및 배열(343)에서 알 수 있듯이, 심볼 그룹(322)의 심볼 인덱스 세트(332) 내 심볼 인덱스들의 순열(352) 및 심볼 그룹(323)의 심볼 인덱스 세트(333) 내 심볼 인덱스들의 순열(353)이 도출될 수 있다.
앞서 언급된 바와 같이, 키 생성기(140)는 사용자 아이디 정보(102)에 대응하는 암호 키(104)를 사전 계산된 키들로부터 생성할 수 있다. 예시적인 설명을 위해, 암호 키(104)는 다음의 수학식에 따라 주어지는 해쉬 값 H(ID)의 이산로그 값 x로 정의된다고 가정한다.
Figure 112014069384795-pat00006
여기서, ID는 사용자 아이디 정보(102), n은 사용자 아이디 정보(102)에 포함된 심볼들의 총 개수, p는 사용자 아이디 정보(102)가 파티셔닝된 심볼 그룹들의 총 개수, si(단, 1≤i≤n)는 사용자 아이디 정보(102)에 포함된 심볼들, πj(단, 1 ≤j≤p)는 심볼 그룹들에 각각 대응하는 순열들, 그리고 hi(단, 1≤i≤n) 및 h'j(단, 1 ≤j≤p)는 이산로그 순환군에서 정의된 해쉬 함수들(예컨대, 암호학적으로 안전한 SHA1, SHA-256, SHA-512 등)일 수 있다.
몇몇 실시예들에서, 각각의 hi 및 각각의 h'j는 동일한 해쉬 함수 h이고 f는 각 인자의 곱셈으로 정의될 수 있다. 그러한 경우, H(ID)는 다음의 수학식과 같이 주어질 것이다.
Figure 112014069384795-pat00007
이제, 이산로그 순환군 내 원소인 해쉬 함수 값 h(z)의 이산로그 값을 x(z)라고 할 때, 사용자 아이디 정보(102)에 대응하는 암호 키(104)는 다음의 수학식과 같이 주어질 것이다.
Figure 112014069384795-pat00008
위 수학식에서 알 수 있듯이, x는 이산로그 값들(x(s1), ... , x(sn), x(π1), ... ,x(πp))로부터 산출될 수 있는데, 이 이산로그 값들 각각은 사용자 아이디 정보(102)에 포함된 심볼들 중 하나 또는 사용자 아이디 정보(102) 내 심볼들로부터 도출되어 심볼 그룹들에 각각 적용된 순열들 중 하나에 대응하는 키라고 볼 수 있다. 이러한 이산로그 값들은 사용자 아이디 정보(102)가 입력 분석기(120)에 입력되기 전에 사전 계산기(160)에 의해 계산될 수 있고, 저장부(180)에 미리 저장될 수 있다. 키 생성기(140)는 저장부(180)를 액세스하여 필요한 이산로그 값들을 획득할 수 있고, 획득된 이산로그 값들을 이용하여 암호 키(104)를 생성할 수 있다.
몇몇 실시예들에 따르면, 해쉬 값 h(z)는 심볼 z가 어느 심볼 그룹에 포함되는지 또는 순열 z가 어느 심볼 그룹에 대응하는지에 의존적일 수 있다. 다시 말해, 해쉬 값은 h(z)= h(j, z)로 주어질 수 있다(1≤j≤p). 이를 위해, 키 생성기(140)는 각 심볼 그룹에 대하여 그 심볼 그룹에 포함된 심볼 및 그 심볼 그룹에 대응하는 순열 각각을 그 심볼 그룹에 대응하는 그룹 인덱스와 연관시켜 인덱싱(indexing)할 수 있다. 이와 같이 심볼 그룹들(321, 322, 323)과 일대일로 대응하는 그룹 인덱스들(361, 362, 363)은 미리 설정된 개수의 그룹 인덱스들 중 적어도 일부일 수 있다. 예를 들어, 입력 분석기(120)에 입력되는 어떠한 사용자 아이디 정보라도 최대 20개의 심볼을 포함하고 어떠한 심볼 그룹이라도 최대 4개의 심볼을 포함할 것이 요구되는 경우, 입력 분석기(120)는 가능한 한 많은 심볼 그룹들이 4개의 심볼들을 가지도록 그 사용자 아이디 정보를 파티셔닝하는 정책을 취할 수 있다. 이러한 파티셔닝 정책에 따르면, 그 사용자 아이디 정보 내의 심볼들은 최대 5개의 심볼 그룹으로 파티셔닝될 수 있다. 따라서, 키 생성기(140)는 "1"부터 "5"까지의 5개의 그룹 인덱스 중에서 그룹 인덱스 "1"부터 그 사용자 아이디 정보 내 심볼들이 파티셔닝된 심볼 그룹들의 총 개수를 나타내는 그룹 인덱스까지의 그룹 인덱스들을 선택할 수 있고, 선택된 그룹 인덱스들과 그 심볼 그룹들을 각각 연관시켜 인덱싱할 수 있다.
구체적인 예로서, 키 생성기(140)는 도 3의 심볼 그룹(321)에 대하여 심볼 그룹(321) 내 심볼들("h", "j", "1" 및 "2") 및 심볼 그룹(321)에 대응하는 순열({"3","4","1","2"}) 각각을 "1"이라는 그룹 인덱스(361)와 연관시켜 인덱싱할 수 있다. 마찬가지로, 키 생성기(140)는 심볼 그룹(322) 및 심볼 그룹(323)에 대하여 각각 "2"라는 그룹 인덱스(362) 및 "3"이라는 그룹 인덱스(363)를 이용한 인덱싱 동작을 수행할 수 있다.
이러한 경우, 도 3의 사용자 아이디 정보(201)에 대응하는 H(ID)는 다음 수학식으로 나타낼 수 있다.
Figure 112014069384795-pat00009
그러면, 도 3의 사용자 아이디 정보(201)에 대응하는 개인 키 x는 다음 수학식에 따라 도출될 수 있다.
Figure 112014069384795-pat00010
여기서, x(j, z)는 해쉬 값 h(j, z)의 이산로그 값이다(1≤j≤p). 이를 위해, 키 생성기(140)는 저장부(180)로부터 이산로그 값 x(j, z)을 획득할 수 있고, 획득된 이산로그 값들을 합산하여 x를 산출할 수 있다. 산출된 x는 암호 키(104)로서 발급될 수 있다.
이를 위하여 몇몇 실시예들에 따라 사전 계산기(160)가 수행하는 동작들을 이하에서 더욱 구체적으로 설명한다. 특히, 사전 계산기(160)는 키 생성기(140)가 암호 키(104)를 생성하는 데 필요로 할 수 있는 키들을 미리 계산하기 위하여 사용자 아이디 정보(102) 내 심볼들이 미리 설정된 개수 이하의 심볼 그룹들 중 어느 심볼 그룹에 포함되는지, 또한 도출된 순열들이 그 심볼 그룹들 중 어느 심볼 그룹에 대응하는지를 고려할 수 있다. 예를 들어, 사용자 아이디 정보(102) 내 심볼들은 최대 5개의 심볼 그룹들로 파티셔닝될 수 있고, 그러한 심볼 그룹들은 "1"부터 "5"까지의 5개의 그룹 인덱스 중 적어도 일부에 각각 대응할 수 있다.
사전 계산기(160)는 63개의 후보 심보들 각각을 그룹 인덱스들 각각과 연관시켜 인덱싱할 수 있다. 또한, 사전 계산기(160)는 인덱싱된 후보 심볼들에 각각 대응하는 제1 서브 키들을 계산할 수 있다. 앞서 언급된 바와 마찬가지 방식으로, 사전 계산기(160)는 제1 서브 키를 계산하기 위해 이산로그 순환군 내 특정 원소를 생성하고 그 원소에 대응하는 이산로그 값들을 계산할 수 있다. 그러한 원소의 생성을 위해 해쉬 함수가 적용될 수 있다. 다만, 동일한 심볼이라도 어느 그룹 인덱스로 인덱싱되었는지에 따라 (가령 상이한 해쉬 함수가 적용되어) 상이한 해쉬 값이 산출될 수 있음에 유의하여야 한다.
예컨대, 사전 계산기(160)는 심볼 "A"를 5개의 그룹 인덱스 "1", "2", "3" "4" 및 "5" 각각과 인덱싱하여 5개의 인덱싱된 심볼들을 생성할 수 있다. 이러한 방식으로 사전 계산기(160)는 총 63개의 심볼들 각각을 5개의 인덱스 각각과 연관시켜 인덱싱함으로써, 63*5=315개의 인덱싱된 심볼들을 생성할 수 있다. 이어서, 사전 계산기(160)는 315개의 인덱싱된 심볼들에 각각 대응하는 315개의 제1 서브 키들을 계산할 수 있다. 이와 같이, 심볼 "A"가 어느 심볼 그룹에 포함되는지(예컨대, "1"이라는 그룹 인덱스로 인덱싱되었는지 또는 "5"라는 그룹 인덱스로 인덱싱되었는지)에 따라 그 심볼에 대응하는 제1 서브 키는 달라질 수 있다.
나아가, 사전 계산기(160)는 후보 순열들 각각을 그룹 인덱스들 각각과 연관시켜 인덱싱할 수 있다. 또한, 사전 계산기(160)는 인덱싱된 후보 순열들에 각각 대응하는 제2 서브 키들을 계산할 수 있다. 앞서 언급된 바와 마찬가지 방식으로, 사전 계산기(160)는 제2 서브 키를 계산하기 위해 이산로그 순환군 내 특정 원소를 생성하고 그 원소에 대응하는 이산로그 값들을 계산할 수 있다. 그러한 원소의 생성을 위해 해쉬 함수가 적용될 수 있다. 다만, 동일한 순열이라도 어느 그룹 인덱스로 인덱싱되었는지에 따라 (가령 상이한 해쉬 함수가 적용되어) 상이한 해쉬 값이 산출될 수 있음에 유의하여야 한다.
몇몇 실시예들에 따르면, 후보 순열들은 다음과 같이 주어질 수 있다. 앞서 언급된 바와 같이, 각 심볼 그룹 내 심볼의 개수가 1 이상이고 4 이하인 경우, 각 심볼 그룹 내 적어도 하나의 심볼은 "1"부터 "4"까지의 4개의 심볼 인덱스 중 적어도 일부에 각각 대응할 수 있다. 예를 들어, 적어도 하나의 심볼에 일대일로 대응하는 적어도 하나의 심볼 인덱스는 "1"부터 그 심볼(들)의 총 개수 M(단, 1≤M≤4)를 나타내는 심볼 인덱스까지의 M개의 순차적인 심볼 인덱스들일 수 있다. 이에 따라, 후보 순열들은 (i) 4개의 심볼 인덱스들 "1", "2", "3" 및 "4"에서 도출 가능한 4!개의 순열들 외에도 (ii) 심볼 인덱스들 중 3개인 "1", "2" 및 "3"으로부터 도출 가능한 3!개의 순열들, (iii) 심볼 인덱스들 중 2개인 "1" 및 "2"으로부터 도출 가능한 2!개의 순열들 및 (iv) 심볼 인덱스들 중 1개의 인덱스 "1"로부터 도출 가능한 1개의 순열 {"1"}을 포함할 수 있다. 따라서, 후보 순열들이 위와 같이 설정되었다면, "oonx"이라는 심볼 그룹에 대한 순열 {"3", "1", "2", "4"})과 "oon"라는 다른 심볼 그룹에 대한 순열 {"3", "1", "2"}은 각각 상이한 해쉬 값에 대응할 것이고, 그 해쉬 값들로부터 도출되는 이산로그 값들도 서로 상이할 것이다.
예컨대, 사전 계산기(160)는 순열 {"3","1","2"}을 5개의 그룹 인덱스 "1", "2", "3" "4" 및 "5" 각각과 인덱싱하여 5개의 인덱싱된 순열들을 생성할 수 있다. 이러한 방식으로 사전 계산기(160)는 4!+3!+2!+1!(=33)개의 순열들 각각을 5개의 인덱스 각각과 연관시켜 인덱싱함으로써, 33*5=165개의 인덱싱된 순열들을 생성할 수 있다. 이어서, 사전 계산기(160)는 165개의 인덱싱된 순열들에 각각 대응하는 165개의 제1 서브 키들을 계산할 수 있다. 이와 같이, 순열 {"3","1","2"}가 어느 심볼 그룹에 대응하는지(예컨대, "1"이라는 그룹 인덱스로 인덱싱되었는지 또는 "5"라는 그룹 인덱스로 인덱싱되었는지)에 따라 그 순열에 대응하는 제2 서브 키는 달라질 수 있다.
사전 계산기(160)에 의해 미리 계산되어 저장부(180)에 저장된 서브 키들은 미리 설정된 개수의 서브 키 그룹으로 배열될 수 있다. 예를 들어, 사용자 아이디 정보(102) 내 심볼들은 최대 5개의 심볼 그룹들로 파티셔닝되는 경우, 앞서 언급된 제1 서브 키들 및 제2 서브 키들은 5개의 서브 키 그룹에 포함될 수 있다. 각각의 심볼 그룹에 대하여 5개의 서브 키 그룹 중 대응하는 서브 키 그룹은 그 심볼 그룹에 대응하는 그룹 인덱스로 인덱싱된 후보 심볼들에 각각 대응하는 제1 서브 키들 및 그 그룹 인덱스로 인덱싱된 후보 순열들에 각각 대응하는 제2 서브 키들을 포함할 수 있다. 이에 따라, 키 생성기(140)는 암호 키(104)를 생성하는 데 필요한 사전 계산된 키를 저장부(180)로부터 획득하기 위해 5개의 서브 키 그룹 중 복수의 서브 키 그룹(예컨대, 심볼 그룹들의 총 개수가 3개인 경우에는 그룹 인덱스 "1"부터 "3"에 각각 대응하는 3개의 서브 키 그룹)을 검색할 수 있다. 예를 들어, 도 3을 다시 참조하면, 키 생성기(140)는 "1"이라는 그룹 인덱스(361)로 인덱싱된 심볼 그룹(321)에 대응하는 서브 키 그룹을 검색하여 심볼 그룹(321) 내 심볼들("h", "j", "1" 및 "2")에 각각 대응하는 제1 사전 계산된 키들과 순열(351)({"3","4","1","2"})에 대응하는 제2 사전 계산된 키를 저장부(180)로부터 획득할 수 있다. 이는 심볼 그룹(322) 및 심볼 그룹(323)에 대하여도 동일하게 적용될 수 있다.
몇몇 실시예들에서, 키 생성 시스템(100)은 컴퓨팅 장치 내에 구현되거나 포함될 수 있다. 이러한 컴퓨팅 장치는 하나 이상의 프로세서 및 그 프로세서에 의해 액세스 가능한 컴퓨터 판독 가능 저장 매체를 포함할 수 있다. 컴퓨터 판독 가능 저장 매체는 프로세서의 내부 또는 외부에 배치될 수 있고, 잘 알려진 다양한 수단으로 프로세서와 연결될 수 있다. 컴퓨터 판독 가능 저장 매체에는 컴퓨터 실행 가능 명령어가 저장되어 있을 수 있다. 프로세서는 컴퓨터 판독 가능 저장 매체에 저장된 명령어를 실행할 수 있다. 그러한 명령어는 프로세서에 의해 실행되는 경우 컴퓨팅 장치로 하여금 예시적인 실시예에 따른 동작을 수행하게 할 수 있다. 몇몇 다른 실시예들에서, 입력 분석기(120)와 키 생성기(140)가 하나의 컴퓨팅 장치 상에서 그 컴퓨팅 장치의 하드웨어에 의해 구현되고, 사전 계산기(160) 및 저장부(180)는 다른 컴퓨팅 장치 상에서 그 컴퓨팅 장치의 하드웨어에 의해 구현될 수 있다.
도 4는 예시적인 실시예에 따라 사용자 아이디 정보에 대응하는 개인 키를 생성하기 위한 과정을 도시한다. 예를 들어, 예시적인 과정(400)에 포함된 동작들은 키 생성 시스템(100)에 의해 수행될 수 있다.
시작 동작 후, 과정(400)은 동작(S410)으로 진행된다. 동작(S410)에서, 복수의 서브 키들이 사전 계산된다. 예를 들어, 사전 계산기(160)는 사용자 아이디 정보에 이용 가능한 후보 심볼들 각각을 미리 설정된 제1 개수의 그룹 인덱스들 각각과 연관시켜 인덱싱할 수 있고, 인덱싱된 후보 심볼들과 각각 연관된 제1 서브 키들을 계산할 수 있다. 사용자 아이디 정보 내 심볼들이 심볼 그룹들로 파티셔닝되는 경우, 미리 설정된 제1 개수는 그 심볼 그룹들의 최대 가능 개수일 수 있다. 그러한 파티셔닝이 적용되지 않는 경우에는 미리 설정된 제1 개수는 1일 수 있다. 또한, 사전 계산기(160)는 미리 설정된 제2 개수의 심볼 인덱스들 중 적어도 일부로부터 도출 가능한 후보 순열들 각각을 상기 그룹 인덱스들 각각과 연관시켜 인덱싱할 수 있고, 인덱싱된 후보 순열들과 각각 연관된 제2 서브 키들을 계산할 수 있다. 미리 설정된 제2 개수는 각 심볼 그룹 내 심볼들의 최대 가능 개수일 수 있다.
이어서, 사전 계산된 복수의 서브 키들이 저장부에 저장된다(S420). 저장된 서브 키들은 하나 또는 복수의 서브 키 그룹으로 배열될 수 있다. 서브 키 그룹의 총 개수는 미리 설정된 제1 개수일 수 있다. 예를 들어, 사전 계산기(160)는 제1 서브 키들 및 제2 서브 키들을 저장부(180)에 저장할 수 있다. 키 생성기(140)는 사용자 아이디 정보에 대응하는 암호 키를 생성하기 위해 저장된 서브 키들을 이용할 수 있다.
동작(S430)에서, 사용자 아이디 정보로부터 복수의 심볼들이 식별되고 복수의 심볼들로부터 적어도 하나의 순열이 도출된다. 예를 들어, 입력 분석기(120)는 사용자 아이디 정보로부터 복수의 심볼들을 식별하고 그 심볼들을 복수의 심볼 그룹들로 파티셔닝할 수 있다. 이어서, 각 심볼 그룹에 대하여 그 심볼 그룹 내 적어도 하나의 심볼에 일대일로 대응하는 적어도 하나의 심볼 인덱스의 순열을 도출할 수 있다. 위와 같은 파티셔닝이 적용되지 않는 경우, 입력 분석기(120)는 사용자 아이디 정보로부터 복수의 심볼들을 식별하고 그 심볼들에 일대일로 대응하는 심볼 인덱스들의 순열을 도출할 수 있다.
동작(S440)에서, 식별된 복수의 심볼들에 각각 대응하는 복수의 제1 사전 계산된 키 및 도출된 적어도 하나의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키가 획득된다. 예컨대, 키 생성기(140)는 앞서 수학식 5와 관련하여 언급된 바와 같이 해쉬 값 h(z)의 이산로그 값 x(z)을 획득할 수 있다. 다른 예로서, 키 생성기(140)는 앞서 수학식 10과 관련하여 언급된 바와 같이 해쉬 값 h(j, z)의 이산로그 값 x(j, z)을 획득할 수 있다(1≤j≤p).
동작(S450)에서, 사전 계산된 키들로부터 사용자 아이디 정보에 대응하는 개인 키가 생성된다. 예를 들어, 키 생성기(140)는 앞서 수학식 5와 관련하여 언급된 바와 같이 이산로그 값 x(z)을 합산하여 개인 키를 생성할 수 있다. 다른 예로서, 키 생성기(140)는 앞서 수학식 10과 관련하여 언급된 바와 같이 이산로그 값 x(j, z)을 합산하여 개인 키 x를 생성할 수 있다.
한편, 소정의 실시예는 본 명세서에서 기술한 과정을 컴퓨터상에서 수행하기 위한 프로그램을 포함하는 컴퓨터 판독 가능 저장 매체를 포함할 수 있다. 이러한 컴퓨터 판독 가능 저장 매체는 프로그램 명령, 로컬 데이터 파일, 로컬 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 그 컴퓨터 판독 가능 저장 매체는 본 발명을 위하여 특별히 설계되고 구성된 것들일 수 있다. 컴퓨터 판독 가능 저장 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체, CD-ROM, DVD와 같은 광 기록 매체, 플롭티컬 디스크와 같은 자기-광 매체, 및 롬, 램, 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함할 수 있다. 다른 실시예에 따르면, 본 명세서에서 기술한 과정을 실행하기 위한 컴퓨터 프로그램이 제공될 수 있다. 그러한 프로그램은 하드웨어와 결합하여 위 과정을 실행하기 위하여 컴퓨터 판독 가능 저장 매체와 같은 매체에 저장될 수 있다.
이상에서 본 발명의 대표적인 실시예들을 상세하게 설명하였으나, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 상술한 실시예에 대하여 본 발명의 범주에서 벗어나지 않는 한도 내에서 다양한 변형이 가능함을 이해할 것이다. 그러므로 본 발명의 권리범위는 설명된 실시예에 국한되어 정해져서는 안 되며, 후술하는 특허청구범위뿐만 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.
100: 키 생성 시스템
120: 입력 분석기
140: 키 생성기
160: 사전 계산기
180: 저장부

Claims (25)

  1. 사용자 아이디 정보로부터 복수의 심볼을 식별하고, 상기 복수의 심볼과 동일한 개수의 심볼 인덱스를 상기 복수의 심볼과 연관시키며, 상기 복수의 심볼로부터 적어도 하나의 순열(permutation)을 도출함에 따라 생성되는 상기 심볼 인덱스들의 순열을 도출하도록 구성되는 입력 분석기; 및
    상기 복수의 심볼에 각각 대응하는 복수의 제1 사전 계산된 키 및 상기 심볼 인덱스들의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키를 포함하는 복수의 사전 계산된 키를 획득하고, 상기 복수의 사전 계산된 키로부터 상기 사용자 아이디 정보에 대응하는 암호 키를 생성하도록 구성되는 키 생성기를 포함하는
    키 생성 장치.
  2. 청구항 1에 있어서,
    상기 복수의 사전 계산된 키 각각은 이산로그 순환군 내 원소의 이산로그 값을 나타내는, 키 생성 장치.
  3. 청구항 2에 있어서,
    상기 키 생성기는 또한 상기 암호 키를 생성하기 위해 상기 복수의 사전 계산된 키를 합산하도록 구성되는, 키 생성 장치.
  4. 청구항 1에 있어서,
    상기 복수의 심볼 각각은 복수의 후보 심볼 중 하나이고, 상기 적어도 하나의 순열 각각은 복수의 후보 순열 중 하나이며, 상기 복수의 후보 순열 각각은 상기 복수의 후보 심볼의 적어도 일부로부터 도출 가능한, 키 생성 장치.
  5. 청구항 4에 있어서,
    복수의 서브 키가 저장되어 있는 저장부를 더 포함하되, 상기 복수의 서브 키는 미리 설정된 제1 개수의 서브 키 그룹으로 배열되고, 상기 키 생성기는 또한 상기 복수의 제1 사전 계산된 키 및 상기 적어도 하나의 제2 사전 계산된 키를 상기 저장부로부터 획득하기 위해 상기 미리 설정된 제1 개수의 서브 키 그룹 중 하나 또는 복수의 서브 키 그룹을 검색하도록 구성되며,
    상기 미리 설정된 제1 개수의 서브 키 그룹 각각은 복수의 제1 서브 키 및 복수의 제2 서브 키를 포함하되, 상기 복수의 제1 사전 계산된 키가 상기 저장부로부터 획득 가능하도록 상기 복수의 제1 서브 키 중 각각의 제1 서브 키는 상기 복수의 후보 심볼 중 각자의 후보 심볼에 대응하고, 상기 적어도 하나의 제2 사전 계산된 키가 상기 저장부로부터 획득 가능하도록 상기 복수의 제2 서브 키 중 각각의 제2 서브 키는 상기 복수의 후보 순열 중 각자의 후보 순열에 대응하는, 키 생성 장치.
  6. 청구항 5에 있어서,
    상기 복수의 후보 순열 각각은 미리 설정된 제2 개수의 심볼 인덱스의 적어도 일부의 순열인, 키 생성 장치.
  7. 청구항 6에 있어서,
    상기 미리 설정된 제1 개수는 1인, 키 생성 장치.
  8. 청구항 5에 있어서,
    상기 복수의 후보 순열 각각은 미리 설정된 제2 개수의 심볼 인덱스 중 적어도 일부의 순열이고,
    상기 입력 분석기는 또한 상기 복수의 심볼을 복수의 심볼 그룹으로 파티셔닝(partitioning)하도록 구성되며, 상기 적어도 하나의 순열은 상기 복수의 심볼 그룹에 각각 대응하는 복수의 순열을 포함하고, 상기 복수의 심볼 그룹 중 각각의 심볼 그룹은 상기 복수의 심볼 중 적어도 하나의 심볼을 포함하며,
    상기 입력 분석기는 또한 상기 각각의 심볼 그룹에 대하여 상기 복수의 순열 중 대응하는 순열로서 상기 미리 설정된 제2 개수의 심볼 인덱스 중 적어도 하나의 심볼 인덱스의 순열을 도출하기 위해 상기 적어도 하나의 심볼을 상기 적어도 하나의 심볼 인덱스와 각각 연관시키도록 구성되는, 키 생성 장치.
  9. 청구항 8에 있어서,
    상기 미리 설정된 제1 개수는 2 이상이고,
    상기 키 생성기는 또한 상기 각각의 심볼 그룹에 대하여 상기 복수의 서브 키 그룹 중 대응하는 서브 키 그룹을 검색하여 상기 복수의 제1 사전 계산된 키 중 적어도 하나의 제1 사전 계산된 키 및 상기 적어도 하나의 제2 사전 계산된 키 중 하나의 제2 사전 계산된 키를 상기 저장부로부터 획득하기 위해 상기 대응하는 서브 키 그룹을 식별하도록 구성되며, 상기 적어도 하나의 제1 사전 계산된 키는 상기 적어도 하나의 심볼에 각각 대응하고, 상기 하나의 제2 사전 계산된 키는 상기 적어도 하나의 심볼 인덱스의 상기 순열에 대응하는, 키 생성 장치.
  10. 청구항 5에 있어서,
    상기 입력 분석기가 상기 복수의 심볼을 식별하기 전에 상기 복수의 서브 키를 계산하여 상기 저장부에 저장하도록 구성된 사전 계산기를 더 포함하는, 키 생성 장치.
  11. 청구항 10에 있어서,
    상기 각각의 제1 서브 키는 이산로그 순환군 내 제1 원소의 제1 이산로그 값을 나타내고, 상기 각각의 제2 서브 키는 상기 이산로그 순환군 내 제2 원소의 제2 이산로그 값을 나타내되, 상기 사전 계산기는 또한 상기 제1 이산로그 값을 계산하기 위해 상기 각자의 후보 심볼로부터 상기 제1 원소를 생성하고 상기 제2 이산로그 값을 계산하기 위해 상기 각자의 후보 순열로부터 상기 제2 원소를 생성하도록 구성되는, 키 생성 장치.
  12. 청구항 11에 있어서,
    상기 사전 계산기는 또한 상기 제1 원소를 생성하기 위해 상기 각자의 후보 심볼에 해쉬 함수를 적용하고 상기 제2 원소를 생성하기 위해 상기 각자의 후보 순열에 상기 해쉬 함수를 적용하도록 구성되는, 키 생성 장치.
  13. 사용자 아이디 정보로부터 복수의 심볼을 식별하는 단계;
    상기 복수의 심볼과 동일한 개수의 심볼 인덱스를 상기 복수의 심볼과 연관시키는 단계;
    상기 복수의 심볼로부터 적어도 하나의 순열을 도출함에 따라 생성되는 상기 심볼 인덱스들의 순열을 도출하는 단계;
    상기 복수의 심볼에 각각 대응하는 복수의 제1 사전 계산된 키 및 상기 심볼 인덱스들의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키를 포함하는 복수의 사전 계산된 키를 획득하는 단계; 및
    상기 복수의 사전 계산된 키로부터 상기 사용자 아이디 정보에 대응하는 암호 키를 생성하는 단계를 포함하는
    키 생성 방법.
  14. 청구항 13에 있어서,
    상기 복수의 사전 계산된 키 각각은 이산로그 순환군 내 원소의 이산로그 값을 나타내는, 키 생성 방법.
  15. 청구항 14에 있어서,
    상기 암호 키를 생성하기 위해 상기 복수의 사전 계산된 키를 합산하는 단계를 더 포함하는, 키 생성 방법.
  16. 청구항 13에 있어서,
    상기 복수의 심볼 각각은 복수의 후보 심볼 중 하나이고, 상기 적어도 하나의 순열 각각은 복수의 후보 순열 중 하나이며, 상기 복수의 후보 순열 각각은 상기 복수의 후보 심볼의 적어도 일부로부터 도출 가능한, 키 생성 방법.
  17. 청구항 16에 있어서,
    복수의 서브 키를 저장부에 저장하는 단계를 더 포함하되, 상기 복수의 서브 키는 미리 설정된 제1 개수의 서브 키 그룹으로 배열되고, 상기 키 생성 방법은 상기 복수의 제1 사전 계산된 키 및 상기 적어도 하나의 제2 사전 계산된 키를 상기 저장부로부터 획득하기 위해 상기 미리 설정된 제1 개수의 서브 키 그룹 중 하나 또는 복수의 서브 키 그룹을 검색하는 단계를 더 포함하며,
    상기 미리 설정된 제1 개수의 서브 키 그룹 각각은 복수의 제1 서브 키 및 복수의 제2 서브 키를 포함하되, 상기 복수의 제1 사전 계산된 키가 상기 저장부로부터 획득 가능하도록 상기 복수의 제1 서브 키 중 각각의 제1 서브 키는 상기 복수의 후보 심볼 중 각자의 후보 심볼에 대응하고, 상기 적어도 하나의 제2 사전 계산된 키가 상기 저장부로부터 획득 가능하도록 상기 복수의 제2 서브 키 중 각각의 제2 서브 키는 상기 복수의 후보 순열 중 각자의 후보 순열에 대응하는, 키 생성 방법.
  18. 청구항 17에 있어서,
    상기 복수의 후보 순열 각각은 미리 설정된 제2 개수의 심볼 인덱스의 적어도 일부의 순열인, 키 생성 방법.
  19. 청구항 18에 있어서,
    상기 미리 설정된 제1 개수는 1인, 키 생성 방법.
  20. 청구항 17에 있어서,
    상기 복수의 후보 순열 각각은 미리 설정된 제2 개수의 심볼 인덱스 중 적어도 일부의 순열이고,
    상기 키 생성 방법은 상기 복수의 심볼을 복수의 심볼 그룹으로 파티셔닝하는 단계를 더 포함하며, 상기 적어도 하나의 순열은 상기 복수의 심볼 그룹에 각각 대응하는 복수의 순열을 포함하고, 상기 복수의 심볼 그룹 중 각각의 심볼 그룹은 상기 복수의 심볼 중 적어도 하나의 심볼을 포함하며,
    상기 키 생성 방법은 상기 각각의 심볼 그룹에 대하여 상기 복수의 순열 중 대응하는 순열로서 상기 미리 설정된 제2 개수의 심볼 인덱스 중 적어도 하나의 심볼 인덱스의 순열을 도출하기 위해 상기 적어도 하나의 심볼을 상기 적어도 하나의 심볼 인덱스와 각각 연관시키는 단계를 더 포함하는, 키 생성 방법.
  21. 청구항 20에 있어서,
    상기 미리 설정된 제1 개수는 2 이상이고,
    상기 키 생성 방법은 상기 각각의 심볼 그룹에 대하여 상기 복수의 서브 키 그룹 중 대응하는 서브 키 그룹을 검색하여 상기 복수의 제1 사전 계산된 키 중 적어도 하나의 제1 사전 계산된 키 및 상기 적어도 하나의 제2 사전 계산된 키 중 하나의 제2 사전 계산된 키를 상기 저장부로부터 획득하기 위해 상기 대응하는 서브 키 그룹을 식별하는 단계를 더 포함하며, 상기 적어도 하나의 제1 사전 계산된 키는 상기 적어도 하나의 심볼에 각각 대응하고, 상기 하나의 제2 사전 계산된 키는 상기 적어도 하나의 심볼 인덱스의 상기 순열에 대응하는, 키 생성 방법.
  22. 청구항 17에 있어서,
    상기 식별하는 단계 전에 상기 복수의 서브 키를 상기 저장부에 저장하기 위해 상기 복수의 서브 키를 계산하는 단계를 더 포함하는, 키 생성 방법.
  23. 청구항 22에 있어서,
    상기 각각의 제1 서브 키는 이산로그 순환군 내 제1 원소의 제1 이산로그 값을 나타내고, 상기 각각의 제2 서브 키는 상기 이산로그 순환군 내 제2 원소의 제2 이산로그 값을 나타내되, 상기 키 생성 방법은
    상기 제1 이산로그 값을 계산하기 위해 상기 각자의 후보 심볼로부터 상기 제1 원소를 생성하는 단계; 및
    상기 제2 이산로그 값을 계산하기 위해 상기 각자의 후보 순열로부터 상기 제2 원소를 생성하는 단계를 더 포함하는, 키 생성 방법.
  24. 청구항 23에 있어서,
    상기 제1 원소를 생성하기 위해 상기 각자의 후보 심볼에 해쉬 함수를 적용하는 단계; 및
    상기 제2 원소를 생성하기 위해 상기 각자의 후보 순열에 상기 해쉬 함수를 적용하는 단계를 더 포함하는, 키 생성 방법.
  25. 하드웨어와 결합되어,
    사용자 아이디 정보로부터 복수의 심볼을 식별하는 단계;
    상기 복수의 심볼과 동일한 개수의 심볼 인덱스를 상기 복수의 심볼과 연관시키는 단계;
    상기 복수의 심볼로부터 적어도 하나의 순열을 도출함에 따라 생성되는 상기 심볼 인덱스들의 순열을 도출하는 단계;
    상기 복수의 심볼에 각각 대응하는 복수의 제1 사전 계산된 키 및 상기 심볼 인덱스들의 순열에 각각 대응하는 적어도 하나의 제2 사전 계산된 키를 포함하는 복수의 사전 계산된 키를 획득하는 단계; 및
    상기 복수의 사전 계산된 키로부터 상기 사용자 아이디 정보에 대응하는 암호 키를 생성하는 단계를 실행시키기 위하여 매체에 저장된 컴퓨터 프로그램.
KR1020140093303A 2014-07-23 2014-07-23 키 생성 장치 및 방법 KR101599144B1 (ko)

Priority Applications (3)

Application Number Priority Date Filing Date Title
KR1020140093303A KR101599144B1 (ko) 2014-07-23 2014-07-23 키 생성 장치 및 방법
US14/561,641 US9479327B2 (en) 2014-07-23 2014-12-05 Apparatus and method for generating key
CN201410737927.3A CN105281898B (zh) 2014-07-23 2014-12-05 密钥生成装置及方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020140093303A KR101599144B1 (ko) 2014-07-23 2014-07-23 키 생성 장치 및 방법

Publications (2)

Publication Number Publication Date
KR20160011956A KR20160011956A (ko) 2016-02-02
KR101599144B1 true KR101599144B1 (ko) 2016-03-02

Family

ID=55150294

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020140093303A KR101599144B1 (ko) 2014-07-23 2014-07-23 키 생성 장치 및 방법

Country Status (3)

Country Link
US (1) US9479327B2 (ko)
KR (1) KR101599144B1 (ko)
CN (1) CN105281898B (ko)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9779233B2 (en) * 2015-03-05 2017-10-03 Ricoh Co., Ltd. Broker-based authentication system architecture and design
US10341098B2 (en) * 2017-01-24 2019-07-02 Nxp B.V. Method of generating cryptographic key pairs
US10635792B2 (en) 2017-08-31 2020-04-28 Sybase 365, Inc. Multi-factor authentication with URL validation
US10903997B2 (en) * 2017-10-19 2021-01-26 Autnhive Corporation Generating keys using controlled corruption in computer networks
CN107580003A (zh) * 2017-10-31 2018-01-12 哈尔滨工业大学深圳研究生院 工业物联网环境下安全的无证书可搜索公钥加密方案
US11012435B2 (en) * 2017-12-19 2021-05-18 International Business Machines Corporation Multi factor authentication

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100682290B1 (ko) * 1999-09-07 2007-02-15 소니 가부시끼 가이샤 콘텐츠 관리 시스템, 장치, 방법 및 프로그램 격납 매체
JP2003529256A (ja) * 2000-03-24 2003-09-30 ヴォートヒア インコーポレイテッド 安全な複数オーソリティ選挙のためのエルガマル暗号化データのように暗号化されたデータの検証可能な秘密シャッフル
HU0101106D0 (en) * 2001-03-14 2001-05-28 Tozai Trading Corp Id alsorithm
AU2003298560A1 (en) * 2002-08-23 2004-05-04 Exit-Cube, Inc. Encrypting operating system
US7596701B2 (en) * 2004-07-07 2009-09-29 Oracle International Corporation Online data encryption and decryption
US8566593B2 (en) * 2009-07-06 2013-10-22 Intel Corporation Method and apparatus of deriving security key(s)
EP2334006B1 (en) * 2009-12-10 2016-03-23 Nxp B.V. Side-channel resistant modular exponentiation
KR101166129B1 (ko) 2011-05-31 2012-07-23 서울대학교산학협력단 사전계산 테이블을 이용한 이산대수 계산 방법 및 그 장치
KR101301609B1 (ko) * 2012-05-31 2013-08-29 서울대학교산학협력단 비밀키 생성 장치 및 방법, 그리고 그 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 기록매체
KR101329007B1 (ko) * 2012-05-31 2013-11-12 삼성에스디에스 주식회사 아이디 기반 암호 시스템을 위한 비밀키 생성 장치 및 그 방법, 그리고 그 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 기록매체
KR101493212B1 (ko) * 2012-10-31 2015-02-23 삼성에스디에스 주식회사 아이디 기반 암호화, 복호화 방법 및 이를 수행하기 위한 장치

Also Published As

Publication number Publication date
CN105281898B (zh) 2020-06-16
KR20160011956A (ko) 2016-02-02
US9479327B2 (en) 2016-10-25
CN105281898A (zh) 2016-01-27
US20160028538A1 (en) 2016-01-28

Similar Documents

Publication Publication Date Title
KR101599144B1 (ko) 키 생성 장치 및 방법
Chatterjee et al. Cracking-resistant password vaults using natural language encoders
EP3012754B1 (en) Searchable symmetric encryption processing system
US9558366B2 (en) Computer system for storing and retrieval of encrypted data items, client computer, computer program product and computer-implemented method
EP2731041A1 (en) Computer system for storing and retrieval of encrypted data items, client computer, computer program product and computer-implemented method
US20170033933A1 (en) Redactable document signatures
US10270588B2 (en) Method and system for additive homomorphic encryption scheme with operation error detection functionality
EP3637674A1 (en) Computer system, secret information verification method, and computer
CN110851481B (zh) 一种可搜索加密方法、装置、设备及可读存储介质
EP2892175A1 (en) Secure software components anti-reverse-engineering by table interleaving
CN110084599A (zh) 密钥处理方法、装置、设备和存储介质
JP2019207281A (ja) 大小判定サーバ、大小判定暗号化システム、及び大小判定方法
Kuvonchbek Method Authentication of Objects Information Communication
KR101282653B1 (ko) 데이터 치환 암호화 장치 및 방법
US11281688B2 (en) Ranking and de-ranking data strings
US11558371B2 (en) Authentication system(s) with multiple authentication modes using one-time passwords of increased security
KR101977128B1 (ko) 장문 텍스트열에 대한 고정 길이 암호화 장치 및 방법
Sharma et al. Privacy-preserving boosting with random linear classifiers
US12008146B2 (en) Code-based signatures for secure programs
US20230085239A1 (en) Querying fully homomorphic encryption encrypted databases using client-side preprocessing or post-processing
Srimathi et al. Improved Cloud Storage Encryption Using Block Cipher-Based DNA Anti-Codify Model.
US9698977B2 (en) Information processing apparatus, information processing method, and program
KR101095862B1 (ko) 데이터 암호화 장치 및 방법, 데이터 복호화 장치, 데이터 검색 방법
CN115408703A (zh) 格式化文件处理方法、装置及存储介质
Sharma et al. Poster: Privacy-Preserving Boosting with Random Linear Classifiers

Legal Events

Date Code Title Description
A201 Request for examination
E902 Notification of reason for refusal
E701 Decision to grant or registration of patent right
GRNT Written decision to grant
FPAY Annual fee payment

Payment date: 20190102

Year of fee payment: 4

FPAY Annual fee payment

Payment date: 20200121

Year of fee payment: 5