rsa implementation question

[Bryan Olson]

Heiko Wundram wrote:
> Am Mittwoch, 11. August 2004 10:21 schrieb Bryan Olson:
> > I agree with about half of Heiko Wundram's response.
> 
> Well, with what don't you agree? ;)

Well, since you asked:  

|> RSA (Rivest-Shamir-Adleman encryption) never works in 
|> "blocks", as there is no notion of blocks in public key 
|> cryptography, there's only the notion of doing an operation
|> on plaintext modulo a large prime n.

There is a notion of blocks in many public-key ciphers, 
including RSA.  The modulus n in RSA is composite, not prime. 
The "only the notion" statement implies that integer modular 
arithmetic is the only base for public-key cryptography, which 
is not true.

> Anyway, I've not read anywhere that for signing a message it is
> discredited to use RSA decrypt with private key, encrypt with
> public key.

Try the book you cited, section 11.2.3, Note 11.10, Example 
11.11, and Remark 11.12.

    http://www.cacr.math.uwaterloo.ca/hac/

Subsequent to the publishing of HAC, the 'redundancy function' 
they describe in Section 11.3.5 'ISO/IEC 9796 formatting', fell 
to a series of attacks, first by J. S. Coron, D. Naccache and J. 
Stern, then improved and extended by D. Coppersmith, S. Halevi 
and C. Jutla, and several following works.

The other redundancy function they describe is the one for which 
I presented Python code (for the SHA-1 usage).  Don't use it 
without the hash function.

There are now more trustworthy padding methods for RSA signing 
and encryption, based on the "Exact Security" and "OAEP" papers 
of Bellare and Rogaway, with arguably interesting follow-ups by
Victor Shoup.

> Basically, what I always implemented is something like (pseudocode):

Don't do that, even for encryption.  See Bleichenbacher's 
attacks on RSA encrpytion:

  http://www.bell-labs.com/user/bleichen/bib.html

[...]

> So much for what I always did. I really don't know whether this is some form 
> of secure way to go, but at least no cryptography book I read has ever 
> discouraged the use of random padding while encrypting data which is much 
> shorter than the "block size" of a public-key crypto algorithm (esp. for 
> RSA).

Then I'm guessing I won't see you at Crypto 04 next week ;)


-- 
--Bryan