Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I'm trying to set up ECDH-P521 in Java and in Javascript. When using Java to generate a random private key. The generated key is either 1106 or 1107 bytes long (numbers only): This is an example:

15820270820141785816508777546203531689397946918613745468462603511458850423735031236282445164790395076155411229705956992877455649694419951259815498849641848956793392569045506106338396430345514875364588149215420982410615090262386011249279377007189537198544102932831235151647334621266741883332267482199057654063069729082799737905050086941552356414365792094508247832797412165636806665188024116805607359318120544594780610477605975008223644760704394837637072221003537804667178513144692473717207693650306256166790681513961163796420375992922218031413538508572794041070701747098140868685408978389831865028565290722501932667707996915573487058648431621518149227993785806909802170460371436145333083760566303169691568046425839430068891781807170021374723765506150397187910341832953219584851438649194730918454685957040826761543322936147842766850606220910894957631257378631127669363364813311193883079583031746841655876182942885709199770097746824286605559149397118191358456587872885030782034454860401745346003765896386571368923655586179370790207197187566088431280170974634208293227790322797039340473922398828338464549441688137751710973749367927461997861185608651814994134154175060908514761793814754889974559846767817507960397160298087058383585313615198273143302981598184601225727030755877428380894071552155791294552064517459671978866676985727202720541805730675850984248266052030444206599263294760860634934913468045359182435960368023318502332954491611933601349311509182510883866794137413930035320456347995927194339240033629065690304534478580225447049666892255367229258883280219823032071097118734610749845413093897284837952891370996283453237084081419580203494949306977231679602890531081600905532087450668616559047874677601826905373800315088818529279872840090269552749150499535549921276713988246375429155061571670643314130773631866437904666788666488783335838392536121530145864364636174583014342481891364339458238750191299573339587509518138240117546711257195751941347080124250704736898032156513478184149894183706958255671419069885058556235701045131590204750075341914718798918790670499508931088713264611694838012622908103442925003472479584051029440528491924917754964517471115461567673156429598420669745734261020740090009202463131488319174995464578466128802667941283019307103002277640328285072993038328108784113852788529272864662666087074589129657267528285391202557341166349466161725657944282881739800241080797191142310062568485973723648443648077850944186220678327142829394151600201142833375152688586804001175535136063825907502274037130619843154405563351802134623888647709108981151169641100689979329480496700088007597285257702689829924317514159614861849857081022624034381280564846793128203

When generating a random number with a modified implementation of JSBN, the private key length is only 158 bytes long:

5535897720806662122039126663930000984487250150132382355111119995338835252624008129420646982091044426711642890391134454309659227204735914527771461168248154791

Now my question is: How long should the private key when using ECDH-P521R1?

share|improve this question
1  
There is no one true format for keys. Some formats include envelopes, a description of the curve parameters... But no idea how you ended up with just a number. Those extended private keys are a sequence of bytes, not a decimal number. –  CodesInChaos Apr 21 '13 at 11:12
    
A simple scalar (private key without any other information) should have about 157 decimal digits. –  CodesInChaos Apr 21 '13 at 11:14
    
Yes, I'm just talking about the scalar. Do you have any idea why the generated scalar using bouncy castle is as huge as above? –  JayBeOh Apr 21 '13 at 12:59
    
Please post some code. I guess that what BouncyCastle produced isn't just the scalar. –  CodesInChaos Apr 21 '13 at 13:01
    
You're right. I didn't use the scalar but made the mistake to print out the encoded version of the private key object which of course was more. Thank you so much for your help! –  JayBeOh Apr 21 '13 at 13:17

1 Answer 1

up vote 2 down vote accepted

Let's take your big integer, and convert it to binary, big-endian unsigned encoding (i.e. in Java, I call new BigInteger("...the big numer...").toByteArray() and I write that in a file, removing the leading 0x00 byte which toByteArray() added because it enforces signed encoding, and thus insists on a leading bit of value 0 if the value is positive). I get, indeed, a sequence of 1107 bytes which begins like this:

