How did the signature algorithm come from?

Analysis of digital signature algorithm and Hash signature

Preface: It took me nearly a week to finish this article, and the RSA algorithm involved in it was introduced in detail in the last public key cryptosystem. At present, people still use 512-bit and 124-bit RSA algorithms in digital signature.

Abstract: Digital signature and certification authority are the core technologies of e-commerce. Digital signature, as an important technology of e-commerce in the Internet, has been continuously improved and standardized. Based on the significance of digital signature, this paper introduces the contents and algorithms involved in digital signature in detail, and improves them by combining them.

Keywords: Internet public key encryption Hash function e-commerce encryption digital signature

Introduction to digital signature

We have a certain understanding of encryption and decryption algorithms, so we can further discuss the problem of "digital signature" (be careful not to confuse it with digital authentication), that is, how to sign a computer file. Digital signature can be realized by symmetric algorithm or public key algorithm. However, the former requires third-party authentication in addition to both the document signer and the document receiver, which is more troublesome; Through the implementation method of public key encryption algorithm, because the file encrypted with the secret key needs to be decrypted by the public key, it can be used as a digital signature. The signer encrypts a signature with the secret key (which can include information such as name, certificate number and short message), and the receiver can decrypt it with the public and own public key. If successful, it can ensure that the information comes from the owner of the public key.

The basic principle of public key cryptosystem to realize digital signature is very simple. Assuming that A wants to send an electronic file to B, both parties A and B only need to go through the following three steps:

1. A encrypts the file with its private key, which is the signing process

2. A sends the encrypted file to B

3. B uses A's public key to unlock the file sent by A

. That is,

signature can be confirmed,

signature can't be forged,

signature can't be reused,

file can't be tampered with after being signed,

signature is undeniable, and

digital signature is an alphanumeric string obtained by processing the message to be transmitted through a one-way function to authenticate the source of the message and verify whether the message has changed. Using these strings instead of writing a signature or seal has the same legal effect as writing a signature or seal. The international community has begun to formulate corresponding laws and regulations, taking digital signature as the basis for law enforcement.

methods to realize digital signature

there are many methods to realize digital signature. at present, public key encryption technology is widely used in digital signature, such as PKCS (public key cryptography standards), DSA(Digital Signature Algorithm), x.59 and PGP(Pretty Good Privacy) based on RSA Data Security company. In 1994, American Institute of Standards and Technology published Digital Signature Standard (DSS), which made public key encryption technology widely used. At the same time, applying Hash algorithm is also a method to realize digital signature.

Asymmetric key cryptography algorithm for digital signature

Meaning of the algorithm:

Asymmetric key cryptography algorithm uses two keys: public key and private key, which are used to encrypt and decrypt data respectively, that is, if the public key is used to encrypt data, only the corresponding private key can be used to decrypt it; If the data is encrypted with a private key, it can only be decrypted with the corresponding public key.

the common encryption standards for digital signature using public key cryptography are RSA, DSA, Diffie－Hellman, etc.

Signature and verification process:

The sender (A) first transforms the message with a public one-way function to obtain a digital signature, and then encrypts the digital signature with a private key and sends it together with the message.

the receiver (b) decrypts and exchanges the digital signature with the public key of the sender to obtain a plaintext of the digital signature. The sender's public key can be issued by a trusted technical management organization, namely the Certificate Authority (CA).

the receiver calculates the obtained plaintext through a one-way function, and also obtains a digital signature, and then compares the two digital signatures. If they are the same, it proves that the signature is valid, otherwise it is invalid.

This method enables anyone who has the sender's public key to verify the correctness of the digital signature. Because of the confidentiality of the sender's private key, the receiver can not only reject the message according to the result, but also make it impossible to forge the message signature and modify the message, because the digital signature is a set of fixed-length codes representing the characteristics of the message, and the same person will produce different digital signatures for different messages. This solves the problem that the bank sends a check through the network, and the receiver may change the amount of the check, and also avoids the possibility of the sender evading responsibility.

symmetric key cryptography algorithm for digital signature

algorithm meaning

The encryption key and decryption key used in symmetric key cryptography algorithm are usually the same, and even if they are different, the other can be easily deduced from either one. In this algorithm, the keys used by both encryption and decryption should be kept secret. Because of the computer speed, it is widely used in the encryption process of a large number of data such as files, such as RD4 and DES. It is not recommended to use IDEA as digital signature.

the common encryption standards for digital signature using block cipher algorithm are DES, tripl-des, RC2, RC4, cast, etc.

signature and verification process

Lamport invented a symmetric algorithm called Lamport-Diffle: a set of keys A, whose length is twice the number of bits (n) of the message, is used to generate verification information for the signature, that is, 2n numbers b are randomly selected, and the 2n numbers b are encrypted and exchanged by the signature key to obtain another set of 2n numbers c..

the sender starts from the first bit of the message packet m and checks the I-bit of m in turn. If it is , it takes the I-bit of the key A, and if it is 1, it takes the i+1-bit of the key A; Until all messages are checked. The selected n key bits form the final signature.

when the receiver verifies the signature, it also checks the message m in turn from the first bit. If the I-bit of m is , it thinks that the I-group information in the signature is the I-bit of key A, and if it is 1, it is the i+1-bit of key A.: Until the message is completely verified, n keys are obtained. Because the receiver has the verification information c of the sender, the obtained n keys can be used to check the verification information, so as to confirm whether the message is sent by the sender.

Because this method is signed bit by bit, only one bit has been changed, and the receiver can't get the correct digital signature, so its security is good. Its disadvantages are: the signature is too long (compressing the message before signing can reduce the length of the signature); The signature key and the corresponding verification information cannot be reused, otherwise it is extremely unsafe.

Improvement of combining symmetric and asymmetric algorithms

Symmetric and asymmetric algorithms have their own advantages and disadvantages, so the improvement combined with their respective advantages and disadvantages can be explained by the following module:

Hash algorithm for digital signature

Hash algorithm is also called hash algorithm or message digest, and it will be explained in detail in digital signature algorithm.

the general encryption standards of digital signature based on p>Hash algorithm are: sha-1, MD5, etc.

digital signature algorithm

there are many algorithms for digital signature, and the three most widely used are: Hash signature, DSS signature and RSA signature. These three algorithms can be used separately or together. Digital signature is realized by encrypting and decrypting data through cryptographic algorithms. Commonly used HASH algorithms include MD2, MD5 and SHA-1, and digital signature can be realized by DES algorithm and RSA algorithm. But there are more or less defects or no mature standards.

Hash signature

Hash signature is the most important digital signature method, which is also called digital digest and digital finger print. Unlike RSA digital signature, which is a separate signature, this digital signature method closely links the digital signature with the information to be sent, which is more suitable for e-commerce activities. Combining the individual content of a business contract with the signature increases the credibility and security more than transmitting the contract and the signature separately. Below we will introduce the functions and algorithms in Hash signature in detail.