commit 1cacbb40d5c286bb8ed136da2a728e84703acb52
parent a7a70c75b0fb0e1d6832fd65e9590aa83a491fa0
Author: Andrew Laack <andrew@laack.co>
Date: Sat, 16 May 2026 00:31:20 -0500
Implemented Lamport signature scheme in go
Diffstat:
3 files changed, 238 insertions(+), 0 deletions(-)
diff --git a/mas.s62-cryptocurrency-engineering-and-design/lamport-signature/go.mod b/mas.s62-cryptocurrency-engineering-and-design/lamport-signature/go.mod
@@ -0,0 +1,3 @@
+module lamportsignature
+
+go 1.26.3
diff --git a/mas.s62-cryptocurrency-engineering-and-design/lamport-signature/main.go b/mas.s62-cryptocurrency-engineering-and-design/lamport-signature/main.go
@@ -0,0 +1,119 @@
+package main
+
+import (
+ "crypto/rand"
+ "crypto/sha256"
+ "fmt"
+)
+
+// 1. publicKey, privateKey := GenerateKeys(randomSeed)
+// 2. signature := Sign(privateKey, message)
+// 3. valid := Verify(publicKey, message, signature)
+
+
+// 256 blocks of 256 bits (32 bytes)
+// spread across two rows
+
+type Key struct {
+ firstRow [256][32] byte
+ secondRow[256][32] byte
+}
+
+
+func GenerateKeys () (Key, Key){
+
+ privateKey := Key{}
+
+ for i := range 256 {
+ _, err := rand.Read(privateKey.firstRow[i][:])
+ if err != nil {
+ panic(err)
+ }
+ }
+
+ for i := range 256 {
+ _, err := rand.Read(privateKey.secondRow[i][:])
+ if err != nil {
+ panic(err)
+ }
+ }
+
+
+ publicKey := Key{}
+
+ for i := range 256 {
+ publicKey.firstRow[i] = sha256.Sum256(privateKey.firstRow[i][:])
+ }
+
+ for i := range 256 {
+ publicKey.secondRow[i] = sha256.Sum256(privateKey.secondRow[i][:])
+
+ }
+
+ return publicKey, privateKey
+}
+
+func Sign(privateKey Key, message string) [256][32]byte {
+
+ messageHash := sha256.Sum256([]byte(message))
+
+ signature := [256][32]byte{}
+
+ for index := range 32 {
+ currentByteString := fmt.Sprintf("%08b", messageHash[index])
+ for idx := range 8 {
+ currentBit := currentByteString[idx]
+ if currentBit == '1' {
+ signature[(index * 8) + idx] = privateKey.firstRow[(index * 8) + idx]
+ } else {
+ signature[(index * 8) + idx] = privateKey.secondRow[(index * 8) + idx]
+ }
+ }
+ }
+
+ return signature
+}
+
+
+func Verify(publicKey Key, message string, signature [256][32]byte) bool {
+
+ messageHash := sha256.Sum256([]byte(message))
+
+ for index := range 32 {
+ currentByteString := fmt.Sprintf("%08b", messageHash[index])
+ for idx := range 8 {
+ currentBit := currentByteString[idx]
+ if currentBit == '1' {
+ // signature[(index * 8) + idx] = privateKey.firstRow[(index * 8) + idx]
+ if sha256.Sum256(signature[(index * 8) + idx][:]) != publicKey.firstRow[(index * 8) + idx] {
+ return false
+ }
+ } else {
+ if sha256.Sum256(signature[(index * 8) + idx][:]) != publicKey.secondRow[(index * 8) + idx] {
+ return false
+ }
+ }
+ }
+ }
+
+ return true
+
+}
+
+func main() {
+
+ // Generally, you'd pass a random seed to generatekeys, but crypto/rand.Read
+ // doesn't accept a seed.
+
+ publicKey, privateKey := GenerateKeys()
+
+ message := rand.Text()
+
+ signature := Sign(privateKey, message)
+
+
+ valid := Verify(publicKey, message, signature)
+
+ fmt.Printf("Verified message matches signature: %v\n", valid)
+
+}
diff --git a/mas.s62-cryptocurrency-engineering-and-design/lamport-signature/main_test.go b/mas.s62-cryptocurrency-engineering-and-design/lamport-signature/main_test.go
@@ -0,0 +1,116 @@
+// These are all property based tests.
+
+// These don't validate the implementation against a lamport signature spec, but
+// they do validate expected invariants for signatures, messages, and keys.
+
+package main
+
+import (
+ "crypto/rand"
+ "sync"
+ "testing"
+)
+
+func signAndValidate(t *testing.T, wg *sync.WaitGroup) {
+
+ defer wg.Done()
+
+ publicKey, privateKey := GenerateKeys()
+
+ message := rand.Text()
+
+ signature := Sign(privateKey, message)
+
+
+ valid := Verify(publicKey, message, signature)
+
+ if valid != true {
+ t.Errorf("Signature generation and verification mismatch.")
+ }
+}
+
+
+func signChangeAndValidate(t *testing.T, wg *sync.WaitGroup) {
+
+ defer wg.Done()
+
+ publicKey, privateKey := GenerateKeys()
+
+ message := rand.Text()
+
+ signature := Sign(privateKey, message)
+
+ signature[0][0] += 1
+
+ valid := Verify(publicKey, message, signature)
+
+ if valid != false {
+ t.Errorf("Signature changed, but still verified")
+ }
+}
+
+func signDifferentMessagesAndValidate(t *testing.T, wg *sync.WaitGroup) {
+
+ defer wg.Done()
+
+ publicKey, privateKey := GenerateKeys()
+
+ message1 := rand.Text()
+ message2 := rand.Text()
+
+ signature := Sign(privateKey, message1)
+
+ valid := Verify(publicKey, message1, signature)
+
+ if valid != true {
+ t.Errorf("Unable to validate signature for message it was generated with.")
+ }
+
+ valid = Verify(publicKey, message2, signature)
+
+ if valid != false {
+ t.Errorf("Signature valid for multiple messages")
+ }
+}
+
+func TestSignatureIsValid(t *testing.T) {
+
+ var wg sync.WaitGroup
+
+ for _ = range 100000 {
+ wg.Add(1)
+ go signAndValidate(t, &wg)
+ }
+
+ wg.Wait()
+
+
+}
+
+func TestSignatureChangeInvalidation(t *testing.T) {
+
+ var wg sync.WaitGroup
+
+ for _ = range 100000 {
+ wg.Add(1)
+ go signChangeAndValidate(t, &wg)
+ }
+
+ wg.Wait()
+
+
+}
+
+func TestMessageChangeInvalidation(t *testing.T) {
+
+ var wg sync.WaitGroup
+
+ for _ = range 100000 {
+ wg.Add(1)
+ go signDifferentMessagesAndValidate(t, &wg)
+ }
+
+ wg.Wait()
+
+
+}
