Edwards w-coordinate를 이용한 SIDH 구현

김수리 ( Suhri Kim ),윤기순 ( Kisoon Yoon ),박영호 ( Young-ho Park ),홍석희 ( Seokhie Hong ) 한국정보처리학회 2019 한국정보처리학회 학술대회논문집 Vol.26 No.2

본 논문에서는 Edwards 곡선의 w-coordinate를 이용한 isogeny로 SIDH를 구현하는 방법에 대해 처음으로 제안한다. 이를 위해, 먼저 division polynomial을 이용하여 기존 제안된 w-coordinate 3-isogeny를 4M+6S에서 2M+3S로 연산량을 감소시켜 50%의 속도 향상을 달성하였다. 또한, w-coordinate isogney공식을 사용하기 위해 새로 유한체를 제안하였으며 안전성을 분석하였다. 본 논문의 결과 Edwards 곡선을 이용한 SIDH는 Montgomery 곡선과 비해 2.29% 이상의 속도 향상을 예상할 수 있다.

M-SIDH 구현 및 성능 평가를 통한 효율성 연구

김수리(Suhri Kim),서민혜(Minhye Seo) 한국정보보호학회 2023 정보보호학회논문지 Vol.33 No.4

최근 Castryck-Decru에 의해 SIDH 기반 암호가 다항시간 안에 개인키를 복구할 수 있음에 따라 이에 대응하기 위한 여러 방법이 제안되었다. 이 중, Fouotsa 등이 제안한 M-SIDH는 상대방에게 전달하는 torsion point 정보를 마스킹하여 Castryck-Decru 공격에 대응한다. 본 논문에서는 처음으로 C를 이용해 M-SIDH를 구현하였으며, 최적화를 통해 효율성을 평가한다. 본 논문은 M-SIDH의 성능을 확인하기 위해 1024비트 소수를 사용하여 파라미터를 선택하는 방법을 제시하였으며, square-root Velu 공식의 확장체에서의 구현을 통해 M-SIDH를 최적화하였다. 본 논문의 결과 고전 64비트 보안강도를 가지는 MSIDH-1024의 경우 키 교환하는데 대략 1129ms 정도가 필요하다. Due to the recent attack by Castryck-Decru, the private key of SIDH can be recovered in polynomial time so several methods have been proposed to prevent the attack. Among them, M-SIDH proposed by Fouotsa et al, counteracts the attack by masking the torsion point information during the key exchange. In this paper, we implement M-SIDH and evaluate its performance. To the best of our knowledge, this is the first implementation of M-SIDH in C language. Toward that end, we propose a method to select parameters for M-SIDH instantiation and propose a 1024-bit prime for implementation. We implemented the square-root Velu formula over the extension field for further optimization. As a result, 1129 ms is required for a key exchange in the case of MSIDH-1024, providing the classic 64-bit security level.

격자 기반 차세대 양자 내성 암호에 대한 부채널 분석 기술 동향

김수리(Suhri Kim),김한빛(HanBit Kim),김희석(HeeSeok Kim) 한국정보보호학회 2017 情報保護學會誌 Vol.27 No.6

양자 컴퓨터의 개발 가능성이 증가됨에 따라 인수분해나 이산대수 문제를 효율적으로 해결할 수 있는 Shor 알고리즘의 구현 가능성이 늘어나고 있다. 기존 RSA와 ECC 기반 암호시스템은 Shor 알고리즘이 구현될 경우 다항시간 안에 해독이 가능하기 때문에, 이를 대체할 후 양자 암호의 필요성이 대두되고 있으며, 이러한 후 양자 암호 중 격자 기반 암호는 빠른 속도와 비교적 작은 키 사이즈로 각광받고 있다. 후 양자 암호를 실생활에서 사용하려면 양자 컴퓨터 이외에 기존 공격에 대한 안전성도 고려해야 하며, 가장 강력한 암호 분석으로 알려진 부채널 분석에 대한 안전성 또한 필수적으로 구비되어야 한다. 본 논문에서는 격자 기반 암호에 대한 부채널 분석 및 대응기술 동향에 대해 알아본다.

충돌 전력 분석 공격에 높은 공격 복잡도를 갖는 RSA 알고리즘에 대한 취약점 분석 및 대응기법

