[논문]효율적인 공간 복잡도의 LFSR 곱셈기 설계

정재형; 이성운; 김현성

[국내논문] 효율적인 공간 복잡도의 LFSR 곱셈기 설계
Design of an LFSR Multiplier with Low Area Complexity 원문보기

정재형 (경일대학교 컴퓨터공학부) , 이성운 (경북대학교 컴퓨터공학과) , 김현성 (경일대학교 컴퓨터공학부)

본 논문에서는 GF(2$^{m}$ ) 상에서 효율적인 공간 복잡도를 가진 LFSR(Linear Feedback Shift Register) 구조 기반의 모듈러 곱셈기를 제안한다. 먼저, 공개키 암호화 시스템의 기본 연산인 모듈러 지수승을 위한 지수승 알고리즘을 살펴보고 이를 위한 기본 구조를 제안한다. 특히, 본 논문은 이러한 지수기를 설계하기 위한 기녈 구조로서 효율적인 모듈러 곱셈기를 제안한다. 제안된 구조는 기약다항식으로 모든 계수가 1인 속성의 AOP(All One Polynomial)를 이용하며 구조복잡도 면에서 기존의 구조들보다 훨씬 효율적이다.

This paper proposes a modular multiplier based on LFSR (Linear Feedback Shift Register) architecture with efficient area complexity over GF(2/sup m/). At first, we examine the modular exponentiation algorithm and propose it's architecture, which is basic module for public-key cryptosystems. Furthermore, this paper proposes on efficient modular multiplier as a basic architecture for the modular exponentiation. The multiplier uses AOP (All One Polynomial) as an irreducible polynomial, which has the properties of all coefficients with '1 ' and has a more efficient hardware complexity compared to existing architectures.

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

문제 정의

Fenn등의 연구에서는 AOPM에서 MAOPM으로 변환 하는 과정에서 공간 복잡도를 추가함으로서 시간 복잡도 를 줄이는데 연구의 초점을 맞췄다. 그러나 본 연구에서는 반대로 시간복잡도의 추가로 효율적인 공간 복잡도를 갖는 모듈러 곱셈기를 제안한다. 본 논문에서 제안한 곱셈기는 기존의 구조에 비해서 2클럭사이클이 추가로 필요하다.
본 논문에서는 Fenn이 제안한 구조 복잡도를 줄이기 위한 효율적인 LFSR 곱셈기를 제안한다. 본 논문의 구조는 Fenn의 구조와 마찬가지로 기약 다항식 AOP의 속성을 이용한 LFSR 구조의 곱셈기이다.
본 논문에서는 새로운 모듈러 곱셈 알고리즘을 제안하 였고 LFSR 구조에 기반한 모듈러 곱셈기를 설계하였다. 제안한 모듈러 곱셈기는 기약 다항식으로서 AOP를 이용 한 효율적인 하드웨어 복잡도를 가진 구조이다.
본 논문에서는 Fenn이 제안한 구조 복잡도를 줄이기 위한 효율적인 LFSR 곱셈기를 제안한다. 본 논문의 구조는 Fenn의 구조와 마찬가지로 기약 다항식 AOP의 속성을 이용한 LFSR 구조의 곱셈기이다.

제안 방법

