# The Proposed Signcryption Schemes Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Two signcryption schemes are proposed and implemented here in this work, which provide the security functions such as message confidentiality, senders authenticity, message integrity, non-repudiation, forward secrecy and public verification, with a cost less than or comparable with the existing schemes. Both of them are based on elliptic curve cryptosystem. The schemes spend lower time in computation, especially for receiver and contain four phases: initialization phase, signcryption phase, unsigncryption phase and judge verification phase.

In the Initialization Phase, system generates and publishes domain parameters of elliptic curve, and each user generates his own private key and the related public key. Each user should get the certification of his public key from the certificate authority (CA) [4, 8]. In Signcryption Phase, Alice generates digital signature (T, s) of message m and uses the symmetric encryption algorithm and secret key k to encrypt m. Alice generates the signcrypted text (c, T, s) and sends it to Bob. In Unsigncryption Phase, Bob receives the signcrypted text (c, T, s). He decrypts cipher text 'c' by performing symmetric decryption algorithm with secret key k. He also verifies the signature. In Judge Verification Phase the verificationof the signcrypted message is done by a firewall or judge.

## 4.1.1 Algorithm of ESS-I

In the algorithm of ESS-I we describe these four phases:

## Initialization phase:

In this phase, some public parameters are generated. The steps are as follows:

Chapter 4 The proposed signcryption schemes

q : A large prime number, where q is greater than 2160 [15].

a, b: Two integer elements which are smaller than q and satisfy the following condition

4a3 + 27b2 mod q â‰ 0

F : The selected elliptic curve over finite field q:

y2 = x3 + ax + b mod q,

G : A base point of elliptic curve F with order n,

O : A point of F at infinite,

n : The order of point G, where n is a prime, n X G = O and n â‰¥ 2160. (The symbol " X " denotes the elliptic curve point multiplication,)

H : A one-way hash function,

Ek() / Dk() : Symmetric encryption/decryption algorithm with private key k such as DES or AES.

The sender Alice randomly selects an integer va as her private key and va â‰¤ n-1. She computes her public key Pa = vaG. The recipient Bob also selects private key vb and public key Pb = vbG by the same way as Alice. They need to get a certificate of their public key from the certificate authority (CA).

## Signcryption Phase:

Assume that Alice wants to send a message m to Bob. Alice generates digital signature (T, s) of message m and uses the symmetric encryption algorithm and secret key k to encrypt m. Let c be the cipher text. Alice generates the signcrypted text (c, T, s) in the following steps.

Step 1: Verifies Bob's public key Pb by using his certificate. Step 2: Randomly selects an integer v, where v â‰¤ n - 1.

Step 3: Computes k1 = hash(vG).

Step 4: Computes (k2, k3) = hash(vPb).

Step 5:Uses the symmetric encryption algorithm to generate cipher

c = Ek2 (m)

where the secret k2 is generated in Step 4.

Step 6: Uses one-way keyed hash function to generate:

r = KHk3 (c || k1 || IDA || IDB)

Chapter 4 The proposed signcryption schemes

IDA and IDB are the identifications given by the certificate authority (CA).

Step 7: Computes s = v / (r + va) mod q

Step 8: Compute T = rG.

Step 9: Sends the signcrypted text (c, T, s) to Bob.

## Unsigncryption phase:

Bob receives the signcrypted text (c, T, s). He decrypts cipher text 'c' by performing symmetric decryption algorithm with secret key k. He also verifies the signature. Bob gets the plain text as follows.

Step 1: Verifies Alice's public key Pa by using her certificate.

Step 2: Computes k1 = hash(sT + sPa).

Step 3: Computes (k2, k3) = hash(vbsT + vbsPa).

Step 4: Uses the one-way keyed hash function to generate

r = KHk3 (c || k1 || IDA || IDB)

where IDA and IDB are the identifications given by the certification authority(CA).

Step 5: Uses a symmetric decryption algorithm to generate plain text

m = Dk2 (c)

where the secret key k2 is computed in Step 3.

Step 6: Bob accepts the message 'm' only when rG = T .Otherwise he rejects.

Judge Verification of the signcrypted message by a firewall or judge. Bob only provides signcrypted text (c, T, s) to the judge. The judge performs the following steps:

Step 1: Computes k1 = hash (sT+sPa).

Step 2: Computes r = KHk3 (c || k1 || IDA || IDB)

Step 3: If rG = T, then the signcrypted text (c, T, s) is sent by the sender Alice otherwise not.

Chapter 4 The proposed signcryption schemes

## Proof:

To prove the verification condition:

To prove the decryption stage:

