Parth86's solution to Diffie Hellman on the Elixir track

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.

For generating random numbers, Erlang's :rand.uniform or Enum.random are good places to start.

:math.pow |> round can be used to find the power of a number, and rem for the modulus.

Neither of those works particularly well (or quickly) for very large integers. Cryptography generally makes use of numbers larger than 1024 bits. Erlang's :crypto module has a useful function for finding the modulus of a power, particularly for enormous integers, but you might need :binary to decode it.

Running tests

Execute the tests with:

$ mix test

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

If you're stuck on something, it may help to look at some of the available resources out there where answers might be found.

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.

diffie_hellman_test.exs

defmodule DiffieHellmanTest do
  use ExUnit.Case

  # @tag :pending
  test "private key should be between 1 and P-1, inclusive" do
    prime_p = 23

    assert DiffieHellman.generate_private_key(prime_p) in Range.new(1, prime_p - 1)
  end

  @tag :pending
  test "private key generator should support very large primes" do
    prime_p =
      120_227_323_036_150_778_550_155_526_710_966_921_740_030_662_694_578_947_298_423_549_235_265_759_593_711_587_341_037_426_347_114_541_533_006_628_856_300_552_706_996_143_592_240_453_345_642_869_233_562_886_752_930_249_953_227_657_883_929_905_072_620_233_073_626_594_386_072_962_776_144_691_433_658_814_261_874_113_232_461_749_035_425_712_805_067_202_910_389_407_991_986_070_558_964_461_330_091_797_026_762_932_543

    assert DiffieHellman.generate_private_key(prime_p) in Range.new(1, prime_p - 1)
  end

  @tag :pending
  test "private keys should be random" do
    prime_p = 23

    # Due to the nature of random generators, there's a small chance it could generate
    # the same numbers over an over, so this may fail, but the RNG should be good enough
    # that 100 generated keys between 1 and 22 ought to be at least half unique.

    unique_key_count =
      Stream.repeatedly(fn -> DiffieHellman.generate_private_key(prime_p) end)
      |> Enum.take(100)
      |> Enum.uniq()
      |> length

    min_expected_unique_keys = div(prime_p, 2)

    assert unique_key_count > min_expected_unique_keys
  end

  @tag :pending
  test "public key correctly calculated from two primes and private key" do
    prime_p = 23
    prime_g = 5
    private_key = 6
    expected_public_key = 8

    assert DiffieHellman.generate_public_key(prime_p, prime_g, private_key) == expected_public_key
  end

  @tag :pending
  test "public key generator should support very large primes" do
    prime_p =
      120_227_323_036_150_778_550_155_526_710_966_921_740_030_662_694_578_947_298_423_549_235_265_759_593_711_587_341_037_426_347_114_541_533_006_628_856_300_552_706_996_143_592_240_453_345_642_869_233_562_886_752_930_249_953_227_657_883_929_905_072_620_233_073_626_594_386_072_962_776_144_691_433_658_814_261_874_113_232_461_749_035_425_712_805_067_202_910_389_407_991_986_070_558_964_461_330_091_797_026_762_932_543

    prime_g =
      75_205_441_154_357_919_442_925_546_169_208_711_235_485_855_904_969_178_206_313_309_299_205_868_312_399_046_149_367_516_336_607_966_149_689_640_419_216_591_714_331_722_664_409_474_612_463_910_928_128_055_994_157_922_930_443_733_535_659_848_264_364_106_037_925_315_974_095_321_112_757_711_756_912_144_137_705_613_776_063_541_350_548_911_512_715_512_539_186_192_176_020_596_861_210_448_363_099_541_947_258_202_188

    private_key = 8_675_309

    expected_public_key =
      81_945_102_766_205_597_052_444_239_927_191_366_879_878_802_281_637_258_134_656_723_311_532_689_587_789_695_879_960_502_348_293_388_789_700_383_121_890_410_484_395_608_064_685_866_057_972_603_193_444_399_431_765_316_092_443_741_213_175_747_052_166_212_523_610_645_396_217_140_238_838_864_033_970_876_203_333_493_173_215_068_467_082_830_013_531_737_232_331_628_864_212_666_452_277_691_016_389_511_356_912_249_174

    assert DiffieHellman.generate_public_key(prime_p, prime_g, private_key) == expected_public_key
  end

  @tag :pending
  test "shared secret key correctly calculated from initial prime, Bob's public key, and Alice's private key" do
    prime_p = 23
    bob_public_key = 19
    alice_private_key = 6
    expected_shared_secret = 2

    assert DiffieHellman.generate_shared_secret(prime_p, bob_public_key, alice_private_key) ==
             expected_shared_secret
  end

  @tag :pending
  test "shared secret correctly calculated when using large primes" do
    prime_p =
      120_227_323_036_150_778_550_155_526_710_966_921_740_030_662_694_578_947_298_423_549_235_265_759_593_711_587_341_037_426_347_114_541_533_006_628_856_300_552_706_996_143_592_240_453_345_642_869_233_562_886_752_930_249_953_227_657_883_929_905_072_620_233_073_626_594_386_072_962_776_144_691_433_658_814_261_874_113_232_461_749_035_425_712_805_067_202_910_389_407_991_986_070_558_964_461_330_091_797_026_762_932_543

    bob_public_key =
      75_205_441_154_357_919_442_925_546_169_208_711_235_485_855_904_969_178_206_313_309_299_205_868_312_399_046_149_367_516_336_607_966_149_689_640_419_216_591_714_331_722_664_409_474_612_463_910_928_128_055_994_157_922_930_443_733_535_659_848_264_364_106_037_925_315_974_095_321_112_757_711_756_912_144_137_705_613_776_063_541_350_548_911_512_715_512_539_186_192_176_020_596_861_210_448_363_099_541_947_258_202_188

    alice_private_key =
      2_483_479_393_625_932_939_911_081_304_356_888_505_153_797_135_447_327_501_792_696_199_190_469_015_215_177_630_758_617_902_200_417_377_685_436_170_904_594_686_456_961_202_706_692_908_603_181_062_371_925_882

    expected_shared_secret =
      70_900_735_223_964_890_815_905_879_227_737_819_348_808_518_698_920_446_491_346_508_980_461_201_746_567_735_331_455_825_644_429_877_946_556_431_095_820_785_835_497_384_849_778_344_216_981_228_226_252_639_932_672_153_547_963_980_483_673_419_756_271_345_828_771_971_984_887_453_014_488_572_245_819_864_454_136_618_980_914_729_839_523_581_263_886_740_821_363_010_486_083_940_557_620_831_348_661_126_601_106_717_071

    assert DiffieHellman.generate_shared_secret(prime_p, bob_public_key, alice_private_key) ==
             expected_shared_secret
  end

  @tag :pending
  test "exchanging public keys between Alice and Bob should calculate the same shared secret" do
    prime_p = 23
    prime_g = 5

    alice_private_key = DiffieHellman.generate_private_key(prime_p)
    bob_private_key = DiffieHellman.generate_private_key(prime_p)

    alice_public_key = DiffieHellman.generate_public_key(prime_p, prime_g, alice_private_key)
    bob_public_key = DiffieHellman.generate_public_key(prime_p, prime_g, bob_private_key)

    alice_shared_secret =
      DiffieHellman.generate_shared_secret(prime_p, bob_public_key, alice_private_key)

    bob_shared_secret =
      DiffieHellman.generate_shared_secret(prime_p, alice_public_key, bob_private_key)

    assert alice_shared_secret == bob_shared_secret
  end
