Journal of Applied Sciences

Year: 2007 | Volume: 7 | Issue: 13 | Page No.: 1813-1817
DOI: 10.3923/jas.2007.1813.1817

A New Multisignature Scheme Using Re-Encryption Technique

Sattar J. Aboud and Mohammed A. AL-Fayoumi

Abstract: Anew multisignature scheme using re-encryption technique based on the RSA algorithm is suggested what enhance version of Okamoto scheme. The suggested scheme results bit expansion in block length of the multisignature, but the bit size of the expansion is not larger than the number of signers irrespective of their modulus. In addition, the new scheme has no limitations in signing order and in fact is more efficient than the Okamoto scheme.

Keywords: re-encryption technique, Okamoto scheme, multisignature scheme, bit size expansion and RSA scheme

INTRODUCTION

In the past, we made a signature by signing a name or affixing a seal on a document to establish the corresponding rights and duties. Since we are now in the era of e-commerce and e-government, the use of digital signatures is very important. Learning the use of digital signatures is also significant. However, since the law of digital signature has been passed in October 31 2001, the security of digital signature schemes must not be ignored (Chiou, 2004). Digital signature scheme must accomplish the functions of undeniable, integrity and identification. In general, a digital signature scheme can be done by a public key cryptography. For different security hypothesis, we can divide digital signature algorithms into two types. The first one is a digital signature scheme based on the discrete logarithm problem such as Elgamal digital signature scheme. In this hypothesis the discrete logarithm problem can not be broken; this type of digital signature scheme is secure. Alternatively, if the discrete logarithm problem can be broken, this type of discrete signature scheme will become insecure. The second type is a digital signature scheme based on the factoring problem such as RSA digital signature scheme. Also, under this hypothesis the factoring problem can not be broken; this type of digital signature scheme is secure. It means that if the factoring problem can be broken, this type of digital signature scheme will also be broken. The discrete logarithm problem and the factoring problem are two hard solved mathematical problems and the two problems are believed to be unsolved in the reasonable time period (Al-Fayoumi and Aboud, 2006a,b). However, if any one of the two problems is solved in the future, the digital signature schemes based on this hard problem hypothesis will become insecure. Hence, if there is a digital signature algorithm of which the security is based on both the discrete logarithm problem and the factoring problem, the digital signature scheme will be still secure under the situation that any one of the two problems is solved.

In this study, we propose a new multisignature scheme using re-encryption technique based on the RSA scheme. The security of the RSA scheme is relied on the integer factoring problem (Rivest et al., 1978). The practical example of RSA scheme for multiple operations of a known message results bit expansion difficulty inherently. The early methods to solve this problem are re-blocking algorithm (Kohnfelder, 1978) and repeated square and multiply algorithm Levine and Brawley (1977). To face the problem of bit expansion in the RSA multisignature, they should permit a signer to have the RSA modulus with a different bit length corresponding to the signer place in a hierarchical structure. Thus, the signing order is limited. There are two other multisignature schemes with out bit expansion (Harn and Kiesler, 1989; Kiesler and Harn, 1990). In the first scheme the signing order is selected corresponding to the length of signers' public keys. The second scheme is relied on the re-encryption scheme with permutation polynomials technique. However, the two multisignature schemes have no bit expansion difficulty and the signing order is not limited. All signers should have a modulus with the equal length and the mathematical complexity of finding the multisignature. Alternatively, Okamoto (1998) suggested multisignature scheme without limitation of the signing order (Okamoto, 1998). In this scheme, if the size of midway signature exceeds a pre-determined threshold value, then the additional bits exceeding the threshold value are added on to the document. Thus, the size of the expanded document relies on the number of signers and the bit length of every signer's RSA modulus.

In this study, we suggested a new multisignature scheme using re-encryption technique to enhanced version of Okamoto scheme. The suggested scheme also results bit expansion in block length of the multisignature, but the bit size of the expansion is not more than the number of signers irrespective of their modulus.

HANDWRITTEN SIGNATURE

