Summary of Shanghai Jiaotong University postgraduate entrance examination module -- cryptography

I haven't blogged for a long time , It was originally said that you should prepare well for the second round exam since your grades came out , The result is one month away from the result , There was no movement in the second round , Then I'm still preparing for relevant professional courses , One side in a professional form , Go over the relevant professional course knowledge again , Ah ~ It's so hard ！ I almost forgot that I took the postgraduate exam myself . Okay , I don't say much nonsense , Let's get to the point ！

Information security

• Information security technology It is an effective technical means to prevent attacks , It is also a basic measure to maintain information security .

The four basic attributes of information security

• confidentiality ： It means that information will not be disclosed to unauthorized users 、 Entity , Or be illegally used . Confidentiality essentially means that information is only used by legally authorized users , And restrict others' access . Confidentiality can be divided into ：
  • Transmission confidentiality ： Confidentiality of data and information in transmission , The solution is generally encrypted transmission .
  • Storage confidentiality ： Data confidentiality when storing data , Usually through access control .
• integrity ： Refers to the characteristics of data that cannot be changed without authorization . namely , It is to ensure that computer information and data will not be changed and lost by external events .
• Controllability ： It refers to the ability to control the dissemination and content of information .
• Usability ： Refers to the characteristics of entities that can be authorized to access . namely , Whether the information can be accessed and accessed normally when needed . All kinds of damage to the network 、 Denial of identity 、 Rejection and delayed use both undermine the availability of information .

The mainstream technology of information security

• Modern cryptography and data encryption technology
• Firewall technology
• Intrusion detection system
• Proxy server technology
• Identity Authentication
• Security scanning

Basic concepts and principles of cryptography

Cryptographic technology through the transformation and coding of information , Replace confidential sensitive information with garbled words that are difficult for hackers to understand , There are two main purposes ：

• Hackers who don't know how to decrypt can't get any meaningful information from the garbled code they intercept .
• Make it impossible for hackers to forge any garbled information .

Two branches of cryptography

• Cryptography ： Encode information to achieve information concealment
• Cryptanalysis ： Study and analyze the knowledge of breaking passwords

Password system 5 Basic elements

• Plaintext ： Hidden original message
• Ciphertext ： Encrypted message
• encryption algorithm ： A set of rules used when encrypting plaintext is encryption algorithm
• Decryption algorithm ： A set of rules used to decrypt ciphertext is called decryption algorithm
• secret key ： Key is the key of cryptosystem , Usually, its security determines the security of the cryptographic system

Let's take a look at this 5 The embodiment of three basic elements in a cryptosystem ：

Classification of cryptosystems

• The operation type of converting plaintext into ciphertext
  • Replace ： Every element of plaintext is mapping To another element
  • transposition ： The elements of plaintext are Rearrange

characteristic ： All operations are reversible . Most systems, or product systems, contain multilevel substitution and transposition combinations .

Product password ： In fact, it is a finite combination of transposition password and substitution password , It belongs to mixed password . Because transposition password is a linear change of characters , Can diffuse the correlation between input and output , Alternative passwords can make input and output nonlinear . therefore , The score password can resist the attack of the decoder to a certain extent .

• Number of keys used ：
  • If the sender and receiver use The same key , The system is symmetry 、 Single key 、 Secret key or traditional encryption .
  • If the sender and receiver use Different keys , The system is Asymmetry 、 Double key 、 Or public key encryption .
• Clear text processing
  • Group password ： Process one input element grouping at a time , Generate an output packet corresponding to the packet .
  • Stream code ： Continuous processing of input elements during operation , One output element at a time .

Classification of cryptosystems

