Hi Doug,
You'll have to forgive my ignorance. I'm not sure why I'm having
difficulties answering you. I'll try to walk you through what I
observe.
I'm a Windows guy, so don't hold it against me that I use 'type'
instead of 'cat'. I'm also going to use F(p) rather than F(2^m) since
I believe its easier to follow. Just replace the p with m and f(x).
First, generate the domain parameters:
openssl ecparam -genkey -name secp160k1 -out c:\key.pem
type c:\key.pem
-----BEGIN EC PARAMETERS-----
BgUrgQQACQ==
-----END EC PARAMETERS-----
-----BEGIN EC PRIVATE KEY-----
MFACAQEEFDP8wkW6hxlp8ShA8pHL8LadtNyBoAcGBSuBBAAJoSwDKgAECUThY/ff
d9qioT+AddUV8f76s8ZufLPbZmNYWD3OUK8Ada0Jt6xBiQ==
-----END EC PRIVATE KEY-----
Next, strip the PBE:
openssl ec -in c:\key.pem -out c:\naked.pem
type naked.pem
-----BEGIN EC PRIVATE KEY-----
MFACAQEEFDP8wkW6hxlp8ShA8pHL8LadtNyBoAcGBSuBBAAJoSwDKgAECUThY/ff
d9qioT+AddUV8f76s8ZufLPbZmNYWD3OUK8Ada0Jt6xBiQ==
-----END EC PRIVATE KEY-----
Strip the Base 64 encoding:
openssl base64 -d -in naked.pem -out c:\key.asn1
Next, use Guttmans asn.1 dumper ('openssl asn1parse -in c:\key.asn1'
results in an error):
dumpasn1 c:\key.asn1
0 80: SEQUENCE {
2 1: INTEGER 1
5 20: OCTET STRING
: 33 FC C2 45 BA 87 19 69 F1 28 40 F2 91 CB F0 B6
: 9D B4 DC 81
27 7: [0] {
29 5: OBJECT IDENTIFIER secp160k1 (1 3 132 0 9)
: }
36 44: [1] {
38 42: BIT STRING
: 04 09 44 E1 63 F7 DF 77 DA A2 A1 3F 80 75 D5 15
: F1 FE FA B3 C6 6E 7C B3 DB 66 63 58 58 3D CE 50
: AF 00 75 AD 09 B7 AC 41 89
: }
: }
At this point, the public key is the bit string 04 09 44 E1 ... B7 AC
41 89. It's an ECPoint type (cf: SEC-1 and RFC 5480, Setion 2.2 -
Subject Public Key).
To examine the point encoding, we need to use SEC-1
(http://www.secg.org/download/aid-780/sec1-v2.pdf). Section 2.3.3
covers Elliptic Curve Point to Octet String Conversion, and Section
2.3.4 cover Octet String to Elliptic Curve Point Conversion. Since it
appears the question is related to how is Q encoded, section 2.3.3
applies.
Note that your original example used sect163k1, so you would probably
be interested in Sections 2.3.5 and 2.3.6 which covers encoding and
decoding of Field Elements. Again, I used F(p) rather than F(2^m)
because its easier to visualize for these exercises.
If point compression is being used, the BIT STRING M =Y || X. If point
compression is not being used, then the BIT STRING M = 04 || Y || X.
Since the first octet of the bit string is 0x04, we know that point
compression is *not* being used.
I don't know how to get OpenSSL to give up the remainder of the
secrets, but I do know how to do it in Crypto++ (can anyone help me
out here?). Here's what I got from my Crypto++ program:
C:\Users\Public\Programs\Crypto++\ECParams>ecparams key.asn1
Modulus:
1461501637330902918203684832716283019651637554291
Coefficient A:
0
Coefficient B:
7
Base Point:
X: 338530205676502674729549372677647997389429898939
Y: 842365456698940303598009444920994870805149798382
Subgroup Order:
1461501637330902918203686915170869725397159163571
Cofactor:
1.
Private Exponent:
296795240612937494545889023267033046717591510145
Public Element:
X: 52917001892683237407267355347783044226963125190
Y: 630769944952357370507177294689782720716591612297
C:\Users\Public\Programs\Crypto++\ECParams>
Jeff
On Wed, Oct 21, 2009 at 11:50 AM, Doug Bailey <dbai...@digium.com> wrote:
> ----- "Jeffrey Walton" <noloa...@gmail.com> wrote:
>
>> Hi Doug,
>>
>> > I am trying to figure out where the padding bits
>> > are applied?
>> > ...
>> > The two private keys are described in a different
>> > number of bytes. Since the 2nd generated private
>> > key is shown in 20 bytes i.e. 160 bits, is it assumed
>> > that the MS 3 bits are 0?
>>
>> The public key, also known as the public element, is a point Q(x, y)
>> on the curve of order R. R is the order of the subgroup generator G,
>> where G is a point called the Base Point. The private key, also known
>> as the private exponent, x, is an integer such that Q = xG. Q = xG is
>> similar to RSA's e*d mod n === 1. It's the trap door function - easy
>> to compute one way, hard to compute the other way.
>>
>> All this means is that x, Q_x, and Q_y don't have to be 163 bits.
>> We'd
>> expect them to be slightly less (since this is a finite field), but
>> not too much less since there is a relationship between R, the points
>> on the curve (U), and the cofactor (S). The relationship is U = R *
>> S,
>> and the cofactor (S) is kept small so that subgroup order (R) is
>> large.
>
> So I can understand why the byte descriptions of the keys differ in length.
>
> In your response you indicate that the public key description consists of
> two 163 bit numbers representing a point on the curve (Q_x, Q_y).
>
> Given a display like:
> pub:
> 04:01:9c:db:21:d7:49:17:cd:c4:93:56:13:e4:07:
> c2:af:1b:43:70:a3:b9:03:f1:26:f8:7b:1d:02:69:
> 21:39:cf:d5:28:ee:3b:44:3c:c5:64:7c:aa
>
> How can you tell where the delineation between Q_x and Q_y is? Is Q_y always
> described in 163 bits and Q_x is appended to that? Is there ever any padding
> inserted onto the numbers output by the -text option? What is the magic
> decoder ring to the display provided by the -text option?
>
>
>>
>> A fellow named Marcel Martin wrote a really nice Curve and Parameter
>> generator. According to Marcel, the program correctly counts points
>> on
>> the curve (which can be tricky business). For Marcel's Elliptic Curve
>> Builder (ECB), see http://www.ellipsa.eu/. For a small Curve and
>> Domain Parameter writeup, see
>> http://www.cryptopp.com/wiki/Elliptic_Curve_Builder.
>>
>> Jeff
>>
>> On Tue, Oct 20, 2009 at 3:36 PM, Doug Bailey <dbai...@digium.com>
>> wrote:
>> > I have been trying to generate keys for a ECDSA system that uses a
>> sect163k1 key
>> > pair.
>> >
>> > In generating some of the key sets, I notice that the printed length
>> of the keys
>> > differ when using the -text command option. Since openssl is
>> displaying a 163
>> > bits in a byte-wise display, I am trying to figure out where the
>> padding bits are
>> > applied?
>> >
>> > For example:
>> >
>> > ~$ sudo openssl ecparam -genkey -name sect163k1 -out testkey1.pem
>> > ~$ sudo openssl ec -text -in testkey1.pem
>> > read EC key
>> > Private-Key: (163 bit)
>> > priv:
>> > 00:c4:5c:43:a9:17:57:89:ff:e8:fe:f9:d6:b0:d4:
>> > 52:fc:d4:6b:71:98
>> > pub:
>> > 04:01:9c:db:21:d7:49:17:cd:c4:93:56:13:e4:07:
>> > c2:af:1b:43:70:a3:b9:03:f1:26:f8:7b:1d:02:69:
>> > 21:39:cf:d5:28:ee:3b:44:3c:c5:64:7c:aa
>> > ASN1 OID: sect163k1
>> > writing EC key
>> > -----BEGIN EC PRIVATE KEY-----
>> > MFICAQEEFMRcQ6kXV4n/6P751rDUUvzUa3GYoAcGBSuBBAABoS4DLAAEAZzbIddJ
>> > F83Ek1YT5AfCrxtDcKO5A/Em+HsdAmkhOc/VKO47RDzFZHyq
>> > -----END EC PRIVATE KEY-----
>> >
>> > ~$ sudo openssl ecparam -genkey -name sect163k1 -out testkey2.pem
>> > ~$ sudo openssl ec -text -in testkey2.pem
>> > read EC key
>> > Private-Key: (163 bit)
>> > priv:
>> > 65:06:db:ea:88:38:0d:50:37:9e:3a:92:77:15:ca:
>> > 3c:76:d0:00:12
>> > pub:
>> > 04:07:7d:dd:c1:89:12:75:42:d6:9e:06:79:24:e1:
>> > 8b:4a:49:df:57:ac:e2:04:95:a1:2f:b9:dc:a7:8c:
>> > 5f:c3:18:a5:a7:9c:fc:9d:be:7f:e6:d7:4e
>> > ASN1 OID: sect163k1
>> > writing EC key
>> > -----BEGIN EC PRIVATE KEY-----
>> > MFICAQEEFGUG2+qIOA1QN546kncVyjx20AASoAcGBSuBBAABoS4DLAAEB33dwYkS
>> > dULWngZ5JOGLSknfV6ziBJWhL7ncp4xfwxilp5z8nb5/5tdO
>> > -----END EC PRIVATE KEY-----
>> >
>> > The two private keys are described in a different number of bytes.
>> >
>> > Since the 2nd generated private key is shown in 20 bytes i.e. 160
>> bits, is it
>> > assumed that the MS 3 bits are 0?
>> >
>> > How is the public key partitioned? Where are the padding bits added
>> in this
>> > display?
>> >
>> > Thanks
>> > Doug Bailey
>> >
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
