# Signcryption analyze.

AbstractThe aim of this paper is to provide an overview for the research that has been done so far in signcryption area. The paper also presents the extensions for the signcryption scheme and discusses the security in signcryption. The main contribution to this paper represents the implementation of the signcryption algorithm with the examples provided.

Keywords: ElGamal, elliptic curves, encryption, identity-based, proxy-signcryption, public key, ring-signcryption, RSA, signcryption.

1 Introduction To Cryptography

Cryptography word comes from the two ancient Greek words: "krypto", which means "hidden" and "grafo", which means "to write". Cryptography meaning is how to make what you write obscure, unintelligible to everyone except whom you want to communicate with. It is believed that the oldest known text on which cryptography has been applied occurred some 4000 years ago in Egypt. The hieroglyphic inscriptions on a tomb were written with a number of unusual symbols to confuse or obscure the meaning of the inscriptions. Since the oldest times until the 1970s the cryptography was based on symmetric encryption.

The mid-1970s is a reference period for cryptography as two major public advances have been done.

First is the algorithm Data Encryption Standard (DES) that has been invented. DES is a symmetric block cypher based on a 64 bit block. The user feeds in a 64 block of plain text and is returned 64 bits of cyphertext. The same algorithm and key are used to encrypt and decrypt operations. The aging DES was officially replaced by the Advanced Encryption Standard (AES) in 2001. DES, and its more secure variant, Triple DES, are still used today, been incorporated into many national and organizational standards.

The second development, in 1976, was a very significant step in the history of cryptography. This was the publication of the paper "New Directions in Cryptography" by Whitfield Diffie and Martin Hellman. It introduced a radically new method of distributing cryptographic keys, which went far toward solving one of the fundamental problems of cryptography, key distribution, and has become known as Diffie-Hellman key exchange. The article also stimulated the birth of a new class of enciphering algorithms, the asymmetric key algorithms. Before that, all useful modern encryption algorithms had been symmetric key algorithms, in which the same cryptographic key is used with the underlying algorithm by both the sender and the recipient, who must both keep it secret.

In contrast, asymmetric key encryption uses a pair of mathematically related keys, each of which decrypts the encryption performed using the other. By designating one key of the pair as private, and the other as public, no secure channel is needed for key exchange. This led to important applications we often hear of today. Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed in the field of public-key cryptography. Digital signatures, PGP, use of public certificates, various authentication protocols (for example SSL, SSH) are all in the "galaxy" of public key cryptography.

Public key cryptography is used to solve various problems that symmetric key algorithms cannot. In particular, it can be used to provide privacy, and nonrepudiation. Privacy is usually provided through key distribution, and a symmetric key cipher. This is known as hybrid encryption. Nonrepudiation is usually provided through digital signatures, and a hash function.

The most widely used cryptographic hash functions are MD4, MD5 (where MD stands for Message Digest), and SHA/SHS (Secure Hash Algorithm or Standard). The MD4/5 algorithms were invented by Ron Rivest and RSA Laboratories. MD5 is an improved version of MD4. Both condense a message of any size to a 128-bit digest. SHA/SHS is similar to both MD4 and MD5; it produces a 160-bit digest. Wang et al. [WAN05] have announced cryptanalysis attacks on SHA, MD4, and MD5. For SHA, the attack is able to find two plaintexts that produce the same hash digest in approximately 263 steps, far short of the 280 steps that would be expected of a 160 bit hash function, and very feasible for a moderately well financed attacker [2].

A digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit. Digital signatures are commonly used for software distribution, financial transactions, and in other cases where it is important to detect forgery or tampering.

A digital signature scheme typically consists of three algorithms:

* A key generation algorithm that selects a private key uniformly at random from a set of possible private keys. The algorithm outputs the private key and a corresponding public key.

* A signing algorithm that, given a message and a private key, produces a signature.

* A signature verifying algorithm that, given a message, public key and a signature, either accepts or rejects the message's claim to authenticity.

