Test II Review Sheet for
Colorado State University, Pueblo
Math 319 — Number Theory —
Spring 2014
Definitions
You should be able to give careful, complete, formal definitions of — and
examples and know theorems involving — the following terms:
- the [multiplicative] order of $a$ in mod $n$,
$\operatorname{ord}_n(a)$
- the cyclic subgroup of $(\ZZ/n\ZZ)^*$ generated by $a$,
$\left<a\right>$
- a coset of $\left<a\right>$
- cryptography
- cryptanalysis
- cryptology
- cryptosystem
- confidentiality of a cryptosystem
- [message] integrity of a cryptosystem
- [sender] authentication of a cryptosystem
- [sender] non-repudiation of a cryptosystem
- the scytale cryptosystem
- plaintext
- cipher
- ciphertext
- encrypt, decrypt
- key
- Caesar cryptosystem
- Kerckhoff's Principle
- ROT13
- Vigenère cryptosystem
- one-time pad
- keyspace
- brute force attack
- message space
- frequency distribution and frequency analysis
- ETAOINSHRDL
- square error, a distance between distribution functions
- symmetric/private-key cryptosystem
- asymmetric/public-key cryptosystem, with its
public key and private key
- [cryptographic] salt
- [cryptographic] one-way function
- the RSA cryptosystem
- the prime number counting function $\pi(x)$
- cryptographic hash function
- pre-image resistance
- second pre-image resistance
- collision resistance
- an RSA digital signature: accept, reject,
signing key, and verification key
- man-in-the-middle attack
- digital certificate
- web of trust, key-signing party
- certificate authority [CA]
- public key infrastructure [PKI]
Theorems, Conjectures, and Algorithms
Please know careful, complete statements of the following:
- Wilson's Theorem
- the version of Lagrange's Theorem for $\operatorname{ord}_n(a)$
- Euler's Theorem
- Fermat's Little Theorem [two versions]
Things to know how to do
- encrypt and decrypt messages with the cryptosystems
mentioned above
- sign and verify using RSA digital signatures
- use frequency analysis to crack a simple cryptosystem
- do any of the steps (1)-(7) of §4.4 of
YAINTT (such as,
e.g., fast modular exponentiation)
- sign or verify with the RSA digital signature
algorithm
- use a man-in-the-middle attack in some situation where you
completely control a network
- make a digital certificate for someone (say, at a key-signing
party)
- give proofs of any of the theorems mentioned above
Format of the test
Be able to state — in full formality and five-part harmony — all
the definitions. You will be asked to do so for something like four or five
out of seven or eight choices. You must also be able to give context, ideas,
examples, etc., for each term you define!
You will also be asked to give full and formal statements of several of the
theorems mentioned above, as well as an example (or counterexample when some
hypothesis is dropped) to which the theorem applies. There are only four
theorems above, so you should be ready on all of them. You will also
likely have to use those theorems in proving other statements.
There will then be a choice of three [or four] out of six [seven, or eight]
proof-y and/or computational things to do. Some of these will be proofs of
the above theorems. Others will be to perform some cryptographic or
cryptanalytic task with given data -- obviously, this data will be small, and
you may use a calculator to help you with it. Finally, there will be some
small statements, on the level of maxiquizzes, that you can choose to prove.