Paul Revere’s friend in a tower at MIT says he’ll send the message one if (the British are coming) by land and two if by sea. Since they know that RSA will be invented in the Boston area, they decide that the message should be encrypted using RSA with and . Paul Revere receives the ciphertext 273095689186. What was the plaintext? Answer this without factoring .
What could Paul Revere’s friend have done so that we couldn’t guess which message was encrypted? (See the end of Subsection 9.2.2.)
In an RSA cryptosystem, suppose you know , , and . Factor using the method of Subsection 9.4.2.
Choose two 30-digit primes and and an encryption exponent . Encrypt each of the plaintexts cat, bat, hat, encyclopedia, antidisestablishmentarianism. Can you tell from looking at the ciphertexts that the first three plaintexts differ in only one letter or that the last two plaintexts are much longer than the first three?
Factor 618240007109027021 by the method.
Factor 8834884587090814646372459890377418962766907 by the method. (The number is stored in the downloadable computer files ( bit.ly/2JbcS6p
) as n1.)
Let . Suppose you know that
Factor .
Let . Find and with but .
Suppose you know that
Use this information to factor 670726081.
Suppose you know that . Why won’t this information help you to factor 670726081?
Suppose you know that
How would you use this information to factor 3837523? Note that the exponent 1916460 is twice the exponent 958230.
Alice and Bob have the same RSA modulus , given to them by some central authority (who does not tell them the factorization of ). Alice has encryption and decryption exponents and , and Bob has and . As usual, and are public and and are private.
Suppose the primes and used in the RSA algorithm are consecutive primes. How would you factor ?
The ciphertext 10787770728 was encrypted using and . The factors and of were chosen so that . Decrypt the message.
The following ciphertext was encrypted mod using the exponent :
The prime factors and of are consecutive primes. Decrypt the message. (The number is stored in the downloadable computer files (bit.ly/2JbcS6p
) as naive, and is stored as cnaive.) Note: In Mathematica®, the command Round[N[Sqrt[n],50]] evaluates the square root of to 50 decimal places and then rounds to the nearest integer. In Maple, first use the command Digits:=50 to obtain 50-digit accuracy, then use the command round(sqrt(n*1.)) to change to a decimal number, take its square root, and round to the nearest integer. In MATLAB, use the command digits(50);round(vpa(sqrt(ʼn’)))
.
Let , , and . Let the message be .
Compute and ; then use the Chinese remainder theorem to combine these to get .
Change one digit of (for example, this could be caused by some radiation). Now combine this with to get an incorrect value for . Compute . Why does this factor ?
The method of (a) for computing is attractive since it does not require as large multiprecision arithmetic as working directly mod . However, as part (b) shows, if an attacker can cause an occasional bit to fail, then can be factored.
Suppose that , , and . The ciphertext is transmitted, but an error occurs during transmission. The received ciphertext is 2304329328016936947195. The receiver is able to determine that the digits received are correct but that last digit is missing. Determine the missing digit and decrypt the message.
Test 38200901201 for primality using the Miller-Rabin test with . Then test using . Note that the first test says that 38200901201 is probably prime, while the second test says that it is composite. A composite number such as 38200901201 that passes the Miller-Rabin test for a number is called a strong -pseudoprime.
There are three users with pairwise relatively prime moduli . Suppose that their encryption exponents are all . The same message is sent to each of them and you intercept the ciphertexts for .
Show that .
Show how to use the Chinese remainder theorem to find (as an exact integer, not only as ) and therefore . Do this without factoring.
Suppose that
and the corresponding ciphertexts are
These were all encrypted using . Find the message.
Choose a 10-digit prime and and 11-digit prime . Form .
Let the encryption exponent be . Write a program that computes the RSA encryptions of all plaintexts with . (Do not store or display the results.) The computer probably did this almost instantaneously.
Modify your program in (b) so that it computes the encryptions of all with and time how long this takes (if this takes too long, use ; if it’s too fast to time, use ).
Using your timing from (c), estimate how long it will take to encrypt all with (a year is approximately seconds).
Even this small example shows that it is impractical to make a database of all encryptions in order to attack RSA.