The Digital Signature Standard is on the base of many current research topics today, like signcryption.

2 Signcryption Introduction

In 1997 Yuliang Zheng presented a positive answer to the following question: "is it possible to transfer a message of arbitrary length in a secure and authenticated way with an expense less than that required by signature-then-encryption?". This was for the first time, since public-key cryptography has been invented, that the question is addressed in literature. He discovered a new cryptographic primitive, called signcryption, which simultaneously fulfills both the functions of digital signature and public key encryption in a logically single step, and with a cost significantly smaller than that required by signature-then-encryption [1]. The proposed cryptographic primitive is more efficient for both types of costs involved: computational cost and communication overhead. The computational cost represents how much computational effort has to be invested by the sender and by the receiver of the message. It is determined by counting the number of dominant operations involved. The communication overhead represents the extra bits which are appended to a message in case of a digital signature or encryption based on public key cryptography.

Encryption and digital signature are two fundamental cryptographic tools that can guarantee the confidentiality, integrity, and non-repudiation. Until signcryption, they have been viewed as important but distinct building blocks of various cryptographic systems. In public key schemes, a traditional method is to digitally sign a message then followed by an encryption, named signature-then-encryption. In many applications, both confidentiality and authenticity are needed together. Such applications include secure email (S/MIME), secure shell (SSH), and secure web browsing (HTTPS). In order to accomplish these two goals, many cryptographic schemes have been created: Schnorr signature-then-ElGamal encryption, DSS-then-ElGamal encryption, RSA signature-then-RSA encryption, Schnorr signature-then-RSA encryption, RSA signature-then-ElGamal encryption.

Any signcryption scheme should have the following properties:

1. Correctness: Any signcryption scheme should be correctly verifiable.

2. Efficiency: The computational costs and communication overheads of a signcryption scheme should be smaller than those of the best known signature-then-encryption schemes with the same provided functionalities.

3. Security: A signcryption scheme should simultaneously fulfil the security attributes of an encryption scheme and those of a digital signature. Such additional properties mainly include: Confidentiality, Unforgeability, Integrity, and Non-repudiation. Some signcryption schemes provide further attributes such as Public verifiability and Forward secrecy of message confidentiality while the others do not provide them.

- Confidentiality means that only the intended recipient of a signcrypted message should be able to read its contents.

- Authenticity, we mean that the recipient of a signcrypted message can verify the sender's identity. It is not possible for an attacker to send a message, claiming to be someone else.

- Non-repudiation means that the sender of a message cannot later deny having sent the message. That is, the recipient of a message can prove to a third party that the sender indeed sent the message. Signature schemes always provide non-repudiation, since anyone can verify a signature using only the sender's public key. Some signcryption scheme can provide non-repudiation and these schemes are called S-verifiable, since the verifier uses only the signature scheme S. The first DSAverifiable signcryption scheme has been introduced by Shin, Lee, and Shim [5].

- Forward secrecy means that an attacker cannot read signcrypted messages, even with access to the sender's private key. The confidentiality of signcrypted messages is protected, even if the sender's private key is compromised.

- Past recovery means that the sender is allowed to use his private key to recover the original message from the cipher-text. Forward secrecy and past recovery are mutually exclusive.

Cryptographic operations for signature and encryption are relatively expensive as they typically involve computations on astronomically large numbers and generate additional communication overhead. With the "digital signature followed by public key encryption" method, the computational and communication overhead for achieving unforgeability and confidentiality is the sum of the overhead for digital signature and that for public key encryption.

The cost for signcryption is significantly smaller than that required by \signature followed by encryption". For typical security parameters for high level security applications (size of public moduli = 1536 bits), signcryption costs 58% (50%, respectively) less in computation time and 85% (91%, respectively) less in message expansion than does \signature followed by encryption" based on the discrete logarithm problem (factorization problem, respectively). The saving in cost brought to society by this new technology is potentially huge, especially in the emerging era of electronic commerce in which the assurance of secure and authenticated transactions and communications is a key to its success as well as public acceptance.

