ASN.1: DER for Digital Signatures - Reading (r,s)[ECDSA Home][Home]
We need ways to distribute our public keys, private keys and digital certificates in a portable format. One of the most common forms is Distinguished Encoding Rules (DER) encoding of ASN.1. Overall it is truly binary representation of the encoded data. For a signature we often have the form of (\(r,s\)), a public key (\(pk\)) and a message (\(M\)). To check the signature we take the message (\(M\)), \(r\), \(s\) and \(pk\) and valid the signature. A typical format for the representation of the signature is in a DER format. In this case we will read in a DER hex string, and then determine the values of \(r\) amd \(s\).
|
Notes:
The sample run of a program which generates ECDSA signatures is [here] and gives:
Name: secp256k1, y^2=x^3+a*x+b (mod p) Type: weierstrass, Size: 256, a=0, b=7, G=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 , 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), field=115792089237316195423570985008687907853269984665640564039457584007908834671663, order=115792089237316195423570985008687907852837564279074904382605163141518161494337 Message: b'hello' Private key: 0xeec8fb5d3091e9fc2bf7c287f2f97cbf1100eeeb27fc8aaa650b314b71c7252 Public key: (0x6f7fd766b4a537aac6c6e13e8cf798181cd86a9a49c3e37c2d96331f2dfe3186,0xef72f96fc396682f1ac0206e3434e2b93018d0d2d8ca07d035b735fd1305040f ---- Signed with ECDSA (random k) ---- Signature verification: True Signature: 3046022100e4e87c417196c6e5cd63f93e94929ccda6d04fc0a7446922baf3070e854ec4f4022100a1ecd098008329de9bc93fb2ded6aaceecc921f7183d6b3cfc673b3ef8af219e (r,s) = (103538095576919172103954191057308823615108582223735892815805653712768179553524,73240784190399570630100417340823520804390333537010858492592612757774793646494) ---- Signed with RFC 6979 ---- Signature verification: True Signature: 304502203e2e630c5a44fbfbc597d2b0144b3d71085f04cf4d6f2c50307a9ba96907ff91022100b449b366639e08e9dd915a57940f7bc715262a7ea790000cd2cbc335a9aed837 (r,s) = (28125355183056498779420782786949985438444292178097534907969548818818733178769,81546530753718336152244373242235155657915399927554525755850161853056471193655) ---- Signed with random k ---- Signature verification: True Signature: 304402200310c23c364d143fabe898246def08d2eb4d5400e84f0c3851b2b57138b6a4ac0220502dd47ad66d656891c65a6195473ab6e32ff92db1a2f12126d062ce3e4d6ffd (r,s) = (1386548660892902964070456978751099402817469755802984612851865828870271181996,36266002486497184729991851879345544438395730148830622533520010158883361091581) ---- Signed with k=9 ---- Signature verification: True Signature: 3046022100acd484e2f0c7f65309ad178a9f559abde09796974c57e714c35f110dfc27ccbe022100e6ee8efc7599012f5ac0933ab2686fbace9e4ee44c0ca49368249a3e663d5108 (r,s) = (78173298682877769088723994436027545680738210601369041078747105985693655485630,104453451629840809757050217047625721329522324522833116900506572186093828788488)
Theory
the most common digital signature is ECDSA (Elliptic Curve Digital Signature Algorithm). It takes a message (M), a private key (sk) and a random value (k) and produces a digital signature of r and s. These are just two integer values. To check the signature, we take the message (M), the associated public key (pk), r and s, and perform a validation test, and if it passes, the message has a correct signature. But what does the signature actually look like? Basically, for ECSAA, it us just two numbers \(r\) and \(s\) that we add to the message. In many cases, it takes the form of the DER format, and which uses ASN.1 to define abstract types and values. Basically, it takes the two integer values (r and s) and encapsulates them into a more structured format. This format can be read by any computer system. One of the most basic types is SEQUENCE and is an ordered collection of one or more types. In DER, SEQUENCE is identified with a tag of “30”, and followed by a byte value for the length of the object defined. The other common types are OBJECT IDENTIFIER (and which has a tag of “06”), a BIT STRING (and which has a tag of “03”) and INTEGER (and which has a tag of “02”). In the case of a signature, we just use the INTEGER definition for the values.
So here is an example DER signature from NIST P-192 (and which uses 192-bit integer values):
3035021900935f599bbdb30fc81a8b9de2f82311c6fa704838b53f9d7a0218267e3abb5bc3a44b0e368442ed3699b23ce87a28bc32cc53
We first encounter the SEQUENCE (“30”), and then the next byte defines the length of the values which come next. In this case, “0x35” is 53 bytes. If you count the number of bytes after 35, you will find there are 53 bytes (or 106 hex characters):
30 35 02 19 00935f599bbdb30fc81a8b9de2f82311c6fa704838b53f9d7a 02 18 267e3abb5bc3a44b0e368442ed3699b23ce87a28bc32cc53
Next, we have a “02” tag, and then a “19”, and where the “19” value identifies 25 bytes (or 50 hex characters). We can then read r as the next 50 hex characters. Next, we have another “02” tag, and then a “19”, and where the “18” value identifies 24 bytes (or 48 hex characters). We can then read r as the next 48 hex characters. So, can we check the size of the integers produced? Well, we just multiply the number of bytes by 8, and we will determine this. Thus r is 25 bytes long, but the first byte is a zero, and s is 24 bytes, so the length of the values of r and s are 24 bytes long. This gives us 192 bits and which fits with the curve (P-192).
Now we will try a signature from a common curve (secp256k1) and which uses 256-bit values:
3046022100e4e87c417196c6e5cd63f93e94929ccda6d04fc0a7446922baf3070e854ec4f4022100a1ecd098008329de9bc93fb2ded6aaceecc921f7183d6b3cfc673b3ef8af219e
Again we can parse, and notice that the integer values are longer this time:
30 46 02 21 00 e4e87c417196c6e5cd63f93e94929ccda6d04fc0a7446922baf3070e854ec4f4 02 21 00a1ecd098008329de9bc93fb2ded6aaceecc921f7183d6b3cfc673b3ef8af219e
In fact, we have 0x21 bytes for the values of r and s, but the first byte is a zero, so we actually have 0x20 bytes, and which is 32 bytes. This will give us 256 bits, and which fits with the curve.
Code
The code used is:
import asn1 import binascii from pem import class_id_to_string,tag_id_to_string,value_to_string import sys import base64 der='3046022100e4e87c417196c6e5cd63f93e94929ccda6d04fc0a7446922baf3070e854ec4f4022100a1ecd098008329de9bc93fb2ded6aaceecc921f7183d6b3cfc673b3ef8af219e' # See https://asecuritysite.com/encryption/sigs2 indent=0 if (len(sys.argv)>1): der=str(sys.argv[1]) def make_pem(st): bff="-----BEGIN PUBLIC KEY-----\n" bff=bff+base64.b64encode(st).decode()+"\n" bff=bff+"-----END PUBLIC KEY-----\n" print (bff) def read_pem(data): """Read PEM formatted input.""" data = data.replace("\n","") data = data.replace("","") data = data.replace("-----BEGIN PUBLIC KEY-----","") data = data.replace("-----END PUBLIC KEY-----","") return binascii.hexlify(base64.b64decode(data)) def show_asn1(string, indent=0): while not string.eof(): tag = string.peek() if tag.typ == asn1.Types.Primitive: tag, value = string.read() print(' ' * indent,end='') print('[{}] {}: {}'.format(class_id_to_string(tag.cls), tag_id_to_string(tag.nr),value_to_string(tag.nr, value))) if (tag.nr==4): private_key=binascii.hexlify(value) print(' ' * indent,end='') print("Private key: ",private_key.decode()) if (tag.nr==3): res=binascii.hexlify(value).decode() length=len(res) if (res.__contains__('10001')): # RSA rtn=res[1:].find("02") print (res[rtn+3:rtn+5]) byte = int(res[rtn+3:rtn+5],16)-1 rtn=res[1:].find("00") N=res[rtn+3:rtn+3+(byte)*2] e=res[length-5:] print(' ' * indent,end='') print(f"RSA Modulus ({len(N)*4}) bits: {N}") print(f"RSA e: {e}") else : # ECC public_key_x=res[4:length//2] public_key_y=res[length//2:] print(' ' * indent,end='') print(f"Public key ({public_key_x}, {public_key_y})") elif tag.typ == asn1.Types.Constructed: print(' ' * indent,end='') print('[{}] {}'.format(class_id_to_string(tag.cls), tag_id_to_string(tag.nr))) string.enter() show_asn1(string, indent + 2) string.leave() Print=True if (len(der)>500): Print=False if (der.__contains__("BEGIN")): print("Found PEM") der=read_pem(der) if (Print): print (f"PEM: {der}\n") st=binascii.unhexlify(der) decoder = asn1.Decoder() decoder.start(st) show_asn1(decoder) print() if (Print): make_pem(st)
and pem.py:
# based on code at https://github.com/andrivet/python-asn1 import base64 import asn1 import binascii def read_pem(data): """Read PEM formatted input.""" data = data.replace("-----BEGIN PUBLIC KEY-----","") data = data.replace("-----END PUBLIC KEY-----","") data = data.replace("\n","") data = data.replace("","") return binascii.hexlify(base64.b64decode(data)) tag_id_to_string_map = { asn1.Numbers.Boolean: "BOOLEAN", asn1.Numbers.Integer: "INTEGER (02)", asn1.Numbers.BitString: "BIT STRING", asn1.Numbers.OctetString: "OCTET STRING", asn1.Numbers.Null: "NULL", asn1.Numbers.ObjectIdentifier: "OBJECT (06)", asn1.Numbers.PrintableString: "PRINTABLESTRING", asn1.Numbers.IA5String: "IA5STRING", asn1.Numbers.UTCTime: "UTCTIME", asn1.Numbers.Enumerated: "ENUMERATED", asn1.Numbers.Sequence: "SEQUENCE (30)", asn1.Numbers.Set: "SET" } class_id_to_string_map = { asn1.Classes.Universal: "U", asn1.Classes.Application: "A", asn1.Classes.Context: "C", asn1.Classes.Private: "P" } object_id_to_string_map = { "1.2.840.113549.1.1.1": "RSA Encryption", "1.2.840.10040.4.1": "DSA", "1.2.840.10046.2.1": "Diffie-Hellman", "1.2.840.10045.2.1": "ECC", "1.2.840.10045.3.1.1": "secp192r1", "1.3.132.0.33": "secp224r1", "1.2.840.10045.3.1.7": "secp256r1", "1.3.132.0.34": "secp384r1", "1.3.132.0.35": "secp521r1", "1.3.36.3.3.2.8.1.1.1": "brainpoolP160r1", "1.3.36.3.3.2.8.1.1.3": "brainpoolP192r1", "1.3.36.3.3.2.8.1.1.5": "brainpoolP224r1", "1.3.36.3.3.2.8.1.1.7": "brainpoolP256r1", "1.3.36.3.3.2.8.1.1.9": "brainpoolP320r1", "1.3.36.3.3.2.8.1.1.11": "brainpoolP384r1", "1.3.101.112": "Ed25519", "1.3.101.113": "Ed448", "1.3.6.1.5.5.7.1.1": "authorityInfoAccess", "2.5.4.3": "commonName", "2.5.4.4": "surname", "2.5.4.5": "serialNumber", "2.5.4.6": "countryName", "2.5.4.7": "localityName", "2.5.4.8": "stateOrProvinceName", "2.5.4.9": "streetAddress", "2.5.4.10": "organizationName", "2.5.4.11": "organizationalUnitName", "2.5.4.12": "title", "2.5.4.13": "description", "2.5.4.42": "givenName", "1.2.840.113549.1.9.1": "emailAddress", "2.5.29.14": "X509v3 Subject Key Identifier", "2.5.29.15": "X509v3 Key Usage", "2.5.29.16": "X509v3 Private Key Usage Period", "2.5.29.17": "X509v3 Subject Alternative Name", "2.5.29.18": "X509v3 Issuer Alternative Name", "2.5.29.19": "X509v3 Basic Constraints", "2.5.29.30": "X509v3 Name Constraints", "2.5.29.31": "X509v3 CRL Distribution Points", "2.5.29.32": "X509v3 Certificate Policies Extension", "2.5.29.33": "X509v3 Policy Mappings", "2.5.29.35": "X509v3 Authority Key Identifier", "2.5.29.36": "X509v3 Policy Constraints", "2.5.29.37": "X509v3 Extended Key Usage" } def tag_id_to_string(identifier): """Return a string representation of a ASN.1 id.""" if identifier in tag_id_to_string_map: return tag_id_to_string_map[identifier] return '{:#02x}'.format(identifier) def class_id_to_string(identifier): """Return a string representation of an ASN.1 class.""" if identifier in class_id_to_string_map: return class_id_to_string_map[identifier] raise ValueError('Illegal class: {:#02x}'.format(identifier)) def object_identifier_to_string(identifier): if identifier in object_id_to_string_map: return object_id_to_string_map[identifier] return identifier def value_to_string(tag_number, value): if tag_number == asn1.Numbers.ObjectIdentifier: return object_identifier_to_string(value) elif isinstance(value, bytes): return '0x' + str(binascii.hexlify(value).upper()) elif isinstance(value, str): return value else: return repr(value)
For Example 1, we have two values of \(r\) and \(s\):
PEM: 3046022100e4e87c417196c6e5cd63f93e94929ccda6d04fc0a7446922baf3070e854ec4f4022100a1ecd098008329de9bc93fb2ded6aaceecc921f7183d6b3cfc673b3ef8af219e [U] SEQUENCE (30) [U] INTEGER (02): 103538095576919172103954191057308823615108582223735892815805653712768179553524 [U] INTEGER (02): 73240784190399570630100417340823520804390333537010858492592612757774793646494 -----BEGIN PUBLIC KEY----- MEYCIQDk6HxBcZbG5c1j+T6UkpzNptBPwKdEaSK68wcOhU7E9AIhAKHs0JgAgynem8k/st7Wqs7sySH3GD1rPPxnOz74ryGe -----END PUBLIC KEY-----