Certificates
in [Cryptography]
|
Prev: 26th Chaos Communication Congress: How you can build an eavesdropper for a quantum cryptosystem
Next: Infinite One-Time Pad, is this product BS?
From: Maaartin on 3 Jan 2010 15:48 This may be a stupid question... A certificate contains a hash encrypted by a private key, right? I saw somebody trying to generate a toy certificate with only 64 bit RSA and he gets "RSA_sign:digest too big for rsa key". This is somehow understandable as the hash length is at least 128 bits, which can't be encrypted using 64 bit RSA. I've got a formula int encodableLengthForRsa(int bitLength) { return (bitLength + 7) / 8 - 11; } which seems to be right, but according to it, I'd need at least 1105 bits RSA for MD5/RSA certificate while there're 512 bits certificates in use. Where do I err?
From: unruh on 3 Jan 2010 16:15 On 2010-01-03, Maaartin <grajcar1(a)seznam.cz> wrote: > This may be a stupid question... > A certificate contains a hash encrypted by a private key, right? I saw > somebody trying to generate a toy certificate with only 64 bit RSA and > he gets "RSA_sign:digest too big for rsa key". This is somehow > understandable as the hash length is at least 128 bits, which can't be > encrypted using 64 bit RSA. I've got a formula > > int encodableLengthForRsa(int bitLength) { > return (bitLength + 7) / 8 - 11; > } > > which seems to be right, but according to it, I'd need at least 1105 > bits RSA for MD5/RSA certificate while there're 512 bits certificates > in use. Where do I err? In your arthmetic. (1105+7)/8-1=128 bytes, not bits. Ie, your formula is for the number of bytes that can be encoded, not bits.
From: Thomas Pornin on 3 Jan 2010 16:23 According to Maaartin <grajcar1(a)seznam.cz>: > A certificate contains a hash encrypted by a private key, right? It contains a _digital signature_. There exist several digital signature algorithms. One of them is called RSA and superficially looks like another algorithm, designed for asymmetric encryption (something quite different from digital signatures), and that algorithm is also called RSA. Thinking about digital signatures as a kind of encryption only makes things more obscure. > int encodableLengthForRsa(int bitLength) { > return (bitLength + 7) / 8 - 11; > } > > which seems to be right, but according to it, I'd need at least 1105 > bits RSA for MD5/RSA certificate Here, "bitLength" qualifies the bit length of the modulus, but the function returns a length in octets, not bits. Besides, this is only the maximum length for "PKCS#1 type 1 padding". For a PKCS#1-compliant signature, the padded data must include the hash value but also an extra header which identifies the hash function. All such details are in PKCS#1. Look it up there: http://www.rsa.com/rsalabs/node.asp?id=2125 --Thomas Pornin
From: Maaartin on 10 Jan 2010 17:36 Thank you both for the answers. On Jan 3, 10:23 pm, Thomas Pornin <por...(a)bolet.org> wrote: > According to Maaartin <grajc...(a)seznam.cz>: > > A certificate contains a hash encrypted by a private key, right? > > It contains a _digital signature_. There exist several digital signature > algorithms. One of them is called RSA and superficially looks like > another algorithm, designed for asymmetric encryption (something quite > different from digital signatures), and that algorithm is also called > RSA. > > Thinking about digital signatures as a kind of encryption only makes > things more obscure. I'd like to learn a bit more about that (not the exact standards, but the ideas). You wrote, that the RSA digital signature *superficially* looks like RSA encryption. Does it mean, that using another algorithm the result of the encryption by the private key could be forged? The answer to my other question "are there digital signature algorithms using no encryption" was easy to find.
From: Maarten Bodewes on 10 Jan 2010 17:40
Maaartin wrote: > This may be a stupid question... > A certificate contains a hash encrypted by a private key, right? I saw > somebody trying to generate a toy certificate with only 64 bit RSA and > he gets "RSA_sign:digest too big for rsa key". This is somehow > understandable as the hash length is at least 128 bits, which can't be > encrypted using 64 bit RSA. I've got a formula > > int encodableLengthForRsa(int bitLength) { > return (bitLength + 7) / 8 - 11; > } > > which seems to be right, but according to it, I'd need at least 1105 > bits RSA for MD5/RSA certificate while there're 512 bits certificates > in use. Where do I err? Look at PKCS#1 v1.5 again, you need 11 bytes padding overhead (2 byte header 0001h, PS consof minimum 8 bytes FFFFFFFFFFFFFFFF, 1 byte separator 00h) then a 15 + 20 bytes DER encoded DigestInfo when you choose SHA-1. So 11 + 15 + 20 (where the first 11 + 15 bytes are static) plus the 20 byte SHA-1 hash value. This in total would mean 46 bytes minimum key length. Since we (and most crypto libraries) like powers of two or anything close to it you could use a 48 byte (= 384 bit) key. This is too big for humans to consider so you might as well use 1024 bits. Why was I typing this again? Oh jeah, winding down. Regards, Maarten |