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
Makalah ini mencadangkan algoritma baru untuk mengira pendaraban modular bersaiz dua dengan beberapa prakiraan bergantung kepada modulus. Peranti rendah seperti kad pintar biasanya dilengkapi dengan perkakasan pengganda Montgomery. Walau bagaimanapun, disebabkan kemajuan serangan matematik, institusi keselamatan seperti NIST telah terus menuntut bit-length yang lebih panjang untuk kriptografi kunci awam, menjadikan pengganda cepat usang. Dalam usaha untuk memanjangkan jangka hayat pengganda tersebut, teknik bersaiz dua mengira pendaraban modular dengan dua kali panjang bit pengganda. Teknik dikenali kerana memanjangkan panjang bit pengganda Euclidean klasik, pengganda Montgomery dan gabungannya, iaitu pengganda dwipartit. Walau bagaimanapun, tidak seperti pendaraban klasik dan dwipartit, pendaraban Montgomery melibatkan prapengiraan bergantung kepada modulus, yang berjumlah sebahagian besar penyulitan RSA atau pengesahan tandatangan. Teknik bersaiz dua yang dicadangkan mensimulasikan pendaraban bersaiz dua berdasarkan pengganda Montgomery saiz tunggal, namun prapengiraan pada dasarnya adalah percuma: dalam penyulitan RSA 2048-bit atau pengesahan tandatangan dengan eksponen awam e=216+1, cadangan dengan pengganda Montgomery 1024-bit adalah sekurang-kurangnya 1.5 kali lebih pantas daripada pendaraban Montgomery bersaiz dua sebelumnya.
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.
Salinan
Masayuki YOSHINO, Katsuyuki OKEYA, Camille VUILLAUME, "Faster Double-Size Bipartite Multiplication out of Montgomery Multipliers" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 8, pp. 1851-1858, August 2009, doi: 10.1587/transfun.E92.A.1851.
Abstract: This paper proposes novel algorithms for computing double-size modular multiplications with few modulus-dependent precomputations. Low-end devices such as smartcards are usually equipped with hardware Montgomery multipliers. However, due to progresses of mathematical attacks, security institutions such as NIST have steadily demanded longer bit-lengths for public-key cryptography, making the multipliers quickly obsolete. In an attempt to extend the lifespan of such multipliers, double-size techniques compute modular multiplications with twice the bit-length of the multipliers. Techniques are known for extending the bit-length of classical Euclidean multipliers, of Montgomery multipliers and the combination thereof, namely bipartite multipliers. However, unlike classical and bipartite multiplications, Montgomery multiplications involve modulus-dependent precomputations, which amount to a large part of an RSA encryption or signature verification. The proposed double-size technique simulates double-size multiplications based on single-size Montgomery multipliers, and yet precomputations are essentially free: in an 2048-bit RSA encryption or signature verification with public exponent e=216+1, the proposal with a 1024-bit Montgomery multiplier is at least 1.5 times faster than previous double-size Montgomery multiplications.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1851/_p
Salinan
@ARTICLE{e92-a_8_1851,
author={Masayuki YOSHINO, Katsuyuki OKEYA, Camille VUILLAUME, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Faster Double-Size Bipartite Multiplication out of Montgomery Multipliers},
year={2009},
volume={E92-A},
number={8},
pages={1851-1858},
abstract={This paper proposes novel algorithms for computing double-size modular multiplications with few modulus-dependent precomputations. Low-end devices such as smartcards are usually equipped with hardware Montgomery multipliers. However, due to progresses of mathematical attacks, security institutions such as NIST have steadily demanded longer bit-lengths for public-key cryptography, making the multipliers quickly obsolete. In an attempt to extend the lifespan of such multipliers, double-size techniques compute modular multiplications with twice the bit-length of the multipliers. Techniques are known for extending the bit-length of classical Euclidean multipliers, of Montgomery multipliers and the combination thereof, namely bipartite multipliers. However, unlike classical and bipartite multiplications, Montgomery multiplications involve modulus-dependent precomputations, which amount to a large part of an RSA encryption or signature verification. The proposed double-size technique simulates double-size multiplications based on single-size Montgomery multipliers, and yet precomputations are essentially free: in an 2048-bit RSA encryption or signature verification with public exponent e=216+1, the proposal with a 1024-bit Montgomery multiplier is at least 1.5 times faster than previous double-size Montgomery multiplications.},
keywords={},
doi={10.1587/transfun.E92.A.1851},
ISSN={1745-1337},
month={August},}
Salinan
TY - JOUR
TI - Faster Double-Size Bipartite Multiplication out of Montgomery Multipliers
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1851
EP - 1858
AU - Masayuki YOSHINO
AU - Katsuyuki OKEYA
AU - Camille VUILLAUME
PY - 2009
DO - 10.1587/transfun.E92.A.1851
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2009
AB - This paper proposes novel algorithms for computing double-size modular multiplications with few modulus-dependent precomputations. Low-end devices such as smartcards are usually equipped with hardware Montgomery multipliers. However, due to progresses of mathematical attacks, security institutions such as NIST have steadily demanded longer bit-lengths for public-key cryptography, making the multipliers quickly obsolete. In an attempt to extend the lifespan of such multipliers, double-size techniques compute modular multiplications with twice the bit-length of the multipliers. Techniques are known for extending the bit-length of classical Euclidean multipliers, of Montgomery multipliers and the combination thereof, namely bipartite multipliers. However, unlike classical and bipartite multiplications, Montgomery multiplications involve modulus-dependent precomputations, which amount to a large part of an RSA encryption or signature verification. The proposed double-size technique simulates double-size multiplications based on single-size Montgomery multipliers, and yet precomputations are essentially free: in an 2048-bit RSA encryption or signature verification with public exponent e=216+1, the proposal with a 1024-bit Montgomery multiplier is at least 1.5 times faster than previous double-size Montgomery multiplications.
ER -