0

Can I please get some help in understanding the representation/connection between the issuer key structure, such as the one here:

{
    "kty": "EC",
    "d": "6RDoFJrbnJ9WG0Y1CVXN0EnxbuQIgRMQfzFVKogbO6c",
    "use": "sig",
    "crv": "P-256",
    "x": "eIA4ZrdR7IOzYRqLER9_JIkfQCAeo1QI3VCEB7KaIow",
    "y": "WKPa365UL5KRw6OJJsZ3R_qFGQXCHg6eJe5Nzw526uQ",
    "alg": "ES256"
}

And the actual elliptic curve Curve25519 which is supposed to satisfy the equation: y^2 = x^3+486662x^2+x

Are the x and y above related to the x and y which I see in this equation? If so, in what way exactly? And how is the private key "d" connected to all this? How does the x+y on the curve related to the "d"? And the kid (key-id)? which is not even shown above. Why are they all 43 bytes long?

And what format are above represented in?

Also: I notice the QR code is 1776 bytes long:

shc:/56762909510950603511292437..............656  

Which gets translated to a "numeric" code of length 888:

eyJ7aXAiOiKERUYiLREhbGciOiJFUzI1Ni.......xpW  

(How does one convert it as such?)

which in turn gets to:

{"zip":"DEF","alg":"ES256","kid":"Nlewb7pUrU_f0tghYKc88uXM9U8en1gBu88rlufPUj7"}

And private key in X.509 format looks like this:

-----BEGIN PRIVATE KEY-----
MEECAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQcEJzAlAgEBBCDpEOgUmtucn1YbRjUJ
Vc3QSfFu5AiBExB/MVUqiBs7pw==
-----END PRIVATE KEY-----

Why 92 bytes?

They are all related....just trying to understand how they are converted to one another and particularly to the equation of the curve?

Thanks Steve

2 Answers 2

2

Elliptic Curve Cryptography is a complicated subject, and explaining how it works is far beyond the scope of an answer on this board. But, I'll refer you to Elliptic Curve Cryptography: a gentle introduction by Andrea Corbellini, which I found to by an excellent source when I was trying to understand how Elliptic Curve Cryptography works, and I think this will point you in the right direction towards answers to most of your questions.

In the key that you posted, d is the private key, represented in base64 format: 6RDoFJrbnJ9WG0Y1CVXN0EnxbuQIgRMQfzFVKogbO6c, and "crv": "P-256" denotes that this is a P256 curve. The public key is derived from the private key. To get the public key x and y values, the private key must be multiplied by a 'generator point' using the P256 elliptic curve. We can find the generator point and the parameters for the P256 elliptic curve here: https://safecurves.cr.yp.to/equation.html

The author of the article that I referenced above has a python script that does elliptic curve math here: https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdhe.py I found this script to be useful in understanding how the math works, and playing with the math.

To see how the public key x and y values in the key that you provided are derived from the private key, we can make a few modifications to Corbellini's script, to use the parameters for the P256 curve, and 6RDoFJrbnJ9WG0Y1CVXN0EnxbuQIgRMQfzFVKogbO6c as the private key, like so:

import collections
import base64

EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')

#from https://safecurves.cr.yp.to/field.html:
curve = EllipticCurve(
    'P-256',
    # Field characteristic.
    p=0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff,
    # Curve coefficients.
    a=-3,
    b=41058363725152142129326129780047268409114441015993725554835256314039467401291,
    # Base point.
    g=(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
       0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5),
    # Subgroup order.
    n=0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551,
    # Subgroup cofactor.
    h=1,

)


# Modular arithmetic ##########################################################

def inverse_mod(k, p):
    """Returns the inverse of k modulo p.

    This function returns the only integer x such that (x * k) % p == 1.

    k must be non-zero and p must be a prime.
    """
    if k == 0:
    raise ZeroDivisionError('division by zero')

    if k < 0:
    # k ** -1 = p - (-k) ** -1  (mod p)
    return p - inverse_mod(-k, p)

    # Extended Euclidean algorithm.
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = p, k

    while r != 0:
    quotient = old_r // r
    old_r, r = r, old_r - quotient * r
    old_s, s = s, old_s - quotient * s
    old_t, t = t, old_t - quotient * t

    gcd, x, y = old_r, old_s, old_t

    assert gcd == 1
    assert (k * x) % p == 1

    return x % p


# Functions that work on curve points #########################################

def is_on_curve(point):
    """Returns True if the given point lies on the elliptic curve."""
    if point is None:
    # None represents the point at infinity.
    return True

    x, y = point

    return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0


def point_neg(point):
    """Returns -point."""
    assert is_on_curve(point)

    if point is None:
    # -0 = 0
    return None

    x, y = point
    result = (x, -y % curve.p)

    assert is_on_curve(result)

    return result


