Math 187A (Fall 2025) [ARCHIVE]

December 05: Quiz 6

December 03: <No class>

December 01: <No class>

November 26: 6: We first defined the notion of an order of a point P on an elliptic curve E -- it is the smallest r > 0, if it exists, such that rP = O. We noted that for an elliptic curve over the real numbers, very few points have finite order. An elliptic curve E with a and b integers is nonsingular modulo p if its Discriminant is not divisible by p. Fixing such a p, we discussed the solutions of E modulo p; the solutions of E modulo p along with the point at infinity can also be endowed with an addition operation. Since the number of solutions modulo p is at most p^2, all points on E modulo P have finite order, denoted ord_{E, p}(P). Furthermore, if rP = 0, then ord_{E,p}(P) divides r. The Discrete Logarithm Problem for Elliptic Curves is the following: given a prime p and an elliptic curve E which is nonsingular mod p, and points P and Q on E mod p, if Q = rP, can you compute r? This problem is computationally hard and forms the basis of most Elliptic curve cryptographic algorithms. We then briefly discussed the Elliptic Curve Diffie--Hellman algorithm -- this is very similar to the ordinary Diffie--Hellman algorithm, except the public key is (E, p, P) where E is an elliptic curve which is nonsingular modulo p, and P is a solution of E modulo p; and rather than exponentiating an integer modulo p, both Alice and Bob, after choosing secret keys k_a and k_b, instead compute and share k_a P and k_b P respectively; and the shared message is just the point k_a k_b P on E modulo P.

November 24: For us, an elliptic curve E is, for fixed a and b with -16(4a^3 + 27b^2) ≠ 0, the points on the x-y plane defined by the equation y^2 = x^3 + ax + b along with the point at infinity. We are interested in elliptic curves as we can use the geometry of an elliptic curve to define an addition operation on its points. In class, we fixed the elliptic curve E y^2 = x^3 + 17. The points P = (2,5), Q=(-1,4) and R=(-2,3) are on E. We computed Q+R and 2P in class. To compute Q+R, we first draw the secant line joining Q+R [y = x+5] and find the third point of intersection [(4,9)], and reflect this point along x-axis, to obtain Q+R = (4,9). To compute P+P, we draw the tangent line to E at P [y = 6/5x + 13/5] and reflect the second point of intersection along the x-axis. See this Desmos graph.

November 21: Quiz 5

November 19: For an odd prime p, we introduced the Legendre symbol (a/p) which is defined to be 0 if p divides a, +1 if p does not divide a and a is a quadratic residue mod p, and -1 otherwise. We computed some values and proved Euler's criterion: (a/p) ≡ a^{(p-1)/2} mod p. I finally introduced the notion of an Elliptic curve y^2 = x^3 + ax + b with a, b real numbers; the Discriminant of the Elliptic curve is -16(4a^3 + 27b^2) and for an Elliptic curve, the value of the Discriminant is nonzero.

November 17: After recalling the Diffie--Hellman key exchange protocol, we saw the Elgamal encryption system which also exploits the difficulty of the discrete logarithm problem. We then discussed how to find the order of a^d modulo n provided we know the order of a modulo n -- it is just ord_n(a)/(gcd(d, ord_n(a)). We finally defined the notion of a quadratic residue -- an integer a is a quadratic residue modulo n if a is a square modulo n, i.e., there exists x such that x^2 ≡ a (mod n). 

November 14: We introduced the notion of a primitive root, i.e., an integer a such that the order ord_n(a) = phi(n). Modulo an integer n, a primitive root need not exist, but if n is a prime, a primitive root always exists, i.e., if p is a prime, there exists a g not divisible by p such that g^{p-1} ≡ 1 (mod p) and g^i is not equivalent to 1 (mod p) for 0 < i < p-1. Furthermore, the integers g, g^2, g^3, ..., g^{p-1} are all pairwise unequal modulo p, so that means for each integer j in {1, 2, ..., p-1}, there exists a unique integer i in {1, 2, ..., p-1} such that g^i ≡ j (mod p). We set i to be the discrete logarithm log_g (j mod p). Given a primitive root g modulo p, computing the discrete logarithm is in general a hard problem. We exploit this in the Diffie--Hellman key exchange protocol.  

November 12: We performed the Miller--Rabin primality test on 221 with base 174 and base 2 -- 221 is a strong probable prime to the base 174, but 2 was a witness to the compositeness of 221 = 13 x 17. We then explained how to compute integers from a string of text using our standard letter-to-number correspondence. The issue with this was that if a string began with a trail of A's, then removing the trailing A's would result in the same integer. To fix this, we instead use a base 27 representation where a space corresponds to 0, A corresponds to 1, B corresponds to 2, and so on. We then introduced the notion of order of an integer a modulo n where gcd(a, n) = 1: it is the smallest positive integer r such that a^r ≡ 1 (mod n). We saw that ord_n(a) divides phi(n). 

November 10: Quiz 4

November 07: We showed why RSA works, i.e., why c^d is equivalent to m mod n, and why if you believe factoring n into pq is hard, then RSA is secure (i.e., the codebreaker EVE cannot easily compute phi(n) from her knowledge of n). See this wikipedia page for more information. We then talked about the Miller--Rabin primality test.

November 05: We saw Euler's theorem: for coprime integers a and n, we have a^{phi(n)} ≡ 1 (mod n). This allows us to reduce computations of large exponents a^M to smaller exponents a^r where r is the remainder when M is divided by phi(n) (i.e., M = phi(n) q + r, with 0 <= r < phi(n)). To compute a^r mod n, we can first write r in binary, compute a mod n, a^2 mod n, a^4 = (a^2)^2 mod n, ..., (a^{2^t}) by successive squaring and compute a^r mod n by putting the two together. We then saw the first modern cryptographic algorithm, the RSA algorithm: BOB chooses a large number n = pq, where p and q are two large distinct primes, and also a number d which is coprime to phi(n) = (p-1)(q-1). BOB computes a multiplicative inverse of d mod phi(n), call it e. The pair (n, e) are made public; p, q, and d are private. If ALICE wants to send a message m, she computes c = m^e mod phi(n) and sends c to BOB., who simply computes c^d, which we will show recovers the message m. 

November 03: I explained how to prove the Fundamental theorem of arithmetic from the definition of divisibility and prime. The crucial result we needed was Euler's lemma: if a prime p divides ab, then p either divides a or it divides b. The proof of Euler's lemma is just a clever application of Bezout's identity. I then stated the formula for the phi(n) based on the prime divisors of n and we saw how it easily follows from the multiplicativity of phi -- that is, for coprime integers a and b, phi(ab) = phi(a) phi(b). I sketched a proof of this result. Reflection Assignment 2 is available on Canvas. 

October 31: We saw how to implement a known-plaintext attack for any ciphertext that was encrypted using a simple substitution cipher (see textbook Section 3.9). We then jumped back to basic number theory and defined divisibility, prime numbers, and recalled the prime factorization theorem: given a natural number n > 1, it can be factored uniquely into a product of prime powers (up to reordering). We then defined the Euler totient function by the formula ϕ(n) = number of nonnegative integers < n which are coprime to n. So ϕ(5) = 4 and ϕ(9) = 6 (since 1,2,3 and 4 are coprime to 5, and 1,2,4,5,7,8 are coprime to 9).

 October 29: Quiz 3.

October 27: We learnt how to perform the G-test with an example (see textbook Section 3.7) and how to decipher a ciphertext which was encrypted using rectangular transposition using the G-test.

October 24: We described how to break the Vignere cipher. The key idea we introduced was the Index of coincidence for an English text. The Index of Coincidence is defined in the textbook and it can be approximated by 26 (p_A^2 + p_B^2 + … + p_Z^2) where p_A = (# of times A occurs in the text/(total # of letters in the text), and similarly for p_\alpha for other \alpha. While the Index of coincidence can be as large as 26, for (large) plaintext from the English language, this is almost always between 1.5 and 2, and very often 1.75 ± 0.1. Now, to break the Vignere cipher, we first guess the period p and break the ciphertext into p columns and compute IC of each column. If the IC’s of all columns are ~1.75, we can assume we have guessed the period correctly, and then guess the shifts of each column via a Frequency analysis as we did on October 15. If the IC’s of all columns are not close to 1.75, we change the period and try again…

October 20: Introduced probability spaces, random variables, and conditional probability. Reading homework from last week is only due October 21 by noon via the usual form, and another Reading Homework is due October 22 by midnight (read first three sections of Chapter on Codebreaking and solve Exercises 3.3.5, 3.3.12, 3.3.13, 3.3.14) via new Google Form.

October 17: Quiz 2. Reading Assignment for October 20: Exercise 3.2.4, 3.2.5, 3.2.6, and 3.2.7 (Google Form has been updated).

October 15: We did another Hill Cipher example and moved to Codebreaking, which is the point of view of Eve rather than Alice and Bob. We talked about Frequency Analysis which allows us to easily break any simple substitution ciphers. We fumbled through one example (opening passage of "A tale of two cities") using the Sage cell in the textbook. Please try the last example from Section 3.2. The reading assignment from Oct 13 is only due tomorrow at 9am.

October 13: We saw that if the encryption function E(x) = a x + b and r is an inverse of a mod 26, then the Decryption function is D(y) = ry - rb. We also saw that the number of different Affine ciphers is 12*26. We then talked about 2 x 2 matrices, when they are invertible mod 26, and how to compute their inverse. Using this, we defined the Hill Cipher, the key for which is an invertible 2 x 2 matrix. The reading assignment is slightly different and is only due October 16, 9am.

October 10: We deduced the modular inversion theorem: a is invertible mod n if and only if gcd(a, n) = 1; in this case, the inverse of a is a Bezout coefficient for a in the identity "r a + s n = 1". This allows us to generalize the Caesar cipher in another way, which is called an Affine cipher. The Caesar cipher can be thought of as applying the transformation E(x) = x + b mod 26, where b is the shift. For an affine cipher, we can do any linear transformation E(x) = ax + b mod 26, as long as this function is invertible (so that the ciphertext is decipherable). By the modular inversion theorem, this is possible if and only if gcd(a, 26) = 1. 

October 08: We defined the greatest common divisor of two integers and noted that gcd(a, 0) = a for a nonzero positive, and gcd(bq+r, b) = gcd(b, r). These two observations immediately lead to the Euclidean algorithm. The reason why we care about the Euclidean algorithm is not necessarily to compute the gcd but rather that we immediately obtain Bezout's identity: for any integers m and n, there exists integers r and s such that gcd(m, n) = r m + s n; the coefficients r and s here are called Bezout coefficients. We did many examples in class. 

October 06: Quiz 1

October 03: We finally introduced modular arithmetic and the key identitites: a ≡ a' (mod n) and b ≡ b' (mod n) implies a + a' ≡ b + b' (mod n) and aa' ≡ bb' (mod n). We then recast the Caesar cipher using modular arithmetic (encrypting is just adding the shift mod 26 and decrypting is just subtracting the shift mod 26). This quickly allows us to come up with the Vigenère cipher which requires a KEY word: this is a ``periodic" Caesar cipher where the period is determined by the length of keyword and the shift is determined by the letters of the keyword.  Reflection Assignment 1 is up and is due on October 10.

October 01: We started with a few examples of the Playfair cipher in detail. Explained how to obtain the 5x5 grid used in Playfair cipher from a keyword. Spent some time discussing certain conventional issues that come up in Rectangular transposition, and while encoding the phrase for Playfair cipher. [For the most part, we will stick to the textbook; attempt many examples with the Sage cells to sus out possible edge cases like BOX]. Reading assignment: sections on "Overview of Classical Cryptosystems", "Rectangular transposition", and "Masonic cipher". Reading assignments are due by noon on the day of the next non-quiz class day. 

September 29: Saw the following substitution ciphers:  Caesar Cipher, Simple Substitution cipher, and Polybius Square (ADFGVX cipher). Saw a short example of using the Playfair cipher. Read Chapter 1 from the textbook for Reading Assignment and fill the google form before noon on Oct 1. The first quiz is on October 06.

September 26: Quick history of cryptography. Saw how to use Rectangular transposition