# Re: rsa implementation question

**From:** Heiko Wundram (*heikowu_at_ceosg.de*)

**Date:** 08/12/04

**Next message:**Serj K.: "problems with pysmb"**Previous message:**Edward Diener: "Re: Static method object not callable"**In reply to:**Bryan Olson: "Re: rsa implementation question"**Next in thread:**Bryan Olson: "Re: rsa implementation question"**Reply:**Bryan Olson: "Re: rsa implementation question"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

To: python-list@python.org Date: Thu, 12 Aug 2004 04:10:52 +0200

Am Donnerstag, 12. August 2004 02:36 schrieb Bryan Olson:

*> 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.
*

Pardon me, yeah, the modulus is composite, I should've rather said that most

public key ciphers work in Z{n}. And I know that it's pretty easy to

generalize ElGamal to work in other rings than Z, or take bucket public key

cryptography for example.

I know of others, but: have you ever seen an implementation or use case of

some algorithm not working in Z{n}(*)? I have not, at least not when working

with computers.

*> 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/
*

Yup, I read those, and yeah, I know what they are talking about, and yeah,

that's not what I said. It's not about decrypting to sign, encrypting to

verify, it's about the redundancy function. In case you use a proper hash

function (I'm talking about identity with SHAing before signing), this attack

blatantly fails, as it would mean that you'd have to find hash collisions.

Even when I can easily find a m~ for which I have a valid signature m,

finding a plaintext for m~ which is meaningful should be impossible, due to

the hashing, for "long enough plaintext."

And the example code I gave was not about leaving out hashing before putting

it throught the identity function as "redundancy", it was exactly about

reducing redundancy, which probably I was to stupid to explain correctly,

but I'll try now.

*> Don't do that, even for encryption. See Bleichenbacher's
*

*> attacks on RSA encrpytion:
*

*>
*

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

Link doesn't work... But anyway, look at the same book on page 288, (ii):

"A pseudorandomly generated bitstring should be appended to the plaintext

before encryption (this is also called salting)."

That's exactly what my little example was trying to do: append a salt to the

data which was being encrypted. First, this gives an internal structure to

the data which is being encrypted/decrypted (and thus makes it easy to

discard invalid values), as you just have to check that the two lowest bytes

of the number coming out are <= keysize//8, and also assures that you don't

lose information when for example you are encrypting "what is this?" with a

768 bit key, now when this number comes out of decryption, the string will

have been "prepadded" with zeros, but as you know the actual length of the

string (from the two lowest bytes), you can extract the string properly.

Second, what this also achieves, is that you may encrypt the same plaintext

for the same recipient multiple times without an eavesdropper seeing that the

plaintext is identical (because of the salt), and

Thirdly, the attack stated on the given page is also not successful (when

encrypting to multiple recipients with the same encryption exponent, but this

is certainly not true for most common situations I need cryptography in).

So, pre/postpadding with salt is certainly not the wrong way to go for

encryption.

Now I'd really like to hear from you why this same argument doesn't go for

signing. Because:

1) I generate a signature for a string "some string" with SHA.

2) I decrypt this hash, which is salted by the same standard salting algorithm

I noted above with my private key to get the signature

3) I encrypt the signature to get the salted hash with my public key, which

can easily be unsalted, and then checked for validity.

Forging a valid signature would mean the following steps:

1) Find a pair of numbers (n,E(n)) for which E(n) has the lowest two bytes

<= keysize//8. It's pretty easy to insert additional constraints here: for

example, the string of randomized bits in E(n) has to have parity one to be

accepted, this would make this step harder (but not all of the positions may

be one, except when the bitstring is of length one, or something).

2) Now, find a pair from one of the pairs found in (1) which has a value which

has correct length (sha digests are always 160 bits long),

3) Now, for this pair, find a message which corresponds to the hash

value.

If you complete these three steps (well, you'd only have to find one pair in

step one and two, which should be hard enough), you'll have a faked

signature. But not before this.

I recon that step three is computationally infesible, and I also assume that

finding a pair (n,E(n)) which first of all has the properties that I give to

it (stated above), and also turns out to be a valid hash value for some

string I want it to be is computationally infesible. But, as I stated above,

even if step 1 is dead easy (by using the identify function here), what is

the use if I can easily find a a proper signature for a certain hash value, if

I have no plaintext for the hash value for which I have the signature? The

problem being that I can't construct the signature from the hash value, but

rather even when using identidy redundancy, I have to have the signature

first, before constructing the hash value.

At least that's what my professor taught me at univ, and with what I can

agree.

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

No, you won't, I'm more or less a hobby cryptographer... And I guess I'm

certainly not the smartest at this, but... I'd love to hear why you think the

above argumentation is wrong, or direct me to a paper which explains why

salting a signature with an equally simple algorithm I proposed to salt a

string to encrypt won't make things "more secure" for signing also...

Anyway, if you're up to some more explaining, feel free to contact me

off-list... I'd be glad to learn... :-)

Heiko.

**Next message:**Serj K.: "problems with pysmb"**Previous message:**Edward Diener: "Re: Static method object not callable"**In reply to:**Bryan Olson: "Re: rsa implementation question"**Next in thread:**Bryan Olson: "Re: rsa implementation question"**Reply:**Bryan Olson: "Re: rsa implementation question"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]