For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Ambiguity in Coppersmith' Attacking Method a against NIKS-TAS Scheme
Shigeo TSUJII Kiyomichi ARAKI Masao KASAHARA Eiji OKAMOTO Ryuichi SAKAI Yasuo MAEDA Tomohiko YAGISAWA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/01/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
modulo degeneracy, cryptanalysis, ID-based key sharing, NIKS-TAS,
Full Text: PDF(762.2KB)>>
In this paper it is pointed out that although an elegant differential-like approach is developed, Coppersmith' attacking method on NIKS-TAS cannot succeed to forge a shared key of legitimate entities especially when p-1 contains highly composite divisors, as well as decomposibility-hard divisors. This is mainly due to a severe reduction of modulo size. Computer simulation results confirm this assertion. The ambiguity in the solutions to the collusion equations in the first phase can be analyzed by the elementary divisor theory. Moreover, two basis vectors, qi,ri in the second phase, are found to be inadequate to represent the space spanned by xi-yi and ui-vi(i=1,...,N), because qi,ri exist frequently over the space with small modulo size. Then, the erroneous values of αi,βi,...,εi(i=1,...,N) are derived from the inadequate basis vectors, qi,ri. Also, when the degeneracy in modulo size happens, the solutions to αi,βi,...,εi(i=1,...,N) cannot be solved even by means of the exhaustive search over the small prime divisors of p-1.