Certificates
Maaartin
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?
unruh
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.
Thomas Pornin
> 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
Maaartin
On Jan 3, 10:23 pm, Thomas Pornin <por...@bolet.org> wrote:
> According to Maaartin <grajc...@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.
Maarten Bodewes
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
Thomas Pornin
> You wrote, that the RSA digital signature *superficially* looks like
> RSA encryption.
No, I wrote that the RSA digital signature _algorithm_ superficially
looks like a (reverse) RSA encryption _algorithm_. This is precisely the
reason why you talk about "encrypting with the private key" and I point
out that this is not the fundamental design of digital signatures; this
is merely an artefact of one specific digital siganture algorithm
(namely RSA), which does not work for other signature algorithms (e.g.
DSA or ECDSA) and actually does not work well with RSA either since it
ignores padding issues.
> I'd like to learn a bit more about that (not the exact standards, but
> the ideas).
Actually reading the PKCS#1 standard (which is not that big) would
give you some useful information. You may also want to read the
chapter 11 of the Handbook of Applied Cryptography, which can be
downloaded for free there:
http://www.cacr.math.uwaterloo.ca/hac/
> Does it mean, that using another algorithm the result of the
> encryption by the private key could be forged?
I mean that using another algorithm would just not make sense. In an
asymmetric key encryption system, the public key is for encrypting and
the private key for decrypting. An artefact of RSA is that both public
and private keys can be contrived into the same format, although this is
not usually done because private key operations benefit from using some
more internal knowledge of the private key structure (namely the
factors, for CRT and a 4x speedup). If you then ignore padding (a
cursory reading of PKCS#1 will show you why this is not really an
option) then you might conceive the idea that a digital signature is
"encrypting with the private key". But that is a flawed idea, and you
better stop using it. If you want to understand what is going on, that
is.
If the above paragraph did not make sens to you, then this means that
you do not know enough on RSA and digital signatures to pursue the
subject. This is easily corrected, by reading the documents which I
referred to above.
--Thomas Pornin
Maaartin
> According to Maaartin <grajc...@seznam.cz>:
>
> > RSA encryption.
>
> No, I wrote that the RSA digital signature _algorithm_ superficially
> looks like a (reverse) RSA encryption _algorithm_.
Sure, my fault, the signature is just a bunch of bits, I meant the
alg.
It does make sense to me, nonetheless I'm going to read both
documents. Thank you for the exact answer.
I've got a practical question: I need to find out which private key
corresponds with which certificate. The certificate is a base64 file
starting with "-----BEGIN CERTIFICATE-----" (no idea what's the name
of this format) and using openssl asn1parse I can find to whom it
belongs. The private key looks similar, but there's no such
information there. I do not think it should be there, but I need to
find it out in order to clean up some mess.
There're also some CSRs packed together with the private key in one
file, but maybe even this is wrong, otherwise I'd use the information
therein. One more question: Are the CSRs of any use after having
obtained the certificate?
Thomas Pornin
> I've got a practical question: I need to find out which private key
> corresponds with which certificate. The certificate is a base64 file
> starting with "-----BEGIN CERTIFICATE-----" (no idea what's the name
> of this format) and using openssl asn1parse I can find to whom it
> belongs. The private key looks similar, but there's no such
> information there. I do not think it should be there, but I need to
> find it out in order to clean up some mess.
The format is called PEM, as "Privacy-enhanced Electronic Mail". It is
an old proposal from the IETF (RFC 1421 to 1424), which never really
took off. PEM was using X.509 certificates and related objects, and then
encoding them with Base64 and the "-----BEGIN FOO-----" headers. The
point of that text-based encoding was that it could survive the kind of
abuse which text emails suffered at that time.
In practice, users of X.509 began to use MIME for sending binary objects
through emails, and CMS (aka PKCS#7) for encryption and signature, the
combination of CMS and MIME being called S/MIME. Other people simply
shunned the X.509 part, and redesigned key formats and so on, and this
became PGP.
OpenSSL still retains the encoding format from PEM, mostly through
inertia.
X.509 uses ASN.1. ASN.1 is a notation _and_ a set of encoding rules for
structured data (the encoding rules are called DER or BER). This is what
the OpenSSL 'asn1parse' tool walks through. The public key is hidden in
a nested structure, which asn1parse shows as a 'BIT STRING' (in an
asn1parse dump from a certificate, you should see two BIT STRINGs, and
the public key is in the first). For a complete primer on ASN.1, see the
following book (downloadable for free after registration) :
http://www.oss.com/asn1/larmouth.html
A RSA public key consists mostly of the public modulus and the public
exponent, the latter being almost always a small odd integer (the most
common values being 3, 17 and 65537).
Each private key has its own format. OpenSSL uses the ASN.1-based
format which is described at the end of PKCS#1; that format consists
in about eight big integers, including the public modulus and the
public exponent, so assuming that you could decode both the certificate
and the private key, matching is simply a matter of comparing some
integers for equality. OpenSSL stores such keys with the PEM header
"-----BEGIN RSA PRIVATE KEY-----". However, there are subtleties:
** The PEM format features optional encryption (possibly with a
password-derived key) and OpenSSL is prone to use encryption for
private keys. 'asn1parse' cannot work on ecrypted PEM.
** There are other private key formats out there. One of them is PKCS#8,
which is known to OpenSSL. In that format, the key type is specified
within the (ASN.1-based) structure of the PKCS#8 object, and there is
some nesting. In PEM terms, a PKCS#8 file will use a
"-----BEGIN PRIVATE KEY-----" header (note the absence of the key type).
** PKCS#8 also features optional encryption. Which again defeats
asn1parse.
** Not all algorithms are RSA. Practically, you may also encounter DSA
and ECDSA keys and certificates. The storage format of such private keys
is not well-defined; for ECDSA, one can use the old SEC proposals. An
additional complication is that a DSA or ECDSA private key or public key
may lack the "parameters" (definition of the group in which computations
occur), which weakens the notion of "matching" keys.
For most practical usages, you will be better off using an existing
library which handles those things for you. E.g. OpenSSL.
> There're also some CSRs packed together with the private key in one
> file, but maybe even this is wrong, otherwise I'd use the information
> therein. One more question: Are the CSRs of any use after having
> obtained the certificate?
I do not know what you mean by "CSR".
--Thomas Pornin
William Ahern
> According to Maaartin <graj...@seznam.cz>:
<snip>
> > There're also some CSRs packed together with the private key in one
> > file, but maybe even this is wrong, otherwise I'd use the information
> > therein. One more question: Are the CSRs of any use after having
> > obtained the certificate?
> I do not know what you mean by "CSR".
Certificate Signing Request.
Unless I'm forgetting something, a CSR is just an unsigned X.509
certificate. It's more-or-less useless, and merely a method of passing an
X.509 certificate to the certificate authority for signing. They check the
parameters and then add their signature.
However, what you see may not be a CSR but the signed certificate. It's very
common to keep the private and public key/certificate in the same PEM file.
It's _uncommon_ to keep a CSR with the private key, because the CSR--being
unsigned--probably won't be accepted by, say, a web browser (contrast with a
signed but untrusted certificate).
unruh
> On Jan 11, 2:37?pm, Thomas Pornin <por...@bolet.org> wrote:
>> According to Maaartin ?<grajc...@seznam.cz>:
>>
>> > You wrote, that the RSA digital signature *superficially* looks like
>> > RSA encryption.
>>
>> No, I wrote that the RSA digital signature _algorithm_ superficially
>> looks like a (reverse) RSA encryption _algorithm_.
>
> Sure, my fault, the signature is just a bunch of bits, I meant the
> alg.
That was what he meant as well.
Encryption of message M-> M^e mod N
Signature of "message" M -> M^d mod N
Ie they look identical except that one uses e( the public exponent)
while the other uses d, the private exponent.
In the first case the message M is the actual message
That was what he meant as well.
Encryption of message M-> M^e mod N
Signature of "message" M -> M^d mod N
Ie they look identical except that one uses e( the public exponent)
while the other uses d, the private exponent.
In the first case the message M is the actual message (It must be less
than Min size, and must be bigger than N^(1/e) in size.-- that is what
padding is all about)
In the second case, M is (usually) the hash of the message you are sending, N and d
are your private modulus and exponent. (It could also be any public
piece of information if all you are interested in is signature rather
than verification)
Again it should be larger than N^1/d but this is rarely hard, since d is
usually very large.
Ie, the algorithms look exactly the same, except you use d instead of e.
In other schemes, the inverse algorithm may not be so close to the
forward one. In all cases you want to sign by producing a text C such
that the encryption of C by the public algorithm gives the message M.
Producing C may not be via a procedure that is so close the encryption
algorithm as it is for RSA.
In the second case the message is often a hash of the message.>
>> This is precisely the
>> reason why you talk about "encrypting with the private key" and I point
>> out that this is not the fundamental design of digital signatures; this
>> is merely an artefact of one specific digital siganture algorithm
>> (namely RSA), which does not work for other signature algorithms (e.g.
>> DSA or ECDSA) and actually does not work well with RSA either since it
>> ignores padding issues.
>>
>> > I'd like to learn a bit more about that (not the exact standards, but
>> > the ideas).
>>
>> Actually reading the PKCS#1 standard (which is not that big) would
>> give you some useful information. You may also want to read the
>> chapter 11 of the Handbook of Applied Cryptography, which can be
>> downloaded for free there:
>> ? ?http://www.cacr.math.uwaterloo.ca/hac/
???
Thomas Pornin
> Certificate Signing Request.
Ah. Indeed, it is very unsual to keep them around; they are basically
useless once you have the certificate.
> Unless I'm forgetting something, a CSR is just an unsigned X.509
> certificate.
There are several formats for such requests. Some of them are signed,
either by the key owner himself (as a way to assert that he really
owns the key), or by another entity which uses this to guarantee
to the CA that the information contained in the request is proper.
Either way, this is meant to be transient, and discarded once the
certificate is issued.
--Thomas Pornin