# Cryptography CS 411& CS 507 Term Project 1

\$35.00

## 2 Phase I: Developing software for digital signature

In this phase of the project, you will develop software for signing given any message. For digital
signature (DS) you will us an algorithm, which consists of four functions as follows:
• Public parameter generation: Two prime numbers p and q are generated with q|p − 1,
where q and p are 224-bit and 2048-bit integers, respectively. The generator g generates a
subgroup of Z

p with q elements. Naturally, g
q ≡ 1 mod p. Note that in your system q, p,
and g are public parameters shared by all users, who have different secret/public key pairs.
Refer to the slide (with title “DSA Setup” in chapter 10 for an efficient method for parameter
generation).

• Key generation: A user picks a random secret key 0 < α < q and computes the public
key β = g
α mod p.

• Signature generation: Let m be an arbitrary length message. The signature is computed
as follows:
1. k ← Zq, (i.e., k is a random integer in [0, q − 1]).
1
2. r = g
k
(mod p)

3. h = SHA3 256(m||r)

4. s = α · h + k (mod q)

5. The signature for m is the tuple (s, h).

• Signature verification: Let m be a message and the tuple (s, h) is a signature for m. The
verificiation proceeds as follows:
– v = g

−h
(mod p)
– h˜ = SHA3 256(m||v)
– Accept the signature only if h = h˜ mod q
– Reject it otherwise.

Note that the signature generation and verification of this DS are different than those discussed in
the lecture.

You are required to develop Python software that implements those four functions; namely
Setup for public parameter generation, Key Generation, Signature Generation and
Signature Verification. You are required to test your software using the test routines in
“DS Test.py” provided in the assignment package.

In “DS Test.py”, there are four basic test functions:
1. checkDSparams(q, p, g) takes your public parameters (q, p, g) and check if they are correct.
It returns 0 if they are. Otherwise, it returns a code that indicates the problem.
2. CheckKeys(q, p, g, α, β) takes your public parameters (q, p, g) and key pair (α, β) and check
if the key pair is correct. It returns 0 if they are; otherwise it returns -1.
3. CheckSignature(q, p, g, α, β) takes your public parameters (q, p, g), key pair (α, β) and
generates a signature for a random message and verifies the signature. It returns 0 if the
signatures verifies; otherwise it returns -1.
4. CheckTestSignature() reads the file “TestSet.txt” (provided in the assignment package),
which contains public parameters, a public key, and 10 randomly chosen messages and their
signatures. The test code reads them and runs signature verification function. The test code
returns 0 if all signatures verify; otherwise it returns -1.
In this phase of the project, you are required to upload only a file named “DS.py” with sufficient
comments. We will be able to test your code using “DS Test.py’. If your software cannot be tested
by “DS Test.py’ as it is, you will get no credit.

2
3 Appendix I: Timeline & Deliverables & Weight & Policies etc.
Project Phases Deliverables Due Date Weight
Project announcement 07/12/2018
First Phase Source code (DS.py) 14/12/2018 25%
Second Phase TBA 21/12/2018 TBA
Third Phase TBA 28/12/2018 TBA
Bonus TBA 28/12/2018 TBA

3.1 Policies
• You may work in groups of two.
• You may be asked to demonstrate a project phase to a TA or the instructor.
• In every phase, we will provide you with a validation software in python language that can
be used to check your implementation for correctness. We will also use it to check your
implementation. If your implementation in a project phase fails to pass the validation, you
will get no credit for that phase.
3