Cryptography Reference
In-Depth Information
4.29. Exercise 4.28 shows, in particular, that φ ( n ) / 2 may be used instead of
φ ( n ) in the RSA cipher. Explain why using φ ( n ) / 2 + 1 in place of φ ( n )
would be an exceptionally bad idea.
4.30. Show that in Exercise 4.28, n may be any natural number relatively
prime to x and part 1 still holds.
Also, show that λ ( n ) φ ( n ), for any
N
n
.
4.31. Exercise 4.29 shows that λ ( n ) is an example of what is called a universal
exponent for n , which means an exponent f such that x f
1 (mod n )
for all integers x relatively prime to n .
Show that λ ( n ) is the minimal
universal exponent for n .
( Hint: Use the notion of the order of an integer defined in Definition
A.23 on page 479, in conjunction with the Chinese remainder theorem
A.12 provided on page 478. )
4.32. Let n be an RSA modulus and suppose that m
is a plaintext message
unit. Is it necessary that gcd( m,n ) = 1 in order to use RSA? If not provide
a counterexample. If so prove it.
Z
m e (mod n ) sent by Alice to Bob using the
RSA cipher. To do so, he intercepts c , masks it by the execution,
4.33. Mallory wants to decrypt c
c
cx e (mod n ) ,
) , and sends c
for a randomly chosen x
(
Z
/n
Z
to Bob. Bob computes
m
( c ) d (mod n ) and sends it to Alice. Explain how Mallory can recover
m if he intercepts m .
( The above is an instance of an adaptive chosen-ciphertext attack on RSA.
In such attacks, Mallory may send any number of ciphertexts to be de-
crypted, after which he uses the results to select succeeding ciphertexts.
Eventually, Mallory hopes to reveal data about the plaintext, or even the
key. Hence, this type of attack may be viewed as an interactive form of
the chosen-ciphertext attack ( see Footnote 4.3 on page 176 ) . Such attacks
may be thwarted by ensuring that the plaintext message, m , has a specified
fixed structure, so that if m is disguised as m , then it is unlikely that the
latter will maintain that structure. Therefore, if Bob receives a cipher-
text that decrypts to a plaintext without that structure, he will discard it
as fraudulent. Adaptive chosen-ciphertext attacks can work only when ci-
phertexts satisfy what is called ciphertext malleability , which means that
the ciphertext can be masked in certain ways that have a foreseeable effect
on the deciphering. One well-known prevention of such attacks on RSA is
OAEP ( see page 174 ) . )
Exercises 4.34-4.37 refer to the RSA signature scheme developed on pages
181-183. Use the given parameters in each case to first compute the en-
cryption key e using the Euclidean algorithm on φ ( n ) and d . Then compute
Search WWH ::




Custom Search