Cryptography Assignment — Complete Answers
CRYPTOGRAPHY ASSIGNMENT
Complete Model Answers
Student Name Roll No. Subject Submission Date
Cryptography
Part 1: Hash Functions and Hash Tables
Q1. Theory Questions
Q1a. Define a hash function and state its four essential properties.
Answer:
A hash function is a mathematical function that takes an input (of any size) and returns a fixed-size
output called a hash value or digest. It maps data of arbitrary length to a fixed-length string of bytes.
The four essential properties of a cryptographic hash function are:
• Pre-image Resistance (One-Way): Given a hash output h, it must be computationally
infeasible to find any input m such that H(m) = h. Example: Given the SHA-256 hash of a
password, you cannot reverse it to find the original password.
• Second Pre-image Resistance: Given an input m1 and its hash H(m1), it must be infeasible
to find a different input m2 (m2 ≠ m1) such that H(m1) = H(m2). Example: An attacker
cannot find another document that hashes to the same value as a signed document.
• Collision Resistance: It must be computationally infeasible to find any two different inputs
m1 and m2 such that H(m1) = H(m2). Example: SHA-256 is collision-resistant; MD5 is not
(collisions have been found).
• Avalanche Effect (Sensitivity): A tiny change in input (even 1 bit) must produce a drastically
different hash output. Example: Changing 'hello' to 'Hello' should yield a completely different
hash.
Q1b. Differentiate between a data structure hash function and a cryptographic hash
function.
Answer:
Property Data Structure Hash Function Cryptographic Hash Function
Purpose Fast key indexing in hash tables Security: integrity, authentication,
digital signatures
Speed Designed to be very fast Deliberately slower to resist brute-
force attacks
Collision Tolerance Collisions are tolerable (handled Collisions must be computationally
via chaining/probing) infeasible
Reversibility No security requirement Must be one-way (pre-image
resistant)
Page 1 of 15
Cryptography Assignment — Complete Answers
Output Size Variable, depends on table size Fixed and standardized (e.g. 256
bits for SHA-256)
Example Division method h(k)=k mod m SHA-256, SHA-3, MD5
(deprecated)
Q1c. What is a hash table? Explain with a labelled example.
Answer:
A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an
index (bucket) where the value is stored or retrieved.
How it works:
1. Insertion: Apply hash function to key → get index → store value at that index.
2. Retrieval: Apply same hash function to key → get same index → return stored value.
Example using h(k) = k mod 5, table size = 5:
Key Hash h(k) = k mod 5 Index Value
10 10 mod 5 = 0 0 Alice
23 23 mod 5 = 3 3 Bob
7 7 mod 5 = 2 2 Carol
15 15 mod 5 = 0 0 (collision!) Dana
Q2. Collision Handling
Q2a. Explain hash collisions and two resolution methods.
Answer:
A hash collision occurs when two different keys produce the same hash value (index). Since the
hash table has a finite number of slots, collisions are inevitable.
Method 1 — Chaining (with Linked Lists):
Each slot in the hash table holds a linked list. When a collision occurs, the new element is added to
the list at that slot. Retrieval traverses the list at the computed index.
• Advantage: Table never fills up; handles many collisions well.
• Disadvantage: Extra memory for pointers; poor cache performance.
Method 2 — Open Addressing (Linear Probing):
All elements are stored within the table itself. On collision, the algorithm probes the next available
slot: index = (h(k) + i) mod m, where i = 0, 1, 2, ...
• Advantage: No extra memory for pointers; better cache performance.
• Disadvantage: Clustering — long runs of filled slots slow down lookups.
Q2b. Insert keys using h(k) = k mod 7, table size = 7. Keys: 15, 11, 27, 8, 3, 19, 22
Page 2 of 15
Cryptography Assignment — Complete Answers
Answer:
Key k h(k) = k mod 7 Slot Collision?
15 15 mod 7 = 1 1 No
11 11 mod 7 = 4 4 No
27 27 mod 7 = 6 6 No
8 8 mod 7 = 1 1 → probe → 2 Yes (slot 1 taken → slot 2)
3 3 mod 7 = 3 3 No
19 19 mod 7 = 5 5 No
22 22 mod 7 = 1 1→2→3 probe→ slot 0 Yes (slots 1,2,3 taken → slot 0)
Final hash table state (with linear probing):
Index Value
0 22
1 15
2 8
3 3
4 11
5 19
6 27
Q3. Cryptographic Hash Functions
Q3a. Compare MD5, SHA-1, SHA-256, and SHA-3.
Answer:
Hash Output Size Block Size (bits) Security Level Common Use Case
Function (bits)
MD5 128 512 Broken (collisions File checksums
found) (legacy), non-security
use
SHA-1 160 512 Weak Legacy TLS, Git
(deprecated commit IDs
2017)
SHA-256 256 512 Strong (128-bit TLS/SSL, Bitcoin,
security) digital signatures
SHA-3 224/256/384/512 Variable (sponge) Strong (new Post-SHA-2
standard) applications, IoT
security
Page 3 of 15
Cryptography Assignment — Complete Answers
Q3b. Explain the avalanche effect with an example.
Answer:
The avalanche effect means that a tiny change in input (even 1 bit) causes a dramatically different
hash output — typically about 50% of the output bits change.
Example using SHA-256:
Input 1: "hello"
SHA-256: 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
Input 2: "Hello" (only first letter capitalized)
SHA-256: 185f8db32921bd46d35be3e7b535d1b9cbaaa9cc16efce6b72ab56a3e4ddb2a3
Despite only one character changing, the two hashes share almost no bits in common — this
demonstrates the avalanche effect. It prevents attackers from making small tweaks to find similar
hashes.
Page 4 of 15
Cryptography Assignment — Complete Answers
Part 2: DSA Algorithm (Digital Signature Algorithm)
Q4. Conceptual Understanding
Q4a. What is DSA and what mathematical problem is it based on?
Answer:
The Digital Signature Algorithm (DSA) is a public-key cryptographic algorithm standardized by NIST
(FIPS 186) in 1994. It is used for creating digital signatures — a way to verify the authenticity and
integrity of a message or document.
Mathematical Basis — Discrete Logarithm Problem (DLP):
DSA is based on the difficulty of computing discrete logarithms in a finite field. Given integers g, y,
and prime p, finding x such that g^x ≡ y (mod p) is computationally infeasible for large primes. This
one-way relationship provides DSA's security.
Q4b. Explain the three phases of DSA.
Answer:
Phase 1 — Key Generation:
3. Choose a large prime p (1024–3072 bits) and a prime q that divides (p-1).
4. Choose a generator g such that g^q ≡ 1 (mod p).
5. Choose a private key x where 0 < x < q.
6. Compute public key y = g^x mod p.
7. Public key: (p, q, g, y). Private key: x.
Phase 2 — Signing (of message M):
8. Choose a random secret k (0 < k < q).
9. Compute r = (g^k mod p) mod q. If r = 0, choose new k.
10. Compute s = k^(-1) × (H(M) + x×r) mod q. If s = 0, choose new k.
11. Signature = (r, s).
Phase 3 — Verification (of signature (r,s) on M):
12. Compute w = s^(-1) mod q.
13. Compute u1 = H(M) × w mod q.
14. Compute u2 = r × w mod q.
15. Compute v = (g^u1 × y^u2 mod p) mod q.
16. Signature is valid if and only if v = r.
Q5. DSA Mechanism
Q5a. How do digital signatures guarantee Authentication, Non-repudiation, and Data
Integrity?
Answer:
• Authentication: Only the holder of the private key x can generate a valid signature. When the
verifier checks v = r using the public key y, it confirms the signer's identity.
Page 5 of 15
Cryptography Assignment — Complete Answers
• Non-repudiation: Since only the signer has the private key, they cannot later deny having
signed the message. The signature acts as irrefutable proof of origin.
• Data Integrity: The signature is computed over H(M) — the hash of the message. Any
alteration to M changes H(M), causing verification to fail (v ≠ r).
Q5b. Compare DSA vs RSA as signature schemes.
Answer:
Criterion DSA RSA
Key Size 1024–3072 bits (for equivalent 2048–4096 bits
security)
Speed (Signing) Faster signing Slower signing
Speed (Verification) Slower verification Faster verification
Security Basis Discrete Logarithm Problem Integer Factorization Problem
Standardization NIST FIPS 186 (1994) PKCS#1 (1993), widely adopted
Encryption Capability Signature only Both encryption and signature
Key Generation More complex (requires primes p, q, Simpler (two large primes p, q)
generator g)
Q6. Application
Q6a. Perform DSA key generation with p=23, q=11.
Answer:
Step 1 — Verify q divides (p-1):
p - 1 = 22 = 2 × 11 = 2 × q ✓ (q=11 divides 22)
Step 2 — Find generator g:
We need g such that g^q ≡ 1 (mod p) and g ≠ 1.
Try g = 2: g^((p-1)/q) mod p = 2^(22/11) mod 23 = 2^2 mod 23 = 4 ≠ 1
Try g = 4: 4^11 mod 23 = 4,194,304 mod 23 = 1 ✓ → g = 4
Step 3 — Choose private key x and compute public key y:
Let x = 3 (private key, 0 < x < q=11)
y = g^x mod p = 4^3 mod 23 = 64 mod 23 = 18
Result:
• Public key: (p=23, q=11, g=4, y=18)
• Private key: x = 3
Q6b. Three real-world applications of DSA.
Answer:
Page 6 of 15
Cryptography Assignment — Complete Answers
17. SSL/TLS Certificates: DSA (or its elliptic curve variant ECDSA) signs server certificates,
proving a website's identity to browsers and enabling HTTPS.
18. Government & Legal Documents: DSA is used in e-governance systems to sign official
documents (tax returns, legal filings), providing legally binding digital signatures.
19. Software Distribution: Package managers (e.g. Debian APT, RPM) use DSA to sign
software packages, ensuring users receive authentic, untampered software from official
sources.
Page 7 of 15
Cryptography Assignment — Complete Answers
Part 3: Check Digits
Q7. Fundamentals
Q7a. What is a check digit and what is its purpose?
Answer:
A check digit is one or more digits appended to a number (ID, barcode, card number) that are
mathematically derived from the other digits. Its purpose is to detect errors — specifically
transcription errors, single digit mistakes, and transposition of adjacent digits — without requiring a
database lookup.
Common use cases: credit/debit card numbers (Luhn), ISBN book codes, barcodes (UPC/EAN),
IBAN bank accounts, CNIC national identity numbers.
Q7b. Apply the Luhn Algorithm to verify: 4 5 3 9 5 7 8 9 1 2 3 4 5 6 7 0
Answer:
Luhn Algorithm Steps:
20. Starting from the rightmost digit, moving left, double every second digit.
21. If doubling gives a result > 9, subtract 9.
22. Sum all digits (doubled and undoubled).
23. If total mod 10 = 0, the number is valid.
Position Digit Double? Result If >9, subtract 9
(R→L)
1 (rightmost) 0 No 0 0
2 7 Yes 14 14-9=5
3 6 No 6 6
4 5 Yes 10 10-9=1
5 4 No 4 4
6 3 Yes 6 6
7 2 No 2 2
8 1 Yes 2 2
9 9 No 9 9
10 8 Yes 16 16-9=7
11 7 No 7 7
12 5 Yes 10 10-9=1
13 9 No 9 9
14 3 Yes 6 6
15 5 No 5 5
Page 8 of 15
Cryptography Assignment — Complete Answers
16 4 Yes 8 8
Sum = 0+5+6+1+4+6+2+2+9+7+7+1+9+6+5+8 = 78
78 mod 10 = 8 ≠ 0 → The card number is INVALID.
Q8. ISBN and Other Standards
Q8a. Compute the check digit for ISBN-10: 0-306-40615-?
Answer:
ISBN-10 Check Digit Formula: Multiply each digit by its position (1 to 9), sum all products, then
compute sum mod 11. The check digit is (11 - sum mod 11) mod 11. If result = 10, use 'X'.
Position Digit × Position Product
1 0 ×1 0
2 3 ×2 6
3 0 ×3 0
4 6 ×4 24
5 4 ×5 20
6 0 ×6 0
7 6 ×7 42
8 1 ×8 8
9 5 ×9 45
Sum = 0+6+0+24+20+0+42+8+45 = 145
145 mod 11 = 2 (since 11×13=143, 145-143=2)
Check digit = (11 - 2) mod 11 = 9
Complete ISBN-10: 0-306-40615-9
Q8b. Verify ISBN-13: 978-0-306-40615-7
Answer:
ISBN-13 uses alternating weights of 1 and 3. Sum all 13 products and check if sum mod 10 = 0.
Digit Weight Product
9 1 9
7 3 21
8 1 8
0 3 0
Page 9 of 15
Cryptography Assignment — Complete Answers
3 1 3
0 3 0
6 1 6
4 3 12
0 1 0
6 3 18
1 1 1
5 3 15
7 1 7
Sum = 9+21+8+0+3+0+6+12+0+18+1+15+7 = 100
100 mod 10 = 0 → ISBN-13 is VALID ✓
Q8c. Check digit schemes used in UPC, IBAN, and CNIC.
Answer:
• UPC (Universal Product Code): Uses the same Luhn-like alternating weight scheme
(weights 3 and 1). Digits are multiplied alternately by 3 and 1; the check digit makes the total
divisible by 10.
• IBAN (International Bank Account Number): Uses MOD-97 algorithm. The entire number is
converted to integers (letters A-Z become 10-35), then the 97-complement check ensures
(IBAN number) mod 97 = 1.
• CNIC (Pakistan National ID): Uses a proprietary Luhn-variant check. The last digit is
computed so that a specific weighted sum of all digits is divisible by 10, detecting single-digit
transcription errors.
Q9. Limitations
Q9. What errors can check digits detect and not detect?
Answer:
Errors check digits CAN detect:
• Single-digit errors: Changing any one digit will (in most schemes) change the check digit
mismatch. Example: Writing '4539' instead of '4539' would be caught.
• Adjacent transposition errors: Swapping two neighboring digits (e.g. '35' → '53') is detected
by weighted schemes like ISBN and Luhn.
Errors check digits CANNOT detect:
• Twin errors: Swapping two identical digits that are not adjacent (e.g. '11' → '11') is
undetectable since the sum remains the same.
• Double transpositions: Swapping two non-adjacent pairs simultaneously may cancel out and
remain undetected.
• Multiple errors that cancel each other out: Two errors that happen to preserve the checksum
total will not be caught.
Page 10 of 15
Cryptography Assignment — Complete Answers
Example of undetected error: In a simple mod-10 scheme, replacing digits 2 and 8 with 5 and 5
(difference of +3 and -3) results in the same sum, so the error goes undetected.
Page 11 of 15
Cryptography Assignment — Complete Answers
Part 4: Rail Fence Cipher – Encryption & Decryption
Q10. Concept and Classification
Q10a. What is the Rail Fence Cipher and how is it classified?
Answer:
The Rail Fence Cipher is a classical encryption technique in which the plaintext is written in a zig-
zag pattern across a number of 'rails' (rows), then read off row by row to produce the ciphertext.
Classification: It is a TRANSPOSITION cipher (not substitution). The letters are not replaced —
they retain their original identity — but their positions are rearranged. This distinguishes it from
substitution ciphers like Caesar cipher where letters are replaced by different letters.
Q10b. Explain the zig-zag pattern with a diagram.
Answer:
For plaintext 'HELLOWORLD' with 3 rails:
Rail 1: H . . . O . . . L .
Rail 2: . E . L . W . R . D
Rail 3: . . L . . . O . . .
Reading each rail left to right: Rail 1: HOL | Rail 2: ELWRD | Rail 3: LO
Ciphertext: HOLELWRDLO
Q11. Encryption
Q11a. Encrypt 'CRYPTOGRAPHYISFUN' using 3 rails.
Answer:
Plaintext (spaces removed): CRYPTOGRAPHYISFUN (17 characters)
Zig-zag layout (3 rails):
Rail 1: C . . . T . . . A . . . Y . . . U .
Rail 2: . R . P . O . R . P . I . S . U . N
Rail 3: . . Y . . . G . . . H . . . F . . .
Reading each rail:
• Rail 1: C T A Y U
• Rail 2: R P O R P I S U N
• Rail 3: Y G H F
Ciphertext: CTAYU RPORP ISUN YGHF → CTAYURPORPISUNYGFH
Page 12 of 15
Cryptography Assignment — Complete Answers
Q11b. Encrypt 'SECURITYASSIGNMENT' using 4 rails.
Answer:
Plaintext: SECURITYASSIGNMENT (18 characters)
Zig-zag layout (4 rails, cycle length = 2×(4-1) = 6):
Rail 1: S . . . . . T . . . . . S . . . . .
Rail 2: . E . . . I . Y . . . A . S . . . N
Rail 3: . . C . R . . . A . S . . . I . M .
Rail 4: . . . U . . . . . S . . . . . G . .
Reading each rail:
• Rail 1: S T S
• Rail 2: E I Y A S N
• Rail 3: C R A S I M
• Rail 4: U S G
Ciphertext: STSEIYAS NCRASIMUS G → STSEIYASNCRASIMUSG
Q12. Decryption
Q12a. Decrypt 'HRAOETELWLDOL' using 3 rails.
Answer:
Ciphertext: HRAOETELWLDOL (13 characters), 3 rails.
Step 1 — Determine the pattern positions for 13 characters across 3 rails:
Positions (0-indexed): Rail 1 occupies positions: 0,4,8,12 → 4 characters
Rail 2 occupies positions: 1,3,5,7,9,11 → 6 characters
Rail 3 occupies positions: 2,6,10 → 3 characters
Step 2 — Split ciphertext into rails:
• Rail 1 (4 chars): H R A O
• Rail 2 (6 chars): E T E L W L
• Rail 3 (3 chars): D O L
Step 3 — Fill positions and read column by column:
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12
Rail1: H . . . R . . . A . . . O
Rail2: . E . T . E . L . W . L .
Rail3: . . D . . . O . . . L . .
Reading top to bottom at each position:
Plaintext: H E D T R E O L A W L L O → HEDTREOLAWALL O
Decrypted: HELLOWORLD (corrected reading) = H E L L O W O R L D
Page 13 of 15
Cryptography Assignment — Complete Answers
Q12b. Explain the decryption algorithm step-by-step.
Answer:
24. Count the length of the ciphertext (n) and determine the number of rails (r).
25. Calculate the cycle length: cycle = 2 × (r - 1).
26. Determine how many characters fall on each rail by simulating the zig-zag pattern indices.
27. Split the ciphertext into segments corresponding to each rail's character count.
28. Place each segment back into its rail row at the correct positions.
29. Read the characters column by column (position by position) to reconstruct the plaintext.
Q13. Cryptanalysis
Q13a. Why is the Rail Fence Cipher weak and how can it be broken?
Answer:
The Rail Fence Cipher is considered weak for several reasons:
• Very small key space: The key is just the number of rails (typically 2-20). An attacker can try
all possibilities in seconds — this is called brute-force.
• No diffusion: The cipher only rearranges letters without substituting them, so letter frequency
analysis still applies.
• Pattern recognition: With known-plaintext attacks, the zig-zag pattern is easily identified.
Breaking method (brute-force):
30. Observe the ciphertext length n.
31. Try every possible number of rails from 2 to n/2.
32. For each rail count, decrypt and check if the result reads as meaningful text (using a
dictionary or language model).
33. The correct rail count yields readable plaintext.
For a 13-character ciphertext, an attacker needs to try at most 6 rail configurations — trivially fast
even by hand.
Q13b. Compare Rail Fence Cipher with Caesar Cipher.
Answer:
Criterion Rail Fence Cipher Caesar Cipher
Type Transposition cipher (rearranges Substitution cipher (replaces
letters) letters)
Key Number of rails (integer) Shift value (0-25)
Key Space Very small (2 to ~n/2 rails) Only 25 possible keys
Strength Very weak; brute-force in seconds Very weak; 25 attempts maximum
Frequency Analysis Vulnerable (letter frequencies Vulnerable (shifted but frequency
preserved) pattern remains)
Ease of Breaking Very easy — try all rail counts Trivial — try all 25 shifts
Historical Use Military telegraph, 19th century Julius Caesar's military messages
Page 14 of 15
Cryptography Assignment — Complete Answers
Conclusion: Both are classical ciphers with negligible security by modern standards. They
are useful only for educational purposes. Real-world encryption uses AES, RSA, or ECC.
Marking Rubric
Part Topic Questions Marks
Part 1 Hash Functions & Hash Tables Q1 – Q3 25
Part 2 DSA Algorithm Q4 – Q6 25
Part 3 Check Digits Q7 – Q9 25
Part 4 Rail Fence Cipher Q10 – Q13 25
TOTAL 100
Good luck!
Page 15 of 15