Avatar of johnburkert

johnburkert's solution

to Diffie Hellman in the C# Track

Published at May 23 2019 · 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.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the Skip property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using exercism submit DiffieHellman.cs

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

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 System.Collections.Generic;
using System.Linq;
using System.Numerics;

public static class DiffieHellman
{
    private static IEnumerable<BigInteger> Generate(Random random, byte[] bytes)
    {
        while (true)
        {
            random.NextBytes(bytes);
            yield return new BigInteger(bytes);
        }
    }

    public static BigInteger PrivateKey(BigInteger primeP) => Generate(new Random(), primeP.ToByteArray()).First(x => 1 < x && x < primeP);

    public static BigInteger PublicKey(BigInteger primeP, BigInteger primeG, BigInteger privateKey) => BigInteger.Pow(primeG, (int)privateKey) % primeP;

    public static BigInteger Secret(BigInteger primeP, BigInteger publicKey, BigInteger privateKey) => BigInteger.Pow(publicKey, (int)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?