网络安全 L2 Introduction to Cryptography 密码学

Definitions
1. crypto - hidden/secret + grafia - writing
2. “the science and study of secret writing”
3. Cryptography is the science of protecting data, which provides means of
converting data into unreadable form, so that
        1. the data cannot be accessed for unauthorised use
        2. the content of the data frames is hidden
        3. the authenticity of the data can be established
        4. the undetected modification of the data is avoided
        5. the data cannot be disowned by the originator of the message

Four goals of cryptography

1. Confidentiality - prevent unauthorised access;
2. Integrity - no modification of existing information;
3. Authentication - no identifying either entities or data origins;
4. Non-repudiation - preventing denials of messages sent

Goal 1: Confidentiality
1. This comprises two separate requirements:
        1. no observer can access the contents of the message.确保只有授权的接收者能够阅读或访问消息，防止未授权的第三方获取敏感信息。
        2. no observer can identify the sender and receiver.保护通信双方的身份信息，防止第三方知道谁在发送消息以及消息是发送给谁的。
2. The terms privacy or secrecy are also used to mean confidentiality

• 隐私（Privacy）：这个术语通常用于描述个人信息的保护，确保个人信息不被未授权的第三方获取或滥用。在信息安全的上下文中，隐私与保密性密切相关，因为它涉及到保护个人数据不被泄露。

• 秘密（Secrecy）：这个术语通常用于描述信息保持未知或不公开的状态。在信息安全中，秘密性是指确保信息不被未授权的实体所知晓，这与保密性的要求是一致的。

Goal 2: Integrity
1. This requires that the recipient can be sure that:
        1. the message has not been changed or lost during transmission.
        2. the message has not been prevented from reaching the recipient.
        3. the message has not reached the recipient twice. 

Goal 3: Authentication
1. This requires that:
        1. the sender can be sure that the message reaches the intended recipient, and only
the intended recipient, and
        2. the recipient can be sure that the message came from the sender and not an
imposter. The act by an imposter of sending such a message is referred to as “spoofing”

Goal 4: Non-repudiation
1. This requires that:
        1. the sender cannot deny that the message was sent by him.
        2. the recipient cannot deny that the message was received by him.

Terminology
1. Plain text (or clear text) - text that can be read by a human
2. Encryption - process of transforming plaintext into ciphertext
3. Cipher text (or encrypted text) - text that needs to be processed to be read by a human being
4. Decryption - process of transforming a cipher text into a plain text (the reverse of encryption)
5. Cipher - a secret method of writing (i.e., encryption scheme: mathematical
function(s) or algorithm(s) used for encryption and decryption, they are usually using keys)
6. Key - is a word, number, or phrase that is used to encrypt the clear text.

Conventional encryption model
1. A sender wants to send a “hello” message to a recipient:
        1. The original message (plaintext) is converted to ciphertext by using a key and an algorithm.
        2. The ciphertext is transmitted over the transmission medium.
        3. At the recipient end, the ciphertext is converted back to the original text using the
same algorithm and key that were used to encrypt the message.

Main cryptography techniques
1. Symmetric encryption:
        1. known as secret key cryptography: Ɛk (PT) = CT, Dk (CT) = PT
        2. based on a single key: the same key is used to encrypt and decrypt the data
2. Non-symmetric encryption:
1. known as public key cryptography: Ɛk1(PT) = CT, Dk2 (CT) = PT
2. base on a combination of two keys - secret key and public key.
3. public key is used for encryption, and
4. the secret key is used for decryption.

Symmetric encryption

• Main problem: the sender and the receiver have to agree on a common key, a
secure channel is also required exchange the secret key. 一个公钥加密和解密
• Most widely used secret key algorithms are DES, 3DES, AES.

Non-symmetric encryption

1. Non-symmetric: both keys are required to complete the process (encrypted by
the public key and decrypted by the private key).公钥加密 私钥解密
2. Widely used algorithm: RSA.

Traditional cryptographic techniques
1. Two basic components of classical ciphers: substitution and transposition
        1. Substitution ciphers: letters are replaced by other letters
        2. Transposition ciphers: the letters are arranged in a different order
