[논문]k-역행렬을 이용한 메시지 인증 기법

이희정; 김태권

doi:10.13089/jkiisc.2004.14.6.105

k-역행렬을 이용한 메시지 인증 기법
Message Authentication Code based on k-invertible Matrices 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.14 no.6, 2004년, pp.105 - 110

초록
AI-Helper

메시지 인증 코드(MAC)란 메시지의 무결성을 입증하기 위해서나 사용자 인증 등에 사용되는 것으로 2003년 Crypto에서 Cary와 Venkatesan이 새로운 기법을 소개하였다. 비밀키 들을 이용하여 암호화된 값을 결정하고 행렬식이 $\pm$1인 공개된 행렬들을 이용하여 메시지 인증코드를 생성하는 방식이다. 여기서 공개된 행렬들은 k-invertible(k-역행렬)이라는 특성을 갖게 되는데 이러한 k가 충돌이 일어나는 확률에 영향을 주게 된다. k를 작게 하는 행렬들을 선택하는 것이 중요한데 Cary 등은 임의의 행렬들을 소개하고 그것들이 k-역행렬이 되는 이유를 보여 주고 있다. 본 논문에서는 공개키로 사용되는 k-역행렬 들을 어떻게 선택하여야 하는 지를 살펴본다. 효율성을 높이기 위해서 행렬들의 성분들은 -1, 0, 1로만 제한한다. 특정한 성질을 갖는 22개의 행렬들 중에서 4개의 행렬을 선택할 때의 충분조건을 알아보고 이들의 k값도 살펴본다. 또한, Cary등이 제안한 것보다는 효율성과 안정성이 향상된 k=5인 행렬들을 소개한다.

Abstract ▼ AI-Helper

MAC is used for data origin authentication or message integrity protection. In Crypto'03 Cary and Venkatesan introduced new MAC based on unimodular matrix groups. It is to encrypt messages using private keys and to encrypt them again using public keys which are matrices whose determinants are $\pm$1. These matrices have property called k-invertible. This k effects on the collision probability of this new MAC. The smaller k is, the less collisions occur. Cary shows 6-invertible matrices, and 10-invertible matrices whose components are only 1, 0, -1. In this paper we figure out sufficient conditions about choosing 4 matrices among special 22 matrices. Also, we introduce 5-invertible matrices whose components are 1, 0, -1. Those have better efficiency and security.

주제어

AI 본문요약
AI-Helper

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

문제 정의

그러나 이러한 현상도 구현에 의해서 보여 진다. 네 번째로, 필요조건을 만족하는 행렬들의 k값은 어떻게 나타나는 지에 대해서 조사해 본다. 4개의 행렬들을 선택하여 반복할 경우는 k를 7까지 찾아낼 수 있고 7개의 행렬들을 선택하여 50개까지 반복하여 공개키를 사용할 경우 k를 5까지 줄일 수 있다.
그러나 어떠한 이유에서 그러한 행렬들을 선택했는지 또는 그러한 행렬들의 k값이 최소인지에 대해서는 언급이 없었다. 따라서 본 논문에서는 공개키를 선정하는 방법에 대해서 알아보려고 한다. 이를 위해서 구현을 다소 단순화하고 효율성도 높이기 위해서 행렬의 원소들을 1, 0, -1로 제한한다.
새로운 메시지 인증코드 생성 기법에서 공개키로 사용되어지는 행렬들의 특성을 살펴보았다. 효율성을 높이기 위하여 원소들을 0, 1, -1 로 제한하여 행렬식이 ±1인 것들을 찾아보니 40개의 행렬들이 생성되었다.
어떠한 행렬들을 공개키로 선택가능한 지를 알아보기 위해서 문제를 먼저 간단히 축소해서 알아보자. 위의 행렬들 중에서 같은 부호를 갖는 원소들로 이루어진 행렬 6개를 선택하여 이들 중에서 4개의 행렬을 선택하여 반복할 경우 어떻게 나열하여야 공개키로 가능하며 동시에 k값은 얼마인지를 알아보려고 한다.
이를 위해서 구현을 다소 단순화하고 효율성도 높이기 위해서 행렬의 원소들을 1, 0, -1로 제한한다. 이와 같은 조건에서 가장 작은 k는 얼마인지 그러한 값을 갖기 위해서는 어떤 행렬들을 선택하여야 하는지에 대해서 알아보려고 한다. 첫 번째로, 주어진 행렬들로부터 A가 0이 되지 않을 조건을 언급하려고 한다.

