Cryptography Reference
In-Depth Information
15.2.1.4
Security Analysis
In Section 14.2.1.4, we analyzed the security of the RSA asymmetric encryption
system. Most things we said there also apply for the RSA DSS. This is particularly
true for the properties of the RSA family of trapdoor permutations. If, for example,
somebody is able to factorize the modulus n , then he or she is also able to deter-
mine the signing key and to generate digital signatures at will. Consequently, the
modulus n must be so large that its factorization is computationally infeasible for
the (polynomially bound) adversary one has in mind and against which one wants to
protect.
Also, the multiplicative property of the RSA function is particularly dangerous
whenRSAisusedasaDSS.If m 1 and m 2 are two messages with signatures s 1 and
s 2 ,then
( m 1 m 2 ) d (mod n )
s = s 1 s 2
is a valid signature for m = m 1 m 2 (mod n ). Consequently, we reemphasize that
good practices in security engineering must take care of the multiplicative structure
of the RSA function and protect against corresponding attacks. Remember from
our previous discussion that one can either require that messages have a certain
(nonmultiplicative) structure or randomly pad the messages prior to the generation
of the digital signatures.
In many applications, RSA is used as an asymmetric encryption system and as
a DSS. Consequently, it may be necessary to apply both the RSA Encrypt algorithm
and the RSA Sign algorithm to a particular message m . The question that arises
immediately is whether the order of the operations matters. More specifically, does
one have to encrypt m before it is digitally signed, or does one have to digitally sign
it prior to encryption? In the general case, the answer is not clear, and it matters what
the purpose of the cryptographic protection really is. In many practically relevant
situations, however, the second possibility is the preferred choice. Consequently, it
is often recommended to use the RSA DSS to digitally sign a message and then use
the RSA asymmetric encryption system to encrypt the result. In this case, one must
be concerned about the relative sizes of the moduli in use.
Assume that user A wants to digitally sign and then encrypt message m for
user B. Also assume that ( n A ,d A ) is A's private RSA signing key and ( n B ,e B )
is B's public RSA encryption key. If n A
n B , then the application of the two
algorithms is simple and straightforward (i.e., the output of the RSA Sign algorithm
is smaller than or equal to the modulus n A , and this value can then be used as
input for the RSA Encrypt algorithm). If, however, n A >n B , then the output of
the RSA Sign algorithm may be larger than what is allowed as input for the RSA
Search WWH ::




Custom Search