2. These ciphers may be:
        1. Monoalphabetic - only one substitution/ transposition is used, or
        2. Polyalphabetic - where several substitutions/ transpositions are used
3. Several such ciphers may be concatenated together to form a product cipher.

Substitution cipher
1. Caesar (50-60BC) – monoalphabetic:
        1. ignore space character, gather letters in t-letter blocks
        2. rotate left or right by some number of positions to obtain cipher text.
        3. can describe this cipher as:
                1. Encryption Ɛk : i → i + k mod 26
                2. Decryption Dk : i → i − k mod 26

Substitution cipher (cont’d)
• Caesar cipher generalisation, keyword used to permute the alphabet:
• Write keyword (no repeat characters), suppose keyword is JACKSON, followed by
remainder of alphabet in order:
• What does your partner in crime need to encrypt/decrypt?
• just the keyword.
• How secure? i.e., how difficult to break?
• letter frequency analysis is a good attack.

1. Porta (1563) - monoalphabetic polygraphic:
        1. Replace 2-letter blocks with corresponding symbols
        2. The first letter (key) is stationary while the second letter moves, indicating which
symbol is to be used instead of the original 2-letter block.

1. 加密/解密：

   • 加密：使用固定的第一个字母作为键，将消息中的两个字母块替换为相应的符号。
   • 解密：使用相同的键和符号，将符号替换回两个字母的块，然后将块转换回字母。

1. Porta: A matrix can easily represent the original disc ...
2. The ’key’ for a porta cipher is a key word. e.g. ’FORTIFICATION’
3. To encipher a message, repeat the keyword above the plaintext. 

1. Vigenere (1553) – polyalphabetic:
        1. The message is encrypted using the original plain text, a (text) key, and the table

• 多字母替换：与单字母替换密码（如凯撒密码）不同，维吉尼亚密码使用多个不同的替换表，每个替换表对应一个字母。
• 关键词密钥：加密时使用一个关键词作为密钥，该关键词重复使用，直到覆盖整个明文。

Transposition cipher
1. Turning Grille (Fleissner, Wostrowitz 1881):
        1. This template was a square with a number of holes punched out.
        2. There are an even number of rows and columns (thus the total number of fields is divisible by 4).
        3. One fourth of these fields is cut out. This template is used for both encoding and
decoding the message.

• 模板设计：模板是一个正方形，有偶数行和列，总的格子数可以被4整除。
• 穿孔：模板上有四分之一的格子被剪掉，形成一个穿孔的网格。
• 加密/解密：使用这个穿孔的网格模板来重新排列明文中的字母，形成密文。加密和解密使用同一个模板。

加密过程：

1. 准备明文：将明文按照穿孔栅格的行数和列数排列，如果有必要，可以在明文下方添加空行，直到与模板的行数和列数相匹配。
2. 放置模板：将模板放在明文上方，确保穿孔的网格覆盖明文。
3. 填写密文：从左上角开始，将明文中的字母按照模板的穿孔位置填入密文中。如果模板的格子不够用，可以将明文分成多个部分，每部分使用一个模板。

解密过程：

1. 准备密文：将密文按照穿孔栅格的行数和列数排列，如果有必要，可以在密文下方添加空行，直到与模板的行数和列数相匹配。
2. 放置模板：将模板放在密文上方，确保穿孔的网格覆盖密文。
3. 提取明文：从左上角开始，按照模板的穿孔位置提取字母，形成明文

 Encrypt JIM ATTACKS AT DAWN using this grille.

Product cipher
1. Feistel-IBM-1971:
        1. Predecessor for the Data Encryption Standard (DES).
        2. This system uses permutations (transpositions) on large blocks for the mixing
transformation, and substitution on small blocks for confusion.
        3. This system is based on two hardware components:
                1. P-box (Permutation box)
                2. S-box (Substitution box)

• 混合变换：Feistel-IBM-1971系统使用置换（转置）操作来混合大块数据，并使用替换操作来增加混淆。
• 基于硬件组件：这个系统基于两个硬件组件：
  • P-box（置换盒）：P-box用于将输入数据块中的数据重新排列，以增加密文的随机性。
  • S-box（替换盒）：S-box用于将输入数据块中的数据替换为不同的数据，以增加密文的复杂性。

