1 Introduction

The rise of public-key cryptography tackled the issue of secure key agreement in routine symmetric key cryptography (Diffie and Hellman 1976; Wang et al. 2015; Wei et al. 2014). Moreover, it makes possible the creation of more advanced digital signature schemes. With the help of the innovations in public-key cryptography, electronic commerce of various kinds over open systems has become more and more conceivable and workable (Chang et al. 2009; He et al. 2013, 2015, 2016a, b; Hu et al. 2015, 2016; Jing et al. 2014; Liu et al. 2006, 2014a; Yao et al. 2015). In a typical public-key cryptographic scheme, each entity has a key couple, namely a secret key and a public key. Public keys are generally kept collectively in an open document such as a public-key manual, which is huge in size and yet fully exposed. A gatecrasher can simply trace an entity by replacing his/her public key with a fake key, unless there is a secure key authentication scheme to help watch the door. So far, quite a number of key authentication schemes have been developed and presented. For the most part, in the designs of these schemes there is at least one authority, which is usually referred to as a key authentication center (KAC) or a trusted center (TC). The authority must be solid and strong against any sort of inside or outside attack because it is what the security of whole framework relies on.

Girault (1991) did an extensive survey into a wide range of key authentication schemes and observed that in those schemes the control of the authority over the secret keys fell into one of the three scenarios: (1) KAC has total control over an entity’s secrete key; (2) KAC does not have access to an entity’s secrete key, but it can create a false certificate undetected; (3) KAC does not have access to an entity’s secrete key, and it can be demonstrated that the KAC produced a false certificate if it did. Girault then classified key authentication schemes into three levels of trust: (a) ID-based schemes (Shamir 1985; b) certificate-based schemes; (c) self-certified public-key schemes. Of course Girault offered his own model of self-certified public-key design. Later, to improve Girault’s model, Laih et al. (1994) presented a scheme that was a hybrid of an ID-based scheme and a certificate-based scheme.

In 1996, Horng and Yang (1996) presented a key authentication scheme for cryptosystems based on discrete logarithms. Horng and Yang’s technique is similar to common certificate-based designs, but it requires no authorities. The certificate of the public key of an entity is created by combining her/his password and secrete key. The hash value of her/his password is handed over to the server and put away in the server’s confirmation table. In 1999, pointing out that Horng and Yang’s scheme was vulnerable to the password guessing attack, Zhan et al. (1999) presented their enhanced model. In addition, Lee and Wu (2001) also presented another upgraded scheme to guard against the password guessing attack. In 2003, Lee et al. (2003) claimed that the Zhan et al. key authentication scheme had an issue of non-repudiation of an entity’s public key. Lee et al. then presented an improved key authentication scheme. Later on, Peinado (2004), Wu and Lin (2004), as well as Zhang and Kim (2005) separately showed that Lee et al.’s work had some security flaws and that anyone could derive the secrete key of an entity from public messages.

Now, since the new key authentication schemes for cryptosystems are still facing security difficulties and confidentiality concerns, in this paper, we shall present a new key authentication scheme for cryptosystems in the hope of mending the safety flaws of the current schemes. Functioning in the absence of any authority, the security of our new scheme is based on generalized discrete logarithm problem (GDLP) and integer factorization problem (IFP) (Meshram et al. 2012a, b). In other words, any attacker that attempts to break our new system is facing the difficulty of solving GDLP and IFP at the same time in the same multiplicative group over finite fields.

The rest of this paper is organized as follows. In Sect. 2, we shall briefly introduce some background materials upon which our new scheme is built. Then, in Sect. 3, we shall present the proposed key authentication scheme based on GDLP and IFP. After that, in Sect. 4, we will offer our security analysis and discussions. Then, Sect. 5 will show how our new scheme compares with some similar authentication schemes. Finally, the conclusion will be in Sect. 6.

2 Background materials

2.1 Password authentication procedure