def point_add(point1, point2):
    """Returns the result of point1 + point2 according to the group law."""
    assert is_on_curve(point1)
    assert is_on_curve(point2)

    if point1 is None:
    # 0 + point2 = point2
    return point2
    if point2 is None:
    # point1 + 0 = point1
    return point1

    x1, y1 = point1
    x2, y2 = point2

    if x1 == x2 and y1 != y2:
    # point1 + (-point1) = 0
    return None

    if x1 == x2:
    # This is the case point1 == point2.
    m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
    else:
    # This is the case point1 != point2.
    m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)

    x3 = m * m - x1 - x2
    y3 = y1 + m * (x3 - x1)
    result = (x3 % curve.p,
          -y3 % curve.p)

    assert is_on_curve(result)

    return result


def scalar_mult(k, point):
    """Returns k * point computed using the double and point_add algorithm."""
    assert is_on_curve(point)

    if k % curve.n == 0 or point is None:
    return None

    if k < 0:
    # k * point = -k * (-point)
    return scalar_mult(-k, point_neg(point))

    result = None
    addend = point

    while k:
    if k & 1:
        # Add.
        result = point_add(result, addend)

    # Double.
    addend = point_add(addend, addend)

    k >>= 1

    assert is_on_curve(result)

    return result


private_key_hex='6RDoFJrbnJ9WG0Y1CVXN0EnxbuQIgRMQfzFVKogbO6c='
private_key=int.from_bytes(base64.b64decode(private_key_hex), 'big')

public_key = scalar_mult(private_key, curve.g)
(public_key_x, public_key_y)=public_key

print("private key:", base64.b64encode(private_key.to_bytes(32,'big')))
print("public key x:", base64.b64encode(public_key_x.to_bytes(32,'big')))
print("public key y:", base64.b64encode(public_key_y.to_bytes(32,'big')))

Running this script produces:

private key: b'6RDoFJrbnJ9WG0Y1CVXN0EnxbuQIgRMQfzFVKogbO6c='
public key x: b'eIA4ZrdR7IOzYRqLER9/JIkfQCAeo1QI3VCEB7KaIow='
public key y: b'WKPa365UL5KRw6OJJsZ3R/qFGQXCHg6eJe5Nzw526uQ='

As you can see, the public key x and y values produced by the script match those in the key that you posted. I hope this helps.

8
  • This is excellent, thanks @mti2935! a couple of things: 1)If I want to use the equation y^2 = x^3+486662x^2+x, then I assume this code can be modified as such? 2) So you used the private key I gave to generate both x and y? (funny, I had randomized it, still worked?) 3) If I only had the x and y, is there a code to go through all combos (given the above equation) to be able to guess the private key? Would the given equation not reduce the number of possibilities?
    – Steve237
    Nov 15, 2021 at 3:48
  • Also shouldn't the x and y values satisfy that math equation outright? I mean the given ones are in base64, they are not even a pair of points. How are they represented as a pair of points like x(p1,p2) and y(p3,p4) in order for us to find the 3rd point of cross on that curve, the drop it vertically down to hit the curve again in order to arrive at "x+y" ? I just don't see the graphical representation for the above base64 characters.
    – Steve237
    Nov 15, 2021 at 3:57
  • @Steve, no problem. 1) Those are the parameters for the Curve25519 EC curve. You can find those and the generator point at safecurves.cr.yp.to/equation.html. To use Curve25519 instead of P256, just modify the values in the script (near the top). 2) Usually the private key is generated randomly (it's a 256-bit integer), then the public key (which consists of an x and y value) is derived from the private key. I just used the private key that you posted (instead of a random one) to show how the public key that you posted is derived from that private key.
    – mti2935
    Nov 15, 2021 at 15:00
  • 3) NO!!!* That's the whole point of asymmetric cryptography. The public key is easy to derive from the private key. But, it is very hard (practically impossible) to do the opposite and derive the private key from the public key. If this were possible, then other other people could decrypt messages that were encrypted with your public key, or impersonate you by making digital signatures with your private key, or spend all your bitcoins.
    – mti2935
    Nov 15, 2021 at 15:08
  • WRT Also shouldn't the x and y values satisfy that math equation outright? : yes, but you have to use EC math. See security.stackexchange.com/questions/233099/… for a similar question. I modified the program to print private_key, public_key_x, public_key_y in base64 format so that it would match what you posted. But, these are just integers, you can print them as is to see them in decimal format.
    – mti2935
    Nov 15, 2021 at 15:15
1

While mti gave you a good explanation of the substance, to fill some of the superfical gaps:

The representation

{
    "kty": "EC",
    "d": "6RDoFJrbnJ9WG0Y1CVXN0EnxbuQIgRMQfzFVKogbO6c",
    "use": "sig",
    "crv": "P-256",
    "x": "eIA4ZrdR7IOzYRqLER9_JIkfQCAeo1QI3VCEB7KaIow",
    "y": "WKPa365UL5KRw6OJJsZ3R_qFGQXCHg6eJe5Nzw526uQ",
    "alg": "ES256"
}

