设试验E的样本空间为S，A为E的事件，B1, B2,......,Bn为S的一个划分，且P(Bi)>0，则有
P(A) = P(A|B1)P(B1) + P(A|B2)P(B2) +......+P(A|Bn)P(Bn)
乘法定理
P(ABC) = P(C|AB)P(B|A)P(A)
P(A) = P(A|B)P(B) + P(A|B补)P(B补)
P(B|A) = P(AB)/P(A) = P(A|B)P(B) / (P(A|B)P(B) + P(A|B补)P(B补))
CRYPTOGRAPHY PART
A field with order m only exists if m is a prime power, i.e. m = p^n, for some positive integer n and prime integer p. p is called the characteristic of the finite field. (proof?)
GF(2) modulo addition is equivalent to XOR; GF(2) multiplication is equivalent to AND.
GF(2^m) is called extension fields.Extension fields can be represented as polynomials and the computation in the extension field is achieved by performing a certain type of polynomial arithmetic.
Every field GF(2^m) requires and irreducible polynomial P(x) of degree m with coefficient from GF(2). Not all polynomials are irreducible. For example the polynomial 4 3 1 0 is reducible since (2 1 0)(2 0) and hence cannot be used to construct the extension field GF(2^4). If the polynomial can be divided to more than two single expressions, then it is reducible. The irreducible polynomial for AES is 8 4 3 1 0, which is part of the AES specification.
AES Algorithm
1. AddRoundKey Layer. XOR the matrix and key matrix. This will execute one time at the beginning of AES.
2. SubByte Layer. Look up S-BOX and replace each item in matrix
3. ShiftRow Layer. The i-th row (1≤i≤4) shifts i-1 position to the left.
4. MixColumn Layer. Each column multiply with an constant matrix.
Key Schedule
1. Chose the i+3 column and shift one position to DOWN.
2. SubByte operation to this new column.
3. XOR with the i-th column and the round number. This will be the i+4 column.
4. Round the above operations.
Extended Euclidean Algorithm
void eea (int a, int b, int& gcd, int& x, int& y)
{
x=0, y=1;
int u=1, v=0, m, n, q, r;
gcd = b;
while (a!=0)
{
q=gcd/a; r=gcd%a;
m=x-u*q; n=y-v*q;
gcd=a; a=r; x=u; y=v; u=m; v=n;
}
}
Fermat's Little Theorem
Proof:
1. 1 2 3...p-1 is a ring mod p
2. Multiply a with 1 2 3...p-1 and then mod p, this is still a ring on 12 3...p-1
3. then we know
4.
5.
Privately Outsourcing Computation
GF(2) modulo addition is equivalent to XOR; GF(2) multiplication is equivalent to AND.
GF(2^m) is called extension fields.Extension fields can be represented as polynomials and the computation in the extension field is achieved by performing a certain type of polynomial arithmetic.
Every field GF(2^m) requires and irreducible polynomial P(x) of degree m with coefficient from GF(2). Not all polynomials are irreducible. For example the polynomial 4 3 1 0 is reducible since (2 1 0)(2 0) and hence cannot be used to construct the extension field GF(2^4). If the polynomial can be divided to more than two single expressions, then it is reducible. The irreducible polynomial for AES is 8 4 3 1 0, which is part of the AES specification.
AES Algorithm
1. AddRoundKey Layer. XOR the matrix and key matrix. This will execute one time at the beginning of AES.
2. SubByte Layer. Look up S-BOX and replace each item in matrix
3. ShiftRow Layer. The i-th row (1≤i≤4) shifts i-1 position to the left.
4. MixColumn Layer. Each column multiply with an constant matrix.
Key Schedule
1. Chose the i+3 column and shift one position to DOWN.
2. SubByte operation to this new column.
3. XOR with the i-th column and the round number. This will be the i+4 column.
4. Round the above operations.
Extended Euclidean Algorithm
void eea (int a, int b, int& gcd, int& x, int& y)
{
x=0, y=1;
int u=1, v=0, m, n, q, r;
gcd = b;
while (a!=0)
{
q=gcd/a; r=gcd%a;
m=x-u*q; n=y-v*q;
gcd=a; a=r; x=u; y=v; u=m; v=n;
}
}
Fermat's Little Theorem
Proof:
1. 1 2 3...p-1 is a ring mod p
2. Multiply a with 1 2 3...p-1 and then mod p, this is still a ring on 12 3...p-1
3. then we know
4.
5.
Privately Outsourcing Computation
No comments:
Post a Comment