Chapter 4 The proposed signcryption schemes

## Efficient Signcryption Scheme -II (ESS-II) with forward secrecy

## 4.2.1 Algorithm of ESS-II

The parameters and the Initialization Phase, defined for ESS-I, are also remaining same for this scheme.

## Signcryption phase:

Assume that Alice wants to send a message m to Bob. Alice generates digital signature (T, s) of message m and uses the symmetric encryption algorithm and secret key k to encrypt m. Let c be the cipher text. Alice generates the signcrypted text (c, T, s) in the following steps:

Step 1: Verifies Bob's public key Pb by using his certificate.

Step 2: Randomly selects an integer v, where v â‰¤ n - 1.

Step 3: Computes (k1, k2) = hash(vPb).

Step 4: Uses the symmetric encryption algorithm to generate cipher text;

c = Ek1 (m)

where the secret k1 is generated in Step 3.

Step 5: Uses the one-way keyed hash function to generate:

r = KHk2 (c || IDA || IDB)

where IDA and IDB are the identifications given by the certification authority(CA).

Step 6: Computes s = (v -r)/va mod q

Step 7: Compute T = rG.

Step 8: Sends the signcrypted text (c, T, s) to Bob.

## Unsigncryption phase:

Bob receives the signcrypted text (c, T, s). He decrypts cipher text 'c' by performing symmetric decryption algorithm with secret key k. He also verifies the signature. Bob

gets the plain text as follows.

Step 1: Verifies Alice's public key Pa by using her certificate.

Step 2: Computes (k1,k2) = hash(vbT + vbsPa).

Step 3: Uses one-way keyed hash function to generate:

r = KHk2 (c || IDA || IDB)

Chapter 4 The proposed signcryption schemes

IDA and IDB are the identifications given by the certification authority(CA).

Step 4: Uses a symmetric decryption algorithm to generate plain text:

m = Dk1 (c)

where the secret key k1 is computed in Step 2.

Step 5: Bob accepts the message 'm' only when rG = T .Otherwise he rejects.

Judge Verification of the signcrypted message by a firewall or judge.

Using Dffie-Hellman key exchange protocol Bob will send his private key to the verifier or judge.

The verifier computes (k1,k2) = hash(vbT + vbsPa) and then

r = KHk2 (c || IDA || IDB)

where IDA and IDB are the identifications given by the certificate authority(CA).

Finally the verifier accepts the message 'm' only when rG = T .Otherwise he rejects.

## Proof:

To prove the decryption stage:

Chapter 4 The proposed signcryption schemes

## The security functions of ESS-I & ESS-II

Table 4.1 indicates the security features supported by existing signcryption schemes along with the ESS-I and ESS-II. The proof is based on the fact that it is almost intractable to solve the elliptic curve discrete logarithmic problem (ECDLP) [8, 20]. We should choose the parameters in such a way that it will become infeasible for an eavesdropper to solve ECDLP.

## Table 4.1: Comparison based on security properties

## Scheme Name

## Confide-ntiality

## Integrity

## Unforge-ability

## Non-repudiation

## Forward Secrecy

## Public Verification

## Resistance against Side Channel Attacks

## ESS-I

## Yes

## Yes

## Yes

## Directly

## Yes

## Yes

## Yes

## ESS-II

## Yes

## Yes

## Yes

## Another Protocol

## Yes

## Yes

## Yes

Zheng

Yes

Yes

Yes

Another Protocol

No

No

No

Zheng & Imai

Yes

Yes

Yes

Another Protocol

No

No

No

Bao & Deng

Yes

Yes

Yes

Directly

No

Yes

No

Gamage etal.

Yes

Yes

Yes

Directly

No

Yes

No

Jung

et al.

Yes

Yes

Yes

Another protocol

Yes

No

No

## Confidentiality

To be secure, the information needs to be hidden from unauthorized access. To achieve this we must make the data non-intelligible to the interceptor/eavesdropper. This is called confidentiality. In this discussion let us consider Eve as the attacker/eavesdropper. In both schemes, if Eve wants to derive the key k then he has to solve ECDLP. Suppose he has got hash (m) and he knows the seed value of the curve i.e. G which is public to all. Then it is quite infeasible for Eve to solve it.

## Authenticity

In ESS-I, the recipient and the judge can use the sender's public key Pa with its certificate to authenticate the validity of the sender. But in case of ESS-II, the recipient Bob should establish a zero-knowledge interactive protocol or Diffi-Hellman key exchange protocol with the judge to send his private key, for the authentication of the message sent by Alice.

Chapter 4 The proposed signcryption schemes