In a password authentication scheme for multiuser computing systems, an entity needs to not only register with various systems, respectively, but also keep track of the various passwords that are purposely set to be different to achieve high-level security. A password is a series of characters expected to be distinguishable just to the system and the entity. When an entity needs to login to the system, he/she first enters his/her identity (ID) to help the system recognize the person and then provides his/her password (pwd) as a reaction to the system’s demand. Then, the system confirms the pair of (ID, pwd) to see whether the entity is authorized. The system keeps all authorized pairs of (ID, pwd) in a table for authorization verification. However, the system would become extremely insecure should the verification table kept in the system be in plaintext, for an adversary could then easily access the table. Therefore, to keep legal passwords safe from the snooping of possible attackers, a cryptographic solution is recommended (Evans et al. 1974). By using a one-way function \(h\left( . \right) \) (Khan and Kumari 2013, 2014; Yang et al. 2014; Zhou et al. 2015), passwords can be mapped to pictures, and the verification table can then be a table of the mapping results instead of one of the real passwords.

Based on GDLP and IFP, we choose an integer \(N=p\times q\) and a primitive component \(e\left( {\hbox {mod}\, N} \right) \), where q and p are two huge primes, and then we can use the capacity \(e^{\mathrm{pwd}}\left( {\hbox {mod}\, N} \right) \) as a picture for an entity’s password pwd. Such pictures can then be put away in a generally open password table without leaking out any message about the passwords.

2.2 Public-key cryptosystem using GDLP and IFP

There are many public-key cryptosystems using GDLP and IFP (Meshram and Meshram 2011; Meshram and Powar 2016; Meshram et al. 2012a, b; Meshram and Obaidat 2015). In such schemes, there is an integer \(N=p\times q\), where q and p are two huge primes, and there is also a primitive component \(e\left( {\hbox {mod}\, N} \right) \) shared among a group of entities. Each entity arbitrarily chooses an integer \(x<N\) and then calculates

$$\begin{aligned} y\equiv e^{x}\left( {\hbox {mod}\, N} \right) \end{aligned}$$

Here, the public key and the corresponding secrete key of the entity are y and x, respectively.

Let’s take an example and see how Meshram’s et al.’s (2012b) scheme works. To sign a message M, we can compute

$$\begin{aligned} r\equiv e^{k}( {\hbox {mod}\, N} ), \end{aligned}$$

where k is an arbitrarily picked integer moderately prime to \(\varphi \left( N \right) \). Here \(\varphi \left( N \right) =\left( {p-1} \right) \left( {q-1} \right) \) (Hwang et al. 2013; Yang et al. 2013). Then we can unravel for s in the accompanying mathematical statement:

$$\begin{aligned} M\equiv xr+ks \, \hbox {mod}\, \varphi \left( N \right) \end{aligned}$$

The signature for M is the couple \(\left( {r,s} \right) \). To check a signature, we affirm that

$$\begin{aligned} e^{M}\left( {\hbox {mod}\, N} \right) =y^{r}r^{s}( {\hbox {mod}\, N}). \end{aligned}$$

To encrypt a message M, we can select a random number b and compute

$$\begin{aligned} y_1= & {} e^{b} \hbox { mod } \varphi ( N ),\\ C_0= & {} M^{y_1 }\, ( {\hbox {mod}\, N} ), \end{aligned}$$

where k is an arbitrarily picked integer moderately prime to \(\varphi \left( N \right) \).

Then we calculate the ciphertext

$$\begin{aligned} C=C_0^e ( {\hbox {mod}\, N} ). \end{aligned}$$

To decrypt the ciphertext C, we can compute

$$\begin{aligned} \gamma =C^{d}\left( {\hbox {mod}\, N} \right) \end{aligned}$$

and recuperate the plaintext M by processing

$$\begin{aligned} \gamma ^{d^{b}}( {\hbox {mod}\, N} ). \end{aligned}$$

DSA is proposed by the US National Institute of Standards and Technology. It is a variant of the signature scheme based on GDLP and IFP and is depicted in Meshram et al. (2012b).

3 The proposed scheme

In this section, we present the first public-key authentication scheme for cryptosystems based on GDLP and IFP. Suppose an entity i, whose password is \(\hbox {pwd}_i \), produced an integer \(\hbox {sk}_i \) as his/her secrete key and computed his/her public key \(\hbox {pk}_i \) as

$$\begin{aligned} \hbox {pk}_i \equiv h\left( {\hbox {sk}_i } \right) \equiv e^{\hbox {sk}_i }( {\hbox {mod}\, N} ). \end{aligned}$$

