UoN COMP3077 Cryptography 学习笔记

01 Introduction

1. What is cryptography
   • 
   • cryptography: the science and art of writing and solving codes to hide the meaning of messages
   • symmetric: Encryption methods in which both the encryption and decryption algorithms use the same key
     • 
   • asymmetric: Methods which use separate, but related, private and public keys
     • 
   • protocols: The application of cryptographic algorithms in secure systems
   • cryptanalysis: the science and art of breaking cryptosystems

02 Historic Ciphers (Caesar Cipher, Shift Cipher, Affine Cipher), Modular Arithmetic

1. Historic cipher: usually based on transposition or substitution

2. Historic cipher - Caesar Cipher: replace each letter of plaintext with a shifted letter further down the alphabet

   • a special case of the Shift Cipher (with a key k = 3)

3. Historic cipher - Shift Cipher:

   • not secure: frequency analysis, brute force
   • key space: 25 (i.e. integer 1 ~ 25)

4. Historic cipher - Affine Cipher:

   • not secure: frequency analysis, brute force (only a little better than Shift Cipher)
   • key space: (valid a) * 25

5. Modular arithmetic

   • congruence $\equiv$ [一致的]: let $a, r, m \in \Z$, and $m > 0$, $a \equiv r\pmod{m}$ if $m\ |\ (a-r)$
   • equivalence classes:
   • Integer rings
     • 
     • can add or multiply any two numbers in the ring and the result is in the ring. It is closed
     • commutative: $a+b=b+a$, $a\cdot b = b \cdot a$
     • associative: $(a+b)+c=a+(b+c)$, $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
     • neutral element $0$ for addition: $a + 0 \equiv a\pmod m$
     • neutral element $1$ for multiplication: $a \cdot 1 \equiv a\pmod m$
     • the additive inverse $a + (-a) = 0\pmod m$ always exists
     • the multiplicative inverse $a \cdot a^{-1} \equiv 1 \pmod m$ exists for some but not all elements
       • $b/a \equiv b \cdot a^{-1}\pmod m$
       • exists when $\gcd(a, m) = 1$

03 Stream Ciphers, Randomness, One-Time Pad (OTP), Modern Stream Ciphers

1. stream ciphers: encrypt bits one at a time
   • 
   • 
   • encryption and decryption operations are identical
   • Modulo 2 - XOR: balanced, i.e. if the key bit $s_i$ behaves perfectly randomly that it is unpredictable and has exactly a 50% chance to have the value 0 or 1, then both possible ciphertexts also occur with a 50% likelihood
   • stream ciphers give confidentiality, but not integrity
2. Randomness
   • True randomness: impossible to recreate except by chance, e.g. coin flips
   • True Random Number Generator (TRNG)
     • their output cannot be reproduced
     • based on physical processes, e.g. coin flipping, rolling of dice, …
   • Pseudorandom Number Generator (PRNG)
     • Generate a sequence of values based on a seed
     • Usually the only requirement is statistical randomness
     • $s_0 = \text{seed}$ and $s_{i+1} = f(s_i), i = 0,1,...$
     • Linear Congruential Generator (LCG): $s_0 = \text{seed}$ and $s_{i+1} = as_i+b\pmod m\ ,\ i = 0,1,...$, where $a,b,m$ are integer constants
   • Cryptographically Secure Pseudorandom Number Generator (CSPRNG)
     • PRNG which is unpredictable
3. Unconditional Security, Computational Security and Perfect Secrecy
   • Unconditional Security: A cryptosystem is unconditionally or information theoretically secure if it cannot be broken even with infinite computational resources
   • Perfect Secrecy: The ciphertext should reveal no information about the plaintext
     • $\forall m_0, m_1 \in M\ \text{where}\ |m_0| = |m_1|\ \text{and}\ \forall c \in C, \Pr[E(k,m_0)=c]=\Pr[E(k,m_1)=c]$
   • Computational Security: A cryptosystem is computationally secure if the best known algorithm for breaking it requires at least t operations
4. the One-Time Pad (OTP)
   • A stream cipher for which
     • Key stream $s_0 ,s_1 ,s_2 ,...$ is generated by a TRNG
     • The key stream is known only to the communicating parties
     • Every key stream bit $s_i$ is used only once
   • OTP has perfect secrecy: any plaintext is equally likely depending on the key
   • OTP is not practical: key size is same as plaintext size; cannot reuse a key
5. Modern stream ciphers
   • use an initial seed key to generate an infinite pseudorandom keystream
     • 
     • advantage to OPT: greatly reduces key size
   • use a nonce value to alter the keystream for a given key
     • allows to create different keystreams for a given key
     • 
     • nonce - number used once
     • always use a unique (key + nonce) pair
     • nonces are not secret - they are a public random seed for a key stream
   • Modern stream ciphers are CSPRNGs
6. Reuse a keystream in stream cipher - breaks a stream cipher
   • the attacker knows the XOR of 2 plaintext messages
   • crib dragging attack (plain text attack): if the attacker can guess or know part of a plain text message (s)he can begin to decrypt other encrypted messages by dragging a XOR of the known plain text over two or more messages
7. attack a stream cipher that uses PRNG based on the linear congruential generator (LCG)
   • PRNG based on LCG: $s_{i+1} \equiv As_i+B\pmod m\ , i=0,1,...$
   • even if the attacker knows some (very limited) plaintext, e.g. $x_1, x_2, x_3$, in addition to ciphertext (which he certainly knows), he can compute the first few bits of key stream as $s_i \equiv x_i + y_i\pmod m\ ,\ i = 1,2,3$, then $s_2 \equiv As_1+B\pmod m$ and $s_3 \equiv As_2+B\pmod m$, $A$ and $B$ can be calculated

04 Linear Feedback Shift Registers (LFSRs), Trivium, ChaCha20

1. Linear Feedback Shift Registers (LFSRs)

   • A Linear-feedback Shift Register is a register of bits whose positions shift to the right
   • Usually comprised of flip-flops
   • the last bit represents the output
   • e.g.
   • mathematical representation:
   • polynomial representation:
   • maximum length LFSRs: LFSRs that have primitive polynomials (irreducible)
   • attack LFSRs:

2. Trivium

   • 3 LFSRs
   • each takes feedback from previous LFSR with non-linear AND gates
   • Initialises the LFSRs with an 80-bit key and 80-bit random value

3. ChaCha20

   • use only add, xor and rotate operations
   • inputs and outputs:
   • performs 20 rounds
     • Alternates between (10) Column Rounds and (10) Diagonal Rounds
     • Each round is 4 quarter rounds
     • 

05 Block Ciphers, Pseudorandom Permutations, Feistel Networks, Data Encryption Standard (DES)

1. Block ciphers: encrypt whole blocks at a time

   • 
   • Block size varies, often 64 or 128-bit

2. Pseudorandom Permutations

   • A pseudorandom permutation is a function that cannot be distinguished from a random permutation
   • Maps a set of values $\{0,1\}^n\times\{0,1\}^s\to\{0,1\}^n$ such that:
     • For any key, the function $F$ is a bijection
     • There is an efficient algorithm to calculate F(x) for all keys and all messages

3. Confusion & Diffusion

   • Confusion: Obscure the relationship between plaintext, key and ciphertext
     • often achieved through substitution operations - lookup tables
   • Diffusion: Influence of each plaintext and key bit is distributed throughout the ciphertext
     • often achieved via permutation - swapping or otherwise mixing bits or bytes

4. product cipher - combines a sequence of simple transformations such as substitution (S-box), permutation (P-box), and modular arithmetic

   • SP-networks

5. Feistel Networks: one mechanism used to create block ciphers

   • 

   • During each round, only half of the block is encrypted

   • $f$ - pseudorandom function

   • Encryption & Decryption:

     • Encryption:
     • Decryption:

   • 1 or 2 rounds is not sufficient

   • if $f$ is a cryptographically secure pseudorandom function, then:

     • 3 rounds are sufficient to make a pseudorandom permutation
     • 4 rounds are sufficient to make a strong pseudorandom permutation

6. the Data Encryption Standard (DES)

   • 64-bit block size 56-bit key 16 rounds

   • 

   • $IP$ / $IP^{-1}$

     • Facilitates loading of registers L and R in hardware
     • Adds nothing to security

   • the $f()$ function

     • 

     • $Expansion$ - adds diffusion

       • Increases from 32 to 48 bits to match the round key
       • Half of input bits are connected to two output positions
       • 

     • Substitution boxes (S-box) - adds confusion

       • 
       • The S boxes map 6-bit inputs to 4-bit outputs
       • There are 8 S-boxes in total, each is different
       • 
       • S-box Design

         • S-boxes need to be highly non linear : $S(a)\bigoplus S(b) ≠ S(a\bigoplus b)$

           • This prevents simple systems of linear equations such as we saw in LFSRs

         • Key design principles:

           1. No output bit should be too close to a linear combination of input bits
           2. 1 bit change input should lead to at least 2 bits output
           3. If only the 4 middle bits change, each output must occur exactly once
           4. If the first two bits are different but the last two are identical, the output must differ
           5. For any non-zero difference in input, no more than 8 /32 inputs exhibiting this difference should share the same output difference
           6. A collision (zero difference) is only possible for 3 adjacent S-boxes

     • $Permutation$ - moves bits between S-boxes on the next round

   • the avalanche effect: 1 bit changes on the input, in 1 round there will be at least 2 bits changed, 2 rounds - at least 4 bits, …

06 DES (cont.), Double and Triple Encryption (2DES, 3DES, DES-X), attack DES (Meet-in-the-middle (MITM)), Differential Cryptanalysis

1. the Data Encryption Standard (DES) (cont.)
   • Key Schedule
     • 
     • $PC-1$ - Permuted Choice 1
       • selects 56 out of the 64 bits - Key bits 8, 16, 24, … 64 are not used
     • Left rotations
       • each 28-bit block is rotated left by <<<1 for rounds {1, 2, 9, 16} and <<<2 otherwise
       • The total rotation is $4\cdot1 + 12\cdot2 = 28$, which means $C_0 = C_{16}$ and $D_0 = D_{16}$
     • $PC-2$
       • select 48 of the 56 bits to be used as a round key
     • properties of the key schedule
       • entirely permutation based
       • $C_0 = C_{16}$ and $D_0 = D_{16}$ - can be used for systems with almost no memory at all, when decryption can just go from $C/D_{16}$ back to $C/D_0$
2. Breaking DES
   • brute force - $2^{56}$ attempts
   • key collisions - multiple keys encrypting the same $(x_0,y_0)$ pair
     • likelihood of key collision for an $l$ bit key and $n$ bit block cipher: $2^l/2^n$
     • for DES the probability that multiple keys work for a single $(x_0,y_0)$ pair is $2^{56}/2^{64}=2^{-8}$
3. Double Encryption
   • 
4. Breaking Double Encryption DES
   • naïve brute force - $2^{56}\cdot2^{56}=2^{112}$ attempts (impossible)
   • meet-in-the-middle (MITM)
     • 
     • $2^{56}\cdot2=2^{56+1}=2^{57}$ attempts
     • trade off computation for storage - storage requirement is $2^{56}$
     • assumes some kind of $O(1)$ lookup for $Z_{L,i}$
5. 3DES
   • 
   • either ‘enc -> enc -> enc’ or ‘enc -> dec -> enc’
     • ‘enc -> dec -> enc’ can be used in legacy systems to be compatible with 1DES (if $k_1 =k_2=k_3$, it becomes an 1DES)
   • Often used in banking, smart cards and other payment systems
   • MITM - $2^{112}+2^{56}$ attempts (impossible) with infeasible storage requirements
6. DES-X
   • key whitening
   • 
   • theoretically: search space of $2^{k+2n}$, but meet-in-the-middle and other attacks are available
7. cryptanalysis
   • In modern cryptography, a cipher is declared broken by essentially any attack that is more efficient that brute force
   • types of cryptanalysis
     • Analytical Attacks - Exploit some underlying structural or mathematical weakness in a cipher
     • E.g. meet-in-the-middle attack
       • Derivation of taps in LFSRs
     • Statistical Attacks - Capture statistical patterns between input and output to recover key bits
       • Differential Cryptanalysis
       • Linear Cryptanalysis
   • Differential Cryptanalysis - a chosen plaintext attack
     • aim to find predictable changes in output bits caused by known changes in input bits
     • some input change resulting in some output change $(∆x , ∆y)$ is called a differential, and has some probability of occurring
     • tracing and calculating differential characteristics
     • resisting differential cryptanalysis
       • S-boxes must be designed such that the probability of any pair $(∆x, ∆y)$ is as low as possible
         • AES has a maximum likelihood of a differential per s=box of $2^{-6}$
       • More rounds make differentials even less likely
       • Good permutation to involve more S-boxes
       • DES was specifically designed to resist this kind of attack

07 Groups, Fields, Finite Fields (Prime Fields, Extension Fields)

1. Groups

   • 
     • note that the element $1$ here does not mean integer 1, but a symbol
   • example group: the set of integers $\mathbb{Z}_m=\{0,1,...,m-1\}$ with the operation addition modulo $m$ form a group with the neutral element $0$

2. Algebraic structures of Groups, Rings (see notes on Lecture 02) and Fields

   • Fields are an extension of Groups and related to Rings

3. Fields

   • 
   • example field: the set of real numbers $\mathbb{R}$ with neutral element $0$ for addition and $1$ for multiplication

4. Finite Fields (Galois Fields, GFs)

   • a field with a finite number of elements

   • add, subtract, multiply, invert (divide)

   • 

     • e.g. a field with 11 elements $GF(11)$, a field with 256 elements $GF(256)$ or $GF(2^8)$
     • e.g. $GF(12)$ or $GF(2^2\cdot3)$ is not a finite field

   • Prime and Extension fields

     • 

   • Prime Fields

     • a prime field $GF(p)$ contains the integers $\{0,1,...,p-1\}$
     • arithmetic in prime fields: Let $a,b\in GF(p)=0,1,...,p-1$
       • $a+b\equiv c\pmod p$
       • $a-b\equiv d\pmod p$
       • $a\cdot b\equiv e\pmod p$
       • all members of a prime field have a multiplicative inverse $a^{-1}$
         • for prime fields, $\gcd(a,p)=1,\forall a \neq 0\in GF(p)$

   • Extension Fields

     • an extension field $GF(2^m)$ contains polynomials of degree $m$ with coefficients in $GF(2)=\{0,1\}$
     • $a_{m-1}x^{m-1}+...+a_1x+a_0 = A(x)\in GF(2^m)$ where $a_i=\{0,1\}$
     • e.g. $GF(2^3) = \{0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\}$
     • arithmetic in extension fields:
       • add / subtract
         • e.g. $A(x)=x^2+x+1$, $B(x)=x^2+1$, $A(x)+B(x)=(1+1)x^2+x+(1+1)=0x^2+x+0=x$
       • multiply: must reduce the intermediate result modulo an (pre-defined) irreducible polynomial
         • e.g. $A(x)\cdot B(x)=x^4+x^3+x+1 \pmod{x^3+x+1}=x^2+x$
       • invert: $A(x)\cdot A^{-1}(x)\equiv 1\pmod{P(x)}$

5. AES’s Finite Field

   • extension field $GF(2^8)$ or $GF(256)$
   • irreducible polynomial used: $P(x)=x^8+x^4+x^3+x+1$

08 Advanced Encryption Standard (AES)

1. an SP-Network with a 128-bit block size, a key length of 128, 192 or 256-bits, 10, 12 or 14 rounds

2. 

   • the rounds operate on a state of 16 bytes (128 bits)
   • the key expansion produces number of (rounds + 1) keys
   • all rounds are identical, apart from the last round

3. SubBytes (confusion): replaces each byte of the input block with another byte according to a pre-defined S-box

   • S-box: the multiplicative inverse of 8 bit values in $GF(2^8)$ (strongly non-linear mapping, bijective, an invertible 1:1 mapping) + affine transformation (destroys remaining mathematical structure)
     • no fixed points
     • no inverse fixed points (i.e. no $A_i$ for which $S(A_i) \bigoplus A_i = FF$)
     • minimise the number of fixed difference changes for specific changes in input - reduced the likelihood of differentials and helps resist differential cryptanalysis attacks

4. ShiftRows (diffusion): shifts the rows of the input block cyclically to the left. The first row is not shifted, the second row is shifted one byte to the left, the third row is shifted two bytes to the left, and the fourth row is shifted three bytes to the left

5. MixColumns (diffusion): a matrix multiplication operation that operates on each column of the shifted block

   • All the input bytes in a column influence all the output bytes

6. AddKey: adds the key

7. Key Schedule

   • 

8. Implementation

   • very fast in software and pretty fast in hardware
   • There are numerous cache timing and other attacks possible - In general AES is much harder to implement safely than ChaCha20

09 Block cipher modes of operation: Padding, Deterministic vs. Probabilistic Encryption, ECB, CBC, CTR, Galois Counter Mode, Padding Oracle Attack

1. Block Cipher Modes
   • Most messages don’t come in convenient 128 bit block lengths - Padding
   • We’ll need to run a block cipher repeatedly on consecutive blocks - ECB, CBC, CTR
2. Padding: make message length to be a multiple of the block size - Public Key Cryptography Standards PKCS7 is a common padding scheme
   1. Padding bytes are always added to the plaintext before it is encrypted
   2. Each padding byte has a value equal to the total number of padding bytes that are added
   3. The total number of padding bytes is at least one (i.e. if a message has an exact multiple of the block cipher length, a entire block of padding bytes is added)
3. Deterministic vs. Probabilistic Encryption
   • An encryption scheme is deterministic if some plaintext is mapped to a fixed ciphertext if the key is unchanged
   • Probabilistic encryption schemes add randomness to the encryption process to achieve a non deterministic generation of the ciphertext
4. Electronic Code Book (ECB) (deterministic) - just encrypt each block one after another
   • 
   • DO NOT USE: ECB allows an attacker to infer information on the plaintext - divulges whenever messages or blocks are the same
     • for the same key, same plaintext results in same cyphertext
5. Cipher Block Chaining (CBC) (probabilistic) - XOR the output of each cipher block with the next input
   • 
   • Decryption is similar, but the XOR now takes place after decryption - Easier to parallelise
   • The IV ensures that the encryption is probabilistic - that each encryption of any message is different
   • weakness: Altering ciphertext bits can lead to attacks - Padding Oracle Arracks
     • an oracle is a system we can query and it will tell us if, once decrypted, some text has (in)valid padding
     • manipulate bits in the IV to find valid padding (from …01, to … 02 02, to … 03 03 03, …) and recover $z_i$, and then use $y_{i-1} \bigoplus z_i$ to recover plaintext $x_i$
     • 
6. Counter Mode (CTR) - Encrypt a nonce + counter and use this to mask the plaintext with XOR
   • 
   • This is very easily parallelised
   • Each block is encrypted differently, avoiding the issues with ECB mode
   • it is constructed like a stream cipher
   • weakness: attackers can make predictable changes
7. Galois Counter Mode - Extends counter mode to add authenticity & integrity
   • Very similar to counter mode, but adds an authentication tag
   • Extremely parallelisable
   • Robust to message alteration

11 RSA (Key generation, encryption and decryption), Integer Factorisation Problems, Euler Totient, Fermat’s Little Theorem and Euler’s Theorem, Efficient Computation: Square and Multiply

1. keys are usually 2048 or 4096 bits

2. Security is built around the difficulty of factoring large numbers

3. Encryption performed by the public key can only be reversed using the private key

   • 

4. The authenticity of signatures generated by the private key can be verified by the public key

   • 

5. Integer Factorisation: Any integer can be expressed as the multiplication of a list of prime numbers

6. Euler Totient Function

   • integers $a$ and $m$ are relatively prime if they do not share a divisor except 1, i.e. $\gcd(a,m) = 1$

   • The Euler totient $\Phi$ is the number of integers in $Z_m=\{1,2,...,m-1\}$ for which $\gcd(a,m) = 1$

   • e.g. $\Phi(9)=6$

   • calculating $\Phi(n)$

     • $m = p^{e_1}_1 \cdot p^{e_2}_2 \cdot ... \cdot p^{e_n}_n$
     • $\Phi(n)=\prod_{i=1}^n(p^{e_i}_i-p^{e_{i-1}}_{i-1})$
     • e.g. $240 = 2^4*3^1*5^1$ => $\Phi(240) = (2^4-2^3)(3-1)(5-1)=64$

   • for prime numbers: $\Phi(n)=p^{1}-p^{0}=p-1$

   • for semiprimes $n=p\cdot q$: $\Phi(n)=(p^{1}-p^{0})(q^{1}-q^{0})=(p-1)(q-1)$

7. Fermat’s Little Theorem: for some prime $p$, and any integer $a$: $a^{p-1}\equiv 1 \pmod p$

8. Euler’s theorem: $a^{\Phi(m)}\equiv 1 \pmod m$

   • works for any integer ring $Z_m$
   • A generalization of Fermat’s little theorem

9. RSA Key Generation

   • 
   • $n$, $e$ are public, $p$, $q$, $\Phi(n)$, $d$ are private
   • Typically the public key $e$ is smaller (in bits) than the private key $d$

10. RSA Encryption / Decryption

    • encryption: $x^e\equiv y \pmod n$
    • decryption: $y^d\equiv x \pmod n$
    • it can be proved that $x^{ed} \equiv x \pmod n$ (see slides / textbook)

11. why RSA is secure

    • The security of RSA relies on the fact that it is difficult to derive the private key $d$ from the public key $e$ - there is no known efficient algorithm for factoring large prime numbers

    • for an attacker:

      • $?^e\equiv y \pmod n$
      • $y^{d?}\equiv ? \pmod n$

    • the attacker would like to get $d?$ <= $e\cdot d \equiv 1\pmod{\Phi(n)}$ <= the attacker would like to get $\Phi(n)$ <= without knowing $p$ and $q$ it would be hard enough to calculate factors of $n$, i.e. $\Phi(n)$

12. Efficient Computation of Exponentiation: square and multiply

    • 
    • the computational complexity of exponentiation: for a $T$ bit key, complexity is around $1.5T$
    • brute force: for a $T$ bit key, complexity is $2^T$

13. 65537: a very useful public exponent for RSA

    • the prime is $2^{16}+1$, the largest know number of the form $2^{2^n}+1$, in binary is $10000000000000001$

12 Cyclic Group, Diffie-Hellman Key Exchange, Discrete Logarithm Problem

1. Two parties can jointly agree a shared secret over an insecure channel
2. the multiplicative group $Z^*_n$
   • 
   • e.g. $Z^*_9=\{1,2,4,5,7,8\}$
   • In the majority of cases, we use a prime number $p$ as the modulus: $Z^*_p=\{1,2,...,p-1\}$
   • The cardinality (or order) of a group is the number of elements in that group
     • $|Z^*_p| = p-1$
     • $|Z^*_n| = \Phi(n)$
     • In cryptography the order of a group is extremely important for security
       • 
       • e.g. $ord(3) = 5$
   • Cyclic Group: a group that contains an element $g$ of maximum order
     • Any element of maximum order is called a primitive root, or generator
     • e.g. 2 is a primitive root / generator of $Z^*_{11}$ because $ord(2)=10$
     • e.g. 3 is not a primitive root / generator of $Z^*_{11}$ because $ord(3)=5$ but $ord(2)=10$
     • e.g. $Z^*_{11}$ is a cyclic group because it has an element $2$ of maximum order
   • cyclic subgroups: a subset of a group that is generated by a generator
     • e.g. 4 subgroups for $Z^*_{11}$: $\{1\}$ (generated by 1), $\{1, 10\}$ (generated by 10), $\{1, 3, 4, 5, 9\}$ (generated by 3 4 5 9, $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ (generated by 2 6 7 8)
3. Diffie-Hellman
   • steps
     1. Alice and Bob agree on a large prime $p$ , and a generator $g$ that is a primitive root of $p$
     2. Alice and Bob choose private numbers $a$ and $b$ at random in $Z^*_{p}$
     3. Alice calculates $g ^a \pmod p$ and sends it publicly to Bob
     4. Bob calculates $g^ b \pmod p$ and sends it publicly to Alice
     5. Alice computes $B^a \pmod p$
     6. Bob computes $A^b \pmod p$
   • 
   • shared secret: $g^{ab}\mod p$
   • The Discrete Logarithm Problem - makes Diffie-Hellman hard to break
     • hard enough to calculate $a$ in $3^a \equiv 4675534 \pmod{10000079}$ (in reality, the values are much larger than in this example, making it even harder)
   • attack: e.g. Pohlig-Hellman is based on the prime factorisation of $|G|$
   • To avoid any unexpected small subgroup attacks (e.g. Pohlig-Hellman attack), commonly used DH primes are safe primes
     • A safe prime is a prime $p$ where $(p-1)/2$ is also a prime
     • This will have three subgroups of order $p-1$, $2$ and $1$
     • By choosing a generator of the subgroup of large prime order, we avoid attacks on small factors of the group order

13 Elliptic Curves (Point addition, doubling and the point at infinity), Elliptic Curve Discrete Logarithm Problem

1. elliptic curve for cryptography:
   • points on the curve forms a cyclic group with point addition operation $+$
     • closed, associative, neutral element, inverses, commutative (abelian)
   • point addition (note: all graphs in this chapter is the elliptic curve over $R$. To use it in cryptography a$\pmod{p}$ should be applied to the points on the curve)
     • 
     • point doubling: add a point to itself
     • note: $2P$ is not $2\cdot P$ i.e. $P$ multiplied by $2$. It is just a way to say $P+P$
     • point addition equations:
   • 
     • $P=(x,y)$ $-P=(x,-y)$
   • neutral element: the point $\mathcal{O}$ at infinity
     • The point at infinity is the neutral element on an elliptic curve
     • In practice the point doesn’t have coordinates, and can’t be used within the normal formula
     • $P+(-P)=\mathcal{O}$
     • $P+\mathcal{O}=P$
     • in point addition, when the $x$ values are equal and $y$ values are inverses$\pmod{p}$, the result will be the point at infinity => i.e. $P=(x,y), -P=(x,-y) \to P+(-P)=\mathcal{O}$
       • e.g. $E:y^2\equiv x^3+2x+2\pmod{17}$ $(7,6)+(7,11)=\mathcal{O}$ because $x_1=x_2=7$ and $y_1+y_2 = 6+11=17\equiv 0\pmod{17}$
2. Cyclic groups
   • The points on an elliptic curve including the neutral element $\mathcal{O}$ form cyclic subgroups
   • Under certain conditions all points form a cyclic group
   • 
3. Elliptic Curve Discrete Logarithm Problem
   • give a curve $E$, a primitive root $P$, and a point $aP$, it is hard enough to calculate $a$

14 Elliptic Curve Cryptosystems, Cyclic group, Efficient Computation: Double and Add, Elliptic Curve Diffie-Hellman (ECDH)

1. Cyclic groups in elliptic curve cryptosystems: Given a generator point, points on elliptic curves generate cyclic groups
   • each cyclic group includes the point at infinity $\mathcal{O}$
   • e.g.
   • since $19P=\mathcal{O}$ any multiples of $P$ that add to 19 will be inverses
2. Group cardinality
   • The size of cyclic groups is very important to the security
     • A large $\#E$ is very important to prevent various attacks on ECDLP
   • a curve have $< 2p+1$ points (ideally, if all points on the curve are valid in the cyclic group)
   • Hasse’s theorem: for a curve $E$ over a field $Z_p$, the number of elements $\# E$ is bounded by $\#E=p+1+\epsilon$ where $|\epsilon|\leq 2\sqrt{p}$
   • do not generate own elliptic curves - The vast majority of applications use standard curves
3. Elliptic Curve Discrete Logarithm Problem (ECDLP) in elliptic curve cryptosystems: private keys such as $a$ are integers, generators and public keys are points $(x,y)$
   • generic algorithms like Pohlig-Hellman requires $O(\sqrt{\#E})$ steps
4. Efficient Computation to calculate $a\cdot P$: double and add
   • e.g.
5. Elliptic Curve Diffie-Hellman (ECDH)
   • 
   • shared secret: $ab\cdot G$
6. Elliptic Curve Cryptosystem structure:
7. Implementation of Elliptic Curve Diffie-Hellman
   • point compression: in practice, we do not need to transport full $(x, y)$ coordinates
     • each point contains a unique $x$ and one of two $y$ (positive / negative) where $y = \sqrt{x^3+ax+b} \pmod{p}$
     • Most implementations will use the full $x$ value, and append a single bit representing a positive or negative $y$ value
   • projective coordinates: some implementations adjust the formula for point addition to use projective coordinates $(x, y, z)$ rather than $(x, y)$
     • the curve sits on the plane $z = 1$
     • point at infinity $\mathcal{O}=(0,1,0)$
   • standard curves: The choice of curve parameters influences both security and efficiency of cryptosystems based around ECs
     • no small subgroups, efficient point addition and doubling, known order ($\#E$) of the curve

15 Digital Signatures

1. digital signature that uses a symmetric key: provides authenticity and integrity, but not non-repudiation