Handwritten signature has long been employed as a proof of authorship of or at least agreement with the contents of a message (Davies and Price, 1984; Yoshimura and Yoshimura, 1996). The reasons of employing signature as authorship proof (Bruce, 1996) are as follows:

THE PROPOSED MULTISIGNATURE SCHEME

First we present the notations used in this section:

Also, in this section we present a new re-encryption scheme in which the length of the encrypting block differs with the length of the message block. Assume n is the RSA modulus which is the product of two large prime numbers and b is a public key with gcd (b, θ (n)) = 1. The secret key k is then computed using the multiplicative inverse (Aboud and Al-Fayoumi, 2005). Suppose an odd message m where 0 < m < 2^x*n. Then θ (2^x *n) = 2^{x -1}*θ and gcd (b, 2^x-1 *θ (n)) = 1. If b*k ≡ 1(mod 2^x-1 *θ(n)), then m^b*k ≡ m mod 2^x*n. Thus, x differs with the length of a message m and k differs with x. If c = m^b mod 2^x *n and e*k₁ ≡ 1 mod 2^x-1 then c mod 2^x = m^b mod 2^x and m mod 2^x = c^k1 mod 2^x. So, the suggested re-encryption technique can not be directly employed for encrypting m with large block length. However, this new re-encryption technique can be implemented in the multisignature scheme if every user calculates xⁱ from nⁱ as follows:

The multisignature generation is achieved as follows:

The first signer u₁ signs₁ = (2* h (m)+1)^k1 mod 2*n₁, then the first signer u₁ sends the message m and s_i to the second signer u_2. The second signer u_i sign

where b_i *k_i = m mod 2^xi-1*θ (n_i) and the second signer then sends m and s_i to the next signer.

The multisignature verification is done as follows:

The receiver verifies that s_t is the multisignature of m by signers u₁, ..., u_t

But when bi+1

and b_i *k ≡ 1 mod 2^xi then

Though, we can not get the most significant |n_i+1| bits of s_i from c_i and the most significant |n_i+1| bits of s_i from s_i-1. But when z = max (|n₁|, |n₂|,..., |n_t|), then the bit size of the multisignature .Thus the size expanded by the suggested method is not larger than the number of signers. For instance when (|n₁| = |n₂| = |n_t|) = 768 and (|n₂| = |n₄| = |n₆|) = 512 , then |s_t|#774. Thus, the expanded bit size is 6. But, in this example, Okamoto scheme has an expansion of 509 bits. As a result, the suggested scheme is more efficient than the Okamoto scheme. In addition, the new scheme has no limitations in signing order.

In some circumstances, the number of signers could be several. For instance, in an organization any two authorized signers may be permitted. So, according to this point the above algorithm can be extended to meet this extra work. However, when there are possible signers, then n random private keys k₁, k₂, k_n are selected. The public key b is selected so that:

Every signer is then given all the secret keys unless one. For instance the jth signer is provided all k_i unless k_j. Every signer keeps all these keys and also their outcomes. Suppose k_i = k₁,..., k (j-1) k (j+1),... k_n. If the jth signer wants to sign a cheque, c he signs it to compute:

and adds his identity. The other signer can then achieve the signing by looking on the absent key, which also permits him to check the cheque and then to compute:

The receiver and any member can again check the signature by decryption with b.

Digital multisignature scheme which requires the knowledge of the message as on input to the verification algorithm is called digital signature scheme with appendix. Digital signatures schemes with appendix are the most commonly employed in practice (Menezes, 1997). They based on cryptography hash function rather than redundancy function and are less prone to existential forgery attacks. The proposed scheme is designed to use a combination of an appropriate one way hash function h with which m shell be hashed before signing in order to bound the size of the key in verification. To avoids the potentiality of message collisions. It is preferable that the hash function employed must have a 160 bits product and secure hash algorithm (FIPA 180-1; 1995) which seems to be appropriate choice.

