Let a composite number n pq has two prime factors prove

Question

Question 1. Solve the index equation: 4x¹² ≡ 25 mod 127

Question 2. Check if p = 753179420969 is prime or not via Rabin-Miller's Probabilistic Test. You must use at least 25 bases.

Question 3. Let a composite number n = pq has two prime factors. Prove that n cannot be a Carmichael number.

Question 4. Alice wants to send the plaintext "CRYFTOLOGY" to Bob via RSA cryptosystem, using Bob's public key. Bob then has to decrypt it. How can she implement it? How can Bob decrypt it? You must use your own two primes p and q and encryption key e coprime to Φ(n).

Question 5. Let Φ(n) is given by Φ(n) = 38547272829660. Find the factors of n.

Question 6. Let (n, e) = (16504217646971, 78893) be Bob's public key, where e represents the encryption key. Suppose Oscar has obtained the decryption key d = 5568617131253. Then Oscar can factor n. Find the factors of n.

Question 7. Let n = 16504217646971 be Bob's public key. Suppose Oscar has obtained the decryption key d < n^(1/4)/3. Find the factors of n = 16504217646971 via Wiener's "Low Decryption Exponent Attack". You must choose your own d coprime to Φ(n).

Question 8. Let (n, e) be Bob's public key. Alice sends the ciphertext C using Bob's public key (n, e) for the plaintext M:= HILBERT. Show how Bob decrypt it via the Chinese Remainder Theorem. You must use your own moduli with the encryption key e and the corresponding decryption key d.

Answer 1

For the following mathematics problem, simplify the following questions and show results by exhibiting the complete procedure. Q1. Simplify the index equation: 4x12 = 25 mod 127 Q2. Check if p = 753179420969 is prime or not by using the Rabin-Miller's Probabilistic Test. You should use at a minimum of 25 bases. Q3. Assume a composite number n = pq consists of two prime factors. Prove that n can’t be a Carmichael number. Q4. Alice wishes to send the plaintext "CRYFTOLOGY" to Bob through RSA cryptosystem, by using Bob's public key. Bob then has to decrypt it. Illustrate how can she implement it? Explain how can Bob decrypt it? You should use your own two primes p and q and encryption key e coprime to F(n). Q5. Suppose n = 16504217646971 be Bob's public key. Assume Oscar has obtained the decryption key d < n(1/4)/3. Determine the factors of n = 16504217646971 through Wiener's ‘Low Decryption Exponent Attack’. You should select your own d coprime to F(n).