ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

Published at Mar 29 2021
·
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.

The test program supplies prime numbers p and g.

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

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.

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.

Execute the tests with:

```
$ mix test
```

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.

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

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

```
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
```

```
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.
A video example is available at:
https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/diffie-hellman-key-exchange-part-2
"""
@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
# i was already looking through the crypto documentation
# for erlang, and this rng seemed best
:crypto.rand_uniform(1, 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
# finding the mod_pow function was the hardest part of this
# erlang's docs are not crazy helpful
:binary.decode_unsigned(:crypto.mod_pow(prime_g, private_key, prime_p))
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
# secret they share is g^a*b mod p
# public key b is the result of the preceding function for user b
# pub_key_a ^ priv_key_a % prime_p independently verified in iex, so i know this works :)
:binary.decode_unsigned(:crypto.mod_pow(public_key_b, private_key_a, prime_p))
end
end
```

The best thing I did to figure this challenge out was to ensure I first had a strong grasp of how Diffie-Hellman worked, independently of Elixir. These Computerphile videos were most helpful:

https://www.youtube.com/watch?v=NmM9HA2MQGI

https://www.youtube.com/watch?v=Yjrfm_oRO0w

After working my way through DH manually with small numbers on paper, the actual programming felt much, much simpler than I think it would've without the prep.

I was lucky to find an RNG in the :crypto module which made the first step easy. The second part was tough, though, mostly because the Erlang documentation is hard to understand (at least, with no prior knowledge of Erlang). I searched for "exponent" and found `:crypto:.rsa_key()`, which was a red herring I lost some time to. After stumbling onto math_pow, the binary decoder was easier to find.

`math_pow` docs are here: https://erlang.org/doc/man/crypto.html#mod_pow-3

`binary_decode` docs here: https://erlang.org/doc/man/binary.html#decode_unsigned-1

I ran the algorithm manually in iex while developing the challenge, so I confirmed the shared secrets matched in iex before running the last chunk of code. iex console output pasted below for additional proof of work. In the test below, the small prime g was 5, the big prime p was 1531, Alice's private key was 792 and Bob's was 1266.

```

Interactive Elixir (1.11.2) - press Ctrl+C to exit (type h() ENTER for help)

iex(1)> alice = :crypto.mod_pow(5, 792, 1531)

<<2, 142>>

iex(2)> b_alice = :binary.decode_unsigned(alice)

654

iex(3)> bob = :crypto.mod_pow(5, 1266, 1531)

<<5, 13>>

iex(4)> b_bob = :binary.decode_unsigned(bob)

1293

iex(5)> bob_pub = :crypto.mod_pow(b_bob, 792, 1531)

<<4, 217>>

iex(6)> alice_pub = :crypto.mod_pow(b_alice, 1266, 1531)

<<4, 217>>

iex(7)> :binary.decode_unsigned(alice_pub)

1241

iex(8)> :binary.decode_unsigned(bob_pub)

1241

```

Level up your programming skills with 3,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments