theKingOfNight's Blog

Crypto-密码学复习

Word count: 5kReading time: 26 min
2019/01/19 Share 基本概念 Chapter 2 Classical Cryptology

Monoalphabetic cipher

Monoalphabetic cipher is a cipher which each plaintext character is replaced by exactly one ciphertext character

type

####Caesar cipher

####Keyword cipher Polyalphabetic Cipher

Polyalphabetic cipher is a substitution cipher in which each plaintext character is represented by more than one ciphertext character and each ciphertext character represents more than one plaintext character。

Vigenere cipher  Autokey cipher

A small key length and the repeat of keyword are the weakness of Vigenere cipher, one fix that has been used is called an Autokey cipher Rotor ciphers（了解）

• A rotor cipher is an electromechanical system that implements a complicated polyalphabetic substitution Polygraphic Cipher

-A polygraphic cipher works on more than one plaintext character at a time. Groups of plaintext characters are replaced by assigned groups of ciphertext characters
-The simplest example is a digraphic cipher, which is stronger than a monographic cipher because they are more digraphs (pair of letters) than individual letters.

Double Playfair

Encryption
• This cipher uses two Playfair squares formed from two keywords.If the last group is incomplete, break it into equal pieces. If it has an odd number of letters, add a ‘x’ to fill it out.

• Encipher the top/bottom letter pairs in two steps
Find the top letter in the first Playfair square and the bottom letter in the second Playfair square
–If they form a rectangle then take the other two corner letters (same row rule)
–If they are in the same row then take the letter to the right of each one in the other square
Use the letters discovered above in the same way (except the first letter is found in the second square and the second letter is found in first square) to determine the actual substitution

• Select two keywords such as “software” and “computer”     ##Transposition Cipher
There are two types of transpositions
Monographic methods - deal with individual letters
Polygraphic methods - deal with units greater than single letters (words, phases, etc)

Permutation cipher

Encryption
• Break the plaintext up into groups of a fixed size, d
• Define a permutation of the integers 1 to d called f
• Within each block, permute the letters according to f
• The key is (d, f) Column permutation cipher

• Write the plaintext into a matrix by rows, then generate the ciphertext by selecting the columns in a given order
• The key is the given order
– the length of the keyword is the number of columns
– the order of the letters in the keyword determines the order in
which the columns are selected
For example, the keyword “general” defines a column transposition with 7 columns
• To define the order of columns assign each letter a number based on its order in the alphabet Double-Transposition cipher

• The plaintext is enciphered using a column permutation cipher
• The resulting ciphertext is enciphered using column permutation cipher again
• The keyword may be the same for both transpositions or not
• The result is a thorough mixing of the positions of the plaintext

Chapter 3 Stream Ciphers

RC4

Encryption
•KSA initialing S

->PRGA random elements of S and modifying S for the next selection

CA

key->二进制
000->111相对应 2DCA For example, if (X,C,N,S,W,E) = (001110) then it is rule 14 since (001110) is binary 14

Chapter 4 Block Cipher

DES

• It is a substitution-permutation cipher
• 16 SP stages
• DES works on 64 bit blocks
• Using a 56 bit key
• Every ciphertext character depends on a plaintext character            AES

– One of the fastest and strongest algorithms
– Variable block length: 128, 192, 256 bits
– Variable key length: 128, 192, 256 bits
– Variable number of rounds (iterations): 10, 12, 14
– Number of rounds depend on key/block length
– The number of rounds N=max(Nk, Nb) +6，where Nb is the block length and Nk is the key length, every 32bits is a unit Encryption
• Initial Step
– The process begins by grouping the plaintext bits into a column array by bytes
– The first four bytes form the first column; the second four bytes form the second column, and so on
– If the block size is 128 bits then this becomes a 4x4 array. For larger block sizes the array has additional columns
– The key is also grouped into an array using the same process • Substitution
– The substitution layer uses a single S-box (rather than the 8 Sboxes used in(DES). The Rijndael S-box is a 16 x 16 array
– Each element in the current column array serves as an address into the S-box where the first four bits identify the S-box row and the last 4 bits identify the S- box column
– The S-box element at that location replaces the current column array element  • Row Shift Operation
– A row shift operation is applied to the output of the S-box in which the four rows of the column array are cyclically shifted to the left
– The first row is shifted by 0, the second by 1, the third by 2, and the fourth by 3 • 列混淆 – The final operation adds a subkey derived from the original key to the
column array
– This completes one round of AES • 密钥扩展算法 1) 将种子密钥按图(a)的格式排列，其中k0、k1、……、k15依次表示种子密钥的一个字节；排列后用4个32比特的字表示，分别记为w、w、w、w；
2) 按照如下方式，依次求解w[j]，其中j是整数并且属于[4,43]；
3) 若j%4=0,则w[j]=w[j-4]⊕g(w[j-1]),否则w[j]=w[j-4]⊕w[j-1]；

a) 将w循环左移8比特；
b) 分别对每个字节做S盒置换；
c) 与32比特的常量（RC[j/4],0,0,0）进行异或，RC是一个一维数组，其值如下。（RC的值只需要有10个，而此处用了11个，实际上RC在运算中没有用到，增加RC是为了便于程序中用数组表示。由于j的最小取值是4，j/4的最小取值则是1，因此不会产生错误。）
RC = {0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36}

IDEA（了解）

International Data Encryption Algorithm
1990 PES（朱学嘉）， 1991 IPES， 1992 IDEA
128bit key, 8 rounds
A stronger alternative to DES
Built into PGP
Appears to be resistant to both differential and linear cryptanalysis

RC6（了解）

One of the AES finalists submitted by Rivest, Robshaw, Sidney, and Yin
Key(128,192 or 256 bits）
20 Rounds
Block size (128 bits)
Fast and easy to be implemented by hardware

Twofish（了解）

Submitted by Schneier, et al.
Has some of the features of both RC6 and Rijndael
Block size (128bits)
Variable length of key (0-255bits)
16 Rounds of a Feistel network
Some operations such as S-Box and matrix-multiplication Chapter 5 Public Key Cipher

Public Key Transaction ###RSA
• Suggested in 1977
• Named after 3 researchers at MIT who developed the cipher: Rivest-Shamir-Adleman Cipher
• Solve the security problem of key transmission
• Used both for encryption/decryption and digital signature
• Based on the concept of an exponentiation cipher that use multiplication to generate the ciphertext
•RSA depends on the difficulty of factoring large numbers for its security

Key
• Select two 100 digit (or more) prime numbers, p and q
• Multiply them to obtain n = pq
• Publish n
• Calculate φ(n)=(p-1)(q-1)
• Select another number d which is relative prime to φ(n), that means GCD(d, φ(n))=1
• Calculate e so that it is the inverse of d when reduced mod (p-1)(q-1)
that is de=1 mod φ(n)
• Publish e but keep p, q, and d secret
• The pair of public and secret keys are (d, n), (e, n)

Encryption
• Divide the message into blocks such that the bit string can be viewed
as a digit number - call this block m
• Compute and send
C=Epk(M)=M^e mod n

Decryption
• Compute
M=Esk(C)=C^d mod n
• This works because
C^d = (M^e)d mod n = M^1 mod n

Chapter 5 Public Key Ciphers

RSA Problems(了解)
How can I find large prime numbers?
How can I find the required modular inverse
i.e. given e and n find d such that ed = 1 mod n
How can I be sure that my primes are large enough to avoid factoring?
How can I perform long integer arithmetic?
In order to solve these problems, we need to explore some basic ideas in number theory, which will play a role in alternative public key algorithms

Modular Inverse（了解）
Generating the keys for RSA requires finding tow large primes to create n = pq, selecting a secret key, d and then finding the public key e such that
de mod (p-1)(q-1) = 1
e is the modular inverse of d (d^-1)
PROBLEM: How do you find e (especially for large integers)?

Factoring（RSA attack）
RSA can be broken if the two primes that made n can be found by actoring n
Fermat’s Factoring Algorithm
• Search for an x and y that satisfy n = x2 – y2 which is the same as using
x2 - n = y2
• Start with the smallest integer k for k2 >= n
• Look at numbers k2–n, (k+1)^2–n, (k+2)^2-n, . . . until some value m >= sqrt(n) is found such that m2-n is a square
• Then we know x and y so p = (x+y) and q = (x-y)

Fast exponentiation  ELGAMAL Cipher

Background
• Among these is the ElGamal cipher developed in 1985 by T. ElGamal
• Can be used in encipher/decipher and digital signature
• It relies on the difficulty of solving the discrete logarithm problem

• The discrete logarithm problem begins with a prime p and two integers a and b where
b = a^x mod p for some integer x
• The problem is one of finding x
– If p is small this problem can be solved by exhaustive search
– For example, given p = 17, a = 3, and b = 5 find x such that 5 = 3^x mod 17
– Trying all possible values of x beginning with 1 until a match is found results in key
• The keys are generated by selecting a large prime number p
• Get a generator number g of a cyclic group Gp and select a random integer a less than p-1
• With these numbers compute b = g^a mod p
• The public key consists of the three number (p, g, b) and the secret key is the number a
• To find a given the public key, an attacker must be able to solve the discrete logarithm problem

Encryption
• If Alice wants to send a message to Bob, she begins by looking up her public key (p, g, b) and representing the message as an integer m in the range 1 to p-1
• She then selects a random key k that is less than p-1
• Using these numbers, Alice computes two numbers • She sends (c1,c2) to Bob

Decryption
• When Bob receives the ciphertext, he will recover the plaintext using his secret key, “a”, to compute this works because ECC Cipher（椭圆曲线密码）

Background
• In 1985 both Koblitz and Miller independently suggested the use of Elliptic Curves in the development of a new type of public key cipher, and widely used from 2004.

– The line through those points intercepts the curve at a third point
– The sum of P and Q is defined as the reflection of their intercept point across the x-axis.(P+Q是P和Q在椭圆曲线上第三个交点关于x轴对称点)  3P是先通过P切线关于x轴对称找2P点，在P和2P连线与椭圆曲线的第三个焦点关于X轴对称，就是上图椭球下面那个3P点，4P。
Encryption
• ECDLP (Elliptic Curve Discrete Logarithm Problem)
• One method begins by selecting an Elliptic Curve and a point G on the curve and a secret number k which will be the private key
• The public key is G and P_A , where P_A = kG
• A message is encrypted by converting the plaintext into a number m, selecting a random number r, and finding a point on the curve P_m where the difference of the x and the y co-ordinates equals m(在曲线Pm上找到x和y坐标的差等于m的点来加密消息。)
• The ciphertext consists of two points on the curve
C = {rG, P_m + rP_A}

Decryption
• The secret key, k is used to decipher the ciphertext
• Multiply the first point by k and subtract the result from the second point
P_m + rP_A – k(rG) = P_m + r(kG) – k(rG) = P_m

Knapsack Cipher

•1976年，Ralph Merkle和Martin Hellman首次提出建立公钥系统的可能性
•看起来这个概念在60年代早期被英国情报部门所知，但直到90年代才被归类
•他们基于背包问题实施了一个公钥系统版本
•原始背包密码破裂，因此今天不使用
•然而，这是一个有趣的探索密码，因为它将NP完全问题适用于密码学

tips:
The knapsack deciphering algorithm is based on an easy knapsack problem
Easy knapsacks have a sequence of numbers that are superincreasing.That is each number is greater than the sum of the previous numbers.Such a sequence is (3, 5, 9, 18, 38, 75, 155, 312).

Encryption
• The Merkle-Hellman knapsack cipher encrypts a message as a knapsack problem
• The knapsack is given as a list of numbers m_1, …, m_n, the message block is a collection of n binary bits b_1, . . ., b_n and the ciphertext is the sum S
• For example, given the knapsack list (5, 14, 9, 23, 16, 7, 31, 27), the character “a” represented in ASCII as 0110 0001, the ciphertext is
S = 05 + 114 + 19 + 023 + 016 + 07 + 031 + 127 = 50

Decryption

改进：Trapdoor knapsack

• Given a superincreasing knapsack sequence A’ = (al’, . . ., an’ ) the transformation to a trapdoor knapsack sequence, A, involves the following steps
– Select an integer u > 2an’
– Select another integer w such that GCD (u, w) = 1
– Construct the trapdoor sequence A = wA’ mod u
• Given our superincreasing knapsack: (3, 5, 9, 18, 38, 75, 155, 312)
– Select u > 624, say 672
– Select w = 13
– The Trapdoor knapsack is: (3x13) mod 672, (5x13) mod 672 , . . .
–(39 65 117 234 494 303 671 24)

key
• Find the inverse of w mod u, w-1
• The private key is the original superincreasing knapsack and the value of w-1 and u
• The public key is the trapdoor knapsack

• Given a sum determined by the public key, multiply it by w-1 and use the new target with the superincreasing knapsack to decipher the ciphertext  Combination of RSA and DES DES_key被RSA加密

Chapter 6 Key Management

• Key management is the set of techniques and procedures supporting the establishment and maintenance of keying relationships between authorized parties
It includes such issues as
• Key Generation
• Key Distribution
• Distributing your own public key
—- Obtaining someone else’s public key
• Establishing a shared key with another party
—-Key Storage and Recovery
• Saving keys and recovering lost keys

Chapter 7 Authenticity

Key Exchange
Key exchange not only include pair exchange but also concern about group exchange.

Diffie-Hellman Key Exchange（1976）  Group keys   DH Mode

• The multi-role mode of DH does pose some problems
—- If someone wants to join the group, they have to go through these steps again
—- If someone leaves the group, then the key assignment process must begin again as well
—- In short, this process does not offer the degree of flexibility required for large and variable size groups Chapter 7 Authentication（认证，只是检查消息是否被篡改）

1.摘要:消息摘要就是根据一定的运算规则对原始数据进行某种形式的信息提取，通过数据摘要后的消息摘要的长度总是固定的，可以唯一的标识一段数据。著名的摘要算法有RSA公司的MD5算法和SHA-1算法。
2.数字签名:使用非对称加密技术生成一对公私钥对，消息的发生者A使用私钥进行数据的加密，消息的接受者B使用公钥进行解密来验证消息的真实性。
3.将原文数据和签名数据一块进行传输
4.消息的接收者接收到数据之后，首先使用同样的方法对原文进行消息摘要(md5,sha-1…..)，得到摘要A，然后使用公钥给数字签名进行解密，得到消息摘要B，最后比较摘要A和摘要B，如果相同，数据原文没有被篡改，否则就表示原文被篡改。

5.数字证书(CA)主要包括三方面的内容：证书所有者的信息、证书所有者的公钥和证书颁发机构的签名。

The goal of information security
 Confidentiality
 Integrity
 Availability
 Reliability
 Accountability

MD5

MD，Message Digest , is concluded from message, has a fixed length and can reflect the characteristic of the message
MD is very important in authenticity and digital signature
MD5 is a MD algorithm designed by Rivest in 1991
Experience the lower version from MD1, MD2, MD4 to MD5

Principle
Any length (<2^64) of input message
The fixed 128 bit length of output
512 bit block process
4 disturb functions

For MD5, the message is padded so that its bit length equals 448 mod 512 (this is 64 bits less than an integer multiple of 512 bits)
The padding consists of a single 1 bit followed by enough 0 bits to create the required length
Second, the original length of the message is added to the end of the expanded message as a 64 bit number For example, if a message consisted of 704 bits, 256 bits would be added on to the end (a 1 followed by 255 0’s) to expand the message to 960 bits (960 mod 512 = 448), and the final 64bit are 54 0’s plus 1011000000

Parameters Initialization
4个常数：

• A = 0x67452301
• B = 0x0EFCDAB89
• C = 0x98BADCFE
• D = 0x10325476
4个函数：
• F(X,Y,Z)=(X & Y) | ((~X) & Z);
• G(X,Y,Z)=(X & Z) | (Y & (~Z));
• H(X,Y,Z)=X ^ Y ^ Z;
• I(X,Y,Z)=Y ^ (X | (~Z));
将用户输入的消息以512位为一组进行处理，以上面4个函数为起始变量，每一组进行按照上面4个函数进行变化，重新输出4个变量，以这4个变量为一组在进行下一组的运算，如果已经是最后一个分组，那么这4个变量就是最后一组的结果，MD5值。

md5应用
1、一致性检验：MD5可以对报文产生消息摘要，可以检测消息是否被篡改
2、数字证书 ： 如果有一个第三方的认证机构，用MD5还可以防止文件作者的“抵赖”，这就是所谓的数字签名应用。
3、安全访问认证 ：目前许多网站用户密码都用md5保存。

SHA-1（了解）

Background
It was modeled after MD4, a precursor to MD5 so it has many of MD5’s features
It accepts a message of any size and produces a 160-bit digest
It works on blocks of 512 bits divided up into 32-bit strings
It runs in four rounds with 20 steps per round

The message is padded by the method used in MD5

Parameters Initialization(比MD5多1个)
The initial input to SHA-1 is placed in five 32-bit registers A, B, C, D and E which will later hold the intermediate and final results of the hash function
The initial values (in hex) are

• A = 67452301
• B = EFCDAB89
• C = 98BADCFE
• D = 10325476
• E=C3D2E1F0
Round Process
Similar as MD5, four disturb functions, four rounds, 20 operations per rounds, together 80 operations Digital Signatures（流程图，简答题可能会出）

Given a message, m, the standard approach is to create a fixed sized message digest, h(m) and then sign the digest, S(h(m))
The signed message is sent as the pair (m,S(h(m)))
The message is verified by reversing the signature process to recover the value of h(m) and applying h to the received message
If the two values are equal then the message is authentic    DSS

DSS was the first digital signature system actually endorsed by any government and it does offer an alternative to an RSA-type signature

DSA

DSA(Digital Signature Algorithm)
DSA is based on the ELGamal public key system however it is strictly a signature algorithm and is not intended for encryption
It uses a large number of public/private parameters
The final verification test is based on the value of r   PKI  Identity-based Cryptography (IBC)

• IBC significantly reduces the system complexity and the cost for managing the public key compared with PKI.