The notations used in the proposed scheme are defined in Table 1.

Table 1 Notations used in the proposed scheme
Full size table

3.1 Registration phase

This scheme depends on the accompanying suppositions:

  1. 1.

    The password authentication procedure of the system uses a one-way exponentiation function \(h:Z_N^*\rightarrow Z_N^*\) defined by \(h\left( x \right) =e^{x}\left( {\hbox {mod}\, N} \right) \) with respect to basis e and modulus N. By continual squaring, it is easy to calculate \(h\left( b \right) \) for any given \(b\in Z_N^*\), where \(Z_N^*=\left( {0,1,\ldots ,N-1} \right) \) is a multiple cyclic group of order N. Let N be an integer that satisfies \(=p\times q\), where q and p are huge primes. Its Euler function is given by \(\varphi \left( N \right) =\left( {p-1} \right) \left( {q-1} \right) \). Choose an arbitrary integer \(e,1\le e\le \varphi \left( N \right) \) s.t. \(gcd\left( {e,\varphi \left( N \right) } \right) =1\). It is also a primitive element \((\hbox {mod}\, N)\). Then, pick a distinct integer \(d,1\le d\le \varphi \left( N \right) \) s.t. \(ed\equiv 1\left( {\hbox {mod} \,\varphi \left( N \right) } \right) \). Then \(h\left( . \right) \) goes public to all entities.

  2. 2.

    By successfully applying the one-way exponentiation function, the picture of i’s password \(\hbox {pwd}_i \) is kept in the password table as \(h\left( {\hbox {pwd}_i \oplus \hbox {sk}_i } \right) \), where \(\oplus \) is an excusive-or operation and \(\hbox {sk}_i \) is also used against password guessing attacks.

  3. 3.

    Furthermore, to save on the consumption of the storage space for the system password table, a public hash function \(H_N \left( {.} \right) \) can be utilized to hash the aftereffect of \(h\left( . \right) \) of a password. Then, the picture \(H_N \left( {h\left( {\hbox {pwd}_i \oplus \hbox {sk}_i } \right) } \right) \) of the password \(\hbox {pwd}_i \) is stored in the password table.

  4. 4.

    The password table can now be directly open to all entities, as the passwords are already under proper protection.

  5. 5.

    The one-way function \(h\left( . \right) \) is the same exponentiation function used by the cryptosystem based on GDLP and IFP.

3.1.1 Certificate generation phase

The certificate of the public key is produced by the entity, not by means of a TC or a KAC. Now entity i can process the certificate \(C_i \) of his/her public key by pairing up his/her password \(\hbox {pwd}_i \) and his/her secrete key \(\hbox {sk}_i \) such that

$$\begin{aligned} C_i \equiv \left( {\hbox {pwd}_i \oplus \hbox {sk}_i +\hbox {sk}_i \, \hbox {pk}_i } \right) \left( {\hbox {mod} \, \varphi \left( N \right) } \right) \end{aligned}$$

The certificate \(C_i \) and \(\hbox {pk}_i \) are open to public in the network.

3.2 Authentication phase

Each entity presents three items for authentication: the public key, the encrypted password, and a certificate.

3.2.1 Key verification phase

The password image is given by

$$\begin{aligned} h\left( {C_i } \right)\equiv & {} {e}^{\left( {\hbox {pwd}_i \oplus \hbox {sk}_i +\hbox {sk}_i \hbox {pk}_i } \right) \left( {\hbox {mod} \,\varphi \left( N \right) } \right) }\left( {\hbox {mod}\, N} \right) \\\equiv & {} {e}^{\left( {\hbox {pwd}_i \oplus \hbox {sk}_i } \right) }{e}^{\left( {\hbox {sk}_i \hbox {pk}_i } \right) }\left( {\hbox {mod}\, N} \right) \\\equiv & {} \left( {e^{\left( {\hbox {pwd}_i \oplus \hbox {sk}_i } \right) }\left( {\hbox {mod}\, N} \right) } \right) \left( {{e}^{\left( {\hbox {sk}_i \hbox {pk}_i } \right) }\left( {\hbox {mod}\, N} \right) } \right) \left( {\hbox {mod}\, N} \right) \\\equiv & {} h(\hbox {pwd}_i \oplus \hbox {sk}_i )\hbox {pk}_i ^{\hbox {pk}_i }\left( {\hbox {mod}\, N} \right) \end{aligned}$$

