Cryptography Reference
In-Depth Information
to a secret key recovery. This means that the lack of equivalence between RSADP and
RSAFP guarantees that we cannot extract a secret key from a sealed decryption device.
3, we do not
know if computing a cubic root is equivalent to factorizing N in the RSA case, i.e. when
gcd( e
Obviously, breaking RSA means computing e -th roots. Even with e
=
,
( p
1)( q
1))
=
1. We can prove equivalence in some other cases, i.e. when e
is not invertible modulo ( p
2, we can prove that computing square
roots is equivalent to factorizing N : we just pick a random x , compute y
1)( q
1). For e
=
x 2
=
mod N ,
and compute one square root z of y .If x
z (mod N ), we just try again. Otherwise
we use the Fermat method in order to factorize N . This eventually halts because the
square root algorithm has no means to know which are the two square roots which are
not interesting (namely x and N
≡±
=
3, we can similarly prove that computing
cubic roots is equivalent to factorizing N when 3 divides ( p
x ). For e
1)( q
1).
9.3.2 RSA Standards
PKCS (Public-Key Cryptography Standards) is a set of algorithms published by the
RSA Data Security company. Of course, they are based on the RSA algorithm. Here
we give details about the encryption scheme of the PKCS#1v1.5 standard. Note that it
is now replaced by PKCS#1v2.1 (Ref. [14]) as we will discuss in Section 9.3.8.
We are given a modulus N of k bytes. In order to encrypt a message M of length
at most k
11 bytes, we proceed as follows.
1. We generate a string PS of pseudorandom nonzero bytes so that the message
concatenated with PS is of length k
3 bytes.
2. We construct the byte string by concatenating a zero byte, a byte equal to 2, PS,
another zero byte, and the message. We write this 00
||
02
||
PS
||
00
||
M .
3. This byte string is converted into an integer.
4. We compute the plain RSA encryption.
5. We convert the result into a string of k bytes.
The decryption is then straightforward.
1. We convert the ciphertext into an integer. We reject it if it is greater than the
modulus.
2. We perform the plain RSA decryption and obtain another integer.
3. We convert the integer back into a byte string.
4. We check that the string has the 00
||
02
||
PS
||
00
||
M format for some byte strings
PS and M where PS has no zero bytes.
5. We output M .
The 02 byte is used in order to specify that the message is an encrypted message in the
RSA format. Some other parts of the PKCS standard use other values for this byte.
Search WWH ::




Custom Search