When the recipient decrypted the cipher text c to get the plain text m, he can use the formula given below to authenticate the correctness of the received message. If the equation holds, the recipient is sure that the received message does not modify in the transmission process. Therefore, the proposed scheme provides the authentication of the sender's identity and the transmitted message.

rG = T

## Integrity

In our proposed schemes (ESS-I and ESS-II), the recipient can verify whether the received message is the original one that was sent by the sender. In the signcryption phase, the sender computes and sends (c, T, s) to the recipient. If the attacker changes the cipher text c to c' then by the property of Random Oracle Model [5] it is infeasible to obtain two messages which give the same digest [4].

## Unforgeability

Dishonest Bob is the most powerful attacker to forge a signcrypted message, because he is the only person who knows the private key vb which is required to directly verify a signcryption from Alice. Given a signcrypted text (c, T, s) Bob can use his private key vb to decrypt the cipher text c and obtain (m, T, s). As we know ECDSA is unforgeable against adaptive attack. Hence it is unforgeable.

## Non-repudiation

The target of non-repudiation is to prevent Alice from denying the signcryption she sent. Unforgeability implies non-repudiation if there is no duplication of the signcrypted message. If the signcryption text is forgeable, Alice will have opportunity to deny. When dispute occurs between sender and recipient, the recipient can send the signcrypted message to the judge for settling the original message M sent by the intended sender or not. Judge now run the verification algorithm and take the necessary action.

## Forward Secrecy

An adversary that obtains va will not be able to decrypt past messages. Previously recorded values of (c, T, s) that were obtained before the compromise cannot be decrypted because the adversary that has va will need to calculate vb to decrypt. Calculating vb requires solving the ECDLP, which is computationally infeasible [8].

Chapter 4 The proposed signcryption schemes

## Public Verifiability

Verification requires knowing only Alice's public key. All public keys are assumed to be available to all system users through a certification authority or a public directly. For ESS-I, the receiver of the message does not need to engage in an external protocol like zero knowledge proof whereas for scheme II, a zero knowledge key exchange protocol is needed.

## Resistance Against Side Channel Attacks

Point multiplication performed using Algorithm 2 ( Appendix C) along with the randomization of parameters using Coron [30] method for parameter randomization, provides resistance from the SPA(Simple Power Analysis) and DPA (Differential Power Analysis) attacks respectively [20].

Thus the security features provided by the Signcryption scheme, mainly depends on the secrecy of r and dB, which are the empirical and static secret keys, respectively which are used in the Signcryption and Unsigncryption phases. Algorithm (SCA resistant) is not used in the point multiplication operations involved in calculating; sâˆ™G + vâˆ™R. So the values of s and v can be obtained by the adversary through SCA. Even then the security properties are maintained by the scheme since the random number r remains secret.

## Implementation

JAVA being an Object Oriented Language (OOL) includes the advanced security features and packages. It could accept a prime number up to 1024 number of bits or even more. That could help us to generate large prime numbers. Code for generating the Secure hash Function to make the message digest can also be written in JAVA. So we can implement the proposed schemes in JAVA.

In our thesis work we have used the SHA-1, one way hash function, for the message digest. This compression function will give a fixed length output of 160 bits. Maximum message size that it takes is 264-1 and the block size is 512 bits. Total 80 numbers of rounds has been used with a word size of 32 bits.

## 4.5 Analysis of Computational Cost

Table 4.2 shows the computational cost of various elliptic curve DSS. With the signature-then-encryption based on SECDSS1 or SECDSS2 and elliptic curve

Chapter 4 The proposed signcryption schemes

ElGamal encryption [1], the number of computations of multiples of points is 3,

both for the process of signature-then-encryption and that of decryption-then-verification.

We note that the "square and multiply" method for fast exponentiation (see Appendix B) can be adapted to a "doubling and addition" method for the fast computation of a multiple of a point on an elliptic curve. Namely a multiple can be obtained in about 1.5 |q| point additions [12, 18].

Among the three multiples for decryption-then-verification, two are used in verifying a signature. More specifically these two multiples are spent in computing e1G + e2Pa for two integer's e1 and e2. Shamir's technique [18] for fast computation of the product of multiple

exponentials with the same modulo can be adapted to the fast computation of e1G + e2Pa.

## Signcryption Scheme

## Participants

## EXP

## DIV

## ECPM

## ECPA

## MUL

## ADD

## KH (.) /

## Â

## Â

## Â

## Â

## Â

## Â

## Â

## hash(.)

## Zheng

## Alice

## 1

## 1

## -

## -

## -

## 1

## 2

## Bob

## 2

## -

