15
$\begingroup$

I am trying to test my understanding on ECDSA Signature r|s to ASN.1 DER Encoding for NIST P-256. I have r|s and when I convert this into ASN.1 DER in Java. I get following format:

0x30|b1|0x02|b2|r|0x02|b3|s
b1 = Length of remaining data
b2 = Length of r
b3 = Length of s

For example, suppose:

r|s = b2b31575f8536b284410d01217f688be3a9faf4ba0ba3a9093f983e40d630ec722a7a25b01403cff0d00b3b853d230f8e96ff832b15d4ccc75203cb65896a2d5

Breakdown ASN.1 DER signature format 0x30|b1|0x02|b2|r|0x02|b3|s:

3045022100B2B31575F8536B284410D01217F688BE3A9FAF4BA0BA3A9093F983E40D630EC7022022A7A25B01403CFF0D00B3B853D230F8E96FF832B15D4CCC75203CB65896A2D5

My question is - will I be getting this format always or will there be a chance that r and s could be converted and to make length of curve?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
26
$\begingroup$

The ASN.1 DER format is deterministic; i.e. there is only a single sequence of bytes that validly encodes given $r$ and $s$ values. Mind the details, though: the encodings of $r$ and $s$ are minimal-sized signed big-endian. Since $r$ and $s$ are positive values, this means that the top bit of the first byte of each encoding must be zero. In your example, the top byte of $r$ is 0xB2, whose top bit is a 1, so an extra 0x00 byte is added, while the top byte of $s$ is 0x22, whose top bit is a 0, so no extra 0x00 byte here.

However, there are some buggy implementations that produce wrong encodings in some cases (e.g. not including a leading 0x00 byte where necessary, or adding an unnecessary leading 0x00 byte). Thus, ECDSA signature verifiers are often a bit lenient in what they accept.

The ECDSA standards (ANSI X9.62, FIPS 186-4) don't define an ECDSA signature as a sequence of bytes, but as a pair of values $(r,s)$. Encoding of signatures is considered to be out of scope; the protocol that uses ECDSA signatures is responsible for defining which encoding will be used. Different protocols used different conventions. In practice, you will encounter two main encodings for ECDSA signatures:

  • The ASN.1 DER format, described above. It's the one used in X.509 certificates and related protocols.

  • The "raw" format in which $r$ and $s$ are merely concatenated. In that format, $r$ and $s$ must first be represented as sequences of bytes with some convention (usually big-endian), possibly with some extra padding bytes (of value 0x00) so that both $r$ and $s$ encodings have the same size. The "same size" requirement is important because verifiers must know where to split. OpenPGP uses the "raw" format.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Usually I2OSP is used (integer to octet string) to generate the raw signatures. I2OSP is defined in PKCS#1 for RSA, it specifies how to encode an unsigned, big endian integer into a given number of octets. The number of octets itself is the minimum number of octets to encode a specific maximum value, which is the order of the curve: i.e. $N$. Some curves such as the brainpool curves make sure that $N$ is always dividable by 8, making encoding the curve just slightly easier. Because $N$ - in the end - is just the curve size. $\endgroup$
    – Maarten Bodewes ♦
    Commented Mar 22, 2018 at 16:30
  • $\begingroup$ Uh, darn, forgot to say that this is also the way it is defined by the German BSI, e.g. for the ePassport specifications / card verifiable certificates. $\endgroup$
    – Maarten Bodewes ♦
    Commented Mar 22, 2018 at 16:40
  • 3
    $\begingroup$ I've seen the name "IEEE P1363 encoding" used to designate the "raw" format, I guess it is in reference to the IEEE standard because of its section 5.5.3 that standardize the ways one may want to convert between integers and octet strings. $\endgroup$
    – Lery
    Commented Mar 22, 2018 at 22:15
  • $\begingroup$ PGP isn't 'raw' for ECDSA; it uses the same format as original DSA in rfc4880 5.2.2, which is two 'multiprecision integer's, each a length prefix plus variable-length value, but unlike BER/DER there is no tag, the length field is always encoded as 2 bytes and is measured in bits not octets, and the value is unsigned thus curves with 'exact-bytes' n like P-256 don't have almost half their r,s values expand by an octet to indicate positive. $\endgroup$
    – dave_thompson_085
    Commented Oct 14, 2019 at 19:13
  • $\begingroup$ Hi Thomas. Could you _please_ provide any source documentation for the actual concept-to-byte encoding of ECDSA signatures? I'm working with Digital Certificates, going through RFC5280, 3279, 4055 and 4491, together with ITU-T's documents X.509, 680. 690. and 894. I cannot find the exact place where is stated that the DER encoding for ECDSA Signature R|S is 0x30|b1|0x02|b2|r|0x02|b3|s. I can see it in the certificates I have, but that's empirical observation, not law. $\endgroup$
    – Ricardo
    Commented Jul 24 at 8:46
0
$\begingroup$

I stumbled upon this thread while searching for how to convert ASN1 (== DER) to R|S (== P1363) encoding in Java. I am not qualified to answer on the theory but I can provide a software engineer perspective.

I found that the mentioned conversion is built-in the reputable crypto library BouncyCastle:

import org.bouncycastle.asn1.ASN1Integer;
import org.bouncycastle.asn1.ASN1Sequence;
import org.bouncycastle.crypto.signers.PlainDSAEncoding;
import org.bouncycastle.math.ec.custom.sec.SecP256R1Curve;
    
// the asn1EncodedSignature param is typically generated by
// Signature signature = Signature.getInstance("SHA256withECDSA");
private byte[] toP1363(byte[] asn1EncodedSignature) {
    ASN1Sequence seq = ASN1Sequence.getInstance(asn1EncodedSignature);
    BigInteger r = ((ASN1Integer) seq.getObjectAt(0)).getValue();
    BigInteger s = ((ASN1Integer) seq.getObjectAt(1)).getValue();
    BigInteger n = new SecP256R1Curve().getOrder();
    return PlainDSAEncoding.INSTANCE.encode(n, r, s);
}

(Note that it works on Android, and you don't need to add BouncyCastle as a global Provider or anything. You can just use the classes as shown above.)

In my opinion, you can get the answer to your original question by checking the implementation of the PlainDSAEncoding.INSTANCE.encode(n, r, s) function.

As BouncyCastle is a reputable implementation, you can get a confirmation or a hint of the answer as to how the theory works by studying this library.

This would complement @thomas-pornin 's answer that explains the theory.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm sure programming questions are off-topic unless it pertains to technical details such as side-channel resistance, efficiency optimizations, edge-case testing, etc. But I'm not sure if a programming answer is on-topic, or generally desired. I'll refrain from down-voting, and let others suggest improvements. $\endgroup$
    – DannyNiu
    Commented May 31 at 5:31
  • $\begingroup$ I think implementations are good for illustrating how it's done. Formal specifications should be consulted to understand why the implementation does that. $\endgroup$
    – DannyNiu
    Commented May 31 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.