ELECS425F Computer and Network Security
Assignment 1 (15 marks)
1 Task 1. Ciphers Calculation (5 marks)
You must write the calculation steps to obtain the marks. Only result will get zero mark.
Q1: Let X = 2022, Given the secret key (X mod 13) + 1 and the plaintext keephealthy, en-
crypt this message using the Additive Cipher. (1 mark)
Q2: Given secret key = luck, encrypt the message everythingwillbefine using Vigenere cipher. (1
mark)
Q3: Given p = 11,q =1 9 and using Rabin cryptosystem.
a) encrypt message = 200. (1mark)
b) decrypt the ciphertext you get from a) and discuss how to make sure the uniqueness of the
decryption. (2 marks)
2 Task 2. Digital Signature Algorithm - DSA (10 marks)
You must use PARI/GP to write the code. Using a new programming language is part of your
learning. You need to submit your code and include the screenshot of a sample execution of your
code in the report.
PARI/GP
PARI/GP is a widely used computer algebra system designed for fast computations in number
theory (factorizations, algebraic number theory, elliptic curves, ...). It also contains a large num-
ber of other useful functions to compute with mathematical entities such as matrices, polynomi-
als, power series, algebraic numbers etc., and a lot of transcendental functions. PARI is also
available as a C library to allow for faster computations. PARI/GP can be downloaded from
http://pari.math.u-bordeaux.fr/download.html. You can select the platform that you like from
the above URL.
1
The digital signature algorithm (DSA) was adopted in 1994 as a signature standard by the U.S.
Government. Its security is based on the difficulty of the discrete logarithm problem in a large
subgroup of the multiplicative group Z∗p .
1. To generate keys, each user does the following:
• pick a prime p such that p− 1 has a prime factor q.
• select a random integer h, 1 < h < p − 1, and such that h p−1q mod p > 1; let g =
h
p−1
q mod p;
• select a random integer x, 0 < x < q, and compute y = gx mod p;
• the user’s public key is (p, q, g, y); the user’s private key is x.
2. signature generation: A does the following to sign a message m:
• choose a random integer k, 0 < k < q;
• compute k−1 mod q;
• compute r = (gk mod p) mod q;
• compute s = k−1(m + xr) mod q;
//for simplicity we consider m ∈ Zq
• send the signature (r, s) along with message m to B.
3. signature verification: B does the following to verify A’s signature:
• look up A’s public key (p, q, g, y);
• compute w = s−1 mod q;
• compute u1 = mw mod q and u2 = rw mod q;
• compute v = ((gu1yu2) mod p) mod q;
• accept the signature only if v = r.
In this assignment, you are to implement a GP program (which should be called ‘dsa.gp’ which
performs Digital Signature Algorithm as described above). The program must have the following
functions:
• Keygen(x, y): a function to produce the DSA parameters: (p, q, g, y, x) as described above.
The output of this function is (p, q, g, y, x).
• Sign(m): a function to sign a message m using the secret key x.
• Verify(m, r, s): a function to verify a message m with the signature (r, s). A signature is
acceptable if the v = r as described above.
A sample interaction is as follows. |P| 2 = 11 means P has bit length 11 when converted into
binary form.
2
? \r dsa
Digital Signature Algorithm
Enter:
Keygen(x, y): to produce secret and public key parameters
where |P|_2 >= x and |Q|_2 >= y
Sign(m): to sign a message m using the private key
Verify(m, r, s): to verify a message m with signature (r, s)
Help: this screen
? Keygen(10, 5)
P = 1129
|P|_2 = 11
Q = 47
|Q|_2 = 6
Public Key:
g = 30
y = 338
Private Key:
x = 31
? Sign(35)
Signature: (5, 19)
? Verify(35, 5, 19)
Verified OK
? Verify(35, 19, 5)
Reject
? Help
Digital Signature Algorithm
Enter:
Keygen(x, y): to produce secret and public key parameters
where |P|_2 >= x and |Q|_2 >= y
Sign(m): to sign a message m using the private key
3
Verify(m, r, s): to verify a message m with signature (r, s)
Help: this screen
? \q
Good bye!
You need to submit your code and include the screenshot of a sample execution of your code in the
report.
Submission Guideline
1. Submission is via OLE.
2. Put your report and program for Task 1 & 2 in a zip file.
3. Include the compilation instructions with your submission (i.e., provide a readme.txt file for
your program).
4. Late submission will not be accepted.
5. Plagiarism is treated seriously. Students involved will receive zero.
4