Chapter 1: Q22E (page 49)
Prove or disprove: If a has an inverse modulo b, then b has an inverse modulo a.
Yes, It can be proved that ifa has an inverse modulo b, then has an inverse modulo a.
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Find the inverse of:.
Alice and her three friends are all users of the RSA cryptosystem. Her friends have public keys where as always, for randomly chosen n-bit primes . Showthat if Alice sends the same n-bit message M (encrypted using RSA) to each of her friends, then anyone who intercepts all three encrypted messages will be able to efficiently recover M.
(Hint: It helps to have solved problem 1.37 first.)
Compute two different ways: by finding the factorization of each number, and by using Euclid’s algorithm.
Show that any binary integer is at most four times as long as the corresponding decimal integer. For very large numbers, what is the ratio of these two lengths, approximately?
RSA and digital signatures. Recall that in the RSA public-key cryptosystem, each user has a public key P=(N,e) and a secret key d. In a digital signature scheme, there are two algorithms, sign and verify. The sign procedure takes a message and a secret key, then outputs a signature . The verify procedure takes a public key , a signature , and a message M, then returns “true” if could have been created by sign (when called with message M and the secret key (N, e) corresponding to the public key ); “false” otherwise.
(a)Why would we want digital signatures?
(b) An RSA signature consists of sign, where d is a secret key and N is part of the public key . Show that anyone who knows the public key can perform verify , i.e., they can check that a signature really was created by the private key. Give an implementation and prove its correctness.
(c) Generate your own RSA modulus, N=pq public key e, and private key d (you don’t need to use a computer). Pick p and q so you have a 4-digit modulus and work by hand. Now sign your name using the private exponent of this RSA modulus. To do this you will need to specify some one-to-one mapping from strings to integers in . Specify any mapping you like. Give the mapping from your name to numbers then sign the first number by giving the value , and finally show that .
(d) Alice wants to write a message that looks like it was digitally signed by Bob. She notices that Bob’s public RSA key is . To what exponent should she raise her message?
What do you think about this solution?
We value your feedback to improve our textbook solutions.