The multiplicative ability used in this algorithm can also be employed to attack RSA signature in some situation (Aboud, 2004). For instance, since (m₁*m₂) ≡ m₁, m₂) the signature of m₁, m₂ can be gathered from those of m₁ and m₂. Various tools are available to exclude these attacks and they are also usable in this algorithm. One technique is to employ a one way hash function h with which the message should be hashed pre-signing to bind the size of the key in verification. To avoid the potentially of collision of messages, it is preferable that the hash function employed must have a 160 bits outcome and secure hash algorithm (FIPA 180-1, 1994; FIPA 180-1, 1995). So we have h (m₁, m₂) = h (m₁) *h (m₂). This also has the benefit that just single block requires to be signed.

SECURITY OF THE SCHEME

Many useful multisignature schemes do not bear any proof of security; it is known that breaking RSA multisignature is based on the factorization difficulty. The only visible attacks on the suggested schemes are as difficult as factoring the modulus n (Aboud and Abu-Taieh 2006) but it is not shown if there is any certain efficient attack. For the security examination, we gain from the modular design of the proposed system employing well known cryptography scheme. Though all known attacks are verified to be prevented (Rivest, 1978). The security analysis is obviously constructive as we stay away from interaction among the scheme as can as possible. However, we will set out the security of the scheme we proposed. Assume that n is the RSA modulus for the suggested algorithm. As n had large prime factors p and q, then no one can factor n through any integer factoring technique. Furthermore, p-1 and q-1 have large prime factors p and q. Though each user has n_i s, the most significant bits of which are of the same value, the prime factors p_i and q_i of n_i are arbitrary. As a result, u_i can not deduce the prime factors p_i and q_i of the other user u_i. The following theorems are simply verified:

Theorem 1: If we able to calculate the private key k by b*k ≡ 1 mod 2^x-1 * θ (n), then the signature of random message m can be found.

Proof 1: If k ≡ k mod θ (n), then c ≡ m^k ≡ m^k mod n and e*k ≡ b*k ≡ 1 mod θ (n). Thus c is the signature of the message m

Theorem 2: For any odd m where 0<m<2^x *n, we can calculate c by c c ≡ m^b mod 2^x *n so the signature of the message m can be found.

Proof 2: If

So

then c is the signature of the message m.

Through theorems 1 and 2, the security of the scheme relied on the novel re-blocking method based on the security of RSA signature algorithm.

Many practical multisignature schemes including the RSA are liable to existential forgery attacks if a hash function is not employed pre-signing. In such attacks, there are unrestricted numbers of multi-signatures for random messages may be created. For the suggested algorithm, a simple existential forgery is that the value s = 1 is the multisignature for the message m = c. Additional random multi-signatures appear difficult to perform.

Choosing forgery relates to the complexity of forging a multisignature of a message selected in advance by the opponent. With the employment of one technique hash function, this seems the only way to compute any valid multisignature (Stinson, 2006). The opponent selects a message m and is needed to compute a signature S with s^m mod n = c. The possibility to calculate the multisignature s from knowledge of the public key is identical to breaking the RSA encryption algorithm for an existing cipher text c and public key b, with the part data there is a factor of θ (n) of size 160 bits. It is unobvious if the part data is an aid in factoring n. The likeness to the security of identification protocol (Brickel and McCurle, 1992; Aqel and Ammar, 2005) may again be explored.

A suitable selected message attack that employs multi-signatures on selected messages is difficult to hinder the attack of employing just the public key. Such an attack is no longer identical to an attack of RSA but could accord to a case where an opponent could select the public key of the RSA and get the original message according to the cipher text c (Aboud and El Sheikh, 2004; Trappe and Washington, 2006). It does not seem to be a clear manner that aids an opponent.

CONCLUSIONS

We have suggested a multisignature algorithm and also a novel re-blocking technique in which the length of the encryption block differs by the length of a message block and have employed the novel re-blocking technique to a multisignature scheme. Every signer is allowed to have the RSA modulus with different bit length. It results bit expansion which relies only on the number of signers despite of the bit size of RSA modulus. The size of the expansion is less than or equal to the number of signers. But when every signer has the RSA modulus and the same length, then our algorithm and Okamoto one have an equal expansion. But the proposed scheme has lesser bit expansion than Okamoto’s algorithm. So the suggested scheme is claimed to be more efficient than Okamoto scheme.

REFERENCES