[논문]저전력 장비에 적합한 효율적인 RSA 기반의 PAKE 프로토콜

이세원; 윤택영; 박영호; 홍석희

doi:10.13089/jkiisc.2009.19.6.23

저전력 장비에 적합한 효율적인 RSA 기반의 PAKE 프로토콜
Efficient RSA-Based PAKE Procotol for Low-Power Devices 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.19 no.6, 2009년, pp.23 - 35

이세원 (고려대학교 정보경영공학전문대학원) , 윤택영 (고려대학교 정보경영공학전문대학원) , 박영호 (세종사이버대학교) , 홍석희 (고려대학교 정보경영공학전문대학원)

초록
AI-Helper

패스워드 기반의 키 교환(PAKE) 프로토콜은 난수를 공유하거나 PKI가 구축되어 있지 않은 환경에서 공유한 패스워드를 사용하여 세션키를 공유할 수 있게 함으로써 안전한 통신을 제공하는 암호학적 도구이다. RSA를 사용하여 효율적으로 설계하는 것이 쉽지 않기 때문에 대다수의 PAKE 프로토콜들은 Diffie-Hellman 키 교환을 기반으로 설계되어 왔다. 본 논문에서는 RSA 암호화의 효율성을 활용하여 비대칭 통신환경에 적합한 효율적인 RSA-PAKE 프로토콜을 제안한다. 제안하는 RSA-PAKE 프로토콜이 이론적인 계산량과 파라메타를 바탕으로 한 실험을 통하여 얼마나 효율적인지 판단한다. 제안하는 RSA-PAKE 프로토콜에서 비대칭 통신환경의 저전력 장비는 계산적으로 기존 프로토콜 중에서 안전하고 가장 효율적인 CEKEP보다 약 84% 효율적인 비용으로 키 교환을 수행할 수 있다. 특히, 일정 부분의 연산을 키 교환 과정이 진행되기 이전에 수행함으로써 키 교환 과정의 효율성을 극대화 할 수 있다. 제안하는 RSA-PAKE 프로토콜의 안전성은 RSA 문제를 기반으로 렌덤 오라클 모델에서 증명한다.

Abstract ▼ AI-Helper

Password-Authenticated Key Exchange (PAKE) Protocol is a useful tool for secure communication conducted over open networks without sharing a common secret key or assuming the existence of the public key infrastructure (PKI). It seems difficult to design efficient PAKE protocols using RSA, and thus many PAKE protocols are designed based on the Diffie-Hellman key exchange (DH-PAKE). Therefore it is important to design an efficient PAKE based on RSA function since the function is suitable for designing a PAKE protocol for imbalanced communication environment. In this paper, we propose a computationally-efficient key exchange protocol based on the RSA function that is suitable for low-power devices in imbalanced environment. Our protocol is more efficient than previous RSA-PAKE protocols, required theoretical computation and experiment time in the same environment. Our protocol can provide that it is more 84% efficiency key exchange than secure and the most efficient RSA-PAKE protocol CEPEK. We can improve the performance of our protocol by computing some costly operations in offline step. We prove the security of our protocol under firmly formalized security model in the random oracle model.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

또한, 지수연산은 기본적인 square-and- mltiply 알고리즘을 사용하고 소수 생성 및 판정은 Miller-Rabin 소수 판정법을 사용한다. 각 프로토콜에서 요구되어지는 세부적인 사항을 살펴보자. SNAPI 프로토콜에서 서버는 n과 1024-비트보다 큰 소수 e를 생성하고, 클라이언트는 e의 소수 판별 비용과 RSA 암호화인 e에 대한 지수승 연산 비용이 요구된다.
본 논문에서는 매우 효율적인 RSA-PAKE 프로토콜을 제안하였다. 기존의 대부분의 PAKE프로토콜들은 RSA를 사용하여 효율적으로 설계하는 것이 쉽지않기 때문에 Diffie-Hellman 키 교환을 기반으로 설계되어 왔다.
본 논문에서는 매우 효율적인 키 교환을 제공하는 RSA-PAKE 프로토콜을 제안한다. 제안하는 RSAPAKE 프로토콜은 SNAPI 프로토콜, PEKEP, CEKEP와 RSA-EPAKE 프로토콜보다 매우 효율적인 키 교환을 제공한다.
정리 3에 의해서 제안한 프로토콜에서는 서버가 n을 생성하고, 클라이언트에서 최소 52-비트 소수 e를 생성한다. 소수를 생성하는데 필요한 알고리즘인 Miller-Rabin 소수 판정법에서 각 소수에 대해 실행되는 수행 횟수를 살펴보자.
여기서 Adv(E) = Adv(E, P0)이고, 본 논문에서는 E가 다른 인스턴스들을 이용하여 Adv(E, P0) ≤ Qse/|D|+ε을 만족시키도록 하는 것이 목적이다.

