257 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) ISSN (Print) 2313-4410, ISSN (Online) 2313-4402 Β© Global Society of Scientific Research and Researchers http://asrjetsjournal.org/ Cryptanalysis and Modification of an Improved Self- Certified Digital Signature Scheme with Message Recovery Mahshid Sadeghpour* Iran University of Science and Technology, Tehran, Iran Email: m_sadeghpour@ieee.org Abstract Digital signature plays a key role in bringing authenticity to cryptographic communications. A signature scheme with message recovery has two characteristics. The public key of the signer can be authenticated while verifying the signature; and the receiver is able to obtain the message. In 2013, Wu and Xu presented a self-certified digital signature scheme with message recovery by combining the two concepts of digital signature with message recovery and self-certified public key. They also claimed that their scheme provides provable security against man-in-the-middle attack, forgery attack, and message leakage. This paper first reviews the scheme of Wu and Xu, and then presents an insider forgery attack to this scheme. It will be shown that this scheme is not secure against insider forgery attack. A modification is proposed in order to overcome this weakness. Keywords: Authenticated encryption; Digital signature; Message recovery; Self-certified public key. 1. Introduction In cryptographic cryptosystems, digital signature is of paramount importance. It can provide integrity, authenticity, and non-repudiation. In public key cryptosystems, the integrity of the public keys must be kept. In classical digital signature schemes, the system authority 𝑺𝑺𝑺𝑺 is used to bind users to their own public keys. However, the management of the certificates of public keys costs a lot. In 1991, Girault [1] introduced the notion of self-certified public key cryptosystem. In his scheme, the features of discrete logarithm problem and factoring problem are combined. ------------------------------------------------------------------------ *Corresponding author. http://asrjetsjournal.org/ American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 28, No 1, pp 257-265 258 Each user is able to choose his own private key, and the user’s public key is derived from user’s identity and his own private key. In this kind of cryptosystem, the user’s public key is generated by 𝑺𝑺𝑺𝑺 whereas his private key is only known by user himself. The user’s public key and identity can be verified implicitly in self-certified public key cryptosystems. In 1994, Neyberg and Ruppel [2] introduced a novel digital signature scheme that provides the property of message recovery based on discrete logarithm problem. Later, at the same year, Horster and his colleagues [3] proposed a modification of the scheme of Neyberg and Ruppel and called it authenticated encryption scheme. Based on Horster and his colleagues’ scheme, in 2003, Tseng and his colleagues [4] designed an authenticated encryption scheme. They also introduced two variants of their scheme. In 2004, Shao [5] demonstrated that their scheme is insecure against insider forgery attack, and proposed an improvement of their scheme. However, Chen and Jan [6] showed that the scheme of Shao is still not secure against insider forgery attack. In 2005, Chang and his colleagues [7] proved that the scheme of Tseng and his colleagues cannot resist 𝑺𝑺𝑺𝑺’s forgery attack. They also designed an improvement to overcome this flaw. However, in 2006, Yoon and Yoo [8] showed that their proposed improvement is vulnerable to known plaintext-ciphertext attack. In their paper, they introduced a new signature scheme which could resist the known plaintext-ciphertext attack. In 2013, Wu and Xu [9] pointed out that the scheme of Yoon and his colleague is vulnerable to man-in-the-middle attack. They also proposed a new self-certified digital signature scheme with message recovery, and provided its provable security in eight aspects. In this paper, it will be demonstrated that the scheme of Wu and Xu is vulnerable to insider forgery attack, and the specified verifier is able to forge the signature if another verifier fully collaborates with him, in terms of providing the specified receiver with his own private key. The rest of the paper is organized as follows. Section 2 is the review of the scheme of Wu and Xu. In section 3, it will be shown that this scheme is insecure against insider forgery attack. Section 4 is the modification of the scheme of Wu ad Xu. Finally, the conclusion is given in section 5. 2. The scheme of Wu and Xu This scheme consists of four phases: system initialization phase, signature generation phase, message recovery phase, and signature conversion phase. The process of the signature is given in Figure 1. 2.1. System initialization phase In the system initialization phase, there exists a system authority (𝑺𝑺𝑺𝑺) that is responsible for generating system parameters. 𝑺𝑺𝑺𝑺 first chooses two large primes 𝒑𝒑 and 𝒒𝒒 of almost the same size such that 𝒑𝒑 = πŸπŸπ’‘π’‘β€² + 𝟏𝟏 and 𝒒𝒒 = πŸπŸπ’’π’’β€² + 𝟏𝟏, where 𝐩𝐩′ and 𝒒𝒒′ are also primes. Then, he computes 𝑡𝑡 = 𝒑𝒑.𝒒𝒒. Afterwards, he chooses an integer π’ˆπ’ˆ which is a base element of order 𝒑𝒑’.𝒒𝒒’. The system authority keeps 𝒑𝒑,𝒒𝒒,𝒑𝒑’ and 𝒒𝒒’ secret and publishes π’ˆπ’ˆ,𝒏𝒏, the group β„€π’π’βˆ— , and four collision free one- way hash functions as follows: American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 28, No 1, pp 257-265 259 𝑭𝑭,𝑯𝑯: {𝟎𝟎,𝟏𝟏}βˆ— �⎯� {𝟎𝟎,𝟏𝟏}π’Œπ’Œ π‘­π‘­πŸπŸ: {𝟎𝟎,𝟏𝟏}βˆ— �⎯� {𝟎𝟎,𝟏𝟏}π’π’πŸπŸ π‘­π‘­πŸπŸ: {𝟎𝟎,𝟏𝟏}βˆ— �⎯� {𝟎𝟎,𝟏𝟏}π’π’πŸπŸ Where 𝒍𝒍𝑡𝑡 is of the length of 𝑡𝑡 in binary, and 𝒍𝒍𝑡𝑡 = π’π’πŸπŸ + π’π’πŸπŸ. The scheme can deal with 𝑴𝑴 ∈ {𝟎𝟎,𝟏𝟏}π’π’πŸπŸ. In this scheme, π’Œπ’Œ = ⌈π₯π₯π₯π₯π₯π₯(𝑷𝑷)βŒ‰,and 𝑷𝑷 = 𝐦𝐦𝐦𝐦𝐦𝐦(𝒑𝒑′,𝒒𝒒′). When the user π‘Όπ‘Όπ’Šπ’Š wants to join the system, he chooses his private key π’™π’™π’Šπ’Š at random and computes π’‘π’‘π’Šπ’Š = π’ˆπ’ˆπ’™π’™π’Šπ’Š π’Žπ’Žπ’Žπ’Žπ’Žπ’Žπ’π’. Then, he submits (π’‘π’‘π’Šπ’Š, π‘°π‘°π‘°π‘°π’Šπ’Š) to the 𝑺𝑺𝑺𝑺. After receiving (π’‘π’‘π’Šπ’Š, π‘°π‘°π‘°π‘°π’Šπ’Š), the system authority computes π’šπ’šπ’Šπ’Š = (π’‘π’‘π’Šπ’Š βˆ’ π‘°π‘°π‘°π‘°π’Šπ’Š)𝑭𝑭(π‘°π‘°π‘°π‘°π’Šπ’Š)βˆ’πŸπŸπ’Žπ’Žπ’Žπ’Žπ’Žπ’Ž 𝒏𝒏, and publishes π’šπ’šπ’Šπ’Š. The user π‘Όπ‘Όπ’Šπ’Š can easily check the validity of π’šπ’šπ’Šπ’Š. 2.2. Signature generation phase When π‘Όπ‘Όπ’Šπ’Š decides to sign a message 𝑴𝑴 with the length π’Œπ’Œ to the verifier 𝑼𝑼𝒋𝒋, he chooses a number π’Œπ’Œπ’Šπ’Š at random and computes the following variables: π’†π’†π’Šπ’Š = π’ˆπ’ˆπ’Œπ’Œπ’Šπ’Š π’Žπ’Žπ’Žπ’Žπ’Žπ’Ž 𝒏𝒏 π‘Ήπ‘Ήπ’Šπ’Š = (π’šπ’šπ’‹π’‹π‘­π‘­οΏ½π‘°π‘°π‘°π‘°π’‹π’‹οΏ½ + 𝑰𝑰𝑰𝑰𝒋𝒋)π’Œπ’Œπ’Šπ’Š π’Žπ’Žπ’Žπ’Žπ’Žπ’Ž 𝒏𝒏 π’‡π’‡π’Šπ’Š = π‘­π‘­πŸπŸ(𝑴𝑴) βˆ₯ π‘­π‘­πŸπŸοΏ½π‘­π‘­πŸπŸ(𝑴𝑴)�⨁𝑴𝑴 π‘»π‘»π’Šπ’Š = π‘Ήπ‘Ήπ’Šπ’Š βŠ• π’‡π’‡π’Šπ’Š π’•π’•π’Šπ’Š = 𝑯𝑯(𝑴𝑴, π’†π’†π’Šπ’Š) π’”π’”π’Šπ’Š = π’Œπ’Œπ’Šπ’Š βˆ’ π’™π’™π’Šπ’Š. π’•π’•π’Šπ’Š.π’‡π’‡π’Šπ’Š Where β€œβ¨β€ denotes the exclusive-or operator, and β€œβˆ₯” denotes the concatenation operator. At last, π‘Όπ‘Όπ’Šπ’Š sends (π’†π’†π’Šπ’Š, π’”π’”π’Šπ’Š,π‘»π‘»π’Šπ’Š) to 𝑼𝑼𝒋𝒋 as the signature of 𝑴𝑴. 2.3. Message recovery phase After receiving (π’†π’†π’Šπ’Š, π’”π’”π’Šπ’Š,π‘»π‘»π’Šπ’Š), the verifier 𝑼𝑼𝒋𝒋 computes π‘Ήπ‘Ήπ’Šπ’Š = π’†π’†π’Šπ’Šπ’™π’™π’‹π’‹ π’Žπ’Žπ’Žπ’Žπ’Žπ’Ž 𝒏𝒏, and calculates π’‡π’‡π’Šπ’Š = π‘Ήπ‘Ήπ’Šπ’Šβ¨π‘»π‘»π’Šπ’Š. Then, he can achieve the message 𝑴𝑴 by the following equation 𝑴𝑴 = π‘­π‘­πŸπŸ([π’‡π’‡π’Šπ’Š]π’π’πŸπŸ)⨁[π’‡π’‡π’Šπ’Š]π’π’πŸπŸ American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 28, No 1, pp 257-265 260 where [π’‡π’‡π’Šπ’Š]π’π’πŸπŸ is the left π’π’πŸπŸ bits of π’‡π’‡π’Šπ’Š, and [π’‡π’‡π’Šπ’Š]π’π’πŸπŸ is the right π’π’πŸπŸ bits of π’‡π’‡π’Šπ’Š. In order to check the validity of the signature, 𝑼𝑼𝒋𝒋 first computes π’•π’•π’Šπ’Š = 𝑯𝑯(𝑴𝑴, π’†π’†π’Šπ’Š) and then, he checks whether the following equation holds or not. π’†π’†π’Šπ’Š = π’ˆπ’ˆπ’”π’”π’Šπ’Š(π’šπ’šπ’Šπ’Šπ‘­π‘­(π‘°π‘°π‘°π‘°π’Šπ’Š) + π‘°π‘°π‘°π‘°π’Šπ’Š)π’•π’•π’Šπ’Šπ’‡π’‡π’Šπ’Š π’Žπ’Žπ’Žπ’Žπ’Žπ’Ž 𝒏𝒏 If the above equation holds, he accepts the signature as a valid signature for 𝑴𝑴. Otherwise, he rejects the signature. 2.4. Signature conversation phase 𝑼𝑼𝒋𝒋 can publish (𝑴𝑴, π’•π’•π’Šπ’Š, π’†π’†π’Šπ’Š), and anyone can confirm the validity of the signature by the following equation: π’•π’•π’Šπ’Š = 𝑯𝑯(𝑴𝑴, π’†π’†π’Šπ’Š) phase 𝑆𝑆𝑆𝑆 π‘ˆπ‘ˆπ‘–π‘– π‘ˆπ‘ˆπ‘—π‘— System initialization phase Computes 𝑦𝑦𝑖𝑖 = (𝑝𝑝𝑖𝑖 βˆ’ 𝐼𝐼𝐼𝐼𝑖𝑖)𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖)βˆ’1π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 , and publicize 𝑦𝑦𝑖𝑖 . Chooses π‘₯π‘₯𝑖𝑖 randomly and computes 𝑝𝑝𝑖𝑖 = 𝑔𝑔π‘₯π‘₯𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘šπ‘›π‘›. Submits (𝑝𝑝𝑖𝑖 , 𝐼𝐼𝐼𝐼𝑖𝑖) to the 𝑆𝑆𝑆𝑆. Signature generation phase Computes 𝑒𝑒𝑖𝑖 = π‘”π‘”π‘˜π‘˜π‘–π‘– π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, 𝑅𝑅𝑖𝑖 = (𝑦𝑦𝑗𝑗𝐹𝐹�𝐼𝐼𝐷𝐷𝑗𝑗� + 𝐼𝐼𝐼𝐼𝑗𝑗)π‘˜π‘˜π‘–π‘–π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, 𝑓𝑓𝑖𝑖 = 𝐹𝐹1(𝑀𝑀) βˆ₯ 𝐹𝐹2�𝐹𝐹1(𝑀𝑀)�⨁𝑀𝑀 𝑇𝑇𝑖𝑖 = 𝑅𝑅𝑖𝑖 βŠ• 𝑓𝑓𝑖𝑖 𝑑𝑑𝑖𝑖 = 𝐻𝐻(𝑀𝑀, 𝑒𝑒𝑖𝑖) 𝑠𝑠𝑖𝑖 = π‘˜π‘˜π‘–π‘– βˆ’ π‘₯π‘₯𝑖𝑖 . 𝑑𝑑𝑖𝑖 . 𝑓𝑓𝑖𝑖 π‘ˆπ‘ˆπ‘–π‘– sends (𝑒𝑒𝑖𝑖, 𝑠𝑠𝑖𝑖 ,𝑇𝑇𝑖𝑖) to π‘ˆπ‘ˆπ‘—π‘— Message recovery phase Calculates 𝑅𝑅𝑖𝑖 = 𝑒𝑒𝑖𝑖π‘₯π‘₯𝑗𝑗 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, 𝑓𝑓𝑖𝑖 = 𝑅𝑅𝑖𝑖⨁𝑇𝑇𝑖𝑖 , and obtains 𝑀𝑀 = 𝐹𝐹2([𝑓𝑓𝑖𝑖]𝑙𝑙1)⨁[𝑓𝑓𝑖𝑖]𝑙𝑙2 . Computes 𝑑𝑑𝑖𝑖 = 𝐻𝐻(𝑀𝑀, 𝑒𝑒𝑖𝑖). Then, checks whether 𝑒𝑒𝑖𝑖 = 𝑔𝑔𝑠𝑠𝑖𝑖(𝑦𝑦𝑖𝑖𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖) + 𝐼𝐼𝐼𝐼𝑖𝑖)𝑑𝑑𝑖𝑖𝑓𝑓𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 Figure 1: Scheme of Wu and Xu American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 28, No 1, pp 257-265 261 3. Insider forgery attack to scheme of Wu and Xu In this section, an insider forgery attack to the aforementioned scheme will be presented. In the insider forgery attack, the specified receiver π‘ˆπ‘ˆπ‘—π‘— forges the received signature of a given message for other system users. The other user is denoted by π‘ˆπ‘ˆπ‘‚π‘‚. If π‘ˆπ‘ˆπ‘‚π‘‚is willing to provide π‘ˆπ‘ˆπ‘—π‘— with his secret key π‘₯π‘₯π‘œπ‘œ, then π‘ˆπ‘ˆπ‘—π‘— is able to forge a valid signature for him. This cooperation between π‘ˆπ‘ˆπ‘‚π‘‚ and π‘ˆπ‘ˆπ‘—π‘— makes sense in many cases of applications of digital signature scheme with message recovery, e.g. in electronic election or in electronic commerce. As an instance, consider that π‘ˆπ‘ˆπ‘—π‘— and π‘ˆπ‘ˆπ‘‚π‘‚ are two friends who want to purchase e-tickets for some mp3 files. They decide to buy just one e-ticket and forge another e-ticket cooperatively. Thus, π‘ˆπ‘ˆπ‘—π‘— buys the ticket (which is π‘ˆπ‘ˆπ‘–π‘–β€²π‘ π‘  signature with message recovery) and offers π‘ˆπ‘ˆπ‘‚π‘‚ a forged e-ticket. If π‘ˆπ‘ˆπ‘‚π‘‚ trusts π‘ˆπ‘ˆπ‘—π‘—, he might reveal his secret key to π‘ˆπ‘ˆπ‘—π‘— in order to obtain a forged e-ticket. Follows demonstrate how this forgery attack operates. Assume that π‘ˆπ‘ˆπ‘—π‘— has recovered 𝑀𝑀 from the signature (𝑒𝑒𝑖𝑖 , 𝑠𝑠𝑖𝑖 ,𝑇𝑇𝑖𝑖) signed by π‘ˆπ‘ˆπ‘–π‘– . He wants to forge a signature (𝑒𝑒𝑖𝑖, 𝑠𝑠𝑖𝑖 ,𝑇𝑇′𝑖𝑖) of 𝑀𝑀 for π‘ˆπ‘ˆπ‘‚π‘‚. The claim is that (𝑒𝑒𝑖𝑖 , 𝑠𝑠𝑖𝑖 ,𝑇𝑇′𝑖𝑖) is a valid signature of 𝑀𝑀 signed by π‘ˆπ‘ˆπ‘–π‘– for π‘ˆπ‘ˆπ‘‚π‘‚. First, π‘ˆπ‘ˆπ‘‚π‘‚ reveals his own private key π‘₯π‘₯π‘œπ‘œ to π‘ˆπ‘ˆπ‘—π‘— . Thereafter, π‘ˆπ‘ˆπ‘—π‘— performs the following steps to forge a valid signature: 1) Compute 𝑅𝑅′𝑖𝑖 = 𝑒𝑒𝑖𝑖π‘₯π‘₯0 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛. 2) Compute 𝑇𝑇′𝑖𝑖 = 𝑅𝑅′𝑖𝑖 βŠ• 𝑓𝑓𝑖𝑖. ( π‘ˆπ‘ˆπ‘—π‘— has obtained 𝑓𝑓𝑖𝑖 in the message recovery phase.) 3) Send the forged signature (𝑒𝑒𝑖𝑖, 𝑠𝑠𝑖𝑖 ,𝑇𝑇′𝑖𝑖) to π‘ˆπ‘ˆπ‘‚π‘‚. The signature (𝑒𝑒𝑖𝑖 , 𝑠𝑠𝑖𝑖 ,𝑇𝑇′𝑖𝑖) can be verified easily since 𝑀𝑀 = 𝐹𝐹2([𝑓𝑓𝑖𝑖]𝑙𝑙1)⨁[𝑓𝑓𝑖𝑖]𝑙𝑙2 𝑑𝑑𝑖𝑖 = 𝐻𝐻(𝑀𝑀, 𝑒𝑒𝑖𝑖) , and 𝑒𝑒𝑖𝑖 = 𝑔𝑔𝑠𝑠𝑖𝑖(𝑦𝑦𝑖𝑖𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖) + 𝐼𝐼𝐼𝐼𝑖𝑖)𝑑𝑑𝑖𝑖𝑓𝑓𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, therefore; π‘ˆπ‘ˆπ‘‚π‘‚ can claim that (𝑒𝑒𝑖𝑖 , 𝑠𝑠𝑖𝑖 ,𝑇𝑇′𝑖𝑖) is the signature of 𝑀𝑀 signed by π‘ˆπ‘ˆπ‘–π‘– for him. In case of any disputes over the validity of the signature, π‘ˆπ‘ˆπ‘‚π‘‚ publishes (𝑀𝑀, 𝑑𝑑𝑖𝑖 , 𝑒𝑒𝑖𝑖), to satisfy whomever questions the validity of (𝑒𝑒𝑖𝑖 , 𝑠𝑠𝑖𝑖 ,𝑇𝑇′𝑖𝑖). The reason of vulnerability of Wu and Xu’s scheme to this attack is that the verification equations 𝑑𝑑𝑖𝑖 = 𝐻𝐻(𝑀𝑀, 𝑒𝑒𝑖𝑖), and 𝑒𝑒𝑖𝑖 = 𝑔𝑔𝑠𝑠𝑖𝑖(𝑦𝑦𝑖𝑖𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖) + 𝐼𝐼𝐼𝐼𝑖𝑖)𝑑𝑑𝑖𝑖𝑓𝑓𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 cannot detect the change in the amount of 𝑇𝑇𝑖𝑖 which is replaced by 𝑇𝑇′𝑖𝑖 in the forged signature. American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 28, No 1, pp 257-265 262 The process of the attack is illustrated in Figure 2. phase π‘ˆπ‘ˆπ‘–π‘– π‘ˆπ‘ˆπ‘—π‘— π‘ˆπ‘ˆπ‘‚π‘‚ Signature generation phase Computes 𝑒𝑒𝑖𝑖 = π‘”π‘”π‘˜π‘˜π‘–π‘– π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, and 𝑅𝑅𝑖𝑖 = (𝑦𝑦𝑗𝑗𝐹𝐹�𝐼𝐼𝐷𝐷𝑗𝑗� + 𝐼𝐼𝐼𝐼𝑗𝑗)π‘˜π‘˜π‘–π‘– π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 , and 𝑓𝑓𝑖𝑖 = 𝐹𝐹1(𝑀𝑀) βˆ₯ 𝐹𝐹2�𝐹𝐹1(𝑀𝑀)�⨁𝑀𝑀, 𝑇𝑇𝑖𝑖 = 𝑅𝑅𝑖𝑖 βŠ• 𝑓𝑓𝑖𝑖, 𝑑𝑑𝑖𝑖 = 𝐻𝐻(𝑀𝑀, 𝑒𝑒𝑖𝑖), and 𝑠𝑠𝑖𝑖 = π‘˜π‘˜π‘–π‘– βˆ’ π‘₯π‘₯𝑖𝑖 . 𝑑𝑑𝑖𝑖. 𝑓𝑓𝑖𝑖 π‘ˆπ‘ˆπ‘–π‘– (𝑒𝑒𝑖𝑖,𝑠𝑠𝑖𝑖,𝑇𝑇𝑖𝑖)�⎯⎯⎯⎯� π‘ˆπ‘ˆπ‘—π‘— Message recovery phase Calculates 𝑅𝑅𝑖𝑖 = 𝑒𝑒𝑖𝑖π‘₯π‘₯𝑗𝑗 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, 𝑓𝑓𝑖𝑖 = 𝑅𝑅𝑖𝑖⨁𝑇𝑇𝑖𝑖 , and obtains 𝑀𝑀 = 𝐹𝐹2([𝑓𝑓𝑖𝑖]𝑙𝑙1)⨁[𝑓𝑓𝑖𝑖]𝑙𝑙2 . Computes 𝑑𝑑𝑖𝑖 = 𝐻𝐻(𝑀𝑀, 𝑒𝑒𝑖𝑖). Then, checks whether 𝑒𝑒𝑖𝑖 = 𝑔𝑔𝑠𝑠𝑖𝑖(𝑦𝑦𝑖𝑖𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖) + 𝐼𝐼𝐼𝐼𝑖𝑖)𝑑𝑑𝑖𝑖𝑓𝑓𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 Insider forgery attack Computes 𝑅𝑅′𝑖𝑖 = 𝑒𝑒𝑖𝑖π‘₯π‘₯0 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 , 𝑇𝑇′𝑖𝑖 = 𝑅𝑅′𝑖𝑖 βŠ• 𝑓𝑓𝑖𝑖 forges the signature and π‘ˆπ‘ˆπ‘—π‘— (𝑒𝑒𝑖𝑖,𝑠𝑠𝑖𝑖,𝑇𝑇′𝑖𝑖)�⎯⎯⎯⎯⎯� π‘ˆπ‘ˆπ‘‚π‘‚ Chooses π‘₯π‘₯𝑂𝑂 as his secret key π‘ˆπ‘ˆπ‘—π‘— π‘₯π‘₯𝑂𝑂 �⎯⎯⎯⎯� π‘ˆπ‘ˆπ‘‚π‘‚ Claims that π‘ˆπ‘ˆπ‘–π‘– signed (𝑒𝑒𝑖𝑖, 𝑠𝑠𝑖𝑖 ,𝑇𝑇′𝑖𝑖) for him. Figure 2: Insider forgery attack to the scheme of Wu and Xu 4. Modification of Wu and Xu’s self-certified digital signature scheme with message recovery This section represents a slight modification to overcome the security flaw in the scheme of Wu and Xu. Given the fact that the reason of insecurity of Wu and Xu’s scheme against insider forgery attack is that the verification equation cannot find the change in 𝑇𝑇𝑖𝑖 , it is sufficed to make a slight change in the equation 𝑑𝑑𝑖𝑖 = 𝐻𝐻(𝑀𝑀, 𝑒𝑒𝑖𝑖). With changing 𝑑𝑑𝑖𝑖 = 𝐻𝐻(𝑀𝑀, 𝑒𝑒𝑖𝑖) to 𝑑𝑑𝑖𝑖 = 𝐻𝐻(π‘€π‘€βˆ—, 𝑒𝑒𝑖𝑖) where π‘€π‘€βˆ— = 𝑀𝑀 βˆ₯ 𝑇𝑇𝑖𝑖 , the insider forgery attack is not successful against the modified scheme because any changes in term of 𝑇𝑇𝑖𝑖 would cause changes in the amount of π‘€π‘€βˆ— and 𝑑𝑑𝑖𝑖. The modified scheme has also four phases: system initialization phase, signature generation phase, message recovery phase, and dispute arbitration phase. The modified scheme is represented in Figure 3. 4.1. System initialization phase This phase is exactly the same as system initialization phase in Wu and Xu’s scheme. American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 28, No 1, pp 257-265 263 4.2. signature generation phase When π‘ˆπ‘ˆπ‘–π‘– wants to sign a message 𝑀𝑀 with the length π‘˜π‘˜ to the verifier π‘ˆπ‘ˆπ‘—π‘—, he chooses a number π‘˜π‘˜π‘–π‘– randomly and calculates the following variables: 𝑒𝑒𝑖𝑖 = π‘”π‘”π‘˜π‘˜π‘–π‘– π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 𝑅𝑅𝑖𝑖 = (𝑦𝑦𝑗𝑗𝐹𝐹�𝐼𝐼𝐷𝐷𝑗𝑗� + 𝐼𝐼𝐼𝐼𝑗𝑗)π‘˜π‘˜π‘–π‘– π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 𝑓𝑓𝑖𝑖 = 𝐹𝐹1(𝑀𝑀) βˆ₯ 𝐹𝐹2�𝐹𝐹1(𝑀𝑀)�⨁𝑀𝑀 𝑇𝑇𝑖𝑖 = 𝑅𝑅𝑖𝑖 βŠ• 𝑓𝑓𝑖𝑖 π‘€π‘€βˆ— = 𝑀𝑀 βˆ₯ 𝑇𝑇𝑖𝑖 𝑑𝑑𝑖𝑖 = 𝐻𝐻(π‘€π‘€βˆ—, 𝑒𝑒𝑖𝑖) 𝑠𝑠𝑖𝑖 = π‘˜π‘˜π‘–π‘– βˆ’ π‘₯π‘₯𝑖𝑖 . 𝑑𝑑𝑖𝑖 . 𝑓𝑓𝑖𝑖 Where β€œβ¨β€ denotes the exclusive-or operator, and β€œβˆ₯” denotes the concatenation operator. Then, π‘ˆπ‘ˆπ‘–π‘– sends (𝑒𝑒𝑖𝑖, 𝑠𝑠𝑖𝑖 ,𝑇𝑇𝑖𝑖) to π‘ˆπ‘ˆπ‘—π‘— as the signature of 𝑀𝑀. 4.3. Message recovery phase Upon receiving (𝑒𝑒𝑖𝑖 , 𝑠𝑠𝑖𝑖 ,𝑇𝑇𝑖𝑖), the verifier π‘ˆπ‘ˆπ‘—π‘— computes 𝑅𝑅𝑖𝑖 = 𝑒𝑒𝑖𝑖π‘₯π‘₯𝑗𝑗 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 ,and 𝑓𝑓𝑖𝑖 = 𝑅𝑅𝑖𝑖⨁𝑇𝑇𝑖𝑖 . Then, he can achieve the message 𝑀𝑀 = 𝐹𝐹2([𝑓𝑓𝑖𝑖]𝑙𝑙1)⨁[𝑓𝑓𝑖𝑖]𝑙𝑙2 , where [𝑓𝑓𝑖𝑖]𝑙𝑙1 is the left 𝑙𝑙1 bits of 𝑓𝑓𝑖𝑖, and [𝑓𝑓𝑖𝑖]𝑙𝑙2 is the right 𝑙𝑙2 bits of 𝑓𝑓𝑖𝑖. In order to check the validity of the signature, π‘ˆπ‘ˆπ‘—π‘— first computes π‘€π‘€βˆ— = 𝑀𝑀 βˆ₯ 𝑇𝑇𝑖𝑖 , and 𝑑𝑑𝑖𝑖 = 𝐻𝐻(π‘€π‘€βˆ—, 𝑒𝑒𝑖𝑖). Then, he checks whether the following equation holds or not. 𝑒𝑒𝑖𝑖 = 𝑔𝑔𝑠𝑠𝑖𝑖(𝑦𝑦𝑖𝑖𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖) + 𝐼𝐼𝐼𝐼𝑖𝑖)𝑑𝑑𝑖𝑖𝑓𝑓𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 If the above equation holds, he accepts the signature as a valid signature for 𝑀𝑀. Otherwise, he rejects the signature. If the signature is valid and signed by π‘ˆπ‘ˆπ‘–π‘–, then the above equation must hold because 𝑔𝑔𝑠𝑠𝑖𝑖(𝑦𝑦𝑖𝑖𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖) + 𝐼𝐼𝐼𝐼𝑖𝑖)𝑑𝑑𝑖𝑖𝑓𝑓𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 = 𝑔𝑔𝑠𝑠𝑖𝑖(𝑔𝑔π‘₯π‘₯𝑖𝑖)𝑑𝑑𝑖𝑖𝑓𝑓𝑖𝑖 = 𝑔𝑔𝑠𝑠𝑖𝑖 .π‘”π‘”π‘˜π‘˜π‘–π‘–βˆ’π‘ π‘ π‘–π‘– = π‘”π‘”π‘˜π‘˜π‘–π‘– π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 , and as mentioned in signature generation phase π‘”π‘”π‘˜π‘˜π‘–π‘– = 𝑒𝑒𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘šπ‘›π‘›. 4.4. Dispute arbitration phase In case of any dispute over the validity of the signature, π‘ˆπ‘ˆπ‘—π‘— can publish (𝑀𝑀, 𝑑𝑑𝑖𝑖, 𝑒𝑒𝑖𝑖), and anyone can confirm the American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 28, No 1, pp 257-265 264 validity of the signature by the following equation: 𝑑𝑑𝑖𝑖 = 𝐻𝐻(π‘€π‘€βˆ—, 𝑒𝑒𝑖𝑖) phase 𝑆𝑆𝑆𝑆 π‘ˆπ‘ˆπ‘–π‘– π‘ˆπ‘ˆπ‘—π‘— System initialization phase Computes 𝑦𝑦𝑖𝑖 = (𝑝𝑝𝑖𝑖 βˆ’ 𝐼𝐼𝐼𝐼𝑖𝑖)𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖)βˆ’1π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 , and publicize 𝑦𝑦𝑖𝑖 . Chooses π‘₯π‘₯𝑖𝑖 randomly and computes 𝑝𝑝𝑖𝑖 = 𝑔𝑔π‘₯π‘₯𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘šπ‘›π‘›. Submits (𝑝𝑝𝑖𝑖 , 𝐼𝐼𝐼𝐼𝑖𝑖) to the 𝑆𝑆𝑆𝑆. Signature generation phase Computes 𝑒𝑒𝑖𝑖 = π‘”π‘”π‘˜π‘˜π‘–π‘– π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, 𝑅𝑅𝑖𝑖 = (𝑦𝑦𝑗𝑗𝐹𝐹�𝐼𝐼𝐷𝐷𝑗𝑗� + 𝐼𝐼𝐼𝐼𝑗𝑗)π‘˜π‘˜π‘–π‘–π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, 𝑓𝑓𝑖𝑖 = 𝐹𝐹1(𝑀𝑀) βˆ₯ 𝐹𝐹2�𝐹𝐹1(𝑀𝑀)�⨁𝑀𝑀, and 𝑇𝑇𝑖𝑖 = 𝑅𝑅𝑖𝑖 βŠ• 𝑓𝑓𝑖𝑖 Then, Computes π‘€π‘€βˆ— = 𝑀𝑀 βˆ₯ 𝑇𝑇𝑖𝑖 , 𝑑𝑑𝑖𝑖 = 𝐻𝐻(π‘€π‘€βˆ—, 𝑒𝑒𝑖𝑖) 𝑠𝑠𝑖𝑖 = π‘˜π‘˜π‘–π‘– βˆ’ π‘₯π‘₯𝑖𝑖 . 𝑑𝑑𝑖𝑖. 𝑓𝑓𝑖𝑖 π‘ˆπ‘ˆπ‘–π‘– sends (𝑒𝑒𝑖𝑖, 𝑠𝑠𝑖𝑖 ,𝑇𝑇𝑖𝑖) to π‘ˆπ‘ˆπ‘—π‘— Message recovery phase Calculates 𝑅𝑅𝑖𝑖 = 𝑒𝑒𝑖𝑖π‘₯π‘₯𝑗𝑗 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛, 𝑓𝑓𝑖𝑖 = 𝑅𝑅𝑖𝑖⨁𝑇𝑇𝑖𝑖 , and obtains 𝑀𝑀 = 𝐹𝐹2([𝑓𝑓𝑖𝑖]𝑙𝑙1)⨁[𝑓𝑓𝑖𝑖]𝑙𝑙2 . Computes π‘€π‘€βˆ— = 𝑀𝑀 βˆ₯ 𝑇𝑇𝑖𝑖 , 𝑑𝑑𝑖𝑖 = 𝐻𝐻(π‘€π‘€βˆ—, 𝑒𝑒𝑖𝑖). Then, checks whether 𝑒𝑒𝑖𝑖 = 𝑔𝑔𝑠𝑠𝑖𝑖(𝑦𝑦𝑖𝑖𝐹𝐹(𝐼𝐼𝐷𝐷𝑖𝑖) + 𝐼𝐼𝐼𝐼𝑖𝑖)𝑑𝑑𝑖𝑖𝑓𝑓𝑖𝑖 π‘šπ‘šπ‘šπ‘šπ‘šπ‘š 𝑛𝑛 Figure 3: Modification of an improved self-certified digital signature scheme with message recovery 5. Conclusion In the present paper an improved self-certified digital signature scheme with message recovery is reviewed. A security analysis for the scheme is presented by proposing an insider forgery attack against this scheme, and it is demonstrated that this scheme cannot withstand the attack. It is also argued that in modern electronic environments, the aforementioned attack can cause negative consequences, particularly in electronic commerce and electronic voting systems. A slight improvement for the scheme is suggested in order to remove the weakness. The propose modification is secure against insider forgery attack. Acknowledgement The author would like to thank the anonymous reviewers for their comments. American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 28, No 1, pp 257-265 265 References [1] M. Girault, β€œSelf-certified public-keys”, Advances in Cryptology β€”EUROCRYPT’91, Berlin: Springer, 1991, pp. 491-497. 
 [2] K. Neyberg and R. Ruppel, β€œMessage recovery for signature schemes based on the discrete logarithm problem”, Advances in CryptologyErocryt’94, LNCS 950, Berlin: Springer, 1994, pp. 175-190. 
 [3] P. Horster and M. Michels and H. Petersen, (1994, Jul.), β€œAuthenticated encryption schemes with low communication costs.”, Electronic Letters, [On-line], 30(15), pp. 1212-1213. Available: http://ieeexplore.ieee.org/document/311896 [Aug. 2, 2002]. [4] Y.-M. Tseng and J.-K. Jan and H.-Y. Chien, (2003, Mar.), β€œDigital signature with message recovery using self- 
