CSC327 · TU past paper

Cryptography 2079 question paper

The complete TU 2079 exam paper for Cryptography (CSC327), all 12 questions with solved model answers written to the mark scheme.

Past Papers2082 2081 2080 2079 2078 2076

Tap a question to open its answer.

1Advanced Encryption StandardsHideAnswer
Security Policy and Mechanism, Block vs Stream Cipher, and AES Key Expansion
--- A security policy is a set of rules and guidelines that define what is and is not allowed in a system. It is a high-level statement of intent that specifies the security goals an organization wants to achieve. It answers the question...
210 marksProperties of Hash functionsHideAnswer
Describe the properties of hash functions. Discuss how hash value is generated using SHA-1 algorithm.[10]
A hash function is a function that maps a message of any length into a fixed-length hash value, which serves as an authenticator. Cryptographic hash functions are a fundamental tool of cryptography for efficient and secure information pr...
310 marksNumericalElgamal Cryptographic SystemHideAnswer
Show that Z 5 is a field. John publishes the ElGamal public key (q, α, YA) =(101, 2, 14). Jane desired to send the secret message CSIT to John. Using the equivalence A = 0, B=1, ..., Z=25, encrypt the message using John’s public key. Use a random number k = 4.[10]
--- Field problem: - Set: $\mathbb{Z}5 = \{0,1,2,3,4\}$ under addition and multiplication mod 5. ElGamal problem: - Public key: $(q, \alpha, YA) = (101, 2, 14)$ - Message: "CSIT" - Encoding: $A=0, B=1, \dots, Z=25$ - Random number:
--- Field problem: - Set: $\mathbb{Z}5 = {0,1,2,3,4}$ under addition and multiplication mod 5. ElGamal problem: - Public key: $(q, \alpha, YA) = (101, 2, 14)$ - Message: "CSIT" - Encoding: $A=0, B=1, \dots, Z=25$ - Random number:
45 marksTypes of Malicious LogicHideAnswer
Differentiate between Trojan horse and virus. Describe any two types of intruders. [5]
--- Basis Trojan Horse Virus --------- Definition A program with a known (legitimate) look but an unwanted/hidden effect. It performs a desired task but also performs unexpected functions. A self-replicating malicious program that attach...
55 marksNumericalSubstitution TechniquesHideAnswer
The message “IMOGUN” was encrypted with a Playfair cipher using keyword “GALOIS”. Decrypt the message. [5]
Ciphertext: IMOGUN - Keyword: GALOIS - Convention: I/J combined into a single cell. Keyword unique letters: G, A, L, O, I, S. Then fill remaining alphabet (I/J shared, skip already-used letters): Remaining after G,A,L,O,I,S: B, C, D, E...
65 marksInternational Data Encryption StandardHideAnswer
How encryption is done using IDEA algorithm. [5]
IDEA (International Data Encryption Algorithm) is a symmetric block cipher that: - Operates on 64-bit plaintext blocks - Uses a 128-bit key - Performs 8 rounds of encryption followed by a final output transformation - Uses three algebrai...
75 marksEmail SecurityHideAnswer
Describe the services provided by Pretty Good Privacy protocol to secure email. [5]
Pretty Good Privacy (PGP) is an open-source, freely available software package designed for email security. It provides confidentiality and authentication services that can be used for electronic mail and file storage applications. PGP o...
85 marksChallenge Response SystemHideAnswer
Define challenge response system. Why do we need Kerberos? [5]
--- A challenge response system is a handshake authentication process in which the authenticator (server) issues a challenge to the user seeking authentication, and the user must provide a correct response in order to be authenticated. 1...
95 marksDigital SignaturesHideAnswer
How direct digital signature different from arbitrated digital signature? How digital signature generation and verification is done using RSA. [5]
--- - Involves only two parties: the sender and the receiver. - The sender signs the message using their private key. - The receiver verifies the signature using the sender's public key. - No third party is involved in the process. - Wea...
105 marksNumericalHideAnswer
Why do we need discrete logarithm over normal logarithm? Find out whether 3 is primitive root of 7 or not. [5]
Base to test: $g = 3$ - Prime modulus: $p = 7$ - Task: Determine whether 3 is a primitive root of 7. --- Normal (continuous) logarithm: If $b = a^i$ , then $i = \loga b$ . This is defined over real numbers and is easy to compute in both ...

Base to test: $g = 3$ - Prime modulus: $p = 7$ - Task: Determine whether 3 is a primitive root of 7. --- Normal (continuous) logarithm: If $b = a^i$, then $i = \loga b$. This is defined over real numbers and is easy to compute in both ...
115 marksNumericalTransposition TechniquesHideAnswer
Which one is more secure, monoalphabetic cipher or poly alphabetic cipher? Justify. Using rail fence cipher encrypt the text 'LEARNING AND TEACHING ARE DIFFERENT' using 3 as rails. [5]
Plaintext: LEARNING AND TEACHING ARE DIFFERENT - Number of rails: 3 - Task 1: Compare security of monoalphabetic vs polyalphabetic cipher. - Task 2: Encrypt using rail fence with 3 rails. --- Polyalphabetic cipher is more secure than m...
125 marksNumericalNumber TheoryHideAnswer
What is the condition of for two integers, x and y, to be relatively prime? Find whether 61 is prime or not using Miller-Rabin algorithm. [5]
Relatively Prime Condition and Miller-Rabin Test for 61

STEP 1 - EXTRACT (Given data)
- Number to test: $n = 61$
- Question asks: (a) condition for two integers $x, y$ to be relatively prime; (b) test primality of 61 using Miller-Rabin.
- No specific witness $a$ is given, so we choose valid witnesses.
STEP 2 - SOLVE

Part 1: Condition for Relatively Prime

Two integers $x$ and $y$ are relatively prime (coprime) if and only if their greatest common divisor is 1:

$\gcd(x, y) = 1$

They share no common positive divisor other than 1.

Example: $\gcd(8, 15) = 1$ , so 8 and 15 are relatively prime.

Part 2: Miller-Rabin Test for n = 61

Step 1: Write $n - 1 = 2^k \cdot m$ , m odd

$n - 1 = 60 = 2^2 \times 15$

So $k = 2$ , $m = 15$ (odd, confirmed).

Step 2: Choose witness $a = 2$ (valid: $1 < 2 < 60$ ).

Step 3: Compute $b = a^m \bmod n = 2^{15} \bmod 61$

$2^{15} = 32768$ $32768 \bmod 61: \quad 61 \times 537 = 32757, \quad 32768 - 32757 = 11$

Cross-check via the alternative decomposition: $b = 11$ .

Step 4: Is $b = 1$ ? No, $11 \neq 1$ . Proceed to loop.

Step 5: Loop $i = 0$ to $k-1 = 1$

Check $b = n - 1 = 60$ at start of each iteration:
- $i = 0$ : $b = 11 \neq 60$ . Square: $b = 11^2 = 121 \equiv 121 - 61 = 60 \pmod{61}$ .
  
  Now $b = 60 = -1 \pmod{61}$ at the moment it is produced.
Note on algorithm form: In the correct Miller-Rabin loop, after squaring we check whether we hit $-1$ . The sequence of squarings starting from $2^{15}$ is:

$2^{15} \equiv 11, \quad 2^{30} \equiv 11^2 = 60 \equiv -1 \pmod{61}$

Since one of the values $a^{2^i m}$ equals $-1$ (here $2^{30} \equiv -1$ ), the test declares probably prime. Witness $a = 2$ is a strong liar-free result: 61 passes.

$11^2 = 121, \quad 121 - 61 = 60 \quad (\text{not } 59)$

Therefore, with $a = 2$ itself, the test returns Prime (no second witness needed).

Double-check with $a = 7$ :

$7^2 = 49,\ 7^4 = 49^2 = 2401 \equiv 2401 - 39(61)=2401-2379=22$ $7^8 = 22^2 = 484 \equiv 484 - 7(61) = 484 - 427 = 57$ $7^{15} = 7^8 \cdot 7^4 \cdot 7^2 \cdot 7 = 57 \cdot 22 \cdot 49 \cdot 7 \pmod{61}$ $57 \cdot 22 = 1254 \equiv 1254 - 20(61)=1254-1220=34$ $34 \cdot 49 = 1666 \equiv 1666 - 27(61)=1666-1647=19$ $19 \cdot 7 = 133 \equiv 133 - 2(61) = 11 \pmod{61}$

So $7^{15} \equiv 11 \neq 1, \neq 60$ . Square: $11^2 = 121 \equiv 60 \equiv -1$ . Returns Prime.

(Note that $7^{15} \equiv 11$ , not $60$ ; the squaring still gives $-1$ , so the conclusion "Prime" holds.)

Conclusion

$\boxed{61 \text{ is Prime (probably prime by Miller-Rabin)}}$
Relatively Prime Condition and Miller-Rabin Test for 61

STEP 1 - EXTRACT (Given data)
- Number to test: $n = 61$
- Question asks: (a) condition for two integers $x, y$ to be relatively prime; (b) test primality of 61 using Miller-Rabin.
- No specific witness $a$ is given, so we choose valid witnesses.
STEP 2 - SOLVE

Part 1: Condition for Relatively Prime

Two integers $x$ and $y$ are relatively prime (coprime) if and only if their greatest common divisor is 1:

$$\gcd(x, y) = 1$$

They share no common positive divisor other than 1.

Example: $\gcd(8, 15) = 1$, so 8 and 15 are relatively prime.

Part 2: Miller-Rabin Test for n = 61

Step 1: Write $n - 1 = 2^k \cdot m$, m odd

$$n - 1 = 60 = 2^2 \times 15$$

So $k = 2$, $m = 15$ (odd, confirmed).

Step 2: Choose witness $a = 2$ (valid: $1 < 2 < 60$).

Step 3: Compute $b = a^m \bmod n = 2^{15} \bmod 61$

$$2^{15} = 32768$$ $$32768 \bmod 61: \quad 61 \times 537 = 32757, \quad 32768 - 32757 = 11$$

Cross-check via the alternative decomposition: $b = 11$.

Step 4: Is $b = 1$? No, $11 \neq 1$. Proceed to loop.

Step 5: Loop $i = 0$ to $k-1 = 1$

Check $b = n - 1 = 60$ at start of each iteration:
- $i = 0$: $b = 11 \neq 60$. Square: $b = 11^2 = 121 \equiv 121 - 61 = 60 \pmod{61}$.
  
  Now $b = 60 = -1 \pmod{61}$ at the moment it is produced.
Note on algorithm form: In the correct Miller-Rabin loop, after squaring we check whether we hit $-1$. The sequence of squarings starting from $2^{15}$ is:

$$2^{15} \equiv 11, \quad 2^{30} \equiv 11^2 = 60 \equiv -1 \pmod{61}$$

Since one of the values $a^{2^i m}$ equals $-1$ (here $2^{30} \equiv -1$), the test declares probably prime. Witness $a = 2$ is a strong liar-free result: 61 passes.

$$11^2 = 121, \quad 121 - 61 = 60 \quad (\text{not } 59)$$

Therefore, with $a = 2$ itself, the test returns Prime (no second witness needed).

Double-check with $a = 7$:

$$7^2 = 49,\ 7^4 = 49^2 = 2401 \equiv 2401 - 39(61)=2401-2379=22$$ $$7^8 = 22^2 = 484 \equiv 484 - 7(61) = 484 - 427 = 57$$ $$7^{15} = 7^8 \cdot 7^4 \cdot 7^2 \cdot 7 = 57 \cdot 22 \cdot 49 \cdot 7 \pmod{61}$$ $$57 \cdot 22 = 1254 \equiv 1254 - 20(61)=1254-1220=34$$ $$34 \cdot 49 = 1666 \equiv 1666 - 27(61)=1666-1647=19$$ $$19 \cdot 7 = 133 \equiv 133 - 2(61) = 11 \pmod{61}$$

So $7^{15} \equiv 11 \neq 1, \neq 60$. Square: $11^2 = 121 \equiv 60 \equiv -1$. Returns Prime.

(Note that $7^{15} \equiv 11$, not $60$; the squaring still gives $-1$, so the conclusion "Prime" holds.)

Conclusion

$$\boxed{61 \text{ is Prime (probably prime by Miller-Rabin)}}$$

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2082 paper 2081 paper 2080 paper 2078 paper 2076 paper

Cryptography 2079 question paper

Relatively Prime Condition and Miller-Rabin Test for 61

STEP 1 - EXTRACT (Given data)

STEP 2 - SOLVE

Part 1: Condition for Relatively Prime

Part 2: Miller-Rabin Test for n = 61

Conclusion

Relatively Prime Condition and Miller-Rabin Test for 61

STEP 1 - EXTRACT (Given data)

STEP 2 - SOLVE

Part 1: Condition for Relatively Prime

Part 2: Miller-Rabin Test for n = 61

Conclusion

Relatively Prime Condition and Miller-Rabin Test for 61

STEP 1 - EXTRACT (Given data)

STEP 2 - SOLVE

Part 1: Condition for Relatively Prime

Part 2: Miller-Rabin Test for n = 61

Conclusion