2.1 Shorten Digital Signature Standard

Zheng first scheme is based on the shortened version of the Digital Signature Standard known as SDSS. Shorten Digital Signature Standard parameters are:

p = a large prime number, public to all

q = a large prime factor of p-1, public to all

g = an integer with order q modulo p, in [1,..., p-1], public to all

hash = a one-way hash function

x = a random number from [1, ..., q-1]

Xa = Alice's private key chosen randomly from [1,..., p-1]

Ya = Alice's public key = [g.sup.xa] mod p

The Shortened Digital Signature Standard has two versions: SDSS1 and SDSS2. Alice's signature on a message m is composed of two numbers r and s, where

r = hash ([g.sup.x] mod p, m)

s = x/(r + Xa) mod q

in case of SDSS1 and

r = hash ([g.sup.x] mod p, m)

s = x/(1 + Xa x r) mod q

in case of SDSS2.

The signature of a message m will be (r, s). In order to verify the signature it is necessary to calculate

k = [(Ya x [g.sup.r]).sup.s] mod p, in case of SDSS1, and k = [(g x Y[a.sup.r]).sup.s] mod p, in case of SDSS2.

When k is obtained the last check can be done: hash(k, m) = r

The most important characteristic of the presented scheme is that, although [g.sup.x] mod p is not explicitly contained in the signature (r, s), it can be calculated by the receiver using r, s and the other public parameters.

SDSS1 is more efficient than SDSS2 in signature generation, as the second involves an extra modulo multiplication [2]. In signcryption algorithm there are used two has function, one-way hash function and one-way hash function with key. Techniques based on hashing are heavily used in many applications, information retrieval, geometry processing, chemical and medical applications and mostly in cryptography [24].

2.2 Signcryption Algorithm

A signcryption scheme typically consists of three algorithms:

* Key Generation (Gen) - generates a pair of keys

* Signcryption (SC) - is a probabilistic algorithm

* Unsigncryption (USC) - is a deterministic algorithm.

Signcryption parameters:

p = a large prime number, public to all

q = a large prime factor of p-1, public to all

g = an integer with order q modulo p, in [1,..., p-1], public to all

hash = a one-way hash function

KH = a keyed one-way hash function = KHk(m) = hash(k, m)

(E, D) = the algorithms which are used for encryption and decryption of a private key cipher.

Alice sends a message to Bob.

Alice has the pair of keys (Xa, Ya):

Xa = Alice's private key, chosen randomly from [1, .., q-1]

Ya = Alice's public key = [g.sup.xa] mod p

Bob has the pair of keys(Xb, Yb):

Xb = Bob's private key, chosen randomly from [1, .., q-1]

Yb = Bob's public key = [g.sup.xb] mod p.

In order to signcrypt a message m to Bob, Alice has to accomplish the following operations:

1. Calculate

k = hash([Yb.sup.x]) mod p

Split k in k1 and k2 of appropriate length.

2. Calculate r = KHk2(m) = hash(h2, m)

Calculate s = x/(r+Xa) mod q, if SDSS1 is used.

3. Calculate s = x/(1+Xa x r) mod q, if SDSS2 is used.

4. Calculate c = Ek1(m) = the encryption of the message m with the key k1.

Alice sends to Bob the values (r, s, c).

In order to unsigncrypt a message from Alice, Bob has to accomplish the following operations:

1. Calculate k using r, s, g, p, Ya and Xb

hash([(Ya * [g.sup.r]).sup.s x xb] mod p), if is used SDSS1

hash([(g * Y[a.sup.r]).sup.s x xb] mod p), if is used SDSS2

Split k in k1 and k2 of appropriate length.

2. Calculate m using the decryption algorithm m = Dk1(c).

3. Accept m as a valid message from Alice only if KHk2(m) = r.

Using the two schemes SDSS1 and SDSS2, two signcryption schemes have been created, SCS1 and SCS2, respectively. The two signcryption schemes share the same communication overhead, (|hash(*)| + |q|). SCS1 involves one less modular multiplication in signcryption then SCS2, both have a similar computational cost for unsigncryption [1].

