Chapter 1: Q42E (page 52)

Suppose that instead of using a composite $N = p q$ in the RSA cryptosystem (Figure 1.9), we simply use a prime modulus p . As in RSA, we would have an encryption exponent e, and the encryption of a message $m m o d p$ would be $m^{e} \mod p .$ Prove that this new cryptosystem is not secure, by giving an efficient algorithm to decrypt: that is, an algorithm that given and $p, e,$ $and m^{e} \mod p$ as input, computes . Justify the correctness and analyze the running time of your decryption algorithm.

Short Answer

Expert verified

It can be proved that the given decryption algorithm works correct and the running time of the algorithm is $O (n^{3})$

Step by step solution

Step 1:Explain RSA Cryptosystem

RSA cryptosystem is cryptographic algorithm that is asymmetric, that works on both public and private keys. The RSA is based on the larger integer that is difficult to factorize.

Justify the correctness and analyse the running time

Consider the RSA cryptosystem that uses a prime modulus p and encryption exponent e. The message $m m o d p$ is encrypted as $m^{e} m o d p$ .

The requirement for e relatively prime to $(p - 1)$ ,

So the decryption of the message will be as follows,

$d = e^{1} md (p - 1)$

Apply decryption over the given encrypted message as follows,

$(m^{e})^{d} \equiv m^{e d m o d (p - 1)} (m^{e})^{d} \equiv m m o d p$

Therefore, It is proved that the given decryption algorithm works correct and the running time of the algorithm is $O (n^{3})$

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Short Answer

Step by step solution

Step 1:Explain RSA Cryptosystem

Justify the correctness and analyse the running time

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Problem Solving Techniques

Algorithms in Computer Science

Theory of Computation

Computer Systems

Game Design in Computer Science

Databases

Study anywhere. Anytime. Across all devices.