• Symmetric cryptosystem and asymmetric cryptosystem

  • Symmetric cryptography ： Also known as single key cryptosystem . It is characterized by Both encryption and decryption use the same key , therefore The security of this cryptosystem depends on the security of the key . The common symmetric encryption algorithms are DES,3DES and AES.
    advantage ：
    High safety , Fast encryption .
    shortcoming ：
    One 、 With the expansion of network scale , Key management has become a difficulty .
    Two 、 It cannot solve the problem of message confirmation .
    3、 ... and 、 Is the lack of the ability to automatically detect key leakage .
  • Asymmetric encryption system , Also known as double key system , The encryption key is different from the decryption key , At this time, a secure channel is not required to transmit the key , Instead, you only need to use the local key generator to generate the decryption key , And use this to control the decryption operation . Common encryption algorithms of dual drug system include RSA.
    advantage ：
    One 、 Because the encryption and decryption keys of the double key system are different , And can disclose the encryption key , Only the secret decryption key is needed , Therefore, the double key password is easy to manage the key .
    Two 、 Double key system can provide new functions such as identity authentication and digital signature .
    shortcoming ：
    The cryptographic algorithm is more complex , Encryption and decryption speed is slow .

• Block cipher system and sequence cipher system

  • Block cipher system uses a Time varying transformation Handle the plaintext bit by bit . Its encryption method is to first sequence the plaintext Group in fixed length , Each set of plaintext is calculated with the same key and encryption function . In order to reduce the storage and improve the operation speed , The length of the key is generally small , Therefore, the complexity of encryption function is called the key of system security . The core of block cipher design is to construct an algorithm with both reversibility and strong nonlinearity . Encryption functions repeatedly use two basic encryption transformations, substitution and substitution . Common block encryption algorithms are ：DES,3DES and AES.
    advantage ：
    One 、 Plaintext information has good diffusibility
    Two 、 High sensitivity to insertion
    3、 ... and 、 No key synchronization required
    Four 、 It has strong adaptability , Suitable as encryption standard
    shortcoming ：
    One 、 Encryption speed is slow
    Two 、 Errors are easy to spread and spread
  • The encryption process of sequence cipher system is to put Plaintext sequence and key sequence of equal length Conduct Bitwise module 2 Add . The decryption process is to put Ciphertext sequence and equal length key sequence Conduct Bitwise module 2 Add .
    The security of sequence cipher mainly depends on the key sequence .
    advantage ：
    One 、 Fast processing speed , Good real-time
    Two 、 The scope of error propagation is small
    3、 ... and 、 There is no string decoding problem
    Four 、 Applicable to military 、 Diplomatic and other confidential channels
    shortcoming ：
    One 、 The plaintext has poor diffusion
    Two 、 The sensitivity of inserted information is poor
    3、 ... and 、 Key synchronization is required

• Deterministic cryptosystem and probabilistic cryptosystem

  • Deterministic cryptosystem refers to when the plaintext and key are determined , The form of the ciphertext is only certain .
  • Probabilistic cryptosystem refers to when the plaintext and key are determined , The form of the ciphertext is still uncertain , Finally, the generated ciphertext is selected from a ciphertext set by objective random factors . Such as plug-in cryptographic algorithm .
    Probabilistic cryptosystems increase the difficulty of deciphering , But it may significantly increase the length of the ciphertext , Thus increasing the cost of encryption and transmission .

• One way function cryptosystem and two-way function cryptosystem

  • One way cryptosystem is only suitable for some occasions that do not need decryption , It can easily encrypt plaintext into ciphertext , But the opposite is difficult or even impossible . This technique can be used to treat the generated ciphertext as a proof of content integrity of the corresponding plaintext . Because after the plaintext content changes, the corresponding ciphertext content will also change . The well-known single cipher function is MD5, It is called message digest algorithm or hash function algorithm .
  • Two way cryptosystem can carry out reversible encryption 、 Decryption transformation , Most encryption algorithms fall into this category .

Feistel Cryptostructure

For many symmetric block encryption algorithms （ Include DES）, Its structure consists of IBM Of Horest Feistel stay 1973 First detailed description in , The input length of the encryption algorithm is 2w Bit plaintext grouping and key K. The plaintext is divided into two halves ：L₀ and R₀. These two halves of data pass n After round processing, ciphertext grouping is synthesized . The first i The round input is L_i-1 and R_i-1, Produced by the previous round , At the same time, the sub key K_i By key K produce . Usually , Subkey K_i And key K Different , Sub keys are also different from each other , They are all generated by the sub key generation algorithm .

Feistel Cryptographic structure is a special case of the more general structure used by all symmetric block ciphers .

The specific operation of symmetric block cipher depends on the following parameters and design properties

