Unit 3: Assymetric-key Encipherment - Subjective Questions

Asymmetric-key cryptography is primarily based on concepts from number theory and abstract algebra.

• Modular arithmetic: Calculations are performed modulo an integer . Two integers are congruent when .
• Greatest common divisor: The condition determines whether has a multiplicative inverse modulo .
• Modular inverse: An integer satisfies .
• Prime numbers: Large primes are used to construct keys in RSA, ElGamal, and Diffie-Hellman.
• Euler's totient function: counts the positive integers less than that are relatively prime to .
• Exponentiation in finite groups: Security often depends on the difficulty of reversing modular exponentiation.
• Hard mathematical problems: Factoring large composite numbers and solving discrete logarithms are assumed to be computationally infeasible.

These concepts enable the construction of related public and private keys while making recovery of the private key from public information impractical.

A prime number is an integer greater than that has exactly two positive divisors: and itself. For example, , , , and are prime, whereas is composite because .

Large primes are important because:

• In RSA, two large primes and are multiplied to produce .
• In Diffie-Hellman and ElGamal, arithmetic is performed in a finite group commonly defined using a large prime modulus .
• The security of RSA depends on the difficulty of factoring a large composite modulus.
• The security of Diffie-Hellman and ElGamal depends on the difficulty of the discrete logarithm problem.
• Larger primes increase the search space and make exhaustive attacks impractical.

Primes must also be chosen carefully. Weak, repeated, or predictable primes can compromise the private key even when the nominal key size is large.

Trial division determines whether is prime by checking divisibility by every prime up to . If none divides , then is prime.

The Fermat primality test uses Fermat's little theorem. If is prime and , then:

To test , choose one or more bases and evaluate the congruence. If it fails for any base, is composite. If it holds, is only considered a probable prime.

Limitations:

• Trial division is deterministic but inefficient for very large integers.
• Fermat's test can incorrectly classify a composite number as probably prime.
• A Fermat pseudoprime may pass the test for a particular base.
• Carmichael numbers, such as , pass the Fermat test for every base relatively prime to the number.

Therefore, practical cryptographic systems use stronger tests such as Miller-Rabin, often followed by additional verification.

The Miller-Rabin test is a probabilistic primality test suitable for large cryptographic integers.

For an odd integer , write:

where is odd. Choose a base with and calculate:

The number passes the round if , , or repeated squaring produces :

If none of these values is , then is composite.

For example, let . Since , take , , and . Then:

Squaring once gives:

Neither value is initially nor , so is composite.

Repeating the test with independent bases makes the probability of accepting a composite number extremely small.

Integer factorization is the process of expressing a composite integer as a product of prime factors. For example:

In RSA, the public modulus is constructed as:

where and are large secret primes. If an attacker factors , the attacker can compute:

The private exponent can then be recovered from the public exponent by solving:

For sufficiently large and properly generated primes, factoring is computationally difficult using classical computers. Important factorization methods include trial division, Pollard's rho method, the quadratic sieve, and the general number field sieve.

RSA security therefore requires a large modulus, strong random prime generation, balanced prime sizes, and secure padding. RSA security is related to factorization, although breaking every possible RSA construction has not been formally proved equivalent to factoring.

The Chinese Remainder Theorem (CRT) states that if are pairwise coprime, then the simultaneous congruences

have a unique solution modulo .

For the given system:

Define , , and . Their required inverses are:

Therefore:

Thus, the solution is:

Indeed, leaves remainders , , and when divided by , , and , respectively.

Standard RSA decryption computes:

where . The CRT optimization replaces this large modular exponentiation with two smaller operations.

Precompute:

Then calculate:

Recombine the results using:

Since the exponentiations use moduli roughly half the bit length of , RSA-CRT is commonly about four times faster than direct private-key exponentiation.

However, implementations must protect against fault attacks. A fault in one branch can expose a factor of . Implementations may verify the recombined result, use exponent blinding, or apply other fault-detection mechanisms.

Symmetric-key cryptography uses the same secret key, or easily related secret keys, for encryption and decryption. Asymmetric-key cryptography uses a public key and a mathematically related private key.

In practice, systems use hybrid cryptography. An asymmetric mechanism authenticates parties or establishes a session key, while a symmetric cipher efficiently protects the actual data.

RSA key generation consists of the following steps:

1. Select two distinct large random primes and .
2. Compute the modulus:

3. Compute either Euler's totient or Carmichael's function:

4. Choose a public exponent such that:

A common choice is .

5. Compute the private exponent as the modular inverse of :

6. Publish the public key and keep , , and secret.

The primes must be generated with a cryptographically secure random number generator and tested for primality. Real implementations also store CRT parameters for faster private-key operations.

Let the RSA public key be and private exponent be , where:

Thus, for some integer :

Encryption and decryption are:

Consider the computation modulo each prime factor of .

• If does not divide , Fermat's little theorem gives .
• Because is a multiple of , .
• Hence .
• If divides , both and are modulo .

The same argument applies modulo . Therefore:

and

By the Chinese Remainder Theorem:

Thus, RSA decryption recovers the original representative: modulo .

First compute the modulus and totient:

The selected exponent satisfies . Find such that:

Since , we obtain .

• Public key:
• Private key:

Encryption gives:

Using repeated squaring, , , and:

Thus, .

Decryption computes:

Therefore, the decrypted plaintext is . The small parameters are only for illustration and provide no practical security.

RSA security depends on more than choosing a large modulus.

• Factorization attacks: If is too small or its primes are weak, an attacker may factor and recover the private key.
• Textbook RSA attacks: Deterministic RSA reveals when the same message is encrypted repeatedly and is malleable.
• Padding attacks: Incorrect handling of PKCS #1 v1.5 padding can create decryption oracles.
• Small-exponent attacks: A small public exponent combined with poor padding or repeated messages can expose plaintext.
• Shared-prime attacks: If two moduli share a prime, their greatest common divisor reveals the factor.
• Timing and power analysis: Side-channel leakage from private-key operations may disclose .
• Fault attacks: Faults during CRT computation can reveal or .

Secure implementations use sufficiently large keys, RSA-OAEP for encryption, RSA-PSS for signatures, secure random generation, blinding, constant-time operations, CRT verification, and strict error handling.

ElGamal operates in a cyclic group, commonly a subgroup of , where the discrete logarithm problem is hard.

Key generation:

• Choose suitable public group parameters: a prime and generator .
• Select a private key .
• Compute .
• The public key is and the private key is .

Encryption of message :

• Select a fresh random ephemeral value .
• Compute:

• The ciphertext is .

Decryption:

Compute the shared value and its modular inverse. Recover:

Correctness follows because , so multiplication by its inverse removes the masking factor. The random must be fresh, unpredictable, and never reused.

RSA and ElGamal are both asymmetric cryptosystems, but they differ substantially.

Neither textbook scheme provides modern chosen-ciphertext security. RSA should use OAEP for encryption, while ElGamal should be used through a secure hybrid or integrated encryption construction with authentication.

The Rabin cryptosystem uses a modulus , where and are large primes, often selected so that .

• Public key:
• Private key:
• Encryption:

• Decryption: Find square roots of modulo and modulo .

For primes congruent to modulo , roots can be calculated as:

Each modulus has two roots, and . Combining the two choices modulo with the two choices modulo through CRT gives four roots modulo .

Consequently, decryption produces four candidate plaintexts. Redundancy or a structured encoding is required to identify the intended message. Plain Rabin encryption is deterministic and malleable, so a secure encoding transformation is necessary in practice.

Compute the public modulus:

Encryption gives:

Now find square roots of modulo each prime.

Modulo :

so the roots are and .

Modulo :

so the roots are and .

Combining , , , and through the Chinese Remainder Theorem gives:

Thus, the four candidate plaintexts are:

The original plaintext is , but the basic Rabin operation alone cannot determine which root was intended. A secure redundancy or encoding mechanism is required.

Diffie-Hellman allows two parties to establish a shared secret over an insecure channel.

Let the public parameters be a cyclic group with generator . In the classic finite-field form, the parties use a prime and perform arithmetic modulo .

• Alice selects a private value and sends:

• Bob selects a private value and sends:

• Alice computes:

• Bob computes:

Therefore:

An eavesdropper observes , , , and , but recovering from or from requires solving a discrete logarithm. The shared group element should be processed by a key derivation function before use as a symmetric key.

The public parameters are and .

Alice computes her public value:

Since , , and , we obtain:

Bob computes his public value:

Alice then computes:

Bob computes:

Thus, both obtain the same shared value:

These small values are used only to demonstrate the arithmetic. Practical Diffie-Hellman requires approved large groups, public-key validation, authenticated exchanges, and a key derivation function.

Basic Diffie-Hellman establishes a shared secret but does not authenticate the participants. An active attacker can exploit this weakness.

• Alice sends , but the attacker intercepts it and sends to Bob.
• Bob sends , but the attacker intercepts it and sends to Alice.
• Alice creates a secret shared with the attacker.
• Bob creates a different secret shared with the attacker.
• The attacker decrypts, possibly modifies, and re-encrypts messages between them.

The attack is prevented by authenticated Diffie-Hellman, using mechanisms such as:

• Digital signatures over the exchanged public values and session context
• Certificates that bind public keys to identities
• Pre-shared authentication keys and message authentication codes
• Authenticated protocols such as TLS
• Verification of key fingerprints through a trusted channel

Public parameters and received group elements must also be validated to prevent small-subgroup and invalid-key attacks.

The principal asymmetric schemes in this unit have different roles and assumptions.

Common practical observations:

• Textbook asymmetric algorithms should not be used directly.
• Secure encodings, authenticated protocols, and strong randomness are essential.
• Asymmetric operations are slower than symmetric encryption.
• Modern systems generally use these mechanisms to establish or protect symmetric session keys.
• Security depends on parameter size, correct group selection, implementation quality, and resistance to side-channel attacks.