Applying SDSS1 scheme in the algorithm we obtain the following examples for the signcryption scheme.

p q a X XA YA XB YB K 467 233 7 213 177 391 123 13 138 467 233 12 213 127 400 123 22 432 467 233 21 213 127 48 123 141 25 467 233 27 213 127 95 123 448 55 467 233 36 213 127 411 123 59 286 467 233 40 213 127 146 123 68 23 467 233 43 213 127 332 123 411 422 467 233 48 213 127 92 123 38 273 467 733 49 213 127 172 123 169 174 23 11 2 9 3 8 4 16 8 23 11 3 9 3 4 4 12 4 2027 1013 100 219 357 329 158 1316 716 2027 1013 325 219 357 1487 158 878 1473 2027 1013 537 219 357 403 158 599 199 2027 1013 55 219 357 1062 158 1785 1724 2027 1013 71 219 357 1949 158 1644 1028 2027 1013 1001 219 357 1836 158 431 1973 3167 1583 67 246 79 2929 43 1396 1008 3167 1583 25 246 79 498 43 1604 1862 3167 1583 22 246 79 914 43 1189 937 3167 1583 44 246 79 9 43 1641 2592

Changing the value for Alice's private key has an impact only on the Alice's public key.

Changing the value for Bob's private key, his public key will be changed but also the k will have a different value.

Taking fixed values for parameters and different values for the message, the key k remains the same.

When are taken the following fixed parameters:

p q g X XA YA XB YB K 467 233 21 213 127 48 123 141 25

and the following values for the massage, then the calculated values for the hash and signature are as follows:

m r s 77 385 111 100 119 106 789 458 225 1000 235 45 3579 87 185

Identity based signcryption scheme is rapidly emerging in recent years and the notions of ring signcryption and proxy signcryption have been created.

The introduction of elliptic curve cryptography by Neal Koblitz [15] and Victor Miller [16] independently and simultaneously in the mid-1980s has yielded new public-key algorithms based on the discrete logarithm problem. Although mathematically more complex, elliptic curves provide smaller key sizes and faster operations for equivalent estimated security. Yuliang Zheng also proposed an elliptic curve-based signcryption scheme that saves 58% of computational and 40% of communication costs when it is compared with the traditional elliptic curve-based signature-then-encryption schemes [3]. Zheng original construction is built on a modification of ElGamal signature and carefully exploits randomness reuse to authenticate and encrypt the message more efficienty than simply encrypting the message using ElGamal encryption. In 2000, [14] Steinfeld and Zheng created a scheme which is provably unforgeable assuming the hardness of factoring. This algorithm requiresa trasted party to generate system-wide parameters that include an RSA modulus of particular shape.

Schnorr's signature scheme, without being further shortened, can be used to construct a signcryption scheme which is slightly more advantageous in computation than other signcryption schemes from the view point of a message originator.

There are also many other signcryption schemes that are proposed throughout the years, each of them having its own problems and limitations, while they are offering different level of security services and computational costs.

2.3 Signcryption Security

A signcryption scheme is secured if it is able to provide both authenticity and privacy of communicated data. There are two models of security for signcryption: outsider model and insider model. In case of public-key settings, the sender and the receiver do not have the same secret key, but each of them has his/her own secret key. In this situation, it is necessary for the data protection to be kept safety from an outsider but also from an insider, who is a legal user of the system, meaning the sender, the receiver or someone who knows the sender's secret key or the receiver's secret key. In the strong insider security model, the privacy of the signcryption scheme is based on the security of the public-key encryption scheme and the integrity protection of the signcryption scheme is based on the security of the digital signature scheme.