$ hd blob
00000000  30 82 04 4f 02 01 00 30  82 01 b9 06 07 2a 86 48  |0..O...0.....*.H|
00000010  ce 3d 02 01 30 82 01 ac  02 01 01 30 4d 06 07 2a  |.=..0......0M..*|
00000020  86 48 ce 3d 01 01 02 42  01 ff ff ff ff ff ff ff  |.H.=...B........|
00000030  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
*
00000060  ff ff ff ff ff ff ff ff  ff ff 30 81 88 04 42 01  |..........0...B.|
00000070  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
*
000000b0  fc 04 42 00 51 95 3e b9  61 8e 1c 9a 1f 92 9a 21  |..B.Q.>.a......!|
000000c0  a0 b6 85 40 ee a2 da 72  5b 99 b3 15 f3 b8 b4 89  |...@...r[.......|
000000d0  91 8e f1 09 e1 56 19 39  51 ec 7e 93 7b 16 52 c0  |.....V.9Q.~.{.R.|
000000e0  bd 3b b1 bf 07 35 73 df  88 3d 2c 34 f1 ef 45 1f  |.;...5s..=,4..E.|
000000f0  d4 6b 50 3f 00 04 81 85  04 00 c6 85 8e 06 b7 04  |.kP?............|
00000100  04 e9 cd 9e 3e cb 66 23  95 b4 42 9c 64 81 39 05  |....>.f#..B.d.9.|

The trained eye immediately recognizes the first bytes (30 82 04 4f 02 01 00...) as an encoded ASN.1 DER object (a SEQUENCE of length 0x44F, whose first element is an INTEGER of value 0). So that's not an integer at all ! Let's put it through OpenSSL:

$ openssl asn1parse -i -inform DER -in blob
    0:d=0  hl=4 l=1103 cons: SEQUENCE          
    4:d=1  hl=2 l=   1 prim:  INTEGER           :00
    7:d=1  hl=4 l= 441 cons:  SEQUENCE          
   11:d=2  hl=2 l=   7 prim:   OBJECT            :id-ecPublicKey
   20:d=2  hl=4 l= 428 cons:   SEQUENCE          
   24:d=3  hl=2 l=   1 prim:    INTEGER           :01
   27:d=3  hl=2 l=  77 cons:    SEQUENCE          
   29:d=4  hl=2 l=   7 prim:     OBJECT            :prime-field
   38:d=4  hl=2 l=  66 prim:     INTEGER           :01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
  106:d=3  hl=3 l= 136 cons:    SEQUENCE          
  109:d=4  hl=2 l=  66 prim:     OCTET STRING      [HEX DUMP]:01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC
  177:d=4  hl=2 l=  66 prim:     OCTET STRING      [HEX DUMP]:0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00
  245:d=3  hl=3 l= 133 prim:    OCTET STRING      [HEX DUMP]:0400C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650
  381:d=3  hl=2 l=  66 prim:    INTEGER           :01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409
  449:d=3  hl=2 l=   1 prim:    INTEGER           :01
  452:d=1  hl=4 l= 651 prim:  OCTET STRING      [HEX DUMP]:30820287020101044201945<...>

Now this looks a lot like an elliptic curve public/private key pair, tagged as such (the id-ecPublicKey object identifier). This means PKCS#8. We notice the elements describing the curve, beginning with the base field size (which is p = 2521-1), then the a and b parameters for the curve equation Y2 = X3 + aX + b (a = p - 3, which gives a slight performance bonus over other values), then the encoding of the conventional base point G (the "generator"), which is a sequence of bytes beginning with 0x04 (uncompressed encoding: the leading byte is followed by the big-endian encodings of the X and Y coordinates of G). The INTEGER immediately afterwards is the curve order n. These parameters match the definition of the P-521 curve (see FIPS 186-3, page 90).

The final OCTET STRING contains the private key. Let's use OpenSSL again to convert this PKCS#8 object into the internal format which OpenSSL prefers:

$ openssl pkcs8 -inform DER -in blob -nocrypt -out key.pem

(the -nocrypt flag tells to expect a key which is not password-protected). The resulting key.pem file can be then inspected:

$ openssl ec -in key.pem -text -noout
read EC key
Private-Key: (521 bit)
priv:
    01:94:56:2e:83:db:2b:fc:26:ef:19:6a:7a:03:cd:
    68:63:2e:cd:2c:fd:43:45:ac:f7:e2:be:56:65:97:
    c7:72:93:97:3c:92:d7:96:55:af:98:f4:24:75:c9:
    2d:5b:15:4c:0a:cd:ef:30:91:47:97:52:5b:2d:c7:
    20:3e:f7:90:ec:36
pub: 
    04:00:0b:05:86:60:82:b2:09:3f:2a:cc:1c:81:c6:
    14:3c:44:25:b3:02:09:de:03:0a:47:e3:1c:02:5c:
    7a:38:7f:33:8f:04:39:b4:5a:68:69:0a:e0:2c:c5:
    3e:08:13:0c:53:bd:02:a3:02:cf:29:4f:9e:93:44:
    a1:dd:39:15:00:e3:6c:01:1f:fb:38:27:37:23:33:
    60:d6:69:4c:ea:aa:6e:0b:35:6e:40:66:02:0b:42:
    6d:d6:bc:39:f6:0e:b9:36:ce:9b:2e:bf:00:40:6b:
    16:b1:18:1e:ee:c0:25:fd:c4:b7:2d:5c:5f:40:63:
    e2:b7:e1:be:d8:2c:e7:fe:82:2e:a4:f9:0b
Field Type: prime-field
Prime:
    01:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff<...>

so here are your private and public keys, followed by (again) the curve definition parameters.

An elliptic curve private key is an integer in the 1..n-1 range, where n is the order of the conventional base point. Normally, n is a prime integer (the curve has been selected for that). In the case of the standard NIST curves on prime fields, the base point generates whole curve, which has prime order, and n is close to p (indeed, |p+1-n| <= 2*sqrt(p) by Hasse's theorem). So the private key will be, in the case of P-521, an integer of at most 521 bits, potentially at bit smaller (but very rarely much smaller).

share|improve this answer
    
Thanks a lot for your detailed answer. My problem was already solved by CodesInChaos. Yet it's great to get such thorough insight into the way the key file is encoded! –  JayBeOh Apr 21 '13 at 15:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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