The Goldilocks Prime for Enhanced Security

Sitting comfortably? Well, once upon a time there were three bears, and they made some porridge. But the porridge was too hot, so they…

The Goldilocks Prime for Enhanced Security (and Riddinghood, too)

Sitting comfortably? Well, once upon a time there were three bears, and they made some porridge. But the porridge was too hot, so they went for a walk in the woods. Blah, blah, blah, and the rest is history.

And so what has Goldilocks and the Three Bears got to do with Cybersecurity? Well, at the core of many of our secure tunnel connections — such as the one you are using now to connect to this article — is a magical little method known as ECDH (Elliptic Curve Diffie Hellman). With this Bob and Alice create their secret values for the session (a and b), and they pick a point on the curve at G. Bob passes bG and Alice passes aG, and they both end up with the same value of abG (and which is a point on the elliptic curve), and then can derive the secret key they will use for their session.

One of the most popular curves for this is Curve 25519, and which is used with Tor, and many other applications. Overall we use a prime number to define the security level of the curve, and for Curve 25519 it is 2²⁵⁵-19 (“did you see what we did there?”). But, there’s a problem, in that although we are using a 256-bit prime number, the security level is only equivalent to a 128-bit key. While this may be okay now for cracking, the power of the Cloud and GPUs could start to approach this, and our key could be cracked within the next few years.

The Goldilocks prime and X448

And, so we meet Goldilocks. With this we have Curve 448 and the Goldilocks prime number (2⁴⁴⁸-2²²⁴-1). The curve itself fits in with y²+x²=1−39081x²y², and where we use our Goldilocks prime number [here]:

The Goldilocks prime is defined as the golden ratio ϕ≡2²²⁴. The form of ϕ²-ϕ-1, and which is the form of the golden ratio and because 224 = 32 x 7 = 28 x 8 = 56 x 4. This makes it easier to process with 32 bits and 54 bits at a time. Overall this choice of prime makes the calculations related to the prime number extremely fast.

Overall X448 improves the security levels to 256-bit security. Here is a basic Go program to implement ECDH with X448 [here]:

A sample run is [here]:

Alice Secret 74048772585ada2234dec2a64392481b15f1bd4bbc8ac104d4b78b11e12373727f2a4fc0f8d2a0e4284fd251ee4f09720c821eb7b42070f8
Alice Public da5367818e162e97816073a6b154627aebb7d7882799c4444e21b679060cb8079ee921dccb12513743e2bc929eb41b28e2bea1266c87abf4
Bob Secret 1c8a1259f95ca33a7560e0b59f84f543411a2625e92aace4fb3aaa2f2ed02ebb3284660cdde1a11913147d834f3a22100d25ddad6bb3c83c
Bob Public ec68e505b59554a4732670730edfb700f0737ca6c811d0a6676c5d378c1e91a8fc777f2999f8d17938c07a5e691a504282f31a9d00ba0bb7

Bob Shared 91bc39930f8691fd517f875eceb3c5cf16b461bd7f3f2149c4a8060926ff0292ebe072d8cfe1c7166315f8a21b02d17996e6bcabdda42796
Alice Shared 91bc39930f8691fd517f875eceb3c5cf16b461bd7f3f2149c4a8060926ff0292ebe072d8cfe1c7166315f8a21b02d17996e6bcabdda42796

The paper also outlines the Riddinghood prime number, and which is 2⁴⁸⁰-2²⁴⁰-1. This is a useful prime number for performance for a 64-bit processing engine, while the Goldilocks prime is useful for both 32-bit and 64-bit processing.

Ed448

The Ed448 method is used with the signing for the Edwards-Curve Digital Signature Algorithm (EdDSA), and is defined in RFC 8032. It uses a public key size of 57 bytes, a private key size of 57 bytes, and a signature size of 114 bytes. The code is [here]:

package main

import (
  "github.com/cloudflare/circl/sign/ed448"
  "crypto/rand"
  "fmt"
  "os"

)

func main() {

	msg:="Hello"
	cont:="Context"

	argCount := len(os.Args[1:])
	if (argCount>0) { msg= os.Args[1]}
	if (argCount>1) { cont= os.Args[2]}

	alice, err := ed448.GenerateKey(rand.Reader)
	if err != nil {
		panic("error on generating keys")
	}

	message := []byte(msg)
	context := []byte(cont)

	signature, err := alice.SignWithContext(message, context)
  
	if err != nil {
		panic("error on signing message")
	}


	ok := ed448.Verify(alice.GetPublic(), message, context, signature)

  fmt.Printf("Message: %s\n",msg)
  fmt.Printf("Context: %s\n\n",cont)

  fmt.Printf("Alice private key: %x\nAlice Public key %x\n",alice.GetPrivate(),alice.GetPublic())

  fmt.Printf("\nSignature: %x\n",signature)

	if (ok) { fmt.Println("\nSignature verified") }

}

A sample run gives [here]:

Message: Hello
Context: None

Alice private key: 6a56a7bf8ae2ebf3ac985db1aa55b25f9be38795e53e1ae4bba69d49cdffbd3c8496c1490ceeac29448f6d31b88f91ea985687cdd2f5821302
Alice Public key 9d7b6bc88eb8878c9cf0b3616c885be952dc5464c3f5a01833cfc4f50f471c677cee26a539236de11c531b883c2c0a6cbe098ca06b3a045200

Signature: b2968cc1fd3166a83eacface86116146b02b136a9aa9d94fbe0fd94c78082d24f3d90ce3160eaf1b1edbf3774298691119d6a9d1decf20c7003dd020c7a45878a99d37da4f7acaddd42e5e7a6adde3492cda0a35ac60f8b3e325c3f3f28ba79bb6a1a5c980e3437389d48870d69725b50600

Signature verified

Conclusions

Want to remember some primes? Try 99, 997, 2¹⁹-1, 2²⁵⁵-19 and now 2⁴⁴⁸-2²²⁴-1. For the Goldilocks one, just remember “448” and then half the next one, and then subtract 1.