Foundations of Cryptography

1. Hash

$$\text{ hash }:\{0,1{\}}^{\ast }\to \{0,1{\}}^k$$

Mapping variable length inputs to fixed length outputs .

characteristic ：

• Anti collision ： Different inputs map to different outputs ;
• Irreversible ： The input... Cannot be inferred from the output result ;
• Randomness ： Cannot infer output from input ;

Such as ：MD5, SHA-1, SHA-256 etc. .

2. digital signature

For tamper proof .

Generate the key ：

$$(s,v)\leftarrow \text{G}(1^n)$$

Generate signature private key $s$ And verify the public key $v$ . Public key verification is generally advertised , Signing the private key requires strict confidentiality .

Private key signature ：

$$\sigma \leftarrow {\text{Sig}}_s(m)$$

Use the signing private key $s$ The clear $m$ To sign , Get the output $\sigma$ .

Public key verification ：

$$b\leftarrow {\text{Vfy}}_v(m,\sigma )$$

Given plaintext $m$ And signature $\sigma$ , Use authentication public key $v$ verification $\sigma$ Whether it is $m$ The signature of the , Output a Boolean value .

Such as ：ECDSA etc. .

3. Symmetric encryption

Encryption and decryption use the same key .

Generate the key ：

$$k\leftarrow \text{G}(1^n)$$

The key needs to be kept strictly confidential .

encryption ：

$$c\leftarrow {\text{E}}_k(m)$$

Use key $k$ The clear $m$ To encrypt , Get the ciphertext $c$ .

Decrypt ：

$$m\leftarrow {\text{D}}_k(c)$$

Use key $k$ To ciphertext $c$ Decrypt to get plaintext $m$ .

Such as ：DES etc. .

4. Asymmetric encryption

Encryption and decryption use different keys .

Generate the key ：

$$(e,d)\leftarrow \text{G}(1^n)$$

Generate encryption public key $e$ And decrypt the private key $d$ . Encryption public key is generally advertised , Decrypting the private key requires strict confidentiality .

Public key encryption ：

$$c\leftarrow {\text{E}}_e(m)$$

Use public key $e$ The clear $m$ To encrypt , Get the ciphertext $c$ .

Private key decryption ：

$$m\leftarrow {\text{D}}_d(c)$$

Use private key $d$ To ciphertext $c$ Decrypt to get plaintext $m$ .

Such as ：RSA, DAS etc. .

The encryption and decryption speed of asymmetric encryption algorithm is much lower than that of symmetric encryption algorithm , Therefore, it is not applicable to the case with large amount of data .

Because the efficiency of asymmetric encryption is relatively low , But the key of symmetric encryption needs to be kept strictly confidential , Therefore, asymmetric encryption can first be used to transmit the key required for symmetric encryption , Then use symmetric encryption .

5. Use a combination of

encryption & Signature ：

$$\begin{gathered} c\leftarrow {\text{E}}_k(m) \\ \sigma \leftarrow {\text{Sig}}_s(c) \end{gathered}$$

Encrypt first , Post signature , Prevent ciphertext from being tampered with .

verification & Decrypt ：

$$\begin{gathered} {\text{Vfy}}_v(c,\sigma )\stackrel{?}{=}1 \\ m\leftarrow {\text{D}}_k(c) \end{gathered}$$
Decryption is required only after verification .