가설 설정

D는 패스워드의 집합과 pw는 패스워드로 정의할 때, 두 통신 주체 A와 B는 키 교환을 수행하기 위해 pw∈D를 사전에 공유한 것으로 가정한다.
이때 해쉬 함수에서 사용된 질의와 응답은 리스트로 저장되어 지고, 만약 이전의 질의로 다시 질의 되는 경우 랜덤값이 아닌 이전에 리스트에 저장된 값을 준다. RSA 문제를 푸는 것이 어렵다는 것을 가정하고, 증명과정에서는 t시간 동안 내에 RSA 문제가 풀 수 있는 확률이 아주 작다는 표현으로 Adv^rsa(t)를 사용한다. 제안하는 RSA-PAKE의 안전성은 Hybrid Argument 로 구성되어 있으며 Zhang 등의 논문에서 제시된 안전성 분석방법과 거의 동일하다[14].

제안 방법

본 장에서는 제안한 RSA-PAKE 프로토콜의 e-잉여 공격에 대한 안전성을 분석하고, 안전성이 요구되는 RSA 공개키 변수 e의 최소 크기를 제시한다. RSA 공개키 e의 크기를 기준으로 기존의 RSA- PAKE 프로토콜들과 연산량을 비교하여 효율성에 대해 논의한다.
기존에 제안된 RSA-PAKE 프로토콜인 SNAPI, PEKEP, CEKEP, RSA-EPAKE 프로토콜들의 효율성과 본 논문에서 제안한 프로토콜의 효율성을 비교한다. [표 2]는 Windows XP, 3.
다른 보조정리를 정의하고 증명하기 위해 Send 오라클을 5가지로 세분화하여 정의하고 각 오라클이 공격 알고리즘 E에게 미치는 영향을 확인하도록 한다.
본 논문에서 제안하는 RSA-PAKE 프로토콜은 A가 e를 선택하지 않고 B가 e를 선택한다. 따라서, E가 e-잉여 공격을 성공하기 위해서는 B가 선택할 e를 예측하여 자신이 선택하는 n이 e|Φ(n)을 만족하도록 구성해야 한다.
본 장에서는 제안한 RSA-PAKE 프로토콜의 e-잉여 공격에 대한 안전성을 분석하고, 안전성이 요구되는 RSA 공개키 변수 e의 최소 크기를 제시한다. RSA 공개키 e의 크기를 기준으로 기존의 RSA- PAKE 프로토콜들과 연산량을 비교하여 효율성에 대해 논의한다.
본 장에서는 효율적인 RSA-PAKE 프로토콜을 제안한다. 두 사용자를 A, B라고 한다.
제안하는 RSA-PAKE 프로토콜의 안전성을 증명하기 위해[1]에 제시된 안전성 모델을 살펴본다. 본 논문에서는 안전성 모델에 대한 간략한 설명을 제공하므로 안전성 모델에 대한 자세한 설명은 [1]를 참고한다.

데이터처리

SNAPI 프로토콜에서는 1025-비트 소수의 경우 t는 3번이고, RSA-EPAKE 프로토콜에서는 96-비트 소수의 경우 t는 27번이다. 이와 같이 Miller- Rabin 소수 판정법을 사용하여 소수의 신뢰성 수치와 각 비트수에 요구되는 t를 구해서 평준하게 실험하였다.

이론/모형

동일한 조건에서의 비교를 위해 RSA 모듈러 n의 크기가 1024-비트인 경우를 고려한다. 또한, 지수연산은 기본적인 square-and- mltiply 알고리즘을 사용하고 소수 생성 및 판정은 Miller-Rabin 소수 판정법을 사용한다. 각 프로토콜에서 요구되어지는 세부적인 사항을 살펴보자.

성능/효과

