Solution Found!
Suppose that instead of using a composite N = pq in the RSA cryptosystem (Figure 1.9)
Chapter 1, Problem 1.42(choose chapter or problem)
Suppose that instead of using a composite N = pq in the RSA cryptosystem (Figure 1.9), wesimply use a prime modulus p. As in RSA, we would have an encryption exponent e, and theencryption of a message m mod p would be me mod p. Prove that this new cryptosystem is notsecure, by giving an efficient algorithm to decrypt: that is, an algorithm that given p, e, andme mod p as input, computes m mod p. Justify the correctness and analyze the running time ofyour decryption algorithm.
Questions & Answers
QUESTION:
Suppose that instead of using a composite N = pq in the RSA cryptosystem (Figure 1.9), wesimply use a prime modulus p. As in RSA, we would have an encryption exponent e, and theencryption of a message m mod p would be me mod p. Prove that this new cryptosystem is notsecure, by giving an efficient algorithm to decrypt: that is, an algorithm that given p, e, andme mod p as input, computes m mod p. Justify the correctness and analyze the running time ofyour decryption algorithm.
ANSWER:Step 1 of 2
RSA is a short for Rivest-Shamir-Adleman. It is an algorithm used by the computers to encrypt and decrypt messages. It is based on the asymmetric cryptography algorithm which uses two keys known as public key and private key for encryption and decryption.