The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
모듈 반전 속도를 높이는 것은 정보 보안 분야에서 가장 중요한 주제 중 하나입니다. 타원 곡선 위(특정 목표의 소수 유한 필드)에서 공개 키 암호화 시스템과 디지털 서명 체계는 아핀 좌표가 선택된 경우 모듈식 반전을 자주 사용합니다. 일반적인 컴퓨터 환경에서는 네트워크를 통한 대부분의 데이터 전송과 메모리에 대한 데이터 저장, 프로세서의 작동 세트가 5비트 또는 바이트의 배수로 수행됩니다. Dusse와 Kaliski는 몽고메리 방법을 가속화하기 위해 이러한 연산 단위를 DSP에 일치시키는 빠른 모듈식 곱셈 알고리즘을 제안했습니다. 그러나 모듈러 반전 알고리즘은 비트 단위 연산을 사용하여 개발되었으므로 연산 단위가 일치하지 않습니다. 본 논문에서는 임의의 처리 장치에 적합한 모듈러 반전을 위한 두 가지 기술을 제안합니다. 첫 번째 기술은 분할 없이 새로운 확장된 GCD 절차를 제안합니다. 이는 몽고메리 모듈러 산술 알고리즘이 사용하는 이동, 덧셈, 곱셈 연산으로 구성될 수 있습니다. 두 번째 기법은 모듈러 반전 알고리즘의 후처리 지연 시간을 줄일 수 있다. 특히, 몽고메리 표현에 정의된 모듈러 반전에 매우 유용합니다. 이러한 제안된 기술은 모듈러 반전을 약 5배 더 빠르게 만듭니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Tetsutaro KOBAYASHI, Hikaru MORITA, "Fast Modular Inversion Algorithm to Match Any Operation Unit" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 5, pp. 733-740, May 1999, doi: .
Abstract: Speeding up modular inversion is one of the most important subjects in the field of information security. Over the elliptic curve -- on the prime finite field in particular goals -- public-key cryptosystems and digital signature schemes frequently use modular inversion if affine coordinates are selected. In the regular computer environment, most data transmission via networks and data storage on memories as well as the operation set of processors are performed in multiples of eight bits or bytes. A fast modular multiplication algorithm that matches these operation units for DSP was proposed to accelerate the Montgomery method by Dusse and Kaliski. However, modular inversion algorithms were developed using bit by bit operation and so do not match the operation unit. This paper proposes two techniques for modular inversion that suits any arbitrary processing unit. The first technique proposes a new extended GCD procedure without any division. It can be constructed by the shifting, adding and multiplying operations, all of which a Montgomery modular arithmetic algorithm employs. The second technique can reduce the delay time of post processing in the modular inversion algorithm. In particular, it is of great use for the modular inversion defined in the Montgomery representation. These proposed techniques make modular inversion about 5. 5 times faster.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_5_733/_p
부
@ARTICLE{e82-a_5_733,
author={Tetsutaro KOBAYASHI, Hikaru MORITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Fast Modular Inversion Algorithm to Match Any Operation Unit},
year={1999},
volume={E82-A},
number={5},
pages={733-740},
abstract={Speeding up modular inversion is one of the most important subjects in the field of information security. Over the elliptic curve -- on the prime finite field in particular goals -- public-key cryptosystems and digital signature schemes frequently use modular inversion if affine coordinates are selected. In the regular computer environment, most data transmission via networks and data storage on memories as well as the operation set of processors are performed in multiples of eight bits or bytes. A fast modular multiplication algorithm that matches these operation units for DSP was proposed to accelerate the Montgomery method by Dusse and Kaliski. However, modular inversion algorithms were developed using bit by bit operation and so do not match the operation unit. This paper proposes two techniques for modular inversion that suits any arbitrary processing unit. The first technique proposes a new extended GCD procedure without any division. It can be constructed by the shifting, adding and multiplying operations, all of which a Montgomery modular arithmetic algorithm employs. The second technique can reduce the delay time of post processing in the modular inversion algorithm. In particular, it is of great use for the modular inversion defined in the Montgomery representation. These proposed techniques make modular inversion about 5. 5 times faster.},
keywords={},
doi={},
ISSN={},
month={May},}
부
TY - JOUR
TI - Fast Modular Inversion Algorithm to Match Any Operation Unit
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 733
EP - 740
AU - Tetsutaro KOBAYASHI
AU - Hikaru MORITA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1999
AB - Speeding up modular inversion is one of the most important subjects in the field of information security. Over the elliptic curve -- on the prime finite field in particular goals -- public-key cryptosystems and digital signature schemes frequently use modular inversion if affine coordinates are selected. In the regular computer environment, most data transmission via networks and data storage on memories as well as the operation set of processors are performed in multiples of eight bits or bytes. A fast modular multiplication algorithm that matches these operation units for DSP was proposed to accelerate the Montgomery method by Dusse and Kaliski. However, modular inversion algorithms were developed using bit by bit operation and so do not match the operation unit. This paper proposes two techniques for modular inversion that suits any arbitrary processing unit. The first technique proposes a new extended GCD procedure without any division. It can be constructed by the shifting, adding and multiplying operations, all of which a Montgomery modular arithmetic algorithm employs. The second technique can reduce the delay time of post processing in the modular inversion algorithm. In particular, it is of great use for the modular inversion defined in the Montgomery representation. These proposed techniques make modular inversion about 5. 5 times faster.
ER -