rsa implementation question

[Heiko Wundram]

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? ;)

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.

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

def pad_for_rsa_encrypt(data,algo,n):
	retv = [data]
	strlen = len(data)
	nlen = log2(n)/8
	while strlen < nlen-3:
		data.append(<randomchars>)
		nlen -= len(<randomchars>)
	data.append(chr(algo))
	data.append(struct.pack("!H",strlen))
	return "".join(data)

def unpad_after_rsa_decrypt(data,n):
	strlen = struct.unpack("!H",data[-2:])
	nlen = log2(n)/8
	if strlen > nlen-3:
		raise ValueError, "Invalid size of data in packet."
	return data[:strlen], ord(data[-3])

def sign(key,data):
	return key.decrypt(pad_for_rsa_encrypt(sha.new(data).digest(),0,key))
# 0 is for sha algorithm.

def verify(key,data,sign):
	netsgn, algo = unpad_after_rsa_decrypt(key.encrypt(sign),key)
	if algo <> 0:
		raise ValueError, "Invalid digest used in packet."
	datasgn = sha.new(data).digest()
	return datasgn == netsgn

Or something of the like... Anyway, what the deal about this algorithm is that 
the number of digits of the data used for encryption/decryption is not known 
in advance with high probability, only the last few digits might be known 
(length of plaintext encrypted and algorithm used), whereas if you use normal 
padding (with zeros), the problem domain is limited because only a certain 
number of positions of the plaintext (e.g. 160 bits when using a digest) 
actually contain data.

This does not make some public-key algorithms weaker (ElGamal), but RSA has to 
cope with the fact that it doesn't do inherent randomization (so for equal 
data to sign and equal key, you'll get equal signatures, which is bad!) 
That's why I would advise you to go use ElGamal, which is much better in this 
respect, and is patent-free too (well RSA is too, but anyway, the ElGamal 
family of public-key ciphers always was).

And, if you were using it to encrypt/decrypt a symmetric encryption key, you 
could also pad the algorithm used for encryption into the string, so that 
only the proper receiving end could get this last bit of info on the 
encryption method used (security by obscurity, but anyway).

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

Heiko.