제안 방법

그때 가장 작은 k값은 7임을 알 수 있었다. 7보다 작은 k값을 찾기 위해서 22개의 행렬들 중에서 서로 다른 행렬들 5개, 6개, 7개, 8개를 선택하여 반복했을 때 조사해보았다. 5개를 선택하여 반복하였을 때는 가장 작은 k는 7이였고 6개를 선택하여 반복했을 경우는 6.
어떻게 해서 이러한 행렬들을 선택하게 되었으며 이들 주어진 행렬들의 k가 가장 작은 값인 지에 대한 언급이 없었다. 따라서 0, 1, -1 만을 사용하여 행렬식이 ±1인 모든 행렬들을 구하고 이들을 어떻게 선택하여 어떻게 반복했을 때 k가 가장 작아지는 지를 살펴보려고 한다. 0, 1, T만을 사용하여 행렬식이 +1인 행렬들은 모두 40개가 되었다.
4개의 행렬을 선택할 경우 모든 공개키들을 찾아내었는데 k 값은 최저 7이었다. 몇 개의 행렬들을 어떻게 나열하는 것이 k값을 가장 작게 할 것인가를 살펴보았는데 8개까지의 행렬들을 선택하여 k값을 찾아보았다. 같은 부호를 갖는 원소들로 이루어진 6 개의 행렬들 중에서 4개의 행렬을 선택할 경우 4 개의 행렬들 간에만 det(M§ — tKM§)丰 —'을 만족하면 충분하다는 것을 보였다.
이때 원소들에 1, 2, 3 등을 포함시킨 행렬들을 사용하였고 3개의 행렬을 50개까지 반복하여 사용하였다. 위의 장에서는 1, 0, -1 만을 사용하여 k- 역행렬이 되기 위한 필요조건을 만족하는 행렬들 중에서 같은 부호를 갖는 원소들로 이루어진 6개의 행렬들을 선택하고 그들 중에서 4개를 선택할 경우 가능한 모든 공개키들을 살펴보았다. 그때 가장 작은 k값은 7임을 알 수 있었다.
위의 행렬들 중에서 같은 부호를 갖는 원소들로 이루어진 행렬 6개를 선택하여 이들 중에서 4개의 행렬을 선택하여 반복할 경우 어떻게 나열하여야 공개키로 가능하며 동시에 k값은 얼마인지를 알아보려고 한다.
6이었다. 이때 원소들에 1, 2, 3 등을 포함시킨 행렬들을 사용하였고 3개의 행렬을 50개까지 반복하여 사용하였다. 위의 장에서는 1, 0, -1 만을 사용하여 k- 역행렬이 되기 위한 필요조건을 만족하는 행렬들 중에서 같은 부호를 갖는 원소들로 이루어진 6개의 행렬들을 선택하고 그들 중에서 4개를 선택할 경우 가능한 모든 공개키들을 살펴보았다.

대상 데이터

효율성을 높이기 위하여 원소들을 0, 1, -1 로 제한하여 행렬식이 ±1인 것들을 찾아보니 40개의 행렬들이 생성되었다. 이들 중에서 공개키가 되기 위한 필요조건을 만족하는 행렬들 22개를 찾아내어(±7 제외) 7개의 행렬을 선택해서 이들을 50개의 행렬로 반복 나열하였을 때 가장 작은 k 값을 찾아 낼 수 있었다.

성능/효과