김수리(Suhri Kim),김태원(Taewon Kim),조성민(Sungmin Jo),김희석(HeeSeok Kim),홍석희(Seokhie Hong) 한국정보보호학회 2016 정보보호학회논문지 Vol.26 No.2

부채널 분석 중 전력 분석 공격은 가장 실용적이며 강력한 기법으로 알려져 있다. 전력 분석 공격 중 단일 파형공격은 단 하나의 파형을 이용하여 공개키 암호 시스템의 비밀정보를 복원하는 강력한 분석기법으로 최근에 활발히 연구되고 있다. 가장 최근에 Sim 등은 이러한 공격에 높은 안전성을 갖는 새로운 지수승 알고리즘을 소개하였다. 본 논문에서 Sim 등이 제안한 단일 파형 공격에 높은 공격 복잡도를 갖는 알고리즘의 취약점을 분석한다. 메시지 블라인딩과 지수 분할 기법에 윈도우 기법을 적용해 높은 공격 복잡도를 갖는 알고리즘을 제안하였지만 사전 연산과정에서 발생하는 정보를 이용하여 비밀정보를 복원할 수 있음을 확인하였다. 또한 취약점을 보완하여 단일파형 공격에 높은 공격 복잡도를 갖는 지수승 알고리즘을 새롭게 제안하였다. 설계된 알고리즘은 사전 연산 과정에서 실제 지수 연산에 사용되는 값들의 재사용을 최소화 하여 충돌 공격에 대해 높은 안전성를 보장한다. It is known that power analysis is one of the most powerful attack in side channel analysis. Among power analysis single trace attack is widely studied recently since it uses one power consumption trace to recover secret key of public cryptosystem. Recently Sim et al. proposed new exponentiation algorithm for RSA cryptosystem with higher attack complexity to prevent single trace attack. In this paper we analyze the vulnerability of exponentiation algorithm described by Sim et al. Sim et al. applied message blinding and random exponentiation splitting method on 2<SUP>t</SUP>-ary for higher attack complexity. However we can reveal private key using information exposed during pre-computation generation. Also we describe modified algorithm that provides higher attack complexity on collision attack. Proposed algorithm minimized the reuse of value that are used during exponentiation to provide security under single collision attack.

SIDH 기반 암호 구현에 대한 홀수 차수 아이소제니 적용

김수리(Suhri Kim),윤기순(Kisoon Yoon),박영호(Young-Ho Park) 한국정보보호학회 2021 정보보호학회논문지 Vol.31 No.1

본 논문에서는 3차, 5차 아이소제니만 이용해 SIDH를 구현할 경우 몽고메리, 에드워드, 허프 곡선 중 어느 곡선에서 더 효율적인지 분석한다. 본 논문에서는 각 타원곡선의 형태에 대해 SIDH 암호를 구성하는 단위연산에 대한 연산량을 비교한 뒤, 홀수 차수만 활용해 SIDH를 구현하기 위해 소수와 파라미터를 설정하는 방법에 관해 설명한다. 본 논문의 결과 몽고메리와 허프 곡선에서 연산량은 유사하며, 에드워드 곡선보다 0.8% 효율적임을 알 수 있다. SIDH 기반 암호에 대한 다양한 파라미터 사용 가능성으로 인해 5차 아이소제니 구현은 필수적이므로, 본 논문은 이러한 SIDH 기반 암호에 대해 어느 타원곡선을 선택해야 하는지에 대해 가이드라인을 제공할 수 있다. In this paper, when SIDH is instantiated using only 3- and 5-isogeny, we demonstrate which curve is more efficient among the Montgomery, Edwards, and Huff curves. To this end, we present the computational cost of the building blocks of SIDH on Montgomery, Edwards, and Huff curves. We also present the prime we used and parameter settings for implementation. The result of our work shows that the performance of SIDH on Montgomery and Huff curves is almost the same and they are 0.8% faster than Edwards curves. With the possibility of using isogeny of degree other than 3 and 4, the performance of 5-isogeny became even more essential. In this regard, this paper can provide guidelines on the selection of the form of elliptic curves for implementation.

CSIDH 기반 암호에 대한 뒤틀린 몽고메리 곡선 사용

김수리(Suhri Kim) 한국정보보호학회 2021 정보보호학회논문지 Vol.31 No.3

