Ed25519 - Edwards-curve Digital Signature Algorithm (EdDSA) - uses Curve 25519 and SHA-512 to produce an EdDSA signature. In this case we will perform the core operations in the signing and verification. With this we calculate the hash of the message (\(h\)) and have a public key (\(pk\)) and a private key (\(sk\)). We then generate a signature of (\(R,s\)). The public key (\(pk\)) and (\(R,s\)) is then used to check the signature. It is standardized RFC [RFC 8032] and is based on the Schnorr's signature scheme and uses (possibly twisted) Edwards curves. For Ed25519 we use 32 byte values for both the private key and the public key, and for X448 we use 57 byte values for both the private key and the public key.
EdDSA (Ed25519) using Bouncy Castle and C# |
Theory
The generalize form of the curve is:
\(x^2 = (y^2 - 1) / (d y^2 + 1) \pmod p \)
and is specificially defined as:
\(−x^2+y^2=1−(121665/121666)x^2y^2 \pmod p\)
with a prime number (\(p\)) of \(2^{255}-19\) and the order (\(L\)) of \(2^{252}+27742317777372353535851937790883648493\). The base point is \(y=4/5\), and which is:
>>> p=2**255-19 >>> y=4*pow(5,-1,p) >>> print (y) 46316835694926478169428394003475163141307993866256225615783033603165251855960
And we can then work out the x co-ordinate with:
\(x=(u/v)^{(p+3)/8}\)
and where \(u = y^2 - 1\) and \(v = d y^2 + 1\). A Python program to recover the base point is:
p = 2**255 - 19 def inv(x): return pow(x, p-2, p) d = -121665 * inv(121666) I = pow(2,(p-1)//4,p) def findx(y): xx = (y*y-1) * inv(d*y*y+1) x = pow(xx,(p+3)//8,p) if (x*x - xx) % p != 0: x = (x*I) % p if x % 2 != 0: x = p-x return x y = 4 * inv(5) x = findx(y) print (x,y)
and which gives:
15112221349535400772501151409588531511454012693041857206046113283949847762202 46316835694926478169428394003475163141307993866256225615783033603165251855960
With EdDSA, Alice will sign a message with her private key, and then Bob will use her public key to verify that she signed the message (and that the message has now changed):
Key generation
Alice generates a random 32-byte secret key (\(sk\)) and then creates a public key of:
\(pk=sk \cdot G\)
and where \(G\) is the base point of the curve.
Signing
Alice creates a SHA-512 hash of her private key:
\(h=\textrm{HASH}(sk)\)
Create \(r\) from the upper 32 bytes of hash and the message:
\( r = \textrm{HASH}(h[32:] \: || \: m))\)
And where "||" represents a concatenation of the byte array values. Next she matches \(r\) onto curve with:
\(R=r \cdot G\)
Next Alice computes \(s\) with:
\(s=r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk\)
The signature is (\(R,s\)). The values of \(R\) and \(s\) are 32 bytes long, and thus the signature is 64 bytes long.
Verifying
Bob creates \(S\) using \(R\), \(pk\) and \(m\):
\(S =\textrm{HASH}(R \: || \: pk \: || \: m) \)
And next creates two verification values:
\(v_1=s \cdot G\)
\(v_2=R+ pk \cdot S\)
If \(v_1==v_2\) the signature checks. This is because:
\(v_1=sB = (r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk) \cdot G = rG + sk \cdot B \cdot (\textrm{HASH}(R \: || \: pk \: || \: m))= R+ pk \cdot S = v_2 \pmod q \)
Overall, we just need point multiplication and point addition.
Code
First we create a folder named "bc_eddsa", and then go into that folder.We can create a Dotnet console project for .NET 8.0 with:
dotnet new console --framework net8.0
Next we can install the Bouncy Castle library with:
dotnet add package BouncyCastle.Crypto.dll --version 1.8.1
Next some code:
namespace EdDSA { using Org.BouncyCastle.Security; using Org.BouncyCastle.Crypto.Parameters; class Program { static void Main(string[] args) { var msg="Hello"; if (args.Length >0) msg=args[0]; try { Org.BouncyCastle.Crypto.Parameters.Ed25519KeyGenerationParameters keygenParams = new Org.BouncyCastle.Crypto.Parameters.Ed25519KeyGenerationParameters (new SecureRandom()); Org.BouncyCastle.Crypto.Generators.Ed25519KeyPairGenerator generator = new Org.BouncyCastle.Crypto.Generators.Ed25519KeyPairGenerator(); generator.Init(keygenParams); var keyPair = generator.GenerateKeyPair(); // Create signature var signer = SignerUtilities.GetSigner("Ed25519"); var privateKey = (Ed25519PrivateKeyParameters) keyPair.Private; var publicKey = (Ed25519PublicKeyParameters) keyPair.Public; signer.Init(true, privateKey); signer.BlockUpdate(System.Text.Encoding.ASCII.GetBytes(msg), 0, msg.Length); // Verify signature var signer2 = SignerUtilities.GetSigner("Ed25519"); signer2.Init(false, publicKey); signer2.BlockUpdate(System.Text.Encoding.ASCII.GetBytes(msg), 0, msg.Length); var rtn=signer2.VerifySignature(signer.GenerateSignature()); Console.WriteLine("Ed25519"); Console.WriteLine("== Message: {0} ",msg); Console.WriteLine("\n== Signature === "); Console.WriteLine("== Signature: {0} [{1}] ",Convert.ToHexString(signer.GenerateSignature()),Convert.ToBase64String(signer.GenerateSignature())); Console.WriteLine("== Verified: {0} ",rtn); Console.WriteLine("\n== Private key === "); Console.WriteLine("== Private key ==={0} ",Convert.ToHexString(privateKey.GetEncoded())); Console.WriteLine("\n== Public key === "); Console.WriteLine("== Public key ==={0} ",Convert.ToHexString(publicKey.GetEncoded())); } catch (Exception e) { Console.WriteLine("Error: {0}",e.Message); } } } }
A sample run gives:
Ed25519 == Message: Hello 123 == Signature === == Signature: 3107955477B4057EDE800E06C71693A3672BFDD3BA68ADAD1D4196480A1096161FBD88775FEABE7C324A8CB41FCE27E1D1947D6A3CD0F93C002E95CD239A0A02 [MQeVVHe0BX7egA4GxxaTo2cr/dO6aK2tHUGWSAoQlhYfvYh3X+q+fDJKjLQfzifh0ZR9ajzQ+TwALpXNI5oKAg==] == Verified: True == Private key === == Private key ===D90270C1DC41B25B8D1592785C778E02500E7F0C306A1C1EFFA6CB7C882821AA == Public key === == Public key ===701CD3AEE81F50EFADB57C5391E159D2879F73BE527080391F89AC890F7B0B44