Question

Consider the textbook RSA signature scheme (signing m is encrypting m with private key and verification is decrypting the signature with public key). Let us use primes p =23 and q=17. As public key we use e=3. Show how you can forge a valid signature of some messages (e.g., 8, 27, 64, 125, etc) without even knowing the private key (only knowing the public key). Let's say message m is the 2-th number above. Please write down its corresponding signature value in the box below: Your Answer:

Answer 1

The message number 27 can have a forged signature in the RSA signature scheme without knowing the private key because it's a perfect cube, which means raising it to the public key exponent yields the number itself.

Step-by-step explanation:

The student's question involves forging a signature in the RSA signature scheme, using given primes and a public key. In RSA, a valid signature can be forged for some numbers if they are perfect e-th powers, since raising them to the power of the public key exponent will yield the number itself. Considering the given public key e=3, and the 2nd message number 27, which is 33, we can directly calculate the signature as 271/e, which gives us 27, since 27 is a perfect cube. As such, 27 would be its own signature. In this specific case of the RSA signature scheme, knowledge of the private key is not necessary for these particular messages.