부채널 공격에 안전한 슬라이딩 윈도우 기반 곱셈을 이용한 개선된 NTRUEncrypt :Improved NTRUEncrypt secure against side-channel attacks using sliding window-based multiplication

김태현

추천

검색

자료유형: 학위논문

저자정보: 김태현 (인하대학교, 인하대학교 대학원)

지도교수: 이문규

발행연도: 2020

저작권: 인하대학교 논문은 저작권에 의해 보호받습니다.

이용수1

이 논문의 연구 히스토리 (3)

2020

부채널 공격에 안전한 슬라이딩 윈도우 기반 곱셈을 이용한 개선된 NTRUEncrypt

김태현 컴퓨터공학과 2020.01 학위논문

2019

개선된 패턴 기반의 슬라이딩 윈도우 곱셈을 이용한 NTRUEncrypt

김태현 , 이문규 한국통신학회 학술대회논문집 2019.01 학술대회자료

2004

부채널 공격에 안전한 타원곡선 스칼라 곱셈 알고리즘

김태현 , 장상운 , 김웅희 외 1명 정보보호학회논문지 2004.12 학술저널

이 논문의 후속연구가 궁금하신가요?
연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
이 논문의 연구 히스토리 확인하기

초록· 키워드

오류제보하기

오늘날 공개키 암호 알고리즘 중에서 많이 사용되고 있는 알고리즘으로는 RSA, 타원곡선암호(ECC) 등이 있다. 해당 알고리즘들은 소인수분해 문제, 타원곡선상의 이산대수 문제 등을 기반으로 하고 있는데 이러한 문제들은 양자컴퓨터의 개발 이후 Shor의 알고리즘과 같은 양자 알고리즘을 활용하면 쉽게 답이 구해질 것으로 예상되기 때문에 이러한 문제를 기반으로 하는 RSA, ECC 등의 암호 알고리즘도 취약해질 것으로 예상되고 있다. 따라서 NIST에서 양자컴퓨터의 개발 이후로도 안전성을 유지할 수 있는 포스트 퀀텀 암호를 공모하였으며 NTRU, McEliece, UOV, Rainbow 등이 후보로 제출되었다. 그중 NTRU의 암호화 버전인 NTRUEncrypt는 이미 2008년 IEEE P1363.1에 표준으로 채택된 바 있다.
본 논문에서는 NTRUEncrypt의 성능향상을 위한 방법을 제안한다. NTRUEncrypt는 다항식 환에서 정의되며 암호화 및 복호화 과정에서의 곱셈 연산 성능이 전체 성능을 좌우한다. NTRUEncrypt에서는 계수가 {0, 1, -1}만을 가진 다항식을 뽑아 암호화 및 복호화 과정에서 곱셈 연산을 하는데 기존의 NTRUEncrypt에서는 이 점을 이용해 인덱스 기반의 다항식 곱셈연산을 하였다. 2017년에 Pyo 등은 인덱스 기반의 다항식 곱셈연산 대신 슬라이딩 윈도우 방법을 적용하여 곱셈연산의 속도를 더 빠르게 하는 방법을 제안한 바 있다. 본 논문에서는 Pyo 등의 방법을 더 효율적으로 만들기 위해 계수 1과 ?1을 함께 고려함으로써 새로운 윈도우 패턴들을 정의하고, 이들을 이용하여 연산속도를 개선하고 시간 분석과 전력 분석에 대한 부채널 공격 대응 방법을 추가한 개선된 슬라이딩 윈도우 방법을 제안한다.
시간 분석 공격에 대해서는 슬라이딩 윈도우가 적용되더라도 곱셈 연산의 수행시간이 일정하게 유지되도록 대응하였고, 전력 분석 공격에 대해서는 데이터 값을 무작위로 초기화시키고 연산순서가 무작위로 이루어지도록 대응하였다. 마르코프 체인 분석 방법을 이용해서 최적의 윈도우 크기를 구하고 이를 실험을 통해 구한 최적의 윈도우 크기와 큰 차이가 없음을 확인하였다. 기존의 슬라이딩 윈도우를 이용한 다항식 곱셈 대비 제안 방법은 최대 5.4% 향상되었고, NTRUEncrypt에 적용했을 경우 암호화 및 복호화의 경우 각각 최대 4.2%와 4.6% 향상되었다.