## -

## -

## 2

## -

## 2

## Jung et al.

## Alice

## 2

## 1

## -

## -

## -

## 1

## 2

## Bob

## 3

## -

## -

## -

## 1

## -

## 2

## Bao and Deng

## Alice

## 2

## 1

## -

## -

## -

## 1

## 3

## Bob

## 3

## -

## -

## -

## 1

## -

## 3

## Gamage et al.

## Alice

## 2

## 1

## -

## -

## -

## 1

## 2

## Bob

## 3

## -

## -

## -

## 1

## -

## 2

## Zheng and Imai

## Alice

## -

## 1

## 1

## -

## 1

## 1

## 2

## Bob

## -

## -

## 2

## 1

## 2

## -

## 2

## Han et al.

## Alice

## -

## 1

## 2

## -

## 2

## 1

## 2

## Bob

## -

## 1

## 3

## 1

## 2

## -

## 2

## Hwang

## Alice

## -

## -

## 2

## -

## 1

## 1

## 1

## Bob

## -

## -

## 3

## 1

## -

## -

## 1

## ESS-I

## Alice

## -

## 1

## 3

## -

## 1

## 1

## 3

## Bob

## -

## -

## 3

## 1

## -

## -

## 3

## ESS-II

## Alice

## -

## 1

## 2

## -

## 1

## 1

## 2

## Bob

## -

## -

## 3

## 1

## -

## -

## 2Table 4.2: Comparative analysis of computational overhead

Chapter 4 The proposed signcryption schemes

Thus on average the computational cost for e1G + e2Pa is (1 + 3/4) |q| point additions, or equivalently 1.17 point multiples. That is, the number of point multiples involved in decryption-then-verification, can be reduced from 3 to 2.17.

In ESS-I, we try to reduce the receiver's computational cost. Table 4.3 shows the comparisons of computational cost of sender and recipient among our signcryption schemes and others [10].

The ESS-I require only 3 ECPM for signcryption and 2 ECPM for unsigncryption and The ESS-II require only 2 ECPM for signcryption and 2 ECPM for unsigncryption. In the same security level, the elliptic curve point multiplication needs 83 ms and the modular exponentiation operation needs 220 ms for average computational time in the Infineon's SLE66CUX640P security controller [10]. Although our scheme is slower than Zheng and Imai scheme [18] as shown in the Table 4.4 but they provide added functionality such as encrypted message authentication, forward secrecy, public verifiabilty.

## Table 4.3: Comparative analysis of different schemes based on the average computational time of major operations

## Various Schemes

## Sender Average computational time in ms

## Recipient Average computational time in ms

## ESS-I

## 3 X 83=249

## 3 X 83=249

## ESS-II

## 2 X 83=166

## 3 X 83=249

## Zheng [1]

## 1 X 220=220

## 2 X 220=440

## Zheng and Imai [18]

## 1 X 83=83

## 2 X 83=166

## Bao and Deng [16]

## 2 X 220=440

## 3 X 220=660

## Gamage et al. [17]

## 2 X 220=440

## 3 X 220=660

## Jung et al.

## 2 X 220=440

## 3 X 220=660

## Han et al. [11]

## 2 X 83=166

## 3 X 83=249

## Hwang et al. [10]

## 2 X 83=166

## 3 X 83=249

From this we may conclude that the proposed schemes give better result than all other schemes except the schemes such as Hwang et al., Zheng and Imai. ESS-II gives better result as compare to Hwang et al. scheme.

Chapter 4 The proposed signcryption schemes

## Average computational time (ms)

## Figure 4.1: Comparative analysis of different schemes

## 4.6 Analysis of Communication Overhead

Communication overhead calculations are based on the following assumptions:

(a) | hash(.) | = |KH(.)| = |q| / 2

(b) | q | = | pm|

(c) Point compression is used.

The communication overhead of SECDSS1 (see Table 4.2) followed by ElGamal elliptic curve encryption [4] is,

(| hash(.) | + | q |) + 2(| q | + 1) = |hash(.)| + 3 |q| = 3.5 | q |

assuming that:

| q | â‰¥ 1

## For ESS-I and ESS-II:

The communication overhead of the proposed schemes ESS-I and ESS-II are:

| q | + ( | q | + 1) = 2 | q | + 1 â‰ˆ 2 | q |

assuming that

| q | â‰¥ 1

Thus bandwidth saving can be calculated as:

(3.5 | q | âˆ’ 2 | q |) / 3.5 | q | = 42.86%

This saving is higher than the one calculated in Zheng-Imai paper [18], which is 40%. However, it supports forward secrecy.