Should the password picture get hashed, then we have

$$\begin{aligned} H_N (h(\hbox {pwd}_i \oplus \hbox {sk}_i ))\equiv H_N \left( h\left( {C_i } \right) /\hbox {pk}_i ^{{\mathrm{pk}}_i }\right) \end{aligned}$$

when another entity j somehow needs to use entity i’s public key, he/she first asks entity i for \(\hbox {pk}_i \) and \(C_i \) or gets them from the network, and then he/she gets i’s password picture \(h(\hbox {pwd}_i \oplus \hbox {sk}_i )\) or \(H_{N}(h(\hbox {pwd}_{i}\oplus {sk}_{i}))\). directly from the password table. Now, entity j can check the validity of entity i’s public key by means of either of the following equations

$$\begin{aligned} h(\hbox {pwd}_i \oplus \hbox {sk}_i )\equiv h\left( {C_i } \right) /\hbox {pk}_i ^{{\mathrm{pk}}_i } \end{aligned}$$

or

$$\begin{aligned} H_N (h(\hbox {pwd}_i \oplus \hbox {sk}_i ))\equiv H_N \left( h\left( {C_i } \right) /\hbox {pk}_i ^{{\mathrm{pk}}_i }\right) \end{aligned}$$

If the equation holds, entity j acknowledges the public key and goes on to encrypt the messages.

4 Security analysis and discussions

When we say that the image of entity i’s password \(h(\hbox {pwd}_i \oplus \hbox {sk}_i )\) is protected by the system, we mean that it cannot be altered illicitly. What an intruder can do, then, is try to fashion the public key, speculate the password, or deduce the secrete key.

Theorem 4.1

The presented key authentication scheme can withstand the public-key forgery attack.

Proof

Assume that an attacker tries to replace entity i’s public key with a wrong key \(k_{f} \). To make \(k_{f} \) certified as an actual public key, the attacker has to also come by a fake certificate \(C_{\mathrm{f}} \) so that

$$\begin{aligned} h\left( {C_{\mathrm{f}} } \right) \equiv h\left( \hbox {pwd}_i \oplus \hbox {sk}_i \right) k_{f} ^{k_f } \end{aligned}$$

or

$$\begin{aligned} H_N (h(\hbox {pwd}_i \oplus \hbox {sk}_i ))\equiv H_N \left( h\left( {C_{\mathrm{f}} } \right) /k_{f} ^{k_f }\right) \end{aligned}$$

To recover \(C_{\mathrm{f}} \), the intruder needs to calculate

$$\begin{aligned} C_{\mathrm{f}}\equiv & {} h^{-1}\left( {h(\hbox {pwd}_i \oplus \hbox {sk}_i } \right) )+h^{-1}\left( {k_{f} ^{k_{f} }} \right) \left( {\hbox {mod}\, \varphi \left( N \right) } \right) {,} \end{aligned}$$
(1)
$$\begin{aligned} C_{\mathrm{f}}\equiv & {} h^{-1}\left( {h(\hbox {pwd}_i \oplus \hbox {sk}_i } \right) k_{f} ^{k_{f} })\left( {\hbox {mod}\, \varphi \left( N \right) } \right) {,} \quad \hbox {or} \end{aligned}$$
(2)
$$\begin{aligned} C_{\mathrm{f}}\equiv & {} h^{-1}\left( {H_N ^{-1}(H_N \left( {h(\hbox {pwd}_i \oplus \hbox {sk}_i } \right) ))k_{f} ^{k_{f} }} \right) ( {\hbox {mod}\, \varphi ( N )} ),\nonumber \\ \end{aligned}$$
(3)