K0m은 AOP를 기약다항식으로 이용한 모듈러 곱셈기를 구성하기 위한 알고리즘을 제안하였다본 절에서는 AOP 알고리즘의 유도과정을 살펴보고 새로운 알고리즘을 제안한다.
본 장에서는 연산을 위한 AOP 알고리즘을 유도하고, 이 알고리즘에 기반 한 각 구조를 살펴본다. 먼저 Fenm등 의 LFSR 구조에 기반한 모듈러 곱셈기와 본 논문에서 제안한 곱셈기를 살펴본다.
그러나 정규기저 표기법과 이원기저 표기법을 이용한 연산에서는 연산전후에 기저변환 단계를 거쳐야 하는 문제가 있다. 본 논문에서는 다항식기저 표기법으로 필드상의 원 소들을 표현한다 다항식기저 표기법에서의 GF(Zm)의 각 원 소는 다음과 같이 m차수 미만의 다항식으로 표현된다.
본 장에서는 본 논문에서 제안한 곱셈기 구조와 기존의 비트순차 LFSR 구조들과 여러 가지 특성을 비교하고 분석하고 시뮬레이션 결과를 제시한다.
본 장에서는 연산을 위한 AOP 알고리즘을 유도하고, 이 알고리즘에 기반 한 각 구조를 살펴본다. 먼저 Fenm등 의 LFSR 구조에 기반한 모듈러 곱셈기와 본 논문에서 제안한 곱셈기를 살펴본다.
본 장에서는 지수 알고리즘을 살펴보고 지수 연산기를 제안한다.
본 절에서는 4.2절에서 상세히 살펴본 Fenn의 모듈러 곱 셈기와 논문 [8]에서 Kim이 제안한 모듈러 곱셈기를 기반으로 본 논문에서 제안한 구조와 비교 분석한다. 표1은 여러 가지 모듈러 곱셈기를 여러 가지 특성에 기반한 비교를 보여준다.
제안한 구조는 그림5의 MAOFM의 구조 복잡도를 줄이는 데 목적이 있다 Fenn등은 AOP의 속성을 이용한 곱셈기를 제안하기 위하여 제시된 필드보다 한차원 확장된 구조상에서 모듈러 곱셈을 수행하는 AOFM 구조를 제안하였다. 그러나 그 구조는 한차원 확장된 필드의 곱셈 결과 값을 반환하므로 연산 후 추가적인 모듈러 감소 연산이 필요하다.
본 논문에서는 새로운 모듈러 곱셈 알고리즘을 제안하 였고 LFSR 구조에 기반한 모듈러 곱셈기를 설계하였다. 제안한 모듈러 곱셈기는 기약 다항식으로서 AOP를 이용 한 효율적인 하드웨어 복잡도를 가진 구조이다. 표 1에서 보여 준 것처럼 제안한 곱셈기는 기존의 곱셈기와 비교해 보다 효율적인 구조 복잡도를 가짐을 확인할 수 있다.
제어 신호는 입력을 위한 m+1 비트의 T과 연산을 위한 m비 트의 '0'을 필요로 한다. 즉, 본 논문에서 제안한 구조는 모듈러 곱셈 연산 수행을 위해서 AOPM과 같은 전체 2n+l개의 클럭사이클을 필요로 한다.

데이터처리

제안한 구조의 논리적인 검증을 위하여 먼저 C언어로 알고리즘의 검증을 수행하였고, Altem사의 MAX+PLUSD 를 이용하여 구조 시뮬레이션 하였다. 그림 7은 본 논문에서 제안한 구조의 시뮬레이션 결과를 보여준다.

성능/효과

그러므로, 표 1에서 보여준 바와 같이 본 논문에서 제안한 구조가 기존의 구조에 비교하여 보다 효율적인 하드웨어 복잡도를 가짐을 알 수 있다.
제안한 구조는 Fem 의 구조와 비교하여 단지 추가적인 2개의 클럭사이클이 필요하지만 XOR와 AND 게이트의 개수를 1/2 정도 줄일 수 있었다. 본 논문에서 제안한 구조는 제한적인 하드웨어 구조가 요구되는 여러 가지 응용을 위한 기본 구조로 사용될 수 있다.
제안한 모듈러 곱셈기는 기약 다항식으로서 AOP를 이용 한 효율적인 하드웨어 복잡도를 가진 구조이다. 표 1에서 보여 준 것처럼 제안한 곱셈기는 기존의 곱셈기와 비교해 보다 효율적인 구조 복잡도를 가짐을 확인할 수 있다. 제안한 곱셈기는 공개키 기반의 암호화 프로세서 설계에 효 율적으로 이용할 수 있을 것으로 기대된다.

후속연구

제안한 구조는 Fem 의 구조와 비교하여 단지 추가적인 2개의 클럭사이클이 필요하지만 XOR와 AND 게이트의 개수를 1/2 정도 줄일 수 있었다. 본 논문에서 제안한 구조는 제한적인 하드웨어 구조가 요구되는 여러 가지 응용을 위한 기본 구조로 사용될 수 있다.
표 1에서 보여 준 것처럼 제안한 곱셈기는 기존의 곱셈기와 비교해 보다 효율적인 구조 복잡도를 가짐을 확인할 수 있다. 제안한 곱셈기는 공개키 기반의 암호화 프로세서 설계에 효 율적으로 이용할 수 있을 것으로 기대된다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

[국내논문] 효율적인 공간 복잡도의 LFSR 곱셈기 설계
Design of an LFSR Multiplier with Low Area Complexity 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

데이터처리

성능/효과

후속연구

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 효율적인 공간 복잡도의 LFSR 곱셈기 설계 Design of an LFSR Multiplier with Low Area Complexity 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

데이터처리

성능/효과

후속연구

이 논문을 인용한 문헌

저자의 다른 논문 :

김현성 (37)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 효율적인 공간 복잡도의 LFSR 곱셈기 설계
Design of an LFSR Multiplier with Low Area Complexity 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper