MA 591 Cryptography
Time T. T. 4:30-5:45
Classroom: 216 Daniels
Instructor: Ernie Stitzinger, SAS 4121, stitz@ncsu.edu, 919-515-3258
Technology Expert: Katie Ahrens, kaahrens@ncsu.edu
Text: An introduction to mathematical cryptography by Jeffrey Hoffstein, Jill Pipher and Joseph Silverman
Supplementary Texts:
A course in number theory and cryptography, by Neal Koblitz
Introductory algebraic number theory by Saban Alaca and Kenneth Williams.
Lindsey Bosko Kangaroos PDF
The grade will be determined by homework, no tests.
Course:
The course will study classical and new public key cryptography. Systems, whose hardness is based on factoring, such as RSA; discrete logs in abelian groups , such as the Diffie-Hellman key exchange and El-Gamal with elliptic curves; lattices, such as NTRU and ring learning with errors, will be featured. Featured also will be the standard attacks on these systems.
Student Learning Outcomes:
To learn the ideas of security systems; what makes them good or not so good. The interplay between functionality and security. What are the currently studied problems. The influence of the pending quantum computer on todays research. The interplay of pure and applied mathematics in an extremely significant area of research is a highlight. Job market preparation.
Homework
CHAPTER I
I. Find the inverse of 3 mod 29 in two ways.
II Graph problem
III.26a, 34b
IV. 40
V. 9a and 10a
VI 46,48, 50
VII. 9d and 10d. Computer
CHAPTER II (Use the computer whenever you want) DLP.
I. Solve log$_2$(13).
II.Alice and Bob agree on p=1373 and g=2 for a key exchange. Bob chooses exponent b=871 and computes g$^b$ mod p.. Alice picks a and computes g$^a$=974 mod p. What is the key they obtain using Diffie-Hellman?
III. Alice picks prime p=11, g=2 and private key a=6 and computes x=g$^a$=9 and sets out her public key (p-11, g=2, x=9) to use in the El-Gamal. Bob wants to send message w to Alice. He picks k and computes y=$g^k$=8 and z= w$x^k$=4 and sends (y,z) to Alice. What is w?
IV. Solve 11$^x$=21 in F$_{71}$ using Shanks.
V. Find the square root of 340 mod 437
VI. Solve 3$^x$=4 mod 7 using Pohlig-Hellman
VII. Use the Pollard lambda to solve 6$^x$= 3 mod 11
CHAPTER III
Problem Set 3
FACTORING February 5, 2019
I.a. Alice chooses primes p and q and lets n=pq. Alice picks g in Z$_n$ and computes g$_1$=g$^{p-1}$ mod n and g$_2$=g$^{q-1}$ mod n Her public key is (n,g$_1$,g$_2$). Bob wants to send m to Alice.He chooses s and t and computes c=mg$_1^s$ mod n and d=mg$^t$ mod n. Bob sends ciphertext (c,d) to Alice.Alice solves congruences x=c mod p and x=d mod q using the CRT. Prove that x=m so she gets the message.
\vspace{5mm}
b.Alice picks p=3 and q=7 and g=2. She gets ciphertext (6,3) from Bob. Find his message.
\vspace{5mm}
II. Bob’s public key for the RSA is(12191,37) Alice sends Bob ciphertext c=587. Help Eve factor n and decrypt c.
\maketitle
\vspace{5mm}
III Show that n=7.13.19 is a Carmichael number.
\vspace{5mm}
IV. Let n=294409. Use the Miller-Rabin test to conclude that n is composite or probably prime with probability greater then 1-(1/4)$^{2}$
\vspace{5mm}
V. Use Pollard’s p-1 algorithm to factor n=220459.
\vspace{5mm}
VI. Let n=65 and B=8.
a. On values t=9,10,11,12,13,14,15, sieve on values of p$^k$, p $\leq$ B.
b. For the values of t, t$^2$-n sieved to one, write F(t)=t$^2$-n as the product of primes less that B.
c. Use matricies to find all products of values F(t)’s in part bwhich have p to even powers, p $\leq$ B.
d. Use gcd’s to factor n.
CHAPTER IV
SIGNATURES
I. Alice and Bob are using the El-Gamal signature scheme. Alice picks p=11 and primitive g=2 to use mod p. Her private key is a=5.
1.What is her public verification key?
2. Her digital document is D=7. and she picks k=3. What is her signature?
3. Help Bob verify that the document came from Alice.
II. Problem 4.3 page 204: Alice uses the RSA signature scheme with public modulus N=27212325191 and public verification exponent e=22824469379. Factor N and forge Alice’s signature on document D=12910258780.
III. Problem 4.11 page 205. Alice and Bob are using the digital signature algothrim, DSA. Alice has public verification key(p,q,g,A)=(103687, 1571, 21947, 31377).
1. Solve the DLP to find Alice’s private key a. (Use any method)
2. Use her key to sign D=510 using k=1105 and send a bogus message to Alice.
VI. Problem 4.8, page 205.
CHAPTER V
Problem Set 5
PROBABILITY, COLLISION ALGORITHMS
I. Use the Pollard $\rho$ to factor n=4087. Let x$_1$=2 and f(x)=x$^2$+x+1. Use differences x$_{2t}$-$x_{t}$.
II. Problem 21 on page 288. A coin is tossed 10 times. Compute the probabilities for the following events:
a. The first and last tosses are heads.
b. Either the first toss or the last toss or both are heads
c. Either the first toss or the last toss but not both are heads.
d. There are exactly k heads for each k from 10 to 10.
e. There is an even number of heads
f. There is an odd number of heads.
III.Problem 24 on page 289. There are 2 urns. Urn 1 contains three pens and seven pencils and Urn 2 contains eeight pens and four pencils.
a. An urn is chosen and an object is drawn. What is the probability that it is a pencil?
b. An urn is drawn and an object is drawn. If the object is a pencil, then what is the probability that it came from urn 1?
c. If an urn is chosen and two objects arew drawn from it, what is the probability that both are pencils?
IV Problem 39, Chapter 5
V Use the Pollard $\rho$ to solve the DLP 10$^x$= 6 mod 29
CHAPTER VI ELLIPTIC CURVE CRYPTOGRAPHY
I. Let p=11 and E be the elliptic curve y$^2$=x$^3$+x+1
a. Construct E
b. Find 2(1,6)
c. Find (3,8)+(4,6)
\vspace{5mm}
II. Continue I for the ECC El-Gamal
a. Alice picks a=(8,9) and k=2. Find b.
b. Bob sends y=(3,3), z=(2,0) to Alice. Find w.
\vspace{5mm}
III. ECC Pollard p-1 factoring. Let n=51, P:(1,-1),c=1. What is the curve?
Let P:(0,3). Find 2P and 4P to factor n.
\vspace{5mm}
IV. More Pollard p-1 factoring. Let n=923 and y$^2$=x$^3$+2x+9. Let P:(0,3).
Compute 2P and 3P to factor n.
\vspace{5mm}
V. Alice picks y$^2$=x$^3$+3x+8 and p=13 to use for a digital signature scheme. She picks G=(9,7)
a. Show the order of G is 3. Let q=3.
b. Alice is to send message d=1 and picks secret key s=1 and picks e=2. Find her signature.
c. Help Bob show that the message is from Alice.
\vspace{5mm}
VI. We have found the ECC analogue of the digital signature algorithm. Formulate the ECC analogue of the El Gamal signature algorithm which we have described (see sec 4.3)
\vspace{5mm}
VII. Let y$^2$=x$^3$+x+1, p=5, P:(4,2) and Q:(0,1) Solve the ECC DLP for Q=nP.
\vspace{5mm}
VII. Formulate an ECC Diffie-Hellman key exchange and construct an example of your system.
CHAPTER VII. Lattice based cryptography
Use the computer whenever you wish.
\vspace {5mm}
I. Alice is using the NTRU from our example in class: n=3, p=3, q=101, d=1. Same f(x) and g(x), same public key.
a. Bob computes the ciphertext, e(x)=53x$^2$+50. What is the message?
b. What is the NTRU matrix?
c. Use the LLL to help Eve find the message.
\vspace{5mm}
II. In the GGH cryptosystem used in the in class example, Bob has ciphertext (20,191).
a. Find the message for Alice.
b. Help Eve find the message using the LLL.
\vspace{5mm}
III. Knapsack. Problem 7.3 page 454 Page .
\vspace {5mm}
IV. LLL Problem 7.47 Page 466
\vspace {5mm}
V. LLL Problem 7.48 Page 466.
\vspace{5mm}
V. NTRU Problem 7.29 Page 461
\vspace {5mm}
VI. NTRU Problem 7.30 Page 461