kirv_4.mp4

10 min about Crypto-Book project
A: 00:00:00 - 00:49:32   50min   almost no break
B: 00:50:00 - 01:14:52   25min   2min break
C: 01:18:30 - 01:49:10    6min   2min vrtanje  
D: 01:18:30 - 01:49:10   12min   5min break
E: 01:58:27 - 02:31:35   33min   +5min (RSA intro and projects)
----------------------------------------------------------------------------
                         
A: 0-49:32 (1:23:28) (50min)
00:00 Substitution-Permutation Network (SPN)
02:24 E.g. $\ell=m=N_r=4$ and specific permutations $\pi_S$ and $\pi_S$ 
      (determining what is their order - we write a permutation 
      in a form of disjoint cycles and calculating lcm of their lengths)
07:45 Key schedule algorithm
08:30 An example of a specific plaintex encryptions
09:30 Description of AES
13:30 We need to introduce finite fields (called Galois Fields, GF) 
14:00 Repeating the definition of a group
16:40 Solving an equation in a group
17:45 The definition of a finite field $F$ with binary operations + and *
20:20 In a group we did not mention commutativity property,
      so we have to write two distributivity properties
22:15 Example: prime fields $Z_p$
23:00 The smallest field has two elements: $Z_2=\{0,1\}$
24:00 We make an infinite process in a finite field 
      (like when we were studying stream ciphers)
      in note that there has to be some repeatitions: $k\cdot 1=\h\cdot 1$.
      Now suppose that $k,h \in \N_0$, $k<h$ are a pair of the smallest 
      such integers. 
28:10 We conclude that $k=0$ and that $Z_h$ is a subset of $F$.
      We call $h$ the characteristic of $F$. 
30:08 Let us prove that $h$ is prime (by a contradiction) 
32:30 Conclusion: for every finite field $F$ there exists
      a prime characteristics $p$, so that $F$ contains 
      a prime subfield $Z_p$. 
33:00 We show that $F$ is a vector space over $Z_p$.
34:00 So there exists a finite basis 
      (a set of linearly independent vectors,
      so that every element can be expressed as a linear combination of
      basis vectors with coefficients from $Z__p$  (called also scalars)
35:30 Addition with $n$-$-tuples 
      (coordinate wise this a simple addition in $Z_p$).
36:40 Another conclusion: the number of elements in any finite field 
      has to be the power of a prime 
      (e.g. there is no prime field with 6 or 10 elements). 
39:00 We have defined a finite field and find out some structure.
      We can work with $n$-tuples as far as addition is concerned.
      However, what about multiplication?
40:40 A specific case: binary extension fields GF($2^n$).
41:30 Construction of such field with polynomias, 
      that is with a polynomial basis (PB) $\{x^i\}_{i=1}^n$.
42:00 We need an irreducible polynomial $f(x)$ (i.e., it cannot be 
      written as a product of two polynomias of degree at least 1)
43:30 How to multiply two polynomials in GF($2^n$)?
44:20 We first do an usual multiplication $u(x)v(x)$ 
      and then do the reduction modulo $f(x)$.
47:20 The remainder is the actual product.
47:40 Generalization to a general $p$ is very similar.
- 49:32

Break/no break 

B: 00:50:00-01:14:52 (25min)
50:00 A question: how is an irreducible polynomial 
      $x^8+x^4+x^3+x+1$ actually chosen?
50:25 The polynomials of degree $0$ are all the scalars.
50:40 $x$ and $x+1$ are the only polynomials of degree 1 in GF($2^n$).
50:55 List all the polynomials of degree 2 
      and determine which one are irreducible.
52:00 $x^2+x+1$ is the only irreducible polynomial of degree 2.
52:50 Continue with the polynomials of degree 3 and go to the 
      4-tuple presentation.
54:00 Irreducible ones cannot have the last coefficient $0$
      (as otherwise we have divisibility by $x$).
55:00 There are only 4 more candidates
56:00 Define zero of a polynomial, this is $\alpha$ s.t. $p(\alpha)=0$
58:30 We have proven that if a polynomial has a zero ($\alpha$), 
      then it is divisible by $(x-\alpha)$, 
      i.e., $p(x)=(x-\alpha)q(x)$, where $q(x)$ has degree deg$p$-1.
1:00:00 Hence, in the $n$-tuple representation we do not want to have 
        an even number of 1 (otherwise $1$ is a zero) 
        and $p(x)$ is not irreducible.
1:01:10 There are precisely two irreducible polynomials of degree 3:
        $x^3+x+1$ and $x^3+x^2+1$.
1:02:00 Generalization: for every $n\in \N$ there always exists 
        an irreducible polynomial. It does not matter which one you 	
        choose, as the vector spaces are all isomorphic.
1:02:30 How to check that $x^8+x^4+x^3+x+1$ is irreducible?
1:03:20 It obviously have no linear factors.
1:03:30 Trying to divide by $x^2+x+1$. Go to $n$-tuple presentation
        where multiplying by $x^i$ is just left shift.
1:06:52 The remainder is $x+1$, so it is not divisible.
1:08:30 We could do the same with $x^3+x+1$ and $x^3+x^2+1$.
1:09:40 It matters which irreducible polynomial you take 
        when we do calculations
1:10:20 Is the binomial $x^8+1$ irreducible over $Z_2$?
1:11:11 Is $x+1$ a factor of this polynomial? Yes, as 1 is its a zero.
        We need odd number of nonzero coefficients.
1:12:37 Which trinomial is irreducible over $Z_2$?
1:13:00 The ones with all even exponents are not.
1:14:35 So there are only two candidates
- 1:14:40 

2min break (turned out to be almost 4min)

C: 01:18:30-01:24:50 (6min)
1:18:30 Alternative approach to existence of irreducible polynomials:
        we count hove many products of certain degree we have 
1:19:00 Degree 2: there are three products $x*x$, $x(x+1)$, $x^2+1$
        and so one irreducible polynomial: $x^2+x+1$.
1:20:00 Degree 3: there are two products $x*(x^2+x+1)$, $(x+1)*(x^2+x+1)$,
        and so two irreducible polynomials
1:20:50 Larger degree: it takes time to do all this book keeping...
        We can check the tables in HAC 
        for irreducible trinomials and pentonomials.
1:23:30 Back to AES description: Algorithm SubBytes

1:24:50 sosedovo vrtanje (2.5 min)

D: 01:27:36-01:49:10 (20min)
1:27:36 To calculate an inverse in GF$(2^8)$ we use EEA for polynomias 
        $a(x)$ and $b(x)$, where deg$(a)\ge {\rm deg}(b)$:
        $a(x)=q(x)b(x)+r(x)$, where deg$(b)> {\rm deg}(r)$
        (like we were using for numbers their size).
1:28:57 Operation ShiftRows
1:29:48 Algorithm MixColumns
1:30:09 Algorithm KeyExpansions (by RotWord and SubWord)
1:31:00 Description of DES: Feistel Cipher based on 
1:34:10 DES constants
1:34:37 DES function $f$ (not necessarily invertible)
1:36:30 S-boxes
1:38:28 Computation of the DES Keys
1:40:19 Test vectors
1:40:40 Modes of Operation of Symmetric Ciphers
1:41:30 Electronic Code Book mode (ECB) 
1:42:36 Cipher Block Chaining mode (CBC)
1:44:20 Cipher FeedBack mode (CFB) and MAC (an example of hash function)
1:46:20 Output FeedBack mode (OFB) 
1:48:00 Counter mode (CTR)
- 1:49:10

break (5min)

E: 01:58:27-02:31:35 (33min+5min)
1:58:27 Attacks on DES (Differential and Linear Cryptoanalysis)
2:06:00
2:07:00 3-DES (why not 2-DES)
2:13:15 How big is BIG
2:15:40 Computing Power and the size of the secure key-space $2^{80}$
2:19:00 DESX
2:22:49 Man-in-the-middle attack (MIMA) on 2-DES
2:23:26 Differential Cryptoanalysis

2:31:35 RSA System and Factorization
2:36:40