summaryrefslogtreecommitdiff
path: root/go
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2016-08-30 11:22:24 +0200
committerDimitri Sokolyuk <demon@dim13.org>2016-08-30 11:22:24 +0200
commit7ddc3c83dd47daf19222a64d20f278e299ec8c50 (patch)
tree807d571c9f295b6227cd0443520ee5cc0ff0249a /go
parent0b2cbd28e2f47ac7d0831a139b9543cb19ba936f (diff)
Import DH problem
Diffstat (limited to 'go')
-rw-r--r--go/diffie-hellman/README.md56
-rw-r--r--go/diffie-hellman/diffie_hellman.go19
-rw-r--r--go/diffie-hellman/diffie_hellman_test.go183
3 files changed, 258 insertions, 0 deletions
diff --git a/go/diffie-hellman/README.md b/go/diffie-hellman/README.md
new file mode 100644
index 0000000..feef92d
--- /dev/null
+++ b/go/diffie-hellman/README.md
@@ -0,0 +1,56 @@
+# Diffie Hellman
+
+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.
+
+To run the tests simply run the command `go test` in the exercise directory.
+
+If the test suite contains benchmarks, you can run these with the `-bench`
+flag:
+
+ go test -bench .
+
+For more detailed info about the Go track see the [help
+page](http://exercism.io/languages/go).
+
+## Source
+
+Wikipedia, 1024 bit key from www.cryptopp.com/wiki. [http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange](http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange)
+
+## Submitting Incomplete Problems
+It's possible to submit an incomplete solution so you can see how others have completed the exercise.
+
diff --git a/go/diffie-hellman/diffie_hellman.go b/go/diffie-hellman/diffie_hellman.go
new file mode 100644
index 0000000..27d810e
--- /dev/null
+++ b/go/diffie-hellman/diffie_hellman.go
@@ -0,0 +1,19 @@
+package diffiehellman
+
+import "math/big"
+
+func PrivateKey(p *big.Int) (priv *big.Int) {
+ return new(big.Int)
+}
+
+func PublicKey(a, p *big.Int, g int64) (pub *big.Int) {
+ return new(big.Int)
+}
+
+func SecretKey(a, B, p *big.Int) (s *big.Int) {
+ return new(big.Int)
+}
+
+func NewPair(p *big.Int, g int64) (a, A *big.Int) {
+ return new(big.Int), new(big.Int)
+}
diff --git a/go/diffie-hellman/diffie_hellman_test.go b/go/diffie-hellman/diffie_hellman_test.go
new file mode 100644
index 0000000..9d5afe5
--- /dev/null
+++ b/go/diffie-hellman/diffie_hellman_test.go
@@ -0,0 +1,183 @@
+// Diffie-Hellman-Merkle key exchange
+//
+// Step 1: PrivateKey(p *big.Int) *big.Int
+// Step 2: PublicKey(private, p *big.Int, g int64) *big.Int
+// Step 2.1: NewPair(p *big.Int, g int64) (private, public *big.Int)
+// Step 3: SecretKey(private1, public2, p *big.Int) *big.Int
+//
+// Private keys should be generated randomly.
+
+package diffiehellman
+
+import (
+ "math/big"
+ "testing"
+)
+
+type testCase struct {
+ g int64 // prime, generator
+ p *big.Int // prime, modulus
+ a, b *big.Int // private keys
+ A, B *big.Int // public keys
+ s *big.Int // secret key
+}
+
+// WP example
+var smallTest = testCase{
+ 5,
+ big.NewInt(23),
+ big.NewInt(6), big.NewInt(15),
+ big.NewInt(8), big.NewInt(19),
+ big.NewInt(2),
+}
+
+// 1024 bit example modulus from cryptopp.com wiki, random private keys
+var biggerTest = testCase{
+ 2,
+ mph("ab359aa76a6773ed7a93b214db0c25d0160817b8a893c001c761e198a3694509" +
+ "ebe87a5313e0349d95083e5412c9fc815bfd61f95ddece43376550fdc624e92f" +
+ "f38a415783b97261204e05d65731bba1ccff0e84c8cd2097b75feca1029261ae" +
+ "19a389a2e15d2939314b184aef707b82eb94412065181d23e04bf065f4ac413f"),
+
+ mph("2f6afe91cb53ecfa463d45cd800c948f7cb83bb9ddc62a07b5b3fd302d0cdf52" +
+ "18ae53ad015a632d137001a3b34239d54715606a292b6cf895b09d7dcf1bdf7a"),
+
+ mph("3651007bfa8a8b1cbaed2ae9326327599249c3bb6e9d8744b7407f3d4732cb8a" +
+ "0708d95c382747bad640d444f135e7e599618d11b15b9ef32e7ac7194e547f4b"),
+
+ mph("57d5489e3858cbd8fae75120907d1521f8e935cce2206d285b11762847e2a4c4" +
+ "a341a4eea18bdd8b40036c8d0004ffc323d5ae19da55176b08ff6f2d0ac97c65" +
+ "357c1f16756a6901ff926c8544c8af0a90ed2705966851f79a115cb77aac66be" +
+ "ceff569aadd7f02859539c28d55c08c62a03e45613bc52d205ace0704ea7c610"),
+
+ mph("6b189a36db5ca3ff83b66fb2c226078294c323f4c7cef35c506c237b0db7906d" +
+ "64cceb05af15a3603a30fd49834d3a6971d917f520d9a577c159d3b7d2bd8813" +
+ "5d19db47a9618340e4a51ec8845dbf5d50a4c6f14d6161def1eeaacecee8018f" +
+ "8816113a294959399989b759f4618e35dbffc570ab2a5a74ac59fccef35f684c"),
+
+ mph("64f74babc466f8e56d9b77ce2cc65d65fe1603b931c018b98a2a615d66172590" +
+ "803a94ac230db02de4b8ae567497c1844a6f7bd5bed69b95d3137acc1a6462d5" +
+ "aeba5b2b83a0e6b8ed4c072e5135a57c87b654ebe04cf128bbff49ee06df33b7" +
+ "8615e0067fdc9df22f7673b1e0501fb57598c7bff9ff173ddff47270fbd6f98f"),
+}
+
+// must parse hex, short name contrived just to make test data line up with
+// tab width 4.
+func mph(h string) *big.Int {
+ p, ok := new(big.Int).SetString(h, 16)
+ if !ok {
+ panic("invalid hex: " + h)
+ }
+ return p
+}
+
+var tests = []testCase{
+ smallTest,
+ biggerTest,
+}
+
+var _one = big.NewInt(1)
+
+// test that PrivateKey returns numbers in range, returns different numbers.
+func TestPrivateKey(t *testing.T) {
+ priv := func(p *big.Int) *big.Int {
+ a := PrivateKey(p)
+ if a.Cmp(_one) <= 0 || a.Cmp(p) >= 0 {
+ t.Fatalf("PrivateKey(%d) = %d, out of range (1, %d)", p, a, p)
+ }
+ return a
+ }
+ ms := map[string]bool{}
+ mb := map[string]bool{}
+ for i := 0; i < 100; i++ {
+ ms[priv(smallTest.p).String()] = true
+ mb[priv(biggerTest.p).String()] = true
+ }
+ if len(ms) == 1 {
+ t.Fatalf("For prime %d same key generated every time. "+
+ "Want random keys.", smallTest.p)
+ }
+ if len(mb) < 100 {
+ t.Fatal("For prime %d duplicate keys generated. "+
+ "Want unique keys.", biggerTest.p)
+ }
+}
+
+// test that PublicKey returns known results.
+func TestPublicKey(t *testing.T) {
+ tp := func(a, A, p *big.Int, g int64) {
+ if k := PublicKey(a, p, g); k.Cmp(A) != 0 {
+ t.Fatalf("PublicKey(%x,\n%x,\n%d)\n= %x,\nwant %x.",
+ a, p, g, k, A)
+ }
+ }
+ for _, test := range tests {
+ tp(test.a, test.A, test.p, test.g)
+ tp(test.b, test.B, test.p, test.g)
+ }
+}
+
+// test that SecretKey returns known results.
+func TestSecretKeys(t *testing.T) {
+ tp := func(a, B, p, s *big.Int) {
+ if k := SecretKey(a, B, p); k.Cmp(s) != 0 {
+ t.Fatalf("SecretKey(%x,\n%x,\n%x)\n= %x,\nwant %x.",
+ a, B, p, k, s)
+ }
+ }
+ for _, test := range tests {
+ tp(test.a, test.B, test.p, test.s)
+ tp(test.b, test.A, test.p, test.s)
+ }
+}
+
+// test that NewPair produces working keys
+func TestNewPair(t *testing.T) {
+ p, g := biggerTest.p, biggerTest.g
+ test := func(a, A *big.Int) {
+ if a.Cmp(_one) <= 0 || a.Cmp(p) >= 0 {
+ t.Fatalf("NewPair(%d, %d) private key = %d, out of range (1, %d)",
+ p, g, a, p)
+ }
+ if A.Cmp(_one) <= 0 || A.Cmp(p) >= 0 {
+ t.Fatalf("NewPair(%d, %d) public key = %d, out of range (1, %d)",
+ p, g, A, p)
+ }
+ }
+ a, A := NewPair(p, g)
+ test(a, A)
+ for i := 0; i < 20; i++ {
+ b, B := NewPair(p, g)
+ test(b, B)
+ sa := SecretKey(a, B, p)
+ sb := SecretKey(b, A, p)
+ if sa.Cmp(sb) != 0 {
+ t.Fatalf("NewPair() produced non-working keys.")
+ }
+ a, A = b, B
+ }
+}
+
+func BenchmarkPrivateKey(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ PrivateKey(biggerTest.p)
+ }
+}
+
+func BenchmarkPublicKey(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ PublicKey(biggerTest.a, biggerTest.p, biggerTest.g)
+ }
+}
+
+func BenchmarkNewPair(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ NewPair(biggerTest.p, biggerTest.g)
+ }
+}
+
+func BenchmarkSecretKey(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ SecretKey(biggerTest.a, biggerTest.B, biggerTest.p)
+ }
+}