Tutorial Questions Solution

Subject: Cryptography Subject Code: CS21104

Session: 2025-26 Semester: First
Name of Student: Raj Kumar Yadav Reg. No. 2025RCS21

1. Explore and analyze the AKS algorithm pseudo code and its complexity. Justify why
it is not usable.
Ans. AKS Primality Test: The AKS algorithm (Agrawal–Kayal–Saxena) is the first
deterministic algorithm that checks whether a number n is prime in polynomial time without
relying on unproven assumptions.
Pseudocode (Simplified)
The core idea is based on the polynomial identity (x-a) n ≡ (xn - a) mod(n, xr – 1) if and only if
n is a prime number, for all integers a coprime to n, and where r is a suitable small prime
number.
1. Input: Integer n > 1.
2. Step 1 (Perfect Power Check): Check if n is a perfect power (n=ab for b>1). If yes,
n is composite.
3. Step 2 (Find Smallest r): Find the smallest integer r such that the multiplicative order
of n modulo r is greater than log_2(n)^2.

5. Step 4 (Polynomial Congruence Test): For a=1 to a=1 to ⌊√ϕ(r)log(n)⌋

4. Step 3 (Divisibility Check): If gcd(a, n) > 1 for some l<=r then n is composite.

 Check if (x-a)n = (xn - a) {xr - 1, n}

 If the congruence fails for any a, n is composite.
6. Step 5 (Conclusion): If all tests pass, n is prime.
Time Complexity
 The original paper proved a complexity of O(log(n) 12). Subsequent improvements
have reduced the complexity. The currently accepted complexity is:
 O(log(n)6+ε
 This is the key achievement: it is polynomial in the number of digits (log n) of the
input n.
Practical cost reasons for not using AKS
 Large constants and high exponents: Even with the improved ~(log n)^6 type
bounds, constants and polynomial degrees make AKS much slower than probabilistic
tests for sizes used in practice (e.g.,2048-bit primes).
 Expensive polynomial arithmetic: Step 5 requires polynomial exponentiation
modulo xr − 1 over Z/nZ. For realistic n, r can be large and the polynomial
multiplication/convolution costs are high.
 Probabilistic alternatives are far cheaper: Tests like Miller–Rabin (probabilistic) or
deterministic variants with small witness sets for specific ranges are extremely fast
and reliable in practice. For cryptographic sizes, a handful of Miller–Rabin bases give
astronomically small error probability and is orders of magnitude faster than AKS.
 Implementation complexity and memory: Implementing efficient big-integer
polynomial arithmetic with FFT/specialized multiplication and memory to hold
polynomials/coefficients is nontrivial.
  No practical advantage: AKS’s theoretical importance (first unconditional
deterministic poly-time primality test) does not translate into practical performance or
deployment benefits for crypto or large prime testing.

1. Explore the factorization methods viz., Pollard p-1, Pollard rho, Number Field Sieve
and Quadratic Sieve methods and their time complexities.
Ans. Several integer factorization algorithms form the basis of cryptanalysis on RSA.
Pollard p−1 works efficiently when p−1 is B-smooth. Pollard ρ finds factors in expected
O(n1/4). The Quadratic Sieve (QS) has a sub-exponential complexity of L_n [1/2], while
the General Number Field Sieve (GNFS) improves this to L_n [1/3], making it the fastest
known general-purpose factorization method.
A. Pollard p−1 method (Pollard’s p−1)Working: Efficient when n has a prime factor p
such that p − 1 is B-smooth (i.e., all prime factors ≤ B), for reasonably small B.
Algorithm
 Choose bound B and compute M = lcm(1,2,3,...,B) (or product of pk ≤ B).
 Pick random a with 1 < a < n.
 Compute g = gcd (aM − 1 mod n, n).
 If 1 < g < n, g is a nontrivial factor. If g = n or g = 1 increase B or try another a.
B. Pollard ρ (rho) method Working: A generic probabilistic factoring algorithm; good at
finding relatively small factors without relying on smoothness.
Algorithm
 Consider the iteration x_{i+1} = f(x_i) mod n for some polynomial f(x) (commonly
f(x) = x2 + c).
 Run two sequences — one “tortoise” x_i and one “hare” x_{2i} — compute gcd(|x_i
− x_{2i}|, n) periodically.
 Once two sequence values collide modulo a prime factor p, difference is divisible by
p, and gcd extracts a factor.
C. Quadratic Sieve (QS) working: One of the fastest general-purpose factoring methods for
numbers up to a few hundred decimal digits (historically best until NFS took over for very
large sizes).
 Find many integers x such that x2 mod n is B-smooth (factorable over a small prime
base).
 Use linear algebra (mod 2) on the exponents of prime factors to find a subset whose
product is a square; leads to x2 ≡ y2 (mod n) and possibly a nontrivial factor gcd(x−y,
n).
Complexity:
 Sub-exponential: exp ((1 + o(1)) * sqrt( ln n * ln ln n ) ).
 Using L-notation:
 QS: L_n[1/2, 1] ≡ exp( (1 + o(1)) * sqrt(ln n * ln ln n) )That 1/2 exponent
characterizes the sqrt(log n log log n) behavior.
2. Explore and analyze Attacks on RSA and OAEP Protocol
Ans. Attacks on RSA and OAEP Protocol Attacks on RSA
RSA's security relies primarily on the difficulty of factorizing the modulus N=p.q However,
several other attacks exist:
 1. Factorization Attacks (The Core Threat): If the modulus N can be factored into p
and q using methods like NFS, the private key d can be easily computed,
compromising all messages.
 Defense: Use sufficiently large keys (e.g., 2048 bits or higher).
2. Timing Attacks: An attacker measures the precise time taken for the victim's
hardware to perform the decryption operation (C d mod N). Subtle differences in
computation time can reveal information about the bits of the private exponent d.
 Defense: Use blinding (randomizing the input before computation) or constant-
time algorithms.
3. Low Exponent Attacks (Short Public Key e):
 If a short public exponent (e.g., e=3) is used with a message M that is small
enough (Me < N), Me can be computed in plain numbers. Taking the e th root
reveals M.
 Hastad's Broadcast Attack: If the same message is sent to e different users, all
using the same short public exponent e, the system of congruences can be solved
using the Chinese Remainder Theorem (CRT) to recover the original message M.
 Defense: Use Padding (like OAEP) to ensure the message input is large and
random before encryption.
4. Chosen Ciphertext Attack (CCA): An attacker uses the victim's oracle (the decryption
function) to decrypt chosen ciphertexts. This is generally prevented by using proper
padding.
Attacks on OAEP (Optimal Asymmetric Encryption Padding)
The OAEP protocol is designed to prevent all the above CCA attacks and ensure
deterministic encryption isn't used. It combines the message with random padding, hashing,
and a mask before RSA encryption.
1. Malleability Attacks (Pre-OAEP): Before OAEP, RSA was malleable, meaning an
attacker could change a ciphertext C to C' = C r e mod N, which decrypts to M' = M.r
mod N allowing for subtle attacks. OAEP prevents this by linking the padding and
message together, ensuring any manipulation results in a decryption error.
2. Implementation Flaws (OAEP as a Barrier): The main risk is not in the OAEP theory,
but in its implementation. If the decryption routine is not strictly enforced (e.g., if it
leaks information about why the padding check failed), it can lead to a padding oracle
attack. By testing many ciphertexts, the attacker can learn information about the
message.
 Defense: Strict, constant-time validation of the padding ensures no information about
the padding structure is leaked during decryption failure.
3. Explore and analyze other SHA versions viz., SHA-1, SHA-224, SHA-256 and SHA-
384.
Ans. Analysis of SHA-1, SHA-224, SHA-256, and SHA-384
 SHA-1 is no longer secure after practical collision attacks were demonstrated. SHA-
224, SHA-256, and SHA- 384 remain secure and widely used in modern systems.
Their collision resistance of 112, 128, and 192 bits, respectively makes them robust
against current attack methods.
  SHA-1 and SHA-2 family (SHA-224, SHA-256, SHA-384, SHA-512) are iterated
hash functions based on Merkle–Damgård-like or related constructions. SHA-224/256
are truncated variants of SHA-256 construction; SHA-384 is truncated SHA-512.
Security strength (bits)
 SHA-1: 160-bit output → ideal security:
 Collision resistance: 280
 Preimage resistance: 2160
 SHA-224: 224-bit output → collision 2112, preimage 2^224
 SHA-256: collision 2128, preimage 2256
 SHA-384: collision 2192, preimage 2384
Known attacks and statusSHA-1:
 Collisions are practically feasible. Practical chosen-prefix/collision/collisions have
been demonstrated (e.g., “SHAttered” and later chosen-prefix attacks).
 Due to practical collisions, SHA-1 is deprecated for collision-resistant applications
(signatures, certificates).

 SHA-224 / SHA-256 / SHA-384 (SHA-2 family):

o No practical collisions are known to date.
o Best attacks are far from being feasible: collision work is around 2^{128} for
SHA-256 (birthday bound), and no practical improvements with severe
speedups are known.
o SHA-2 remains considered secure for today’s applications; NIST recommends
SHA-2 or SHA-3 for new systems.
Notes on preimage attacks: Preimage attacks for SHA-256 etc. remain computationally
infeasible (costs near 2256 or 2384).
4. Explore the security attacks on digital signature schemes.
Digital signatures provide authentication, integrity, and non-repudiation. Attacks aim to
undermine these properties by creating a valid signature for a message that the signer
never authorized.
Ans:
Key-Only Attack: The attacker only knows the public key of the signer. The goal is to forge
a signature for a new message.
 Defense: Requires the underlying hard problem (e.g., discrete logarithm or
factorization) to be computationally infeasible.
Known Message Attack: The attacker has a set of valid message-signature pairs (M 1, Sig1),
(M2, Sig2), for the signer. The goal is to forge a signature for a new message M not in the
known set.
Chosen Message Attack (CMA): The most powerful attack. The attacker gets the signer to
sign a list of messages of the attacker's choosing. The goal is to create a valid signature for a
different message M.
 Defense: Requires the signature scheme to be existentially unforgeable under CMA (EU-
CMA), the gold standard for signature security. RSA-based schemes like PSS
(Probabilistic Signature Scheme) achieve this.
 Hash Collision Attack: This applies to schemes that use a hash function (all modern
schemes do, such as Sig(M) = Sign(H(M)). If the hash function H is vulnerable to a
collision (like SHA-1), the attacker can find two messages, M and M' such that H(\
text{M}) = H(M'). If the signer signs M', the attacker has a valid signature for the
unauthorized message M.
o Defense: Use strong, collision-resistant hash functions like SHA-256 or SHA-3.
 Replay Attack (Non-Signature Specific): A simpler attack where an attacker captures a
valid signed transaction and simply "replays" it later.
o Defense: Digital signature schemes are stateless, so they don't prevent this alone.
It requires adding timestamps, sequence numbers, or nonces to the message before
it is signed.