Public key cryptographic algorithms that are widely used today include RSA and Elliptic Curve Cryptography (ECC). These algorithms are based on prime factorization problems and discrete logarithmic problems on elliptic curves, respectively. However, these problems are expected to be easily solved by using quantum algorithms such as Shor''s algorithm after the development of quantum computers. In such cases, cryptographic algorithms such as RSA and ECC, which are based on these problems, are also expected to be vulnerable. So NIST held a competition to post-quantum cryptography to maintain safety even after the development of quantum computers, and NTRU, McEliece, UOV, and Rainbow were submitted as candidates. NTRUEncrypt, an encrypted version of NTRU, was already adopted as a standard in IEEE P1363.1 in 2008.
In this paper, we propose a method for improving the performance of NTRUEncrypt. NTRUEncrypt is defined over a polynomial ring, and the performance of multiplication operations during encryption and decryption dominates the overall performance. NTRUEncrypt generates polynomials with only coefficients {0, 1, -1} and multiplies them during encryption and decryption. This polynomial was used to perform index-based polynomial multiplication. In 2017, Pyo et al. proposed a method to speed up multiplication by applying a sliding window method instead of the index-based polynomial multiplication. In this paper, we define new window patterns that cover coefficients 1 and -1 together to make Pyo''s method more efficient. Using them, we propose an improved sliding window method that improves the computational speed and adds side channel attack countermeasures against timing analysis and power analysis.
For the timing analysis attack countermeasure, the execution time of the multiplication operation was kept constant even if the sliding window was applied. For the power analysis attack countermeasure, the values are initialized to a random number and the operation order was randomly permuted. Using a Markov chain analysis method, the optimal window size was estimated and it was confirmed that there is no significant difference from the optimal window size obtained through experiments. The proposed method improves by up to 5.4% compared to the polynomial multiplication using the previous sliding window method, and when applied to NTRUEncrypt, it improves the encryption and decryption speeds by up to 4.2% and 4.6%, respectively.

#NTRU #side channel analysis

목 차 i
표 목차 ⅲ
알고리즘 목차 ⅳ
그림 목차 ⅳ
국문 요약 1
영문 요약 2
1. 서론 4
2. 사전지식 6
2.1. NTRUEncrypt 6
2.1.1. 기본 다항식 연산 6
2.1.2. 개인키 및 공개키 생성 7
2.1.3. 암호화 8
2.1.4. 복호화 8
2.2. 인덱스 곱셈 방법 8
2.3. 슬라이딩 윈도우 곱셈 방법 10
2.4. 부채널 공격 14
3. 제안 방법 15
3.1. 새로운 패턴을 고려한 삼진 다항식 곱셈 방법 15
3.2. 부채널 공격에 대한 대응 21
3.2.1. 전력 분석 공격 대응 21
3.2.2. 시간 분석 공격 대응 22
4. 성능 분석 33
4.1. 최적 윈도우 크기 결정 33
4.2. 성능 비교 37
5. 결론 46
참고 문헌 47

최근 본 자료

전체보기

구분	그룹	데이터 항목
AI 학습용 데이터	원문	원문 PDF 파일
AI 학습용 데이터	원문 + 메타 (기본/상세)	원문 PDF 파일 및 서지정보 CSV
대량 구매용 데이터	B2B 구독 방식	특정 자료 한정으로 원문 접근 권한 부여
대량 구매용 데이터	URL 전달 방식	바로 PDF 뷰어를 열람할 수 있는 URL 제공

구분	그룹	데이터 항목
AI 학습용 데이터	기본 메타	발행기관명, 간행물명, 권호명, 권(vol), 호(issue), 통권, 발행연도, 발행월, 논문명, 저자명, 시작페이지, 종료페이지, 전체페이지, 상세페이지URL
상세 메타 데이터	발행기관 메타	발행기관 이명, 영문명, 창립연도, 홈페이지URL, 발행기관 소개
	간행물 메타	부제목, 간행물 유형, ISSN, ISBN, 최초발행연도, 폐간연도, 간행빈도, 발행주기, 등재사항, 이용수, 피인용수, 권호수, 논문수, 표지이미지
	논문 메타	작성 언어, 부제목, 대등제목, 목차, 키워드, 초록, 이미지, 참고문헌, 이용수, 피인용수, 논문활용도, DBpia통합주제분류, KDC분류, DDC분류, 한국연구재단분류, UCI, DOI
	저자 메타	소속기관, 소속부서, 직급, 연구분야, 연구키워드, 이용수, 피인용수, 저자 논문활용도

구분	그룹	데이터 항목
※ 결합형/맞춤형 메타 데이터는 신청 내용에 따라 다양하게 제공 가능
이용순위 정보	주제분야별 많이 이용된 논문	“인문학”에서 많이 이용된 논문 TOP100
	이용기관별 많이 이용된 논문	“중고등학교”에서 많이 이용된 논문 TOP100
	세부기관별 많이 이용된 논문	“서울대학교”에서 많이 이용된 논문 TOP100
	키워드별 많이 이용된 논문	“Chat GPT”에서 많이 이용된 논문 TOP100
키워드 정보	많이 이용된 키워드	특정기간/분야/저널 내 많이 이용된 키워드
	많이 발행된 키워드	특정기간/분야/저널 내 많이 발행된 키워드
	많이 검색된 키워드	특정기간/분야/저널 내 많이 검색된 키워드
	연구 트렌드 키워드	특정 키워드 연관 연구동향 분석 데이터 키워드

논문 기본 정보

이 논문의 연구 히스토리 (3)

초록· 키워드

목차

최근 본 자료

댓글(0)