rsa implementation question
Heiko Wundram
heikowu at ceosg.de
Wed Aug 11 19:20:58 CEST 2004
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.
More information about the Python-list
mailing list