Quadratic Residue Problem And Cryptanalysis Of One Strong Signature Scheme

This thesis consists of two parts. The frst part aims to investigate systemat-ically the methods to solve quadratic residue problem. Square root extraction is aclassical problem in computers algebra. It plays an essential role in cryptosystemsbased on elliptic curves. There are several algorithms for square root extraction infnite felds. We revisit these algorithms and make appropriate improvements. Theexpected time of Mctwani-Raghavan algorithm is O(len(p)4), while the improvementonly takes expected time O(len(p)3). Besides, we clarify Adleman-Manders-Millersquare root extraction method from a new point of view and present the pseudocodeof this algorithm for the frst time. We analyze the complexity of these algorithmsin this thesis, which will ensure quadratic residue theory more perfect.In the second part, we analyze the GMY strong signature scheme and presentan existential forgery attack against it. The GMY strong signature scheme is basedon the intractability of factorization. In the scheme, messages will be signed in abit-by-bit fashion. It claims that an adversary cannot forge a new signature, evenafter seeing a large number of genuine signed messages. Our existential forgeryattack shows the adversary succeeds in forging the signature of one message, notnecessarily of his choice. We can forge a new signature (Mˉ, xˉk) without knowingthe private key p,q. For this, we construct xˉk,Mˉ, x0to make sure that the forgedmessage and signature pair (Mˉ, xˉk) is valid.