Non-repudiation should not be part of the definition of signcryption security because it is not necessary in all the applications. Although signcryption allows the receiver to be sure that the message has been delivered by the sender, it does not necessarily enables a third-party to verify this because the verification of the authenticity of the message may involve the receiver's secret key, depending on how the signcryption scheme is built [11]. In 2002 [12] Shin proposed a signcryption scheme that enjoys a secure and efficient non-repudiation procedure, allowing receivers to convince a third party of the origin of the message. In 2005, [13] Malone-Lee suggested a similar technique and proposed a scheme extending Schnorr's signature scheme that was additionally supported by a proof of unforgeability.

Regarding the number of the users involved in the signcryption algorithm, there are two models of signcryption: two-user model and multi-user model. The two-user model contains only the sender and the receiver in this process. In a multi-user network, the algorithm works with identities. In the multi-user context, the signcryption scheme needs to respect the following rules:

* For encryption it is necessary to include the sender's identity together with the encrypted message.

* For the digital signature it is necessary to include the receiver's identity together with the signed message.

In the multi-user model the adversary has an extra power, having the ability to access flexible signcryption and unsigncryption oracles which allow him to specify the receiver's and sender's public key, respectively, in addition to the message and signcryptext, respectively. In some applications has been implemented the possibility to place significant constraints on the public keys in such a way that the Certificate Authority ensure that users know the private key associated with their public key.

Evaluating the two-user security of a signcryption scheme is not sufficient for establishing its multi-user security [11].

2.4 Identity Based Cryptography

The idea of identity-based cryptography has been proposed by Shamir in 1984. The main essence of identity-based cryptosystem is to remove the need of certification of the public keys that are required in the conventional public key cryptography setting. The public key of each participant is obtained from his/her public identity, such as email address, IP address combined with a user name, social security number, etc. that can uniquely identify the participant. An ID-based cryptosystem is one in which the public key may be any string or may be derived from any string. This model requires the existence of a trusted authority called Private Key Generator (PKG), whose task is to generate user's private key from their identity information, after a successful identification. The first practical identity-based cryptosystem was that of Boneh and Franklin in 2001[7] and takes advantage of the properties of suitable bilinear maps (the Weil or Tate pairing) over supersingular elliptic curves. The identity-based signcryption scheme with its security model has been introduced first by Malone-Lee. Identity-based signcryption is an adaptation of identity based encryption to the case of signcryption.

3 Ring Signcryption

In Asiacrypt 2001, Rivest, Shamir and Tauman firstly addressed and formalized the notion of ring signatures [8]. A ring signature can be considered as a simplified group signature with no manager, no group setup procedure, and no revocation mechanism, and hence, it provides signer's ambiguity. In a ring signature scheme, the information of all possible signers, i.e. ring members, serves as a part of the ring signature for the signed message. A valid ring signature will convince a verifier that the signature is generated by one of member in the ring, without revealing any information about which participant is the actual signer [9].

Ring signcryption is an anonymous signcryption which allows a user to anonymously signcrypt a message on behalf of a set of users including himself. In an ordinary ring signcryption scheme, even if a user of the ring generates a signcryption, he also cannot prove that the signcryption is produced by himself. In 2008, Zhang, Yang, Zhu, and Zhang solve the problem by introducing an identity-based authenticatable ring signcryption scheme (denoted as the ZYZZ scheme). In the ZYZZ scheme, the actual signcrypter can prove that the ciphertext is generated by himself, and the others cannot authenticate it. In the scheme, a user can anonymously signcrypt a message on behalf of a set of users including himself. ID-based ring signcryption is very useful to protect privacy and authenticity of a collection of users who are connected through an ad hoc network.

4 Proxy Signcryption

The concept of proxy signature was first presented by Mambo in 1996 [6]. Proxy signature schemes are useful for secure communication by computing devices lacking the necessary computational power to perform cryptographic computations on an online realtime basis. These devices can use a more powerful trusted proxy server to perform required cryptographic computations on their behalf while maintaining certain checks and balances against misuse or abuse of the trust placed on the proxy agent [4]. Proxy signature schemes have been suggested for use in a number of applications, particularly in distributed computing where delegation of rights is quite common, such as e-cash systems, mobile agents for electronic commerce, mobile communications, grid computing, global distribution networks, and distributed shared object systems.