is JWK (JSON Web Key) generally defined in rfc7517 based on JSON (JavaScript Object Notation) defined in rfc7159 which in turn is based on JavaScript (now evolved into ECMAScript). Particular key types are defined in rfc7518 including X9/NIST/Weierstrass-form EC in 6.2. The keys for the Montgomery-form key-agreement algorithms Bernstein originally named curve25519 and curve448, now renamed X or sometimes XDH to separate them from the signature algorthms Ed25519[ph] and Ed448[ph] based on transforms of the same curves, are defined in rfc8037.

Your reference to an 'issuer' key suggests you really want not X25519 but the signature algorithm Ed25519, which uses a different Edwards-form equation that is not listed in https://safecurves.cr.yp.to/equation.html but is in rfc8032 section 5 together with its related but different computation.

But what you call 'X.509' format

-----BEGIN PRIVATE KEY-----
MEECAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQcEJzAlAgEBBCDpEOgUmtucn1YbRjUJ
Vc3QSfFu5AiBExB/MVUqiBs7pw==
-----END PRIVATE KEY-----

is not X.509 (which concerns only public keys), although it is a format used by some (not all) the things that concurrently use X.509 (or its Internet profile PKIX) for public-key management. Specifically it is a PEM-style or 'textual' format defined in rfc7468 section 2 which 'armors' in base64 with labels an ASN.1 (binary) structure, in this case (section 10) a private key defined by PKCS8 now available as rfc5208. PKCS8 is a generic structure that embeds algorithm-specific data, which for X9/NISTian EC is SEC1 also available as rfc5915.

Decoding this with openssl (which does base64 and ASN.1 in a foop) shows the structure:

$ openssl asn1parse -i
-----BEGIN PRIVATE KEY-----
MEECAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQcEJzAlAgEBBCDpEOgUmtucn1YbRjUJ
Vc3QSfFu5AiBExB/MVUqiBs7pw==
-----END PRIVATE KEY-----
    0:d=0  hl=2 l=  65 cons: SEQUENCE
    2:d=1  hl=2 l=   1 prim:  INTEGER           :00
    5:d=1  hl=2 l=  19 cons:  SEQUENCE
    7:d=2  hl=2 l=   7 prim:   OBJECT            :id-ecPublicKey
   16:d=2  hl=2 l=   8 prim:   OBJECT            :prime256v1
   26:d=1  hl=2 l=  39 prim:  OCTET STRING      [HEX DUMP]:30250201010420E910E8149ADB9C9F561B46350955CDD049F16EE4088113107F31552A881B3BA7
$ openssl asn1parse -i -strparse 26   # the algorithm-specific part
-----BEGIN PRIVATE KEY-----
MEECAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQcEJzAlAgEBBCDpEOgUmtucn1YbRjUJ
Vc3QSfFu5AiBExB/MVUqiBs7pw==
-----END PRIVATE KEY-----
    0:d=0  hl=2 l=  37 cons: SEQUENCE
    2:d=1  hl=2 l=   1 prim:  INTEGER           :01
    5:d=1  hl=2 l=  32 prim:  OCTET STRING      [HEX DUMP]:E910E8149ADB9C9F561B46350955CDD049F16EE4088113107F31552A881B3BA7

As you can see that last and only 'real' value in the algorithm-specific data is the same value produced by base64-decoding the d in your JWK:

$ <<<"6RDoFJrbnJ9WG0Y1CVXN0EnxbuQIgRMQfzFVKogbO6c=" openssl base64 -d | xxd -p -c32
e910e8149adb9c9f561b46350955cdd049f16ee4088113107f31552a881b3ba7
23
  • +1 Nice answer, especially the part about openssl asn1parse.
    – mti2935
    Nov 16, 2021 at 13:00
  • Thx Dave! Let me read through this carefully once i get some time and get back to you if any questions.
    – Steve237
    Nov 17, 2021 at 1:35
  • Ok Have read though all above but still can't see 2 simple things please: 1-From above What can I plug into y^2 = x^3+486662x^2+x to see that the points lie on that curve? and 2-If I do not have a private key and only public key, what code can I run on a random private key so I can compare the output to the public key to see if a match is made? How many bytes to I have to cycle through? and lastly: 3-mti2935, can you please send me a file attachment of that code as I cannot run it due to indents. Thanks
    – Steve237
    Nov 17, 2021 at 2:12
  • Steve: y^2=x^3+486662x^2+x is the Montgomery form used in curve25519-now-X[DH]25519. The key you posted is for a different curve (usually called P-256) that uses a different form (Weierstrass), and you can't directly use Weierstrass code on Montgomery data or vice versa. However, if you have only the public key in either scheme you can't find the private key during the existence of the Earth, and probably the universe; that's what makes these schemes secure enough for people to use. Meta: normally you need to use atsign (@) to notify anyone other than the post author. Nov 18, 2021 at 6:00
  • @dave_thompson_085: Your thoughts on the Pollard Rho algorithm/attack?
    – Steve237
    Nov 19, 2021 at 2:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .