FiniteFields.pdf: primes, divisors, gcd

extended gcd: xgcd.pdf

Python

intro: PythonBasics.pdf

+ my CommentsOnPythonBasics.html

Alternate view - compare with Java

JavaVsPython.html

develop code for Euclidean algorithm - loop and recursive

uploaded something close to the result: gcd.py

see code for extended Euclidean: xgcd.py

HW includes extended gcd, recursive

See JavaVsPython.html for added parts as needed on multiline statements, assert, function signatures, string formatting, dictionaries/maps, first class objects, and using classes. List comprehensions, Doctests

recursiveTuples2.py for doctest

develop power functions: slow, fast

time analysis of both methods in terms of power n (For now assume each multiplication takes same time. When done mod m, as will usually be the case, this is true.)

Order estimates: see parts of

http://en.wikipedia.org/wiki/Big_Oh

Bases.html

bases.py for practice with lists, loops, essential base idea!

Develop arithmetic time analysis

simplistic gcd time analysis: if k bits: O(k

r

so the remainders shrink exponentially, and the number of steps is bounded by O(log a) which is O(k). All individual operations are O(k

Fancier book analysis base on the fact the the product of all the quotients is less than a, shows the extended Euclidean angorithm takes O(size(a)*size(b))

Actual computers do 32 or 64 or 128 bits at a time, but the same order results.

Back to FiniteFields.pdf: group, rings, fields See the ErrorInFiniteFields

There is Hw from the end of FiniteFields.pdf: 2, 4, 5ab, 6, 8

Python:

Defining classes: Silly simple example animalW.py,

coding infix operators for groups and fields:

simple version for a concrete group mod26A.py,

More robust version allowing operations with integers, too mod26.py,

HW: improve naive inverse() and __pow__ methods.

Multiplicative subgroups

Z/nZ*, the invertable elements of Z/nZ, is a group under multiplication, called the multiplicative group of Z/nZ

Z/nZ* is group, because it is closed: (ab)

For prime p, Z/pZ* contains all elements of Z/pZ except 0, and hence Z/pZ is a field. I like the (shorter) notation for Z/pZ, emphasizing that it is a field: Fp

The Euler phi function will be very important for cryptography:

If p is prime, what is (p)? (p

More on phi:

http://en.wikipedia.org/wiki/Euler_phi_function

Fermat's Little theorem is the basis of RSA:

http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem

Group theory proof

http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem#Proof_using_group_theory

which in turn uses Lagrange's theorem

http://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)

To calculate the phi function easily we can use the Chinese Remainder Theorem

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

The page constructs a solution, but does not include a proof that it is unique.

If x and y are solutions, then z = x-y solves z mod n

Hence z is a multiple of each n

Now to help calculating phi:

Alternate proof that

Phi is multiplicative:

For coprime m,n, (m)(n) = (mn)

Proof: We have a correspondence between (a,b) in Z/mZ X Z/nZ and x in Z/mnZ via the Chinese Remainder Theorem, but we only want to deal with the multiplicative subgroups.We have not show the direct correspondence between them, but we can:

Assume the setup for the Chinese Remainder Theorm, with two equations:

x mod m = a, x mod n = b. assuming gcd(m, n) = 1.

We get the correct count if the following is true:

if gcd(m,a)=1 and gcd(b,n)=1 iff gcd(x, mn)=1.

Proof =>

In this directon we can add the assumption

gcd(a,m) = 1 gcd(b, n) = 1.

Since gcd(m,n)=1, there are s and t so

sm +tn = 1.

This also means gcd(m, t) = 1.

x = bsm + atn is the construction in the Chinese Remainder Theorem.

The assumptions above say none of the factors a, t, n in atn has a common factor with m, but of couse bsm has m as a factor, so x = bsm+atn shares no common factors with m.

By a symmetric argument, x shares no factors with n.

Hence x shares no factors with mn, and gcd(x, mn) = 1

Proof <=

Conversely, if a and m share a factor, so do x and a, since x = bsm + atn.

The argument for b and n is symmetric.

Done.

In particular, we will use the fact for RSA that for distinct primes p,q: (pq) = (p-1)(q-1)

Do examples

Caesar

See caesar.py

...

Matrix operations and inverses are mentioned in several places, but not anything about algorithms

Based on solving systems of linear equations. What are approaches?

Basic examples, oprations, solutions, translations

http://en.wikipedia.org/wiki/Square_matrix

There are many more sub-topics than we need! We will focus on the relationship between matrices and systems of linear equations, determinants, theoretical definition and efficient calculation with systems of linear equations. Issues associated with different number systems as elements: floating point, integer, modular group, modular field, special case of mod a power of 2. Rings of matrices.

http://en.wikipedia.org/wiki/Determinant

See the intro, sections 5 - 8.1

http://en.wikipedia.org/wiki/Elementary_row_operations

See http://en.wikipedia.org/wiki/Gauss%E2%80%93Jordan_elimination

Eventually look at gaussJordan2.py uses mod_arith (solution to HW3) - in the form mod_arith.pyc online

The original Gauss-Jordan algorithm depends on having inverses on each row, though the theoretical derivation through determinants only needs an invertible determinant. For instance in the mod 6 matrix

3 2

2 3

all the elements are zero divisors, but its determinant is 3*3 - 2*2 = 5 = -1, invertible. In fact the matrix is its own inverse!

We can get there with elementary row operations, NOT multiplying by a 1 divisor:

3 2 1 0

2 3 0 1

r1 <- r1 - r2

1 -1 1 -1

2 3 0 1

r2 <- r2 - 2*r1 (using 5 = -1, 3 = -3)

1 -1 1 -1

0 -1 -2 3

r2 <- -r2 (-3 = 3)

1 -1 1 -1

0 1 2 3

r1 <- r1 + r2

1 0 3 2

0 1 2 3

so the matrix is shown to be its own inverse by row operations that do not multiply the determinant by a zero divisor.

OK, that is a concrete example. In general if a and b are in the current column worked on, and a = qb + r (integer arithmetic), then you can replace the row with the a so the column entry becomes a-qb = r, and you could continue working with this row and the row with the b, following the sequence of operations for the gcd until one row contains gcd(a, b), all with row operations that do not change the determinant.

In the example above, after only one step, the gcd was 1, definitely invertible, but in more complicated cases the gcd for two column entries may not be 1 and it may even be a 0 divisor. You need to think about that carefully to attempt HW4 problem E, and prove the algorithm works in general.

For extra extra credit in 331 (or extra credit in 431) you can avoid an extra level of looping if you look at the multiples coming from the q's and see how they relate to xgcd. Try an example. This does not go quite far enough by itself, See the slight elaboration of xgcd, mgcd with its documentation string, in the revised xgcd.py. It could speed up the algorithm....

Relation of determinant of

1 2 3

2 5 9 to

4 0 1

2 4 6 5 2 3 2 5 9 1 2 3

2 5 9 10 5 9 1 2 3 1 2 3

4 0 1 20 0 1 4 0 1 4 0 1

r1*2 c1*5 r1<->r2 r2=r1

Elaborated gaussJordan2.py:

mxvSolve(m, v, gjSolver) solves mx = v, m a square matrix

transpose(m)

add(m1, m2) m1+m2

sub(m1, m2) m1-m2

linComb(m1, m2, a, b) a*m1 + b*m2

mul(m1, m2) converts plain liat s m1 to matrix [m1]

alternate name convertMat for matConvert (to be conistent wih other names)

elaborated display methods

How was the reading? Questions?

Buchamnn block cypher coding basics capLetCode.py

After class added affineEncrypt function - useful for HW

Posted gaussJordan26.pyc and gaussJorday27.pyc to help with HW (Take the one you need and remove digits from the name.)

Corrected class cryptanalysis of affine cipher: affineCrypt.txt. Thi is an (edited) history of messing in the Python shell - it is not executabel Python.

One trick was to solve AW=C for A, we need to consider the equivalent W

Skipping the chapter on the practical AES: important block cipher, but no real intellectual content. It is just a recipe that is quick to execute in hardware. It does get used for a sequence of blocks, and the sequential block algorithms from your reading are important there. By the way, in Python bitwise exclusive-or is ^. The main mathematical content of the block sequence algorithms is just that (a ^ b) ^ b = a, so f(x) = x ^ b is its own inverse.

Both the block sequence code and AES in Python are in aes.py. You are NOT responsible for AES, beyond knowin it is a secure, fast symmetric block cipher.

The code there for the block sequencing CBC, ... may be clearer to programmers than Buchmann's outline.

On to math and some cryptanalysis of RSA:

http://en.wikipedia.org/wiki/RSA

A small e is breakable. e = 2

Python. I do not know what was wrong with his Python environment that the Fermat test did not work. I have two versions online in the code:

FermatPrime.py uses our Mod calculating, which does the powers by squaring, using aclass generated with ZMod.

FermatPrimeDoty.py and the imported modpower.py that he gave you.

There is one strange thing about the terminology. If a<n and a is not prime to n, then the test of Theorem 7.4.1 will fail, So the test fails if a is a witness or if gcd(a, n) > 1. Both indicate n is composite!

I agree with the basic idea of his homework. See my version of the homework, due Monday, Oct 19:

Fixed docs for gcd, xgcd

Exam context: MidTermTopics.html

Questions?

gcd(a[1], a[2], ... a[n])

Historical note on primalty testing: Miller-Rabin is an efficient curent probababalistic test, but it was not the first. For RSA to be practical, a test is needed. An older test is the Solovay-Strassen primality test

http://en.wikipedia.org/wiki/Solovay%E2%80%93Strassen_primality_test

which uses Jacobi symbols in a test that reduced the probability of n being composite by only 1/2 each time.

factorAttack.pdf

http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding

or different e values is needed if a message is going to multiple recipients.

RSA.py In real life RSA is not used to directly encode messages!

More math:

Polynomial Fields

The gcd of polynomials will always be taken to be monic.

To extend F

Rabin's Irreduibility Test(1980):

A polynomial f of degree r over the field F_{p} is irreducible if and only if x^{q} = x mod f, where q = p^{r}, and

gcd(f, x^{s} - x) is a 0-degree polynominal for each s = p^{r/t} where t is a prime factor r.

gcd(f, x

For example, if r is prime, the requirement is just that x

class PolyMod in polymod.py, polynomials over modular rings

class PolyModP in polymodp.py, for finite fields of size p

Look at

xgcd - updated to use divmod in code and after class do mgcd documentation right!

mod_arith.py - updated so class, not just self provides modulus

mod_arith.py - updated so class, not just self provides modulus

projects: finding irreducible polynomials with different levels of efficiency, order of sample elements.

Accumulating a list of irreducible polynomials makes sense, but for any irreducible polynomial p, k*p is also irreducible if k is a number not equivalent to 0. It is not useful to inlude all of these, so we will generally consider monic irreducible polynomials, and use monic polynomials for polynomial moduli.

A loose end from class: generating a constant other than 0 or 1 in xgcd with polynomials. The little script testpolyxgcd.py produces an example:

xgcd param, mod 7: 5x^2 + 3x + 4 and x^3 + x + 1

gcd: 4 with coefficients: 4x + 6 and 1

so gcd is not 1, but another nonzero constant.

This shows the need for the two-step inversion in PolyModP's inverse method.

ElGamal: ElGamal was introducted for a general finite field, with a power of a prime elements. It works fine if the power is 1, and the manipulations are slightly easier.

An issue for any discrete log approach is finding a generator with a large order. Recall Lagrange's theorem that the order of each element divides the order of the group. For Z/pZ*. the order of the multiplicative group is p-1, and while p is prime, there is nothing in general we can say about the factorization of p-1 (other than it has a factor of 2!). On the other hand where we get to choose p, we can make requirements on p-1 also. As Buchmann suggest we can look for a prime p so that p-1 = 2q, for another prime q. How many generators will the multiplitive group have? How can we easily test the order of a random element?

Later see ElGamalIntHW.py. Homework will be to complete ElGamal cryptosystem in Z/pZ.

Some discrete log attacks (Buchmann Ch 10)

Shanks baby/giant step

http://en.wikipedia.org/wiki/Baby-step_giant-step

start Python code. Finsh for HW

Pohlig-Hellman ruduces work in discrete log when the order of the multiplicative group can be factored. Start wih multiple primes in factorization in class. Then case with a power of a prime:

PohligHellman mod p

Code PohligHellman.py

Hashing: pdf SHA-1 Python

Notes after class that will discuss more next week:

- I combined and extended the basic factoring/prime functions into factoring.py.
- primeList is copied in from primeSieve.py (no need for primeSieve.py now)
- I included the algorithm I used in carmichael.py to factor using a prime list into factorGivenPrimes
- Since having prime multiplicities is useful not only in PohligHellman, I added factorMultiplicity.
- I modularized PohligHellman.py and renamed things looking ahead:
- Looking
ahead I renamed the special versons that we discussed mod p with,
PohligHellmanModP, getXModP. There are now stubs for future more
general versions where alpha and beta are just group elements, in an arbitrary finite group.

- Rather than mimicing a previous factoring function (bad programming practice!), I use it (motivating the changes above to factoring.py)
- I emphasized the brute force discrete log by pulling it into a function discreteLogModP (and speeded it up). Illustrating a change to the more general group form, I also added discreteLog for use with an arbitrary group (unused at present).
- I put Dr. Doty's version of the Chinese Remainder Theorem into my crt.py, keeping his name ChineseRemainder.

- In getXModP:
- I got rid of an extraneous modulus calculation (xFinal < q**r always without the mod q**r).
- I got rid of some of the repeated exponentiation by introducing qPow,the current power of q, and oDiv, the curent order: the original group order p-1 divided by the next power of q.
- I got rid of repeated use of xgcd for an inverse, calculating the inverse of alpha, alphaInv, just once before the loop.

- Overall files to download/update: factoring.py, crt.py, PohligHellman.py. For reference, I renamed toversion discussed in class: PohligHellmanOld.py.

Pohlig-Hellman generalize from mod p group, see discreteLogModP vs discreteLog

Rabin irreducible example. PLAN

Comments on HW8 2 -> HW10

More on solving DL: There are other more complicated methods to describe and prove: Pollard rho; index calculus, analogous to attacks for RSA. It may be that the (still unknown possible) killer RSA attack will not translate to the finite fields, but it may well. We will need to go further afield (or a-group) to get to very different situations.

ch 12 through 12.6

http://en.wikipedia.org/wiki/Digital_signature

http://en.wikipedia.org/wiki/Universal_forgery

http://en.wikipedia.org/wiki/Digital_Signature_Algorithm

Alternate groups for DL use elliptic curves:

http://en.wikipedia.org/wiki/Elliptic_curve

I refactored the Mod class. I suggest you copy all your present code to an oldCode directory, as I have done online, though the changes should not interfere except in one situation in doctests where they produce "ZMod" in their output. After backing up, copy all the files in codeChange.zip over the directory with the current files you have from me.

Changes:

Mod is now a named class in mod.py (shortened from mod_arith.py). You can still you ZMod, as in Mod7 = ZMod(7).

You can now iterate over whole Mod, ModPolyP and Elliptic groups given one element, elt:

for z in elt.group():

....

I added this principally to allow brute force calculations of arbitrary small Elliptic groups. See findE.py, an interactive place to print out whole elliptic groups.

There was a bunch of refactoring under the hood, that make the code in Mod, ModPoly, ModPolyP and Elliptic easier, but is presumably just used inside these classes. You can skip the rest of this technical paragraph if you like. The group iterator is implemented uniformly by calling a new method next in each class, that produces a next element after self. In Mod and PolyModP this in turn is implemented usng the idea in irred.py, encoding each element as an int with k = int(elt), and reversing this, given a element, other, in the same group , with other.likeFromInt(k). Cyclic traversal is possible because of the method totCodes: The sequence of all int codes for the finite Mod or PolyModP group containing elt are range(elt.totCodes()). Some common features in my classes are abstracted out into superclasses defined at the top of mod.py: FiniteGroup defines methods next and group, and ParamClass defines methods like and tryLike.

My code: elliptic.py Play with findE.py.

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

We are not likely to get to it, but elliptic curses also provide an algorithm for factoring!

Elliptic curves for digital signature standard:

http://en.wikipedia.org/wiki/Elliptic_Curve_DSA

Proof is not inthe elliptic variation - but almost line for line analogous, with some different names, and swapping the symbolism for the group operation from * to +. I use capital letters for group elements, G, the generator, and Q, the public key.

k = s

= (wz + wrd) mod n

u1G + u2Q = wzG + wrQ = wzG + wzdG = (wz+ wrd)G = kG = (x1, y1) -> r = x1 mod n

Note: there is no arithmetic relationship between n and the size of the underlying finite field, and the underlying field could be formed of polynomials. Hence the conversion to integers of Fq elements used for elliptic curve coordinates must be agreed on - presumably the usual canonical integer representation (obtained in my code by int(x)).

So we have a cryptographic use of elliptic curves. What don't we have that might seem obvious?

How invertibly map a message encoding to an elliptic curve point?

Secret Sharing

http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

HW: SecretShareEncrypt(c, p, n, k) with plaintext c mod prime p, for secret sharing needing n people to decrypt, k >= n, returning a list of k pairs (v, f(v)) for an polynomial f of degree at most n-1 over Z/pZ, that has all coefficients but the constant random, and the constant = c. (The initial post here was wrong in insisting that the polynomial be exactly of degree n-1.) SecretShareDecrypt(pairs) takes n or more of the secret pairs and returns c. Note: We have only used polynomials so far as expressions that are elements of a ring or field. In PolyMod, they are also functions that you can evaluate: For polynomial p, p(k) gives the value, as a normal function.

- findE.py: I do the
checks for prime/irreducible input. I assume irred.py exists. You
can change it to irredHW if you need to.

- PolyMod: sparse polynomial constructor and __pow__ with optional polynomial modulus, allowing use of 3-parameter pow function.
- PolyModP: uses PolyMod 3-parameter pow.

Play with gnupg?

Also use for ssh into Loyola

http://syshandbook.cs.luc.edu/how-to/secure-shell-ssh

Public Key Infrastructure

Buchmann 299-306

ftp://ftp.pgpi.org/pub/pgp/7.0/docs/english/IntroToCrypto.pdf

p6 good reference list, technical and poltics

p13 recognize most fo the names?

p18 nice diagram of hash and digital signature

p22 certificate data. NOte we hae not concentrated on symmetric systems - some new algorithm names

p25 Web browsers largest users of X.509 certificates

p27 trust models

p29 complicated PGP model, with marginal trust.... ? 2 marginally trusted = 1 really trusted?

p32 key splitting - we wre more technical with latest hw

p41 The advertisement had to come in here somewhere.

gpg howto:

http://www.dewinter.com/gnupg_howto/english/GPGMiniHowto.html

have a keysigning party!

http://www.cryptnet.net/fdp/crypto/keysigning_party/en/keysigning_party.html

The shell history or me using this is at gpgShell.txt.

odds and ends to fill in:

2.14 element orders. Thm 2.14.1 hw ex?

4.3 birthday (why avoiding hash collisions is hard) Ex 4.8.6

http://en.wikipedia.org/wiki/Birthday_problem

4.4 perfect secrecy, vernam one-time pad

http://en.wikipedia.org/wiki/One-time_pad

8.5 Diffe-Hellman key exchange code?

http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

12.8 blind signature

http://en.wikipedia.org/wiki/Blind_signature

14.3.3 zero knowledge proofs: general:

http://en.wikipedia.org/wiki/Zero-knowledge_proof

modular arith based: Code?

http://en.wikipedia.org/wiki/Feige-Fiat-Shamir_Identification_Scheme

Go over review with review problems.

Do simpler zero-knowledge algorithm Fiat-Shamir Last week's extra complicated to get basic idea across; book's poorly written; try:

http://www.cse.scu.edu/~tschwarz/coen350/zkp.html

Since r is random and cannot be recovered from r

Of course getting r donesn't help at all with s, but forces truthful r

Questions? Topics for review?

TAKEHOME EXAM as described in email.