본 논문에서는 뒤틀린 몽고메리 곡선을 사용하는 대표적인 암호인 CSURF의 최적화 구현에 대해 분석한다. Projective 형태의 타원곡선 연산은 몽고메리 곡선보다 뒤틀린 몽고메리 곡선이 더 느려서, CSURF는 hybrid 형태의 CSIDH 보다 성능이 느리다. 하지만, square-root Velu 공식을 사용할 경우 타원곡선 연산량을 줄일 수 있으므로 최적화할 여지가 있다. 본 논문에서는 처음으로 뒤틀린 몽고메리 곡선에서의 square-root Velu 공식을 제안하고, 2-isogeny 공식을 최적화하였다. 본 논문의 결과, 제안하는 CSURF는 기존보다 23.3% 빠르고, CSIDH 보다는 10.8% 느리다. 또한, 제안하는 constant-time CSURF의 경우 constant-time CSIDH 보다 6.8% 느리다. 제안하는 결과 CSURF는 CSIDH 보다 느리지만, 기존 뒤틀린 몽고메리를 이용한 구현과 비교하면 상당한 향상으로, 향후 뒤틀린 몽고메리 곡선에 적합한 구현에 본 논문의 결과를 이용할 수 있을 것으로 전망한다. In this paper, we focus on optimizing the performance of CSURF, which uses the tweaked Montgomery curves. The projective version of elliptic curve arithmetic is slower on tweaked Montgomery curves than on Montgomery curves, so that CSURF is slower than the hybrid version of CSIDH. However, as the square-root Velu formula uses less number of ellitpic curve arithmetic than the standard Velu formula, there is room for optimization We optimize the square-root Velu formula and 2-isogeny formula on tweaked Montgomery curves. Our CSURFis 14% faster than the standard CSURF, and 10.8% slower than the CSIDH using the square-root Velu formula. The constant-time CSURF is 6.8% slower than constant-time CSIDH. Compared to the previous implementations, this is a remarkable result.

CSIDH 성능 향상을 위한 Radical Isogeny 적용 분석

김수리(Suhri Kim) 한국정보보호학회 2021 정보보호학회논문지 Vol.31 No.6

CSIDH 기반 암호를 구현하는 데 있어서 가장 큰 단점은 Velu 공식을 활용하여 isogeny를 연산하기 위해 작은 소수 위수를 가지는 커널의 생성점을 선택하는 부분이다. 이 과정은 작은 위수의 경우 실패확률이 크기 때문에 연산량이 많이 들어서, 최근에 radical isogeny를 사용하는 부분에 관한 연구가 진행되었다. 본 논문에서는 CSIDH기반 암호 구현에 있어서 radical isogeny를 사용하는 최적 방안에 대해 제시한다. 본 논문에서는 Montgomery 곡선과 Tate 곡선 사이의 변환을 최적하였으며, 2-, 3-, 5-, 7-isogeny에 대한 공식을 최적화하였다. 본 논문의 결과, CSIDH-512의 경우 radical isogeny를 7차까지 사용할 경우 기존 constant-time CSIDH에 비해서 15.3% 빠른 결과를 얻을 수 있었다. CSIDH-4096의 경우 radical isogeny를 2차까지 사용하는 것이 최적이라는 결론을 얻을 수 있었다. The main obstacle for implementing CSIDH-based cryptography is that it requires generating a kernel of a small prime order to compute the group action using Velu"s formula. As this is a quite painstaking process for small torsion points, a new approach called radical isogeny is recently proposed to compute chains of isogenies from a coefficient of an elliptic curve. This paper presents an optimized implementation of radical isogenies and analyzes its ideal use in CSIDH-based cryptography. We tailor the formula for transforming Montgomery curves and Tate normal form and further optimized the radical 2- and 3- isogeny formula and a projective version of radical 5- and 7- isogeny. For CSIDH-512, using radical isogeny of degree up to 7 is 15.3% faster than standard constant-time CSIDH. For CSIDH-4096, using only radical 2-isogeny is the optimal choice.

Efficient Optimization Method for Polynomial Selection