CEKEP의 가장 효율적이라 고려되는 e = 3, ε = 2-80인 경우와 비교했을 때, 표2에서 제시했듯이 제안하는 RSA-PAKE 프로토콜의 클라이언트 연산량은 CEKEP보다 약 84%의 효율성이 개선되었음을 알 수 있다.
결과적으로 제안하는 RSA-PAKE 프로토콜은 기존의 RSA-PAKE 프로토콜들에 비해 효율적인 키 교환을 제공한다. 또한, e를 미리 계산하여 실제 키 교환 과정에서 52-비트 지수에 대한 지수승 한 번만 수행하면 되므로, 매우 빠르게 키 교환 과정을 진행할 수 있다.
결론적으로 E가 n을 선택하여 e|Φ(n)이 만족할 수 있는 확률은 최대 2l/2m이다.
제안하는 RSA-PAKE의 안전성은 Hybrid Argument 로 구성되어 있으며 Zhang 등의 논문에서 제시된 안전성 분석방법과 거의 동일하다[14]. 결론적으로 제안하는 RSA-PAKE 프로토콜은 정리 1에서 보이는 것과 같이 증명 가능한 안전성을 제공한다.
또한, 프로토콜에서 사용되는 변수 l-비트 n과 m-비트 소수 e를 충분히 큰 값으로 선택함으로써 #, #, # 을 무시할 수 있는 크기의 값으로 설정할 수 있다. 따라서 충분히 큰 변수를 사용하면 제안하는 RSAPAKE 프로토콜은 렌덤 오라클 모델하에서 증명 가능한 안전성을 보장한다.
따라서 효율적으로 키 교환을 제공하는 안전한 RSA-PAKE 프로토콜을 설계하는 것은 매우 의미 있는 연구이다. 비대칭 통신환경에 적합한 효율적으로 제안된 RSA-PAKE 프로토콜은 기존에 제안된 PAKE 프로토콜보다 매우 효율적인 키 교환을 제공한다. CEKEP의 가장 효율적이라 고려되는 e = 3, ε = 2^-80인 경우와 비교했을 때, 표2에서 제시했듯이 제안하는 RSA-PAKE 프로토콜의 클라이언트 연산량은 CEKEP보다 약 84%의 효율성이 개선되었음을 알 수 있다.
소수의 분포에 대한 수학적 사실에 근거하여 본 논문에서 제안한 RSA-PAKE 프로토콜의 e-잉여 공격에 대한 안전성을 분석 및 증명한다.
즉, 연산 능력이 작은 저전력 장비를 사용하는 사용자의 경우 매우 효율적으로 키 교환을 수행할 수 있도록 구성되어 있어 두 통신 주체가 상이한 통신 능력을 보유하고 통신에 참여하는 비대칭 환경에 매우 적합하게 사용될 수 있다. 제안하는 RSA-PAKE 프로토콜에서 적은 연산 능력을 가진 통신 주체의 키 교환 비용은 기존 제안된 프로토콜 중에서 가장 효율적인 프로토콜인 CEKEP보다 약 84% 이상 효율성이 개선되었다. 특히, 일정 부분 연산을 키 교환 프로토콜의 수행 이전에 미리 계산함으로써 실시간 키 교환 비용을 절감할 수 있다.
특히, 일정 부분 연산을 키 교환 프로토콜의 수행 이전에 미리 계산함으로써 실시간 키 교환 비용을 절감할 수 있다. 제안하는 RSA-PAKE 프로토콜의 안전성은 RSA 문제를 기반으로 렌덤 오라클 모델에서 증명하였다.
본 논문에서는 매우 효율적인 키 교환을 제공하는 RSA-PAKE 프로토콜을 제안한다. 제안하는 RSAPAKE 프로토콜은 SNAPI 프로토콜, PEKEP, CEKEP와 RSA-EPAKE 프로토콜보다 매우 효율적인 키 교환을 제공한다. 비대칭 환경에서의 두 통신주체는 서로 다른 능력을 가진 주체이며, 시스템이 잘 갖추어지고 연산 능력이 큰 매체와 시스템 사양도 비교적 낮고 연산 능력이 적은 매체이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	일반적인 패스워드 추측 공격은 무엇이 있나?	패스워드 기반 암호기법은 기억 가능한 엔트로피가 낮은 정보를 패스워드로 사용하기 때문에 패스워드 추측 공격에 안전하게 설계되어야 한다. 일반적인 패스워드 추측 공격은 온라인 패스워드 추측 공격과 오프라인 패스워드 추측 공격이 있다. 공격자는 패스워드를 추측하고, 추측한 패스워드를 사용하여 프로토콜에 직접 참여하여 서버의 반응을 통해 추측한 패스워드가 맞는지 확인하는 온라인 패스워드 공격은 패스워드 기반 프로토콜의 경우 피할 수 없는 공격이지만, 실패횟수를 제한하는 방법 등으로 쉽게 막을 수 있으므로 위협적인 공격으로는 간주하지 않는다.
	패스워드 기반 암호기법이 패스워드 추측 공격에 안전하게 설계되어야 하는 이유는?	패스워드 기반 암호기법은 기억 가능한 엔트로피가 낮은 정보를 패스워드로 사용하기 때문에 패스워드 추측 공격에 안전하게 설계되어야 한다. 일반적인 패스워드 추측 공격은 온라인 패스워드 추측 공격과 오프라인 패스워드 추측 공격이 있다.
	e-잉여 공격에 안전하기 위해 전송되는 공개키의 신뢰성을 확인하기 위해 어떤 방법이 사용되나?	e-잉여 공격에 안전하기 위해 전송되는 공개키의 신뢰성을 확인하기 위해 크게 두 가지 방법이 사용된다. 하나는 challenge/respones 방식의 프로토콜을 수행하여 공개키의 적합성을 검증하는 방법이고, 다른 하나는 특정 조건을 만족하는 공개키를 사용하여 e-잉여 공격에 대한 안전성을 보장하는 방법이다. challenge/respones 방식을 기반으로 설계된 최초의 프로토콜은 Zhu 등에 의해 제안되었다[15].