Many proxy signature schemes have been combined with different encryption methods obtaining proxy signcryption schemes which have a significantly smaller cost, both in terms of cryptographic computation and bandwidth, than the addition of costs for signing and encryption [10].

The basic idea of ID-Based proxy-signcryption schemes is as follows. The original signcrypter sends a specific message with its signature to the proxy signcrypter, who then uses this information to construct a proxy private key. With the proxy private key he can generate proxy signcryption by employing a specified standard ID-Based signcryption scheme. When a proxy signcryption is given, a verifier first computes the proxy public key from some public information, and then checks its validity according to the corresponding standard ID-Based signcryption verification procedure.

5 Conclusion

A lot of research has already been done in the field of signcryption. The signcryption schemes that have been discussed here do not represent the entire list, but instead are intended to give an overview of the various research directions which have been explored so far. Research along signcryption lines is open-ended.

References:

[1.] Y. Zheng. Digital signcryption or how to achieve cost (signature & encryption) << cost (signature) + cost (encryption). In: CRYPTO'97, LNCS 1294, pp. 165-179. Springer Verlag, 1997.

[2.] Whitfield Diffie, Martin Hellman, "New Directions in Cryptography".

[3.] Y. Zheng. How to construct efficient signcryption schemes on elliptic curves.

[4.] Chandana Gamage, Jussipekka Leiwo and Yuliang Zhengon, "An Eficient Scheme for Secure Message Transmission using ProxySigncryption"

[5.] Jun-Bum Shin, Kwangsu Lee, and Kyungah Shim. New DSA-verifiable signcryption schemes. In P.J. Lee and C.H. Lim, editors, Proc. of ICISC '02. Springer-Verlag, 2002.

[6.] M.Mambo, K.Usuda and E.Okamoto. "Proxy signature: Delegation of the power to sign messages". IEICE Trans Fundamentals, 1996.

[7.] D.Bonehand M.Franklin, Identity-based encryption from

[8.] the Weil Pairing, Crypto'01

[9.] R.L. Rivest, A. Shamir and Y. Tauman, How to leak a

[10.] secret, Adv in Cryptology-Asiacrypt 2001.

[11.] Xinyi Huang, Willy Susilo, Yi Mu and Futai Zhang, "Identity-based Ring Signcryption Schemes: Cryptographic Primitives for Preserving Privacy and Authenticity in The Ubiquitous World"

[12.] Meng Wang, and Zhijing Liu, "Identity Based Threshold Proxy Signcryption Scheme".

[13.] Yuliang Zheng, Alexander W. Dent, Moti Yung, "Practical Signcryption", 2010.

[14.] J. Shin, K. Lee and K. Shim, New DSA-Verifiable Signcryption Schemes, Information Security and Cryptology (ICISC 2002).

[15.] John Malone-Lee, Signcryption with Non-interactive Non-repudiation, Designs, Codes and Cryptography, October 2005

[16.] R. Steinfeld and Y. Zheng, A Signcryption Scheme Based on Integer Factorization, Information Security Workshop (ISW '00), 2000.

[17.] N. Koblitz, Elliptic curve cryptosystems, in Mathematics of Computation 48, 1987, pp. 203-209

[18.] V. Miller, Use of elliptic curves in cryptography, CRYPTO 85, 1985

Laura Savu (1)

(1) Department Computer Science--Information Security, University of Bucharest, Faculty of Mathematics and Computer Science, Str. Academiei nr.14, sector 1, C.P. 010014, Bucuresti, Romania, ROMANIA, email:laura.savu@microsoft.com

Printer friendly Cite/link Email Feedback | |

Author: | Savu, Laura |
---|---|

Publication: | Journal of Information Systems & Operations Management |

Date: | May 1, 2012 |

Words: | 4339 |

Previous Article: | Trial incidents regarding the admissibility of electronic evidence. |

Next Article: | Underground economy--a growing challenge for economy and governments. |

Topics: |