부채널 공격에 안전한 슬라이딩 윈도우 기반 곱셈을 이용한 개선된 NTRUEncrypt = Improved NTRUEncrypt secure against side-channel attacks using sliding window-based multiplication
저자
발행사항
인천 : 인하대학교 대학원, 2020
학위논문사항
학위논문(석사)-- 인하대학교 대학원 : 컴퓨터공학과 2020. 2
발행연도
2020
작성언어
한국어
주제어
발행국(도시)
인천
기타서명
Improved NTRUEncrypt secure against side-channel attacks using sliding window-based multiplication
형태사항
iv, 48 p. ; 26 cm
일반주기명
인하대학교 논문은 저작권에 의해 보호받습니다.
지도교수:이문규
참고문헌: p.47-48
UCI식별코드
I804:23009-200000285127
소장기관
오늘날 공개키 암호 알고리즘 중에서 많이 사용되고 있는 알고리즘으로는 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.
서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)