THREE-LEVEL 하이브리드 몽고메리 감산을 통한 ARM CORTEX-M7에서의 CSIDH-512 최적화

다국어 초록 (Multilingual Abstract)

As an efficient key recovery attack on SIDH/SIKE was proposed, CSIDH is drawing attention again. CSIDH is an isogeny-based key exchange algorithm that is safe against known attacks to date, and provide efficient NIKE by modernizing CRS scheme. In this paper, we firstly present the optimized implementation of CSIDH-512 on ARM Cortex-M7. We use three-level hybrid Montgomery reduction and present the results of our implementation. This is a CSIDH implementation in 32-bit embedded devices that has not been previously presented, and it is expected that the results of this paper will be available to implement CSIDH and derived cryptographic algorithms in various embedded environments in the future.

국문 초록 (Abstract)

NIST PQC 표준화 작업 Round 4에 올라 있던 유일한 아이소제니 기반 KEM 알고리즘인 SIKE에 대한 효율적인 키 복구 공격이 발표됨에 따라, 이를 대체할 수 있는 키 교환 알고리즘인 CSIDH가 다시 주목받고 있다. CSIDH는 현재까지 알려
진 공격에 안전한 아이소제니 기반 키 교환 알고리즘으로, CRS 스킴을 현대화하여 효율적인 NIKE를 제공한다.
본 논문에서는 CSIDH-512를 ARM Cortex-M7에서 구현하고 three-level 하이브리드 몽고메리 감산을 적용하여 최적화한 성능을 측정한 뒤 그 결과를 서술한다. 이는 기존에 제시되지 않았던 32-bit 임베디드 기기에서의 CSIDH 구현으로, 향후
다양한 임베디드 환경에서 CSIDH 및 파생 암호 알고리즘을 구현하는데 본 논문의 결과를 이용할 수 있을 것으로 기대한다.

목차 (Table of Contents)

• 요약 i
• Abstract ii
• Contents iii
• List of Figures iv
• List of Tables v
• List of Algorithms vi
• 1 서론 1
• 2 배경지식 3
• 2.1 타원곡선의 모델 3
• 2.2 아이소제니와 벨루의 정리 6
• 2.3 아이소제니 기반 암호 12
• 2.4 몽고메리 감산 17
• 2.5 ARM Cortex-M7 19
• 3 하이브리드 몽고메리 감산 21
• 3.1 하이브리드 몽고메리 감산 21
• 3.2 Three-level 하이브리드 몽고메리 감산 27
• 4 ARM Cortex-M7에서의 CSIDH-512 구현 36
• 4.1 ARM Cortex-M7에서의 three-level 하이브리드 몽고메리 감산 구현 36
• 4.2 일반적인 몽고메리 감산과의 비교 39
• 5 구현 결과 및 분석 41
• 5.1 실험 환경 41
• 5.2 측정 결과 42
• 6 결론 45