Avatar of ChrisPritchard

ChrisPritchard's solution

to Diffie Hellman in the C# Track

Published at Oct 03 2018 · 0 comments
Instructions
Test suite
Solution

Diffie-Hellman key exchange.

Alice and Bob use Diffie-Hellman key exchange to share secrets. They start with prime numbers, pick private keys, generate and share public keys, and then generate a shared secret key.

Step 0

The test program supplies prime numbers p and g.

Step 1

Alice picks a private key, a, greater than 1 and less than p. Bob does the same to pick a private key b.

Step 2

Alice calculates a public key A.

A = g**a mod p

Using the same p and g, Bob similarly calculates a public key B from his private key b.

Step 3

Alice and Bob exchange public keys. Alice calculates secret key s.

s = B**a mod p

Bob calculates

s = A**b mod p

The calculations produce the same result! Alice and Bob now share secret s.

Hints

This exercise requires you to perform calculations on large numbers. To correctly represent large numbers, the BigInteger struct is used.

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

Source

Wikipedia, 1024 bit key from www.cryptopp.com/wiki. http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

DiffieHellmanTest.cs

// This file was auto-generated based on version 1.0.0 of the canonical data.

using System.Linq;
using System.Numerics;
using Xunit;

public class DiffieHellmanTest
{
    [Fact]
    public void Private_key_is_in_range_1_p()
    {
        var p = new BigInteger(7919);
        var privateKeys = Enumerable.Range(0, 10).Select(_ => DiffieHellman.PrivateKey(p)).ToArray();
        foreach (var privateKey in privateKeys)
        {
            Assert.InRange(privateKey, new BigInteger(1), p);
        }
    }

    [Fact(Skip = "Remove to run test")]
    public void Private_key_is_random()
    {
        var p = new BigInteger(7919);
        var privateKeys = Enumerable.Range(0, 10).Select(_ => DiffieHellman.PrivateKey(p)).ToArray();
        Assert.Equal(privateKeys.Distinct().Count(), privateKeys.Length);
    }

    [Fact(Skip = "Remove to run test")]
    public void Can_calculate_public_key_using_private_key()
    {
        var p = new BigInteger(23);
        var g = new BigInteger(5);
        var privateKey = new BigInteger(6);
        Assert.Equal(new BigInteger(8), DiffieHellman.PublicKey(p, g, privateKey));
    }

    [Fact(Skip = "Remove to run test")]
    public void Can_calculate_secret_using_other_partys_public_key()
    {
        var p = new BigInteger(23);
        var theirPublicKey = new BigInteger(19);
        var myPrivateKey = new BigInteger(6);
        Assert.Equal(new BigInteger(2), DiffieHellman.Secret(p, theirPublicKey, myPrivateKey));
    }

    [Fact(Skip = "Remove to run test")]
    public void Key_exchange()
    {
        var p = new BigInteger(23);
        var g = new BigInteger(5);
        var alicePrivateKey = DiffieHellman.PrivateKey(p);
        var bobPrivateKey = DiffieHellman.PrivateKey(p);
        var alicePublicKey = DiffieHellman.PublicKey(p, g, alicePrivateKey);
        var bobPublicKey = DiffieHellman.PublicKey(p, g, bobPrivateKey);
        var secretA = DiffieHellman.Secret(p, bobPublicKey, alicePrivateKey);
        var secretB = DiffieHellman.Secret(p, alicePublicKey, bobPrivateKey);
        Assert.Equal(secretA, secretB);
    }
}
using System;
using bigint = System.Numerics.BigInteger;

public static class DiffieHellman
{
    public static bigint PrivateKey(bigint primeP) 
    {
        var buffer = new byte[primeP.ToByteArray().Length];
        
        var random = new Random();
        random.NextBytes(buffer);
        bigint result;
        while((result = new bigint(buffer, true)) > primeP)
            random.NextBytes(buffer);

        return result;
    }

    public static bigint PublicKey(bigint primeP, bigint primeG, bigint privateKey) 
        => bigint.ModPow(primeG, privateKey, primeP);

    public static bigint Secret(bigint primeP, bigint publicKey, bigint privateKey) 
        => bigint.ModPow(publicKey, privateKey, primeP);
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?