加密过程：

1. 初始置换：将明文数据块进行初始置换，以增加数据的随机性。
2. 多轮加密：将数据块分成多个小块，每个小块都通过P-box和S-box进行加密。
3. 输出：经过多轮加密后，将所有小块合并，形成最终的密文。

 Block ciphers
1. A type of symmetric-key encryption.
2. Transforms a fixed-length block of plaintext into a block of ciphertext of the
same length, using a user provided secret key.
3. Decryption is performed by applying the reverse transformation to the ciphertext block using the same secret key.
 4. The fixed length is called the block size, and for many block ciphers, the block size is 64 bits.

Stream ciphers
1. A stream cipher generates a keystream, a sequence of bits used as a key.
2. Encryption: accomplished by combining the keystream with the plaintext,
usually with the bitwise XOR operation.
3. The generation of the keystream can be independent of the plaintext and
ciphertext, termed as synchronous.
4. Or it can depend on the data and its encryption, termed as self-synchronising.
5. Most stream cipher designs are for synchronous stream ciphers.

Stream ciphers (cont’d)
1. A Vernam cipher is a stream cipher in which the plaintext is XORed with a
random or pseudorandom stream of data of the same length to generate the
ciphertext.
2. If the stream of data is truly random and used only once, then the cipher is a
one-time pad.

1. One Time Pad:
        1. The message is encrypted by combining (usually XORing) it with a perfectly random
key at least as long as the message and the key is only used once.
        2. Apart from the problem of obtaining a perfectly random key, the main problem with
one-time pads is the distribution of keys.

1. 生成密钥：首先，需要一个与明文长度相等的随机密钥。这个密钥可以是一串随机生成的字符、数字或比特。
2. 密钥与明文：将密钥与明文进行位对位的异或（XOR）操作。异或操作的性质是，任何数与自身异或的结果都是0，任何数与0异或的结果都是它本身。
3. 生成密文：通过异或操作生成的结果就是密文。
4. 使用相同的密钥：解密时，使用与加密时相同的随机密钥。
5. 密钥与密文：将密钥与密文进行位对位的异或操作。
6. 生成明文：通过异或操作，可以恢复出原始的明文。

Stream ciphers vs. block ciphers
1. Stream cipher:
        1. A type of symmetric encryption algorithm.
        2. Can be designed to be exceptionally fast, much faster than any block cipher.
        3. Typically operate on smaller units of plaintext, usually bits.
        4. The transformation of plaintext units will vary, depending on when they are
encountered during the encryption process.
2. Block cipher:
        1. Operate on large blocks of data.
        2. The encryption of any plaintext will result in the same ciphertext when the same
key is used.

Cryptographic modes
1. A block cipher encrypts a plain text in fixed-size n-bit blocks (often n = 64)
2. For messages exceeding n bit we can use four different modes of operation:
        1. ECB: Electronic Code Block.
        2. CBC: Cipher-Block Chaining.
        3. CFB: Cipher FeedBack.
        4. OFB: Output FeedBack.

Electronic code block
1. The message is divided into blocks and each block is encrypted separately:

 Cipher block-chaining

1. A plain text block is XORed with the previous cipher text block before
encryption.
2. The first plain text block is XORed with an Initializing Vector IV:Cipher FeedBack
1. Plain text is encrypted in blocks of size r (r < n).
2. The n-bit Shift Register (initially IV) is encrypted into an intermediate cipher
text.
3. The left-most r bits of the intermediate encrypted text are XORed with the next
r bits of the plain text to obtain r bits of cipher text.
4. The r bits of the final cipher text are moved to the right-most r bits of the Shift
Register and its r left-most bits are discarded.

Output FeedBack
1. Plain text is encrypted in blocks of size r (r < n);
2. The n-bit Shift Register (initially IV) is encrypted into an intermediate cipher
text;
3. The left-most r bits of the intermediate encrypted text are XORed with the next
r bits of the plain text to obtain r bits of cipher text;
4. The r bits of the intermediate cipher text are moved to the right-most r bits of
the Shift Register and its r left-most bits are discarded