certified public keys and its variant.”, Applied Mathematics and Computation, [On-line], 136(2-3), pp.203-214. Available: http://www.sciencedirect.com/science/article/pii/S0096300302000103 . [5] Z. Shao, β€œImprovement of digital signature with message recovery using self-certified public keys and 
 its variants”, Applied Mathematics and Computation, vol. 159, pp.391-399, Dec. 2004. [6] Y.-H. Chen and J.-K. Jan, β€œAn authenticated encryption scheme for securely signing a signature with message linkages”, International Conference on Innovative Computing, Information and Control, in Proc ICICIC, 2007, pp. 77-80. 
 [7] Y.F. Chang, C.C. Chang, F.F. Huang, (2005, Feb.). β€œDigital signature with message recovery using self-certified public keys without trustworthy system authority.” Applied Mathematics and Computation. [On-line]. 161(1), pp. 211–227. Available: http://www.sciencedirect.com/science/article/pii/S0096300303012220. [8] E.J. Yoon and K.Y. Yoo, β€œAn improved digital signature with message recovery using self-certified public keys without trustworthy system authority”, Theory and Practice of Computer Science, Czech Republic: Merin, 2006, pp. 548–555. 
 [9] F. Wu, L. Xu, (2013, Sep.). β€œAn improved and provable self-certified digital signature scheme with message recovery”, International Journal of Communication Systems. [On-line]. 28(2), pp. 344-357. Available: http://onlinelibrary.wiley.com/wol1/doi/10.1002/dac.2673/full . http://ieeexplore.ieee.org/document/311896 http://www.sciencedirect.com/science/article/pii/S0096300302000103 http://www.sciencedirect.com/science/article/pii/S0096300303012220 http://onlinelibrary.wiley.com/wol1/doi/10.1002/dac.2673/full Abstract 2.1. System initialization phase Where ,𝒍-𝑡. is of the length of 𝑡 in binary, and ,𝒍-𝑡.=,𝒍-𝟏.+,𝒍-𝟐.. The scheme can deal with π‘΄βˆˆ,{𝟎,𝟏}-,𝒍-𝟐... In this scheme, π’Œ=,,π₯𝐨𝐠-(𝑷)..,and 𝑷=,𝐦𝐒𝐧-(,𝒑-β€²., ,𝒒-β€².).. 2.2. Signature generation phase At last, ,𝑼-π’Š. sends (,𝒆-π’Š., ,𝒔-π’Š., ,𝑻-π’Š.) to ,𝑼-𝒋. as the signature of 𝑴. 2.3. Message recovery phase After receiving ,,𝒆-π’Š., ,𝒔-π’Š., ,𝑻-π’Š.., the verifier ,𝑼-𝒋. computes ,𝑹-π’Š.=,,𝒆-π’Š.-,𝒙-𝒋.. π’Žπ’π’… 𝒏, and calculates ,𝒇-π’Š.=,𝑹-π’Š.⨁,𝑻-π’Š.. Then, he can achieve the message 𝑴 by the following equation 2.4. Signature conversation phase 4.1. System initialization phase This phase is exactly the same as system initialization phase in Wu and Xu’s scheme. 4.2. signature generation phase 4.3. Message recovery phase 4.4. Dispute arbitration phase Acknowledgement References