같은 부호를 갖는 원소들로 이루어진 6 개의 행렬들 중에서 4개의 행렬을 선택할 경우 4 개의 행렬들 간에만 det(M§ — tKM§)丰 —'을 만족하면 충분하다는 것을 보였다. 22개의 행렬들 중에서 임의의 4개 행렬을 선택하여 사용할 경우는 이들이 연속적으로 3번 반복되기 전까지 deKA/》- ”(71/— 1이면 공개키로 가능하다는 것을 알아내었다. 어떠한 근거로 이와 같은 일이 일어나는 지는 이론적으로 밝히지 못하였다.
몇 개의 행렬들을 어떻게 나열하는 것이 k값을 가장 작게 할 것인가를 살펴보았는데 8개까지의 행렬들을 선택하여 k값을 찾아보았다. 같은 부호를 갖는 원소들로 이루어진 6 개의 행렬들 중에서 4개의 행렬을 선택할 경우 4 개의 행렬들 간에만 det(M§ — tKM§)丰 —'을 만족하면 충분하다는 것을 보였다. 22개의 행렬들 중에서 임의의 4개 행렬을 선택하여 사용할 경우는 이들이 연속적으로 3번 반복되기 전까지 deKA/》- ”(71/— 1이면 공개키로 가능하다는 것을 알아내었다.
이는 k-역행렬이 되기 위한 필요조건이다. 두 번째로, 필요조건을 만족하는 22개의 행렬들 중에서 행렬의 구성원들이 모두 같은 부호를 갖는 행렬 6개를 선정하여 임의의 4개의 행렬을 선택하여 반복했을 때 선택된 행렬들의 나열된 위치에 따라 k-역행렬이 되기도 하고 그렇지 않기도 한 것을 발견한다. 먼저 M fU라고 하자.
그러나 이를 이론적으로 증명하지는 못하고 구현에 의해서 보여준다. 세 번째로, 필요조건을 만족하는 22개의 행렬들 중에서 임의의 4개 행렬들을 선택하여 반복적으로 나열할 경우 연속된 12개 행렬이내에서 det(M 9 - M、M, 女 -1이 되면 공개키로 적합함을 알 수 있다. 그러나 이러한 현상도 구현에 의해서 보여 진다.
효율성을 높이기 위하여 원소들을 0, 1, -1 로 제한하여 행렬식이 ±1인 것들을 찾아보니 40개의 행렬들이 생성되었다. 이들 중에서 공개키가 되기 위한 필요조건을 만족하는 행렬들 22개를 찾아내어(±7 제외) 7개의 행렬을 선택해서 이들을 50개의 행렬로 반복 나열하였을 때 가장 작은 k 값을 찾아 낼 수 있었다. 이때 k는 5이다.

후속연구

앞으로 행렬들을 어떻게 선정하여 어떻게 나열하여야 하는지에 관한 충분조건을 찾아내어야 한다. 또한 k값을 가장 작게 하는 공개키는 어떻게 찾아낼 수 있는지에 관하여서도 계속적으로 연구되어져야 할 것이다.

참고문헌 (7)

Mattew. Cary, Ramarathnam Venkatesan, 'A Message Authentication Code Based on Unimodular Matrix Groups', Crypto 2003, LNCS 2729, pp.500-512, 2003
J. Black, S .Halevi, H. Krawczyk, T. Krovetz, P. Rogaway, 'UMAC : Fast and Secure Message Authentication', Advances in Cryptology-Crypto '99, LNCS, vol. 1666, M. Wiener,ed. Springer-Verlag, pp.216-233, 1999
D. Bernstein, 'Factoring-point arithmetic arithmetic and message authentication', draft available as http://cr.yp.to/papers/hash127.dvi
Mihir Bellare, Joe Kilian, Phillip Rogaway, 'The security of the cipher block chaining message authentication code', Journal of computer and system science, 61(3), 362-399, 2000

상세보기
Mariusz H. Jakubowski, R. Venkatesan, 'The chain and sum primitive and its application to MACs and stream ciphers', In Advances in Cryptology-Eurocrypt '98, vol.1403, LNCS, 281-293, Springer-Verlag, 1998

상세보기
홍도원, 신상욱, 강주성, 이옥연, '3GPP MAC 알고리즘 안전성 분석', 정보보호학회논문지, 제11권 제2호, pp.52-59, 2001
임채훈, 이필중, '상호 신분인증 및 디지털 서명기법에 관한 연구', 정보보호학회논문지, 제2권 1호, 1992

저자의 다른 논문 :

표제어: 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

연합인증