Suhri Kim(김수리),Heetaek Kwon(권희택),Yongseong Lee(이용성),Nam Su Chang(장남수),Kisoon Yoon(윤기순),Chang Han Kim(김창한),Young-Ho Park(박영호),Seokhie Hong(홍석희) 한국정보보호학회 2016 정보보호학회논문지 Vol.26 No.3

현재까지 알려진 가장 효율적인 인수분해 방법은 General Number Field Sieve (GNFS)를 이용하는 방법이다. CADO-NFS는 GNFS를 기반으로 구현된 공개된 소프트웨어로 RSA-704의 인수분해에 사용된 도구이다. CADO-NFS에서 다항식 선택은 크게 다항식을 생성하는 과정과 이를 최적화하는 과정으로 나누어져 있다. 그러나 CADO-NFS에서 다항식의 최적화 과정은 전체 다항식 선택 소요 시간 중 약 90%를 차지할 정도로 큰 부하를 주고 있다. 본 논문에서는 사전 연산 테이블을 이용하여 다항식 최적화 과정의 부하를 줄이는 방안을 제안한다. 제안하는 방법은 기존 CADO-NFS의 다항식과 같은 다항식을 선택하지만, 다항식 선택에 걸리는 시간은 약 40% 감소한다. Currently, General Number Field Sieve(GNFS) is known as the most efficient way for factoring large numbers. CADO-NFS is an open software based on GNFS, that was used to factor RSA-704. Polynomial selection in CADO-NFS can be divided into two stages – polynomial selection, and optimization of selected polynomial. However, optimization of selected polynomial in CADO-NFS is an immense procedure which takes 90% of time in total polynomial selection. In this paper, we introduce modification of optimization stage in CADO-NFS. We implemented precomputation table and modified optimization algorithm to reduce redundant calculation for faster optimization. As a result, we select same polynomial as CADO-NFS, with approximately 40% decrease in time.

QKD 후처리 과정에서의 부채널 안전성 분석

김수리(Suhri Kim),허동회(Donghoe Heo),홍석희(Seokhie Hong) 한국통신학회 2020 한국통신학회 학술대회논문집 Vol.2020 No.2

Enhanced Polynomial Selection Method for GNFS

Suhri Kim(김수리),Jihoon Kwon(권지훈),Sungmin Cho(조성민),Nam Su Chang(장남수),Kisoon Yoon(윤기순),Chang Han Kim(김창한),Young-Ho Park(박영호),Seokhie Hong(홍석희) 한국정보보호학회 2016 정보보호학회논문지 Vol.26 No.5

RSA 암호 시스템은 가장 널리 사용되는 공개키 암호 알고리즘 중 하나이며, RSA 암호 시스템의 안전성은 큰 수의 인수분해의 어려움에 기반을 둔다. 따라서 RSA 암호 시스템의 합성수 을 인수분해하려는 시도는 계속 진행 중에 있다. General Number Field Sieve는 현재까지 알려진 가장 빠른 인수분해 방법이고, RSA-704를 인수분해 하는데 사용된 소프트웨어인 CADO-NFS도 GNFS를 기반으로 설계되어 있다. 그러나 CADO-NFS는 다항식 선택 과정에서 입력된 변수로부터 항상 최적의 다항식을 선택하지 못하는 문제점이 있다. 본 논문에서는 CADO-NFS의 다항식 선택 단계를 분석하고 중국인의 나머지 정리와 유클리드 거리를 사용하여 다항식을 선택하는 방법을 제안한다. 제안된 방법을 이용하면 기존의 방법보다 좋은 다항식이 매번 선택되며, RSA-1024를 인수분해 하는데 적용할 수 있을 것으로 기대한다. RSA cryptosystem is one of the most widely used public key cryptosystem. The security of RSA cryptosystem is based on hardness of factoring large number and hence there are ongoing attempt to factor RSA modulus. General Number Field Sieve (GNFS) is currently the fastest known method for factoring large numbers so that CADO-NFS – publicly well-known software that was used to factor RSA-704 – is also based on GNFS. However, one disadvantage is that CADO-NFS could not always select the optimal polynomial for given parameters. In this paper, we analyze CADO-NFS’s polynomial selection stage. We propose modified polynomial selection using Chinese Remainder Theorem and Euclidean Distance. In this way, we can always select polynomial better than original version of CADO-NFS and expected to use for factoring RSA-1024.