Breaking a class of public-key cryptosystems with Euclid's algorithm (Q1179345): Difference between revisions

Okamoto's public key cryptosystem, proposed in \textit{T. Okamoto} [Electronics Letters 22, 581-582 (1986)]\ already was subject to some attacks. The authors of the article claim to present a method capable of breaking this system, namely to calculate the decryption key given the public encryption key. To read the article and to verify the correctness of the claim one needs to consult Okamoto's original paper for explanation of all symbols used here, as well as to deal with a considerable number of types. After a couple of propositions and theorems whose readability is worsened by the types the authors present an algorithm they claim is capable to calculate the decryption key of Okamoto's public key cryptosystem given the public key as an input. The algorithm in the form presented there either terminates immediately, or will run in an infinite cycle. It is not clear how this algorithm (even in the case it is a correct one) could be used to break Okamoto's modified public key cryptosystem, proposed in \textit{T. Okamoto} [Electronics Letters 23, 814-815 (1987)]\ as a response to Shamir's attack to the original proposal.