rsa implementation question
bryanjugglercryptographer at yahoo.com
Thu Aug 12 02:36:59 CEST 2004
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.
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
> Basically, what I always implemented is something like (pseudocode):
Don't do that, even for encryption. See Bleichenbacher's
attacks on RSA encrpytion:
> 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
Then I'm guessing I won't see you at Crypto 04 next week ;)
More information about the Python-list