참고문헌 (15)

M. Bellare, D. Pointcheval, and P. Rogaway, "Authenticated key exchange secure against dictionary attack," Advances in Cryptology - EUROCRYPT 2000 Proceedings, LNCS 1807, pp. 139-155, 2000
S. Bellovin and M. Merritt, "Encrypted key exchange : Password-based protocols secure against dictionary attacks," Proc. of the IEEE Symposium on Research in Security and Privacy, pp. 72-84, May 1992
S. Bellovin and M. Merritt, "Augmented encrypted key exchange : A passwordbased protocol secure against dictionary attacks and password file compromise," Proc. of the 1st ACM Conference on Computer and Communications Security, ACM, pp. 244-250, Nov. 1993
D.M. Burton, Elementary number theory, 6th Ed., McGraw-Hill Higher Education, 2007
D. Catalano, D. Pointcheval, and T. Pornin, "Trapdoor Hard-to-Invert Group Isomorphisms and Their Application to Password-Based Authentication," IACR 2007, pp. 115-149, Jan. 2007

상세보기
R. Gennaro and Y. Lindell, "A framework for password-based authenticated key exchange," Ad-vances in Cryptology - EUROCRYPT 2003 Proceedings, LNCS 2656, pp. 524-542, 2003
S. Lucks, "Open key exchange: How to defeat dictionary attacks without encrypting public keys," Proc. of Security Protocol Workshop, LNCS 1361, pp. 79-90, 1997
P. MacKenzie, S. Patel, and R. Swaminathan, "Password-authenticated key exchange based on RSA," Advances in Cryptology, ASIACRYPT 2000 Proceedings, LNCS 1976, pp. 599-613, 2000
A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography, 4th Ed., CRC Press, Oct. 1996
S.J. Park, J.H. Nam, S.J. Kim, and D.H. Won, "Efficient Password-Authenticated Key Exchange Based on RSA," CT-RSA, LNCS 4377, pp. 309？323, 2007
S.H. Shin, K. Kobara, and H. Imai, "RSA-based Password-Authenticated Key

상세보기
D.S. Wong, A.H. Chan, and F. Zhu, "More Effcient Password Authenticated Key Exchange Based on RSA," In Proc. of INDOCRYPT 2003, LNCS 2904, pp. 375-387, 2003
T.Y. Youn, Y.H. Park, C.H. Kim, and J. Lim, "Weakness in a RSA-based password authenticated key exchange protocol," Inf. Process. Lett, vol. 108, no. 6, pp. 339-342, Nov. 2008

상세보기
M. Zhang, "New approaches to password authenticated key exchange based on RSA," Proc. of Asiacrypt, LNCS 3329, pp. 230-244, 2004
F. Zhu, D.S. Wong, A.H. Chan, and R. Ye, "Password Authenticated Key Exchange Based on RSA for Imbalanced Wireless Networks," In Proc. of ISC 2002, LNCS 2433, pp. 150-161, 2002

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증