The RSA Cryptosystem - Understanding Cryptography - page 198

7.7. An RSA encryption scheme has the set-up parameters p = 31 and q = 37. The
public key is e = 17.

1. Decrypt the ciphertext y = 2usingtheCRT.
2. Verify your result by encrypting the plaintext without using the CRT.

7.8. Popular RSA modulus sizes are 1024, 2048, 3072 and 4092 bit.

1. How many random odd integers do we have to test on average until we expect to
find one that is a prime?
2. Derive a simple formula for any arbitrary RSA modulus size.

7.9. One of the most attractive applications of public-key algorithms is the estab-
lishment of a secure session key for a private-key algorithm such as AES over an
insecure channel.
Assume Bob has a pair of public/private keys for the RSA cryptosystem. Develop
a simple protocol using RSA which allows the two parties Alice and Bob to agree
on a shared secret key. Who determines the key in this protocol, Alice, Bob, or both?

7.10. In practice, it is sometimes desirable that both communication parties influ-
ence the selection of the session key. For instance, this prevents the other party from
choosing a key which is a weak key for a symmetric algorithm. Many block ciphers
such as DES and IDEA have weak keys. Messages encrypted with weak keys can
be recovered relatively easily from the ciphertext.
Develop a protocol similar to the one above in which both parties influence the
key. Assume that both Alice and Bob have a pair of public/private keys for the RSA
cryptosystem. Please note that there are several valid approaches to this problem.
Show just one.

7.11. In this exercise, you are asked to attack an RSA encrypted message. Imagine
being the attacker: You obtain the ciphertext y = 1141 by eavesdropping on a certain
connection. The public key is k pub =( n , e )=(2623 , 2111).
1. Consider the encryption formula. All variables except the plaintext x are known.
Why can't you simply solve the equation for x ?
2. In order to determine the private key d , you have to calculate d e − 1

≡ mod Φ ( n ).

There is an efficient expression for calculating Φ ( n ). Can we use this formula

here?
3. Calculate the plaintext x by computing the private key d through factoring n =
p

q . Does this approach remain suitable for numbers with a length of 1024 bit
or more?

·

7.12. We now show how an attack with chosen ciphertext can be used to break an
RSA encryption.
1. Show that the multiplicative property holds for RSA, i.e., show that the product
of two ciphertexts is equal to the encryption of the product of the two respective
plaintexts.