Digital Signature Scheme Based on Factorization The objective of this study is to discuss an issue in cryptography or computer security. Digital signatures are described as "an analog of handwritten signatures" which are based on "the physically idiosyncratic way of signing one's name. But they can be easily forged." (Grabbe, 1998) The digital signature is "a mathematical method of attaching one's identity to a message" and is held to be more difficult to forge than a handwritten signature." (Grabbe, 1998) Public key cryptography is used for digital signatures and is such that uses two keys: (1) Take an ordinary plain-text message and apply one of the keys to it in an encryption process, and you end up with a scrambled or "encrypted" (or, in the current context, "signed") message; and (2) Apply the other key to the scrambled message in a decryption process, and you end up with the original plain-text message. (Grabbe, 1998)

One of the two keys is a public key and the other is a private key. The work of Goldwasser, Micali and Rivest (1988) report that the idea of "a digital signature first appeared in Diffie and Hellman's seminal paper 'New Direction in Cryptography' in which is it proposed that each users published a 'public key' which would be used for signature validating while "keeping a secret key (used for producing signatures)." (Goldwasser, Micali and Rivest, 1998)

The idea of a digital signature is reported as a replacement for signatures that are handwritten. It is additionally reported that several problems of a technical nature are relative when there is implementation of digital signatures through use of what are known as trap-door functions. However, these complications are addressed and a solution reported gained. It is stated that TMY83 demonstrated how arbitrary or sparse message sets could be handled and how it could be made sure that should a perpetrator view signatures that are previous that the perpetrator is not assisted in the forging of new signatures. (Goldwasser, Micali, and Rivest, 1988)

Lin, Gun and Chen (2009) report that since the first proposal of a digital signature there have been schemes based on discrete logarithms and the factoring problem. Most of those proposed thus far has been proven to lack in security. One stated example is that Harn in 1995 demonstrated that the H-Kiesler scheme can be broken is the individual has the capacity to solve the factorization. (Lin, Gun, and Chen, 2009, paraphrased) In addition, Lin and Hwang demonstrated that if the individual has the capacity to solve the discrete logarithms, that the He-Kiesler scheme can be broken.

I. New Forms of Computer Cryptography and Security

It is related in the work of Al-Saidi (2011) entitled "Signature Identification Scheme Based on Iterated Function Systems" that secure identification is a critical aspect of security. The use of a hash function can be utilized in the construction of a secure digital signature, which is equally complex as the identification scheme. The digital signature scheme can be used in building communication tools, which are effective in nature as well as for ensuring privacy. Al-Saidi (2011) reports that the first proposed method for exchange of public keys was the ZK protocol in digital cash protection on smart cards which is considered to be just as much of a consumer of time than are other methods of authentication however, it is also "harder to crack." (Al-Saidi, 2011)

According to Abdalla and Reyzin (2000) a key-evolving signature scheme is one in which the operation is partitioned into periods with a different secret key for each period. Each secret key is utilized for message signing only during a specific period and for competition of a new secret key when that period has ended. Abdalla and Reyzin (2000) report "The verification algorithm checks not only that a signature is valid, but also that it was generated during a specific time period." This type of scheme is reported as 'forward-secure' if the scheme is not feasible for an "adaptive chosen-message adversary to forge signature for past time periods, even if it discovers the secret key for the current time period." Stated as implications is that past secret keys are unrecoverable from the current one however, in a forward-secure signature scheme it is reported that should the current secret key be comprised the past time period signatures can still be trusted.

II. Components of Digital Signature Scheme

A signature scheme is reported to contain the components as follows:

(1) A security parameter k, which is chosen by the user when he creates his public...

The parameter k determines a number of quantities (length of signatures, length of signable messages, running time of the signing algorithm, overall security, etc.).
(2) A message space, which is the set of messages to which the signature algorithm may be applied. Without loss of generality, we assume in this paper that all messages are represented as binary strings, that is, {0, 1}/. To ensure that the entire signing process is polynomial in the security parameter, we assume that the length of the messages to be signed is bounded by kc, for some constant c > 0.

(3) A signature bound B, which is an integer bounding the total number of signatures that can be produced with an instance of the signature scheme. This value is typically bounded above by a low-degree polynomial in k, but may be infinite.

(4) A key generation algorithm G, which any user A can use on input 1k (i.e., k in unary) to generate in polynomial time a pair (PA, S) of matching public and secret keys. The secret key is sometimes called the trap-door information.

(5) A signature algorithm r, which produces a signature r (M, SA) for a message M. using the secret key SA. Here o- may receive other inputs as well. For example, in the scheme we propose first, o- has an additional input, which is the number of previously signed messages.

(6) A verification algorithm V, which tests whether S. is a valid signature for message M. using the public key PA. (That is, V (S, M, PA) will be true if and only if it is valid.) Any of the above algorithms may be "randomized" algorithms that make use of auxiliary random bit stream inputs. We note that G. must be a randomized algorithm, since part of its output is the secret key, which must be unpredictable to an adversary. The signing algorithm r may be randomized -- we note in particular that our signing algorithm is randomized and is capable of producing many different signatures for the same message. In general, the verification algorithm need not be randomized, and ours is not. (Goldwasser, Micali and Rivest, 1988)

III. Types of Attacks

The types of attacks are reported to be inclusive of the following types:

(1) Key-only attacks in which the enemy knows only the real signer's public key, and (2) Message attacks where the enemy is able to examine some signatures corresponding to either known or chosen-messages before his attempt to break the scheme. (Goldwasser, Micali and Rivest, 1998)

IV. Four Types of Message Attacks

Four kinds of message attacks, which are reported to be "characterized by how the messages whose signatures the enemy sees are chosen." (A denotes the user whose signature method is being attacked)

(1) Known-message attack. The enemy is given access to signatures for a set of messages ml,, mr. The messages are known to the enemy but are not chosen by him.

(2) Generic chosen-message attack. Here the enemy is allowed to obtain from A valid signatures for a chosen list of messages ml,," mt before he attempts to break A's signature scheme. These messages are chosen by the enemy, but they are fixed and independent of A's public key (for example the mi's may be chosen at random). This attack is nonadaptive: the entire message list is constructed before any signatures are seen. This attack is "generic" since it does not depend on the A's public key; the same attack is used against everyone.

(3) Directed chosen-message attack. This is similar to the generic chosen-message attack, except that the list of messages to be signed may be created after seeing A's public key but before any signatures are seen. (The attack is still nonadaptive.) This attack is "directed" against a particular user A.

(4) Adaptive chosen-message attack. This is more general yet: here the enemy is also allowed to use A as an "oracle"; not only may he request from A signatures of messages which depend on A's public key but he may also request signatures of messages which depend additionally on previously obtained signatures. (Goldwasser, Micali and Rivest, 1988)

V. Previous Digital Signature Schemes

Previous digital signature schemes used include those stated as follows:

(1) Trap-door signature schemes: this includes any trap-door signature scheme being at risk of being forged through use of a key only attack because a valid pair is able to be created through starting with a random signature ah application of the public verification algorithm to obtain the corresponding message. A common method for dealing with this issue is to make a requirement…