where only \(h^{-1}(k_{f} ^{k_{f} })\) is controllable by the attacker. Since the attacker cannot change \(h(\hbox {pwd}_i \oplus \hbox {sk}_i )\) or \(H_N \left( {h(\hbox {pwd}_i \oplus \hbox {sk}_i } \right) \) in the password table, without knowing the entity i’s password in both Eqs. (1) and (2), the attacker needs to solve both GDLP and IFP simultaneously in multiple cyclic groups. Meanwhile, in Eq. (3), the attacker will get trapped by the trouble of having to turn the hash function around. Hence it is clear that forging somebody’s public key is not what is going to work for the attacker.

A model of public-key forgery attack has been posted on Horng and Yang (1996), Lee and Wu (2001), Zhan et al. (1999) in Lee et al. (2003). Although it is an ingenious model, it still will not work on cracking our key authentication scheme. Suppose a malicious yet legal entity l uses his/her secrete key \(\hbox {sk}_l \) to sign a record. Generally, the signature will be certified by utilizing l’s public key \(\hbox {pk}_l \). However, later the signer, namely l may deny signing the record and provide a fake certificate \(C_\mathrm{f} \) instead of his/her genuine certificate \(C_l \) to infer that the public key was wrong in the first place as follows:

  1. 1.

    Calculate \(k_{f} ^{k_{f} }\equiv h\left( {C_{\mathrm{f}} } \right) h\left( {\hbox {pwd}_l \oplus \hbox {sk}_l } \right) \left( {\hbox {mod}\, N} \right) \); and

  2. 2.

    Attempt to find \(k_{f} \) from \(k_{f} ^{k_{f} }\left( {\hbox {mod}\, N} \right) \).

However, solving the overhead \(K_{f} \) is actually harder than solving GDLP and IFP (Agnew et al. 1990).\(\square \)

Theorem 4.2

The proposed key authentication scheme is strong against the password guessing attack by a malicious server.

Proof

The servers tend to be highly trustworthy in some certain closed network environments, for example, inside of an enterprise where all servers are run by the same administrator(s). In such cases, it is not very likely that any server will launch a guessing attack, meaning that the public password table can be considered secure from illegal amendment. However, if an attacker should strike at the server end, for finding \(h(\hbox {pwd}_i \oplus \hbox {sk}_i )\), the attacker would have to guess the password \(\hbox {pwd}_i \). Clearly, it is computationally infeasible to guess \(\hbox {pwd}_i \) because the attacker must simultaneously guess \(\hbox {pwd}_i \) and the secrete key \(\hbox {sk}_i \).

On the other hand, an attacker could derive the password from the certificate \(C_i \equiv \left( {\hbox {pwd}_i \oplus \hbox {sk}_i +\hbox {sk}_i \hbox {pk}_i } \right) \left( {\hbox {mod}\, \varphi \left( N \right) } \right) \) at the entity end, but then he/she would still fail to guess the password and the secrete key. \(\square \)

Theorem 4.3

The proposed key authentication scheme can keep the secret key from leaking out through an intercepted certificate.

Proof

In case an entity i’s password is somehow compromised, the adversary may attempt to recover i’s secrete key from \(h(\hbox {pwd}_i \oplus \hbox {sk}_i )\), which is stored in the server. This means the adversary will have to solve GDLP and IFP simultaneously in multiple cyclic groups.

On the other hand, the adversary may decide to take another route and try to deduce the secret key from the certificate \(C_i \equiv \left( {\hbox {pwd}_i \oplus \hbox {sk}_i +\hbox {sk}_i\, \hbox {pk}_i } \right) \left( {\hbox {mod}\, \varphi \left( N \right) } \right) \). The adversary first assumes \(C_i \equiv a+c\hbox {mod}\, \varphi \left( N \right) \), where \(a\equiv \hbox {pwd}_i \oplus \hbox {sk}_i \) and \(c\equiv \hbox {sk}_i\, \hbox {pk}_i \), and then tries to find all possible couples \(\left( {a,c} \right) \) that satisfy \(C_i \equiv a+c\hbox {mod}\, \varphi \left( N \right) \).

For each couple, the adversary takes the following steps to find the secrete key.

  1. 1.

    XOR the compromised \(\hbox {pwd}_i \) with a to find \(\hbox {sk}_i^{\prime } \). On the off chance \(\hbox {sk}_i^{\prime } \hbox {pk}_i^{\prime } \) should be identical to c, then he/she goes to the next step; otherwise, the adversary will have to repeat this first step and try the next couple, and this goes on and on until there is a hit.

  2. 2.

    Confirm if \(h\left( {\hbox {sk}_i^{\prime } } \right) \) is identical to \(\hbox {pk}_i \). If yes, the adversary succeeds in finding the secrete key. Please notice that possible candidates for a include all the numbers from 1 to \(\varphi \left( N \right) \); in other words, there can be a total of \(\varphi \left( N \right) \) trial-and-error tests required. Given that the integer N is sufficiently extensive, it is computational infeasible to deduce the secrete key from \(C_i \).

In regular key authentication schemes based on certificates or self-certified public keys, if all authorities work as a unity in a bad way, it is still possible for the system to become insecure. In the design of our new key authentication scheme, since there are no such things as authorities, there certainly is zero chance for malicious collaboration among certification authorities to happen. In other words, our new scheme achieves the third and top security level defined by Girault (1991).

In an identity-based authentication scheme, the public key is right the entity’s ID. Distinctively, in our new key authentication scheme, an entity is free to change his/her password and secret key. When an entity changes his/her password and(or) public/secrete key, the three associated pieces of data can be effortlessly simplified: the entity’s password picture in the system password table is to be simplified by the system, while the public key and its certificate can be simplified by the entity himself/herself. In addition, an entity can easily perform the authentication phase by himself/herself. Moreover, our new scheme can be executed using the self-certified public keys if the password image cannot be developed by using the hash function \(H_N \left( {.} \right) \).

For example, in our authentication scheme, entity i’s public key \(\hbox {pk}_i \) can be computed by

$$\begin{aligned} \hbox {pk}_i \equiv h\left( {C_i } \right) /h( {\hbox {pwd}_i \oplus \hbox {sk}_i } ), \end{aligned}$$

where \(C_i \) can be regarded as the self-certified public key and \(h\left( {\hbox {pwd}_i \oplus \hbox {sk}_i } \right) \) is obtained from the password table. In this technique, the size of the system password table will go up. To deal with that, the original public keys can now be removed from the public file because we do not need them there anymore. By doing that, we can save half of the original space, since only the self-certified public keys, or certificates, remain in the file. As Girault has mentioned in his discussion on schemes using self-certified public keys, the public file can be removed if we do not require the cryptographic scheme to be non-interactive, since in our design an entity can ask another entity for his/her self-certified public key, and the key itself is a certificate. As a result, the storage space consumed for this part is equivalent to that of an identity-based scheme.\(\square \)

Table 2 Computation cost in registration phase and authentication phase
Full size table
Fig. 1
figure 1

Total computational cost in both registration phase and authentication phase

Full size image

5 Comparisons with other schemes

In this section, we shall demonstrate that our new key authentication scheme can run smoothly at a very low computation cost and that it supports all the functions an ideal key authentication scheme is supposed to serve. To see how our new scheme compares with some related schemes (Hsieh and Leu 2012; Kumaraswamy et al. 2015; Lee et al. 2003; Liu et al. 2014b; Peinado 2004; Wu and Lin 2004; Zhang and Kim 2005) in terms of computation cost, please check out Table 2 and Fig. 1.

Here are the definitions of some notations we use in Table 2:

  • \(t_{\mathrm{inv}}\): Time for executing a modular inverse computation

  • \(t_{\mathrm{exp}}\): Time for executing a modular exponentiation computation

  • \(t_{\mathrm{mul}}\): Time for executing a modular multiplication computation

  • \(t_{\mathrm{add}}\): Time for executing a modular addition computation

  • \(t_{\mathrm{h}}\): Time for executing a one-way hash function computation

  • \(t_{\mathrm{XOR}}\): Time for executing a XOR function computation.

As Table 2 and Fig. 1 suggest, our new scheme runs at the lowest computation cost of them all. This means our new scheme is at the highest level of efficiency.

6 Conclusion

Key authentication schemes have come a long way, and yet the public key authentication problem has always stayed a major challenge. In this study, we try building up the strength of security on the basis of GDLP and IFP in a design where no authorities are included. In our key authentication scheme for cryptosystems, the certificate is controlled by the entity, while the authentication procedure relies on the password table at the system end. Such a design can indeed lift the level of trust of our new key authentication scheme to be significantly higher than that of self-certified schemes.