• Group size ： Larger grouping means higher security , But it reduces the rate of encryption and decryption .128 Bit size grouping is a reasonable compromise and is almost a common choice in block cipher design .
• Key size ： Longer keys mean higher security , But it will reduce the rate of encryption and decryption . The most common key length of modern algorithms is 128 The bit .
• Round iteration number ： Multi round processing can provide better security . The typical size of iteration rounds is 16.
• Sub key generation algorithm ： The higher the complexity of this algorithm , The more difficult it is to break the password .
• Wheel function ： Higher complexity means higher resistance to decoding .

Introduction of three common symmetric block encryption algorithms

One 、 Data encryption standard （Data Encryption Standard）

DES By the former American National Bureau of Standards （ Now National Institute of standards and Technology ,NIST） On 1977 Year adoption , It is the most widely used encryption scheme at present . This algorithm itself is called data encryption algorithm （DEA）.

use DES The plaintext length encrypted by the algorithm is 64 The bit , The key length is 56 The bit , Longer plaintext is divided into 64 Bit grouping , use 16 iteration .

DES stay 1998 year 7 Month proved unsafe , Using current technology , You don't even need to use special hardware to crack DES.

Two 、 triple DES

3DES Use 3 Key and execute 3 Time DES Algorithm , The combination process is based on encryption - Decrypt - encryption （EDE） In the order of ：

3DES The decryption used in the second step of the encryption process has no password meaning . Its only advantage is to make 3DES Users of can decrypt the original single weight DES User encrypted data .

adopt 3 Different keys ,3DES The valid key length for is 168 The bit .3DES Two keys are also allowed , But even K₁=K₃, So the key length is 112 The bit .

FIPS 46-3 Contains 3DES The following provisions of ：

• 3DES yes FIPS Approved optional symmetric encryption algorithm .
• Using a single 56 The original bit key DES, It is only allowed under the standards of previous systems , The new design must support 3DES.
• Encourage the use of the past DES The government agencies of the system are converted to 3DES System .
• expect 3DES With advanced encryption standard AES Will serve as a FIPS Approved algorithms coexist , And allow 3DES Make a gradual transition to AES.

3DES Is a powerful algorithm , Because the underlying cryptographic algorithm is DEA,DEA Claimed resistance to decoding based on its algorithm ,3DES There are also .

3、 ... and 、 Advanced encryption standard AES

3DES The advantages of the algorithm

• because 168 The key length of bits , It overcomes DEA The inadequacy of dealing with exhaustive attacks .
• 3DES The underlying encryption algorithm and DEA identical , And this algorithm takes longer than any other algorithm 、 A more detailed review , Except for the exhaustive method, no effective attack based on this algorithm has been found .

3DES Disadvantages of the algorithm

• The algorithm software runs relatively slowly .
• DEA and 3DES All use 64 Bit size grouping . But for efficiency and safety reasons , Larger groupings are needed .

AES The groups used are 128 The bit , The key length can be 128、192 or 256 The bit , The input of encryption and decryption algorithm is one 128 The grouping of bits .

One of the characteristics worth pointing out is that the structure is not Feistel structure . Typical Feistel structure , Half of the data group is used to replace the other half , Then the two parts are exchanged .AES Not used Feistel structure , Instead, the entire data packet is processed in parallel during each round of replacement and shift .

One last little question ： Why can public key cryptography be used as identity authentication digital signature ？

• This is a function based on the characteristics of public key encryption algorithm .
• Public key encryption algorithm has two different keys , One is the public key , One is the private key .
• A time for encryption , The other is used for decryption .
• The ciphertext obtained by encrypting the plaintext with one of the keys , The original plaintext can only be decrypted with another corresponding key .
• Although the two keys are mathematically related , But if you know one of them , You can't calculate another . So one of them can be made public , Called public key , Free to release .
• The secret key is the private key , Users must keep it strictly and secretly , Never offer... To anyone in any way , Nor will it be disclosed to the other party of the communication , Even if the other party is trusted .
• therefore , It can provide the function of identity authentication and digital signature .

Finally, I would like to welcome all friends to pay attention to my wechat official account ： Honey orange , There are some articles that I am personally interested in , Interesting experience , Come to official account to play with me ！