Shulou(Shulou.com)06/03 Report--

A quick introduction to blockchain (6)-- related technologies of blockchain cryptography and security I. brief introduction of blockchain cryptography security technology

The latest achievements of cryptography and security technology are widely used in blockchain and distributed account books, especially the technologies related to identity authentication and privacy protection. Block chain uses cryptographic security-related technologies including Hash algorithm and digest, encryption algorithm, digital signature and certificate, PKI system, Merkle tree, Bloom filter, homomorphic encryption and so on, to design and realize the confidentiality, integrity, authentication and non-repudiation of block chain.

2. Hash algorithm and Digital Abstract 1. Brief introduction of Hash algorithm

Hash (hash or hash) algorithm, often referred to as fingerprint or digest algorithm, can map a binary plaintext string of arbitrary length to a shorter (usually fixed-length) binary string (Hash value), and it is difficult for different plaintext to map to the same hash value.

The requirements of excellent Hash algorithm:

A, forward fast

Given the original text and Hash algorithm, the hash value can be calculated in limited time and limited resources.

B, reverse difficulty

Given (several) Hash values, it is almost impossible to deduce the original text in a finite time.

C, input sensitivity

Any change in the original input information should result in a significant change in the newly generated hash value.

D, anti-collision

It is difficult to find two plaintext with different contents so that their hash values are the same (that is, collisions occur).

2. Common Hash algorithms

At present, the common Hash algorithms include the international Message Digest (MD series and Secure Hash Algorithm (SHA) series algorithms and the domestic SM3 algorithm.

MD algorithm mainly includes two algorithms: MD4 and MD5. MD4 (RFC 1320) was designed by MIT's Ronald L.Rivest in 1990 and its output is 128bit. MD4 has proved to be insecure. MD5 (RFC 1321) is an improved version of MD4 made by Rivest in 1991. The input is still grouped in 512 bits, and the output is 128bit. MD5 is more secure than MD4, but the process is more complex and the calculation is a little slower. MD5 was successfully collided in 2004, and its security is not enough to be used in business scenarios.

The SHA algorithm is solicited by the American National Institute of Standards and Technology (National Institute of Standards and Technology,NIST). The first implementation of the SHA-0 algorithm came out in 1993 and was cracked in 1998. The subsequent revised version of the SHA-1 algorithm was introduced in 1995 and output as a hash value of 160 bits in length for better security. SHA-1 was successfully collided in 2005 and can no longer meet commercial needs. In order to improve security, NIST later developed more secure SHA-224, SHA-256, SHA-384 and SHA-512 algorithms (collectively referred to as SHA-2 algorithms). A new generation of SHA-3 related algorithms are being studied at present.

The China cryptographic Administration issued GM/T0004-2012 "SM3 Cipher Hash algorithm" on December 17,2010. it established the open Hash algorithm standard in domestic commercial cryptographic system, and has been widely used in digital signature and authentication scenarios.

3. The performance of Hash algorithm.

Most Hash algorithms are computationally sensitive and can be done faster on powerful computing chips. Therefore, hardware acceleration can be considered to improve the performance of Hash computing. For example, using ordinary FPGA to calculate the SHA-256 value, you can easily achieve the throughput of several Gbps, using a special chip will be even higher.

A few Hash algorithms are not computationally sensitive, such as scrypt algorithm, whose computing process requires a lot of memory resources, so it is difficult to accelerate Hash computing by selecting high-performance chips, which can effectively prevent the use of special chips for computing power.

4. Digital summary

Digital digest is one of the important uses of Hash algorithm. Digital digest is the Hash operation of the original digital content to obtain the only summary value.

Taking advantage of the collision resistance of the Hash function, the digital summary can detect whether the content has been tampered with.

When some websites provide file download, they will also provide the corresponding digital summary value. After downloading the original file, the user can calculate the summary value locally and compare it with the summary value provided to ensure that the content of the file has not been tampered with.

5. Hash*** and Protection

Hash algorithm is not an encryption algorithm and can not be used to protect information. But the Hash algorithm can be applied to save the login password. For example, when the website logs in, it needs to verify the user name and password. If the background of the website directly saves the original text of the user's password, the consequences of database leakage will be unimaginable.

Using the anti-collision feature of Hash, the background database can only save the hash value of the user's password, and each time the hash value can be compared to determine whether the input password is correct or not. Even if the database is compromised, the password cannot be easily restored from the hash value.

However, if the security strength of the password set by the user is not enough, some common strings are used, such as password, 123456 and so on. Some people specially collect common passwords, calculate the corresponding hash values, and make dictionaries. You can quickly reverse the original passwords by looking up the hash values of the dictionary, such as dictionaries * * and rainbow tables * * (only the beginning and end values of a Hash chain are saved, and relative dictionaries * * can save storage space).

In order to prevent dictionary, rainbow table and other methods, we can use the method of adding salt (Salt). What is saved is not the direct hash value of the original text, but the hash value of the original text plus a random string (that is, "salt"). Hash results and "salt" are stored in different places, as long as they are not leaked at the same time, it is difficult for people to crack.

3. Encryption and decryption algorithm 1. Brief introduction of encryption and decryption system

Encryption and decryption algorithm is the core technology of modern cryptography, which can be divided into two basic types from the design concept and application scenarios: symmetric encryption and asymmetric encryption.

Typical components of modern encryption and decryption systems include algorithms and keys (including encryption keys and decryption keys). Among them, the encryption and decryption algorithm itself is fixed and generally visible; the key is the most critical information, which needs to be safely saved and even protected by special hardware. Generally speaking, the key needs to be randomly generated according to a specific algorithm before encryption, and the longer the length, the greater the encryption intensity.

In the process of encryption, the plaintext is encrypted by the encryption algorithm and encryption key, and the plaintext is obtained by decrypting the ciphertext through the decryption algorithm and decryption key.

The typical process of encryption and decryption is as follows:

According to whether the keys used in the encryption and decryption process are the same, the algorithm can be divided into symmetric encryption (Symmetric Cryptography) and asymmetric encryption (Asymmetric Cryptography). The two models are suitable for different needs and complement each other. It can be combined in some scenarios to form a hybrid encryption mechanism.

2. Symmetric encryption algorithm

Symmetric encryption algorithm, the encryption and decryption process of the key is the same.

The symmetric encryption algorithm has the advantages of high encryption and decryption efficiency (high speed, small space consumption) and high encryption strength. The disadvantage of the symmetric encryption algorithm is that the participants need to hold the key in advance, and once someone leaks, the security of the system will be compromised; it is a problem to distribute the key in advance in the insecure channel, which needs to be realized by additional Diffie-Hellman negotiation protocol or asymmetric encryption algorithm.

Symmetric ciphers can be divided into two types: block ciphers and sequence ciphers. The former divides plaintext into fixed-length data blocks as the basic encryption unit, which is the most widely used. The latter encrypts only one byte or character at a time, and the password is constantly changing and is only used in specific areas (such as digital media encryption).

The representative algorithms of packet symmetric encryption include DES, 3DES, AES, IDEA and so on.

DES (Data Encryption Standard): a classical block encryption algorithm, the Federal Information processing Standard (FIPS) adopted FIPS-46-3 in 1977 to encrypt 64-bit plaintext to 64-bit ciphertext. Its key length is 64 bits (including 8-bit check code) and is now easy to be cracked by brute force.

3DES: triple DES operation, encryption-- > decryption-- > encryption, processing process and encryption strength are better than DES, but are now considered to be insecure.

AES (Advanced Encryption Standard): adopted by the American National Standards Institute (NIST), it replaces DES as the standard for symmetric encryption. From 1997 to 2000, NIST selected Rijndael algorithm (invented by Belgian cryptographers Joan Daemon and Vincent Rijmen) as AES from 15 candidate algorithms, and the standard is FIPS-197. AES is also a grouping algorithm, with packet lengths of 128,192,256 bits. The advantage of AES lies in its fast processing speed, the whole process can be described mathematically, and there is no effective means to crack it at present.

IDEA (International Data Encryption Algorithm): proposed jointly by cryptographer James Massey and Lai Xuejia in 1991. The design is similar to 3DES, the key length is increased to 128bits, and has better encryption strength.

Sequence encryption, also known as stream encryption. In 1949, Claude Elwood Shannon (founder of information theory) proved for the first time that absolute security and perfect confidentiality (Perfect Secrecy) could be achieved through the symmetric encryption of a "one-time passbook". That is, each time, both sides of the communication use a random key string as long as the plaintext to encrypt the plaintext. Sequence ciphers adopt a similar idea and generate pseudo-random key strings each time through a pseudo-random number generator. Representative algorithms include RC4 and so on.

The symmetric encryption algorithm is suitable for the encryption and decryption process of a large number of data; it can not be used in signature scenarios; and keys need to be distributed securely in advance.

Block encryption can only deal with fixed-length plaintext at a time, so it is necessary to use a certain mode to segment too long content. In practical Cryptography, it is recommended to use ciphertext grouping chain (Cipher Block Chain,CBC), counter (Counter,CTR) and other modes.

3. Asymmetric encryption algorithm

Asymmetric encryption is a great invention of modern cryptography, which effectively solves the problem that symmetric encryption requires secure distribution of keys.

The encryption key and decryption key of asymmetric encryption algorithm are different, which are called public key (Public Key) and private key (Private Key) respectively. The private key is generally generated by the random number algorithm, and the public key can be generated according to the private key. The public key is generally public and accessible to others, while the private key is held by the individual and closely protected and cannot be obtained by others.

The advantage of asymmetric encryption algorithm is that public and private keys are separated, and there is no need for secure channels to distribute keys. The disadvantage is that the processing speed (especially the key generation and decryption process) is often slow, which is generally 2 or 3 orders of magnitude slower than the symmetric encryption algorithm; at the same time, the encryption strength is not as strong as symmetric encryption.

The security of asymmetric encryption algorithms is often based on mathematical problems, including classical mathematical problems such as prime factorization of large numbers, discrete logarithms, elliptic curves and so on.

The representative algorithms of asymmetric encryption algorithms include RSA, ElGamal, Elliptic Curve Crytosystems,ECC, SM2 and so on.

RSA: a classical public key algorithm proposed by Ron Rivest, Adi Shamir and Leonard Adleman in 1978, for which they won the Turing Award in 2002. RSA algorithm takes advantage of the difficulty of prime factorization of large numbers, but there is no mathematical proof that the two are of equal difficulty. Perhaps there are unknown algorithms that can bypass the decomposition of large numbers and decrypt them.

ElGamal: designed by Taher ElGamal, it takes advantage of the difficulty of finding discrete logarithms under modular operation, and generates keys faster than RSA, so it is used in security tools such as PGP.

Elliptic curve algorithm (Elliptic Curve Cryptography,ECC): a series of algorithms that have attracted much attention in modern times, which is based on the fact that it is difficult to calculate the inverse multiplication of specific points on the elliptic curve. It was first proposed by Neal Koblitz and Victor Miller independently in 1985. ECC series algorithms are generally considered to have high security, but the encryption and decryption process is time-consuming.

SM2 (ShangMi 2): Chinese national commercial cipher algorithm standard, issued by China Cryptography Administration on December 17, 2010. it is also based on elliptic curve algorithm, and its security strength is generally considered to be better than that of RSA series algorithm.

Asymmetric encryption algorithm is suitable for signature scenarios or key negotiation process, but it is not suitable for the encryption and decryption of large amounts of data.

RSA algorithms are considered to be difficult to resist the cracking of modern computing devices, and it is generally recommended that the key should be at least 2048 bits in commercial scenarios. If the elliptic curve algorithm with higher security strength is adopted, the 256-bit key can meet most of the security requirements.

4. Select plaintext *

In asymmetric encryption, the public key is public, so anyone can use the public key to encrypt a given plaintext, obtain the corresponding ciphertext, achieve the purpose of cracking, and bring the risk of choosing plaintext.

In order to avoid this risk, modern asymmetric encryption algorithms (such as RSA, ECC) have introduced a certain protection mechanism: encrypting the same plaintext with the same key many times, the result is completely different, avoiding the destruction of choosing plaintext.

There can be a variety of ideas in implementation. One is to deform the plaintext and add random strings or tags, and then deal with the results after adding. The other is to use the randomly generated temporary key to encrypt the plaintext symmetrically, and then encrypt the symmetric key, that is, to use the multi-layer encryption mechanism.

5. Hybrid encryption mechanism

The hybrid encryption mechanism combines the advantages of both symmetric encryption and asymmetric encryption.

The main process of the hybrid encryption mechanism is as follows: first, a temporary symmetric encryption key (or session key) is negotiated by asymmetric encryption (high computational complexity). Then the two sides use the symmetric encryption algorithm (low computational complexity) to encrypt a large amount of data quickly.

A typical application case is the more and more common communication protocol used in websites-secure Hypertext transfer Protocol (Hyper Text Transfer Protocol Secure,HTTPS).

Different from the HTTP protocol which transmits data in clear text, HTTPS introduces Transport Layer Security/Secure Socket Layer (TLS/SSL) encryption layer between the traditional HTTP layer and the TCP layer to achieve secure transmission.

SSL protocol is a standard protocol adopted in the early days of HTTPS. It was first designed and implemented by Netscape in 1994. Its two main versions (including v2.0 and v3.0) have been widely used. SSL is vulnerable to security flaws (such as POODLE and DROWN***) and cannot meet modern security needs. It was abandoned by IETF in 2011 and 2015. Based on SSL protocol (v3.1), IETF proposed an improved security standard protocol TLS, which has become a widely used scheme. In 2008, the TLS1.2 version was released, which fixed many loopholes in the previous version, greatly enhanced security, and recommended for commercial scenarios. In addition to Web services, TLS protocol is also widely used in FTP, Email, real-time messaging, audio and video calls and other fields.

In the scene.

Message authentication code and digital signature 1. Message authentication code

Message authentication code (Hash-based Message Authentication Code,HMAC), which uses symmetric encryption to protect message integrity (Integrity).

The basic process is to process a message using the symmetric key shared in advance and the Hash algorithm to get the HMAC value. The HMAC value holder can prove to the other party that he or she has a symmetric key and ensure that the content of the transmitted message has not been tampered with.

A typical HMAC generation algorithm includes three parameters: K _ (Magi) H _ (1) M. K is the symmetric key shared in advance, H is the pre-agreed Hash algorithm (such as SHA-256), and M is the content of the message to be transmitted. If any of the three parameters are missing, the correct HMAC value cannot be obtained.

Message authentication codes can be used in simple identification scenarios. For example, Alice and Bob share K and H in advance. Alice needs to know whether the other party is Bob or not, and can send a message M to Bob. After Bob to M, calculate its HMAC value and return it to Alice,Alice to verify the correctness of the received HMAC value can verify whether the other party is really Bob.

The main problem of message authentication code is that the key needs to be shared in advance, and when the key may be owned (or even leaked) by multiple parties at the same time, it is impossible to track the true source of the message.

2. Digital signature

A digital signature can not only confirm the integrity of a digital content, but also confirm its source (that is, Non-Repudiation).

A typical scenario is that Alice sends a file (a message) to Bob over the channel. How does Bob know that the file received is the original version sent by Alice? Alice can first summarize the contents of the file, then encrypt (sign) the summary with its own private key, and then send both the file and the signature to Bob. After receiving the file and the signature, Bob uses the public key of Alice to decrypt the signature and get a digital summary, which is compared with the result of the summary of the file. If it is consistent, it means that the file is indeed sent by Alice (because no one else can own the private key of Alice), and the contents of the file have not been modified (the summary results are consistent).

In theory, all asymmetric encryption algorithms can be used to implement digital signatures. In practice, common algorithms include DSA (Digital Signature Algorithm, based on ElGamal algorithm) proposed by NIST in August 1991 and ECSDA (Elliptic Curve Digital Signature Algorithm, based on elliptic curve algorithm) with higher security strength.

In addition to the ordinary digital signature application scenarios, according to some specific security requirements, some special digital signature techniques are produced, including blind signature, multi-signature, group signature, ring signature and so on.

3. Blind signature

Blind signature (Blind Signature) was proposed by David Chaum in his paper "Blind Signatures for Untraceable Payment" in 1982. The signer needs to sign the information without seeing the original content.

Blind signature can protect the signed content and prevent the signer from seeing the original content; on the other hand, blind signature can also achieve anti-tracking (Unlinkability), the signer can not correspond to the signature content and the signature result. Typical implementations include RSA blind signature algorithm and so on.

4. Multi-signature

Multi-signature (Multiple Signature), that is, among n signers, it is considered legal to collect at least m (n > = m > = 1) signatures. Where n is the number of public keys provided and m is the minimum number of signatures that need to match the public key.

Multi-signature can be effectively applied in the scenario where multiple people vote together to make decisions. For example, the two parties negotiate, and the third party acts as the auditor. Any two of the three parties can reach an agreement to complete the negotiation.

Multiple signatures are supported in bitcoin transactions, which enables multiple people to jointly manage bitcoin transactions in an account.

5. Group signature

Group signature (Group Signature), that is, a member of a group can sign anonymously on behalf of the group. The signature verifies that it comes from the group, but cannot trace exactly which member signed.

A group signature requires a group administrator to add new group members, so there is a risk that the group administrator may trace signature membership.

Group signature was first proposed by David Chaum and Eugene van Heyst in 1991.

6. Ring signature

Ring signature (Ring Signature) was first proposed by three cryptographers Rivest,Shamir and Tauman in 2001. Ring signature is a kind of simplified group signature.

The signer first selects a temporary collection of signers, including the signer himself. Then the signer can use his own private key and the public key of others in the signature set to generate the signature independently without the help of others. Other members of the signer collection may not know that they are included in the final signature.

Ring signature also has many uses in protecting anonymity.

5. Digital certificate 1. Brief introduction of digital certificate

For asymmetric encryption algorithms and digital signatures, a very important step is the distribution of public keys. In theory, anyone can get the public key. However, is it possible that the public key file is forged and may be tampered with in the process of transmission? once there is something wrong with the public key itself, the security built on it will no longer be established.

The purpose of digital certificate mechanism is to solve the problem of public key distribution and to ensure the legitimacy of the recorded information. For example, prove that a public key is owned by an entity (individual or organization), and ensure that any tampering can be detected, so as to achieve the secure distribution of the user public key.

According to the purpose of the protected public key, digital certificates can be divided into encrypted digital certificates (Encryption Certificate) and signature verification digital certificates (Signature Certificate). The former is often used to protect the public key used for encryption purposes, while the latter protects the public key used for signature purposes. Both types of public keys can be placed in the same certificate at the same time.

In general, certificates need to be issued and endorsed by a certificate certification authority (Certification Authority,CA). Authoritative commercial certificate certification bodies include DigiCert, GlobalSign, VeriSign and so on. Users can also build their own local CA system and use it in the VPC.

2. X.509 Certificate Specification

Usually, the content of a digital certificate may include certificate domain (certificate version, serial number, signature algorithm type, issuer information, validity period, issued subject, issued public key), CA signature algorithm and signature value of the certificate, and so on. At present, the most widely used standard is the v3 version specification (RFC5280) of X.509 jointly developed by ITU and ISO, which defines the following certificate information fields:

Version number (Version Number): the version number of the specification, which is currently version 3, with a value of 0x2

Serial number (Serial Number): a unique serial number assigned to each certificate issued, maintained by CA, to track and revoke the certificate. As long as you have the issuer information and serial number, you can uniquely identify a certificate. The maximum is 20 bytes.

Signature algorithm (Signature Algorithm): the algorithm used for digital signatures, such as sha256WithRSAEncryption or ecdsa-with-SHA256

Issuer (Issuer): information about the unit that issued the certificate, such as "ClearCNGradeStart Beijing"

Lhasa Beijingjingjingjiao org.example.com.center.org.example.com "

Validity period (Validity): the validity period of the certificate, including the starting and ending time (e.g. Not Before 2018-08-08-00-00UTC After not After 2028-08-08-00-00UTC)

Subject: identification information (Distinguished Name) of the certificate owner, such as "C=CN, ST=Beijing, L=Beijing, CN=personA.org.example.com"

Principal public key information (Subject Public Key Info): protected public key related information

A. Public key algorithm (Public Key Algorithm): the algorithm adopted by the public key

B. Principal public key (Subject Public Key): the content of the public key

Issuer unique number (Issuer Unique Identifier, optional): represents the unique information of the issuer. Only versions 2 and 3 are supported. Optional.

Principal unique number (Subject Unique Identifier, optional): represents the unique information that owns the certificate entity. Only versions 2 and 3 are supported. Optional.

Extensions (Extensions, optional): optional extensions. May include:

Subject Key Identifier: the key identifier of the entity, which distinguishes multiple pairs of keys of the entity

Basic Constraints: generally indicates whether the certificate belongs to a CA

Authority Key Identifier: the public key identifier of the issuer who issued this certificate

Authority Information Access: issue related service addresses, such as issuer certificate acquisition address and revocation certificate list information query address

CRL Distribution Points: the address where the certificate revocation list was published

Key Usage: indicates the purpose or function of the certificate, such as Digital Signature, Key CertSign

Subject Alternative Name: alias of the certificate identity entity, such as the certificate can be the same table .org.example.com, org.example.com,.example.com,example.com identity, and so on.

In addition, the issuer of the certificate needs to sign the certificate content with his own private key to prevent others from tampering with the certificate content.

3. Certificate format

The X.509 specification generally recommends the use of PEM (Privacy Enhanced Mail) format to store certificate-related files. The file name suffix of the certificate file is .crt or .cer, the file name suffix of the corresponding private key file is .key, and the file name suffix of the certificate request file is .csr. Sometimes .pem is used as the file name suffix.

PEM format is stored in the form of text, which generally includes head and tail tags and content blocks, which are encoded by base64.

For example, the PEM format of a sample certificate file is as follows.

-BEGIN CERTIFICATE-MIICMzCCAdmgAwIBAgIQIhMiRzqkCljq3ZXnsl6EijAKBggqhkjOPQQDAjBmMQswCQYDVQQGEwJVUzETMBEGA1UECBMKQ2FsaWZvcm5pYTEWMBQGA1UEBxMNU2FuIEZyYW5jaXNjbzEUMBIGA1UEChMLZXhhbXBsZS5jb20xFDASBgNVBAMTC2V4YW1wbGUuY29tMB4XDTE3MDQyNTAzMzAzN1oXDTI3MDQyMzAzMzAzN1owZjELMAkGA1UEBhMCVVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcTDVNhbiBGcmFuY2lzY28xFDASBgNVBAoTC2V4YW1wbGUuY29tMRQwEgYDVQQDEwtleGFtcGxlLmNvbTBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABCkIHZ3mJCEPbIbUdh/Kz3zWW1C9wxnZOwfyyrhr6aHwWREW3ZpMWKUcbsYup5kbouBc2dvMFUgoPBoaFYJ9D0SjaTBnMA4GA1UdDwEB/wQEAwIBpjAZBgNVHSUEEjAQBgRVHSUABggrBgEFBQcDATAPBgNVHRMBAf8EBTADAQH/MCkGA1UdDgQiBCBIA/DmemwTGibbGe8uWjt5hnlE63SUsXuNKO9iGEhVqDAKBggqhkjOPQQDAgNIADBFAiEAyoMO2BAQ3c9gBJOk1oSyXP70XRk4dTwXMF7qR72ijLECIFKLANpgWFoMoo3W91uzJeUmnbJJt8Jlr00ByjurfAvv-END CERTIFICATE-

You can view its contents through the openssl tool, using the following:

Openssl x509-in example.com-cert.pem-noout-text

In addition, there is DER (Distinguished Encoding Rules) format, which saves certificates in binary and can be converted to and from PEM format.

3. Certificate trust chain

A large amount of information is recorded in the certificate, the most important of which includes the signed public key and CA digital signature. Therefore, as long as you use the public key of CA to sign the certificate again, you can prove whether the recorded public key is legal or not.

Whether the public key of CA is legal or not, on the one hand, it can be authenticated by the certificate issued by the upper CA; on the other hand, some root CA (Root CA) can realize the trust basis by pre-distributing the certificate. For example, in mainstream operating systems and browsers, some authoritative CA certificates are usually preset in advance (by signing their own private keys, the system acknowledges that they are legitimate certificates). All intermediate CA (Intermediate CA) and subsequent CA certified based on the preset authority CA will be verified to be legal. From the pre-trusted root certificate, through the middle-tier certificate, to the lowest entity certificate, a complete certificate trust chain is formed.

Sometimes when using a browser to visit some websites, users may be prompted whether to trust each other's certificate. Indicates that the website certificate cannot be verified by the certificate trust chain in the current system and requires additional check. In addition, when any certificate on the trust chain is unreliable, all subsequent certificates that depend on it will lose security.

Therefore, as the basis of public key trust, the security management of certificate life cycle is very important.

VI. PKI system 1. Brief introduction of PKI

According to the X.509 specification, the public key can be protected by the certificate mechanism, but the steps of certificate generation, distribution and revocation are not involved. In order to manage and distribute certificates securely, we need to follow the PKI (Public Key Infrastructure) system. The PKI system provides a complete framework for certificate management, including the processes of generation, issuance and revocation, and solves the authentication and management problems related to the certificate life cycle.

PKI is a general framework for secure and reliable delivery of messages and identity confirmation based on public and private keys, and does not represent a specific cryptographic technology and process. The platform that implements the PKI specification can securely and reliably manage the keys and certificates of users in the network. At present, it includes a number of specific implementations and specifications, such as RSA's PKCS (Public Key Cryptography Standards) standard and OpenSSL and other open source tools.

Typically, PKI includes at least the following core components:

CA (Certification Authority): responsible for certificate issuance and revocation (Revoke), receiving requests from RA, is the core part, mainly to complete the maintenance of certificate information

RA (Registration Authority): verifies the user's identity, verifies the validity of the data, registers, and sends it to CA after verification.

Certificate database: store certificates, mostly in X.500 series standard format. You can cooperate with LDAP directory service to manage user information.

The common operation process is that the user applies for a certificate through RA registration, provides identity and authentication information, etc.; after CA audit, the certificate is manufactured and issued to the user. If the user needs to revoke the certificate, he or she needs to send a request to CA again.

2. Certificate issuance

To issue a certificate to a user by CA is actually to sign a user's public key using CA's private key. Anyone can verify the validity of the certificate with the public key of CA. If the verification is successful, the content of the user public key provided in the certificate is recognized, and the secure distribution of the user public key is realized.

User certificates can be issued in two ways. The public key and private key can be generated by the user, and then the public key content can be signed by CA (only the user holds the private key), or the certificate (containing the public key) and the corresponding private key can be directly generated by CA (both the user and CA hold the private key). In the former case, the user will first generate a private key and certificate application file (Certificate Signing Request, that is, csr file). The CSR file includes the user's corresponding public key and some basic information, such as a common name.

(common name, that is, cn), organizational information, geographical location, etc. CA only needs to sign the certificate request file, generate the certificate file, and issue it to the user. Throughout the process, the user can keep the privacy of the private key information and will not be known by other parties (including the CA party).

The process of generating certificate application files is not complicated, and users can easily use open source software openssl to generate csr files and corresponding private key files.

After installing openssl, you can execute the following command to generate the private key and the corresponding certificate request file:

Openssl req-new-keyout private.key-out for_request.csr

During the generation process, you need to enter information such as geographical location, organization, common name, and so on. The generated private key and csr file are stored in PEM format by default, and the content is base64 encoded.

The openssl tool provides the ability to view the plaintext of a file in PEM format, such as using the following command to view the plaintext of the generated csr file:

Openssl req-in for_request.csr-noout-text

If the private key is generated by the user, once the private key file is lost, the CA cannot recover it because it does not hold the private key information, which means that the content encrypted by the public key in the certificate cannot be decrypted.

3. Certificate revocation

The certificate will be invalidated after it expires, and the user can also take the initiative to apply to CA for the revocation of a certificate file. Because CA cannot forcibly reclaim digital certificates that have been issued, in order to realize the invalidation of certificates, it is often necessary to maintain a list of revoked certificates (Certificate Revocation List,CRL), which is used to record the serial numbers of revoked certificates. Therefore, in general, when you validate a certificate, you need to first check to see if the certificate is already recorded in the list. If it exists, the certificate cannot be verified. If not, the subsequent certificate verification process continues.

In order to facilitate the synchronization of revocation list information, IETF proposes the online Certificate status Protocol (Online Certificate Status Protocol,OCSP). The services that support this protocol can query the revoked certificate list information online in real time.

7. Brief introduction of Merkel Tree 1 and Merkel Tree

Merkel tree (also known as hash tree) is a typical binary tree structure, which is composed of a root node, a set of intermediate nodes and a set of leaf nodes. Merkel tree was first proposed by Merkle Ralf in 1980 and has been widely used in file systems and P2P systems. Its main features are as follows:

A. the lowermost leaf node contains the stored data or its hash.

B, non-leaf nodes (including intermediate nodes and root nodes) are hashes of the contents of their two child nodes.

Merkel tree can be extended to the case of multi-tree, where the content of a non-leaf node is the hash value of the content of all its child nodes.

Merkel tree records hash value layer by layer, which makes it have some unique properties. For example, any change in the underlying data is passed to its parent node, layer by layer along the path to the root of the tree. The value of the root of the tree actually represents a "digital summary" of all the underlying data.

2. Application scenario of Merkel tree

(1) quickly compare a large amount of data

The Merkel tree structure is constructed after sorting each set of data. When two Merkel trees have the same roots, the two sets of data they represent must be the same. Otherwise, it must be different.

Because the process of Hash calculation can be very fast, the preprocessing can be completed in a short time. The use of Merkel tree structure can bring huge comparative performance advantages.

(2) Quick positioning and modification

If the data in D1 is modified, it will affect N1Magi N4 and Root.

Once it is found that the value of a node such as Root changes, along Root-- > N4muri-> N1, the actual changed data block D1 can be quickly located through O (lgn) time at most.

(3) Zero knowledge proof

How to prove to others that a given content D0 is included in a set of data (D0.D3) without

Expose anything else.

For the Merkel tree shown in this article, announce the N1Magic N5PhenRoot. The verifier can easily detect the existence of D0 by calculating the root value and verifying whether it is consistent with the supplied value. No other information is available to the verifier throughout the process.

8. Bloom filter 1. Brief introduction of Bloom filter

The Bloom filter (Bloom Filter) was proposed by Burton Howard Bloom in his paper "Space/Time Trade-offs in Hash Coding with Allowable Errors" in 1970. Bloom filter is an efficient search structure based on Hash, which can quickly answer the question "whether an element is in a collection or not" (in constant time).

Because of its high efficiency, Bloom filter structure is widely used in the field of network and security, such as information retrieval (BigTable and HBase), spam rules, registration management and so on.

2. Quick search based on Hash

Hash can map arbitrary content to a fixed-length string, and the probability of mapping different content to the same string is very low, which forms a good generation relationship of "content-> index".

Given a content and storage array, fast content-based lookup can be achieved by constructing a Hash function so that the mapped hash value does not exceed the size of the array. For example, if the Hash value of the content "hello world" is "100th", it is stored on the 100th unit of the array. If you need to quickly find anything, such as whether the "hello world" string is in the storage system, just calculate the hash value in a constant time and view the corresponding elements in the system with the hash value.

However, when the mapped value is limited to a certain range (such as the size of the total group), it will be found that the probability of Hash conflict becomes higher, and the smaller the range, the greater the collision probability. In many cases, the size of the storage system can not be expanded indefinitely, resulting in a decline in the efficiency of the algorithm. In order to improve the space utilization, the Bloom filter structure is designed based on the idea of Hash algorithm.

3. The realization principle of Bloom filter.

The Bloom filter uses multiple Hash functions to improve space utilization.

For the same given input, multiple Hash functions calculate multiple addresses, each marked as 1 on these addresses of the bit string. When searching, perform the same calculation process and look at the corresponding elements. If both are 1, then there is a higher probability that the input exists.

Compared with a single Hash algorithm, Bloom filter greatly improves the space utilization, and can use less space to express the existence relationship of larger sets.

The basic idea of both Hash and Bloom filters is content-based addressing.

There is a conflict between the Hash function and the Bloom filter, and there are false positives (False Positive) in both methods, but there is absolutely no False Negative. Bloom filters usually have a low false positive rate in applications. For example, in the case of using 7 different Hash functions, recording 1 million data and using 2MB-sized bit strings, the overall error rate will be less than 1%. However, the false positive rate of the traditional Hash search algorithm will be close to 10%.

9. Homomorphic encryption 1. Introduction to homomorphic encryption

Homomorphic encryption (Homomorphic Encryption) is a special encryption method, which allows the ciphertext to be processed to get the result of encryption. That is, the ciphertext is processed directly, which is the same as encrypting the result after the plaintext is processed. From the point of view of abstract algebra, homogeneity is maintained.

Homomorphism comes from the field of algebra and generally includes four types: addition homomorphism, multiplication homomorphism, subtraction homomorphism and division homomorphism. If it satisfies both additive homomorphism and multiplicative homomorphism, it means algebraic homomorphism, that is, Full Homomorphic. If it satisfies four kinds of homomorphism at the same time, it is called arithmetic homomorphism.

For computer operations, the realization of full homomorphism means that homogeneity can be achieved for all processes. It can only realize the homogeneity of some specific operations, which is called specific homomorphism (Somewhat Homomorphic).

2. Problems and challenges of homomorphic encryption

The problem of homomorphic encryption was first proposed by Ron Rivest, Leonard Adleman and Michael L.Dertouzos in 1978, and RSA encryption algorithm was proposed in the same year. However, the first algorithm of "homomorphism" was not proposed and proved mathematically by Craig Gentry in "Fully Homomorphic Encryption Using Ideal Lattices" in 2009.

Algorithms that only satisfy additive homomorphisms include Paillier and Benaloh algorithms, and algorithms that only satisfy multiplicative homomorphisms include RSA and ElGamal algorithms.

Homomorphic encryption is of great significance in the era of cloud computing and big data. At present, although cloud computing brings advantages such as low cost, high performance and convenience, from a security point of view, users do not dare to put sensitive information directly on the third-party cloud for processing. If there is a more practical homomorphic encryption technology, then we can rest assured to use a variety of cloud services, while a variety of data analysis process will not disclose user privacy. After the encrypted data is processed by the third-party service, the encrypted result can only be decrypted by the user himself, and the third-party platform can not know any valid data information in the whole process.

On the other hand, homomorphic encryption is also a good complementarity for block chain technology. Using homomorphic encryption technology, the intelligent contract running on the block chain can deal with the ciphertext, but can not get the real data, which greatly improves the privacy security.

At present, homomorphic encryption schemes mainly include the following three types:

A. the scheme based on ideal lattice (ideal lattice)

The scheme based on ideal lattice proposed by Gentry and Halevi in 2011 can achieve the security strength of 72 bit, and the corresponding public key is about 2.3GB. At the same time, it takes dozens of minutes to refresh the ciphertext.

B. the scheme based on the integer upper approximation GCD problem

The scheme (and subsequent scheme) proposed by Dijk et al in 2010 adopts a more simplified conceptual model, which can reduce the size of the public key to the order of dozens of MB.

C. A scheme based on perturbed learning (Learning With Errors,LWE) problem

Brakerski and Vaikuntanathan proposed the relevant scheme around 2011; Lopez-Alt An and others designed the multi-key full-homomorphic encryption scheme in 2012, which is close to the needs of real-time multi-party secure computing.

At present, the known homomorphic encryption technology often requires higher computing time or storage cost, and there is still a gap in performance and strength compared with traditional encryption algorithms, but the attention in the field of homomorphic encryption technology has been very high.

3. Function encryption

One problem associated with homomorphic encryption is functional encryption. Homomorphic encryption protects the data itself, while function encryption protects the processing function itself, that is, processing the data without the third party seeing the processing process.

It has been proved that there is no arbitrary multi-key scheme for multiple general functions, but only one key for a particular function can be achieved at present.

Other safety technologies 1. Zero knowledge proof

Knowledge proof (Zero Knowledge Proof) is a process in which the verifier makes the verifier believe that an assertion is correct without providing any additional information to the verifier.

The proof process includes interactive and costly interactive.

For example, Alice proves to Bob that he knows a number, and in the process of proof, Bob can ask a series of questions in a certain order (such as the transformation of numbers plus some random numbers) to be answered by Alice, and finally make sure that Alice knows a number with a higher probability. In the process of proof, Bob cannot know or deduce any additional information (including the number itself) except that Alice does know the number, nor can he prove it to others with the proof of Alice (such as a video of the process of proof). Note that in this process, if Alice guesses the order of Bob problems in advance, there is a possibility of fraud.

The study of zero knowledge proof began with the paper "The Knowledge Complexity of Interactive Proof-Systems" written by Shafi Goldwasser et al in 1985. At present, it is generally believed that at least three conditions should be met:

A, Completeness: authentic proof allows the verifier to verify successfully.

B, Soundness: false proof can not guarantee to pass the verification, but there is a small probability exception in theory.

C, zero knowledge (Zero-Knowledge): if it is proved, no information other than the proved information can be obtained from the process of proof.

2. Verifiable random function

Verifiable random function (Verifiable Random Function,VRF) was first proposed by Silvio Micali (MIT), Michael Rabiny (Harvard University) and Salil Vadha (MIT) in the paper "Verifiable Random Functions" in 1999.

VRF discusses a special class of pseudorandom functions whose results can be verified in some scenarios.

For example, Alice has a public key competition and a corresponding private key Sk. Alice claims a verifiable random function F and an input x and calculates y = F (Sk, x). Bob can use Alice public key competition to verify the same x and F and prove that the result is indeed y. Because of the randomness of F, no one can predict the value of y.

VRF provides a widely accepted and verifiable random sequence that can be used for voting scenarios in distributed systems. At present, there is a consensus algorithm VBFT using VRF.

3. Quantum cryptography

Quantum cryptography (Quantum Cryptography) has received more and more attention with the research of quantum computing and quantum communication, and it is considered that it will have a great impact on the existing cryptographic security mechanisms.

The concept of quantum computing was first put forward by the physicist Feynman in 1981. the basic principle is that qubits can be in multiple coherent superposition states at the same time. In theory, a large amount of information can be expressed by a small number of qubits at the same time and processed at the same time, which greatly improves the speed of calculation. At present, quantum computing has shown the potential to surpass classical computing in some specific fields. For example, the Shor algorithm based on quantum computing (proposed in 1994) can theoretically realize large number factorization which is much faster than the classical computing speed.

In March 2016, human beings used the Shor algorithm to decompose the prime factor of the number 15 in a scalable way for the first time. At present, the widely used asymmetric encryption algorithms, including RSA based on large integer decomposition and ECC based on elliptic curve random numbers, will be easily cracked in the future. Of course, the modern cryptographic system will not collapse with the advent of quantum computing. On the one hand, quantum computing devices are still far away from practical general-purpose computers, and cryptographers can explore more secure cryptographic algorithms. On the other hand, many security mechanisms have not found quantum algorithms that can accelerate cracking, including digital signature (based on Hash), Lattice cipher, code-based cipher and so on.

Quantum communication can provide a mechanism for secure negotiation of keys, which is expected to achieve unconditionally secure "one-time passwords". Quantum communication is based on the quantum entanglement effect, and the two entangled quanta can synchronize the real-time states over a long distance. Once the channel is eavesdropped, both sides of the communication will know the situation and discard the leaked information of this transmission, which is very suitable for a large number of key distribution, such as the BB84 protocol proposed in 1984, which combines quantum channel and open channel to achieve secure key distribution.

One-time password was first proposed by Shannon to achieve absolutely secure symmetric encryption in theory. Its characteristic is that the key is really random and can only be used once; the length of the key is the same as that of the plaintext, and the encryption process is a binary XOR operation between the two.

4. Social Engineering

Cryptography and security have always been an important topic of great concern to academia and industry, and related technologies have been constantly developing and improving. However, even if there is a theoretically perfect technology, there is no perfect system. It seems that the well-designed system was finally broken, not because of deep-seated loopholes in the design. And the problem often comes from some aspects that are very superficial in hindsight. For example, the system administrator posts the login password in front of the computer; the financial staff divulges the user's personal sensitive information on the phone; the company staff runs attachments from unknown emails at will; the unknown person enters the office in the name of sales promotion or questionnaire to steal information, etc.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.