end

test_helper.exs

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

defmodule DiffieHellman do
  @moduledoc """
  Diffie-Hellman is a method of securely exchanging keys in a public-key
  cryptosystem. Two users, Alice and Bob, want to share a secret between
  themselves, while ensuring nobody else can read it.

  Step 0: Alice and Bob agree on two prime numbers, P and G. An attacker, Eve,
  can intercept these numbers, but without one of Alice or Bob's private keys,
  we'll see Eve can't do anything useful with them.

  Step 1: Alice and Bob each generate a private key between 1 and P-1.
  P).

  Step 2: Using the initial primes P and G, Alice and Bob calculate their
  public keys by raising G to the power of their private key, then calculating
  the modulus of that number by P. ((G**private_key) % P)

  Step 3: Alice and Bob exchange public keys. Alice and Bob calculate a secret
  shared key by raising the other's public key to the power of their private
  key, then doing a modulus of the result by P. Due to the way modulus math
  works, they should both generate the same shared key.

  Alice calculates: (bob_public ** alice_private) % P
  Bob calculates: (alice_public ** bob_private) % P

  As long as their private keys are never lost or transmitted, only they know
  their private keys, so even if Eve has P, G, and both public keys, she can't
  do anything with them.
  """

  @doc """
  Given a prime integer `prime_p`, return a random integer between 1 and `prime_p` - 1
  """
  @spec generate_private_key(prime_p :: integer) :: integer
  def generate_private_key(prime_p) do
    :rand.uniform(prime_p-1) # returns a random integer between 1 and `prime_p` - 1
  end

  @doc """
  Given two prime integers as generators (`prime_p` and `prime_g`), and a private key,
  generate a public key using the mathematical formula:

  (prime_g **  private_key) % prime_p
  """
  @spec generate_public_key(prime_p :: integer, prime_g :: integer, private_key :: integer) ::
          integer
  def generate_public_key(prime_p, prime_g, private_key) do
    :crypto.mod_pow(prime_g, private_key, prime_p)
    |> :binary.decode_unsigned # raises prime_g to power private_key and takes modulo prime_p. Returns a binary so decode converts back into int
  end

  @doc """
  Given a prime integer `prime_p`, user B's public key, and user A's private key,
  generate a shared secret using the mathematical formula:

  (public_key_b ** private_key_a) % prime_p
  """
  @spec generate_shared_secret(
          prime_p :: integer,
          public_key_b :: integer,
          private_key_a :: integer
        ) :: integer
  def generate_shared_secret(prime_p, public_key_b, private_key_a) do
    :crypto.mod_pow(public_key_b, private_key_a, prime_p)
    |> :binary.decode_unsigned
  end
end

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?

Parth86's solution

to Diffie Hellman in the Elixir Track