commit 3a4350ed191bd4b3f3fda5148ff5117e2e5bd999
parent fee16fc6e4760b2cb398b319291eda73fe70db62
Author: Andrew Laack <andrew@laack.co>
Date: Sat, 16 May 2026 21:11:08 -0500
Took notes about lamport signatures, added implementation
Diffstat:
2 files changed, 168 insertions(+), 5 deletions(-)
diff --git a/docs/HashFunction.md b/docs/HashFunction.md
@@ -36,9 +36,9 @@ A hash function is perfect if for all valid inputs, there are no collisions (one
$f:K \to N$ is a perfect hash function if
$\forall x,y\in K, f(x) \neq f(y) \text{ where } y \neq x$
-## In Cryptography
+## Cryptographic hash functions
-The above is discussing hash functions within the context of [hashtables](HashTable.md), but expectations vary when using hash functions for cryptography.
+The above is discussing hash functions, primarily in the context of [hashtables](HashTable.md), but expectations differ when using hash functions for cryptography.
### Requirements for a good cryptographic hash function
diff --git a/docs/LamportSignature.md b/docs/LamportSignature.md
@@ -2,8 +2,171 @@
**Source:** MIT MAS.S62 Cryptocurrency Engineering and Design L1
-**Definition:** Lamport
+**Definition:** The Lamport signature scheme is a single use signature scheme where portions of a private key are leaked to prove the private key is known by the sender of the message, as a way to sign the message.
-## Specific
+## Specifics
-TODO. (see mit-ocw code as reference, possibly link it too)
+### Key Generation
+
+To generate a private key you generate a pair of 256 256 bit segments of random data. Since 256 bits is 32 bytes, we see the total size of the private key is 16kb (16384 bytes)
+
+To generate the public key we perform hashing on the data from the private key. Specifically, since the sha256 hash function gives hashes that are exactly 256 bits, we apply the hash function to each of the 512 segments of 256 bits above to generate a public key where each of the resulting segments is the hash of the associated segment from the private key. It is still worthwhile to consider the public key as two keys each with 256 segments, but for the purposes of public key generation this doesn't matter.
+
+### Signing Messages
+
+To sign a message we first hash the message using the sha256 hash function. This gives us 256 bits of data to work with.
+
+Using these 256 bits of data, we perform the operations specified in the below pseudocode:
+
+```
+
+signature = ""
+for idx in range(hash)
+ if hash[idx] == 0:
+ signature += privateKey.first[idx]
+ if hash[idx] == 1:
+ signature += privateKey.second[idx]
+return signature
+
+```
+
+The signature is thus exactly half of the private key where the half revealed is (generally) some portion of the first half and some portion second half of the private key, based on value of the current bit from the message hash.
+
+### Verifying Messages
+
+To verify a message we iterate over each of the bits from the message's hash and verify the segments revealed as the private key hash to the associated segments of the public key.
+
+```
+for idx in range(hash):
+ if hash[idx] == 0:
+ assert sha256sum(privateKey.first[idx]) == publicKey[idx]
+ if hash[idx] == 1:
+ assert sha256sum(privateKey.second[idx]) == publicKey[idx]
+```
+
+## Limitations
+
+- The keys for lamport signatures, along with the signatures themselves, are large
+ - public / private keys are 16kb
+ - signatures are 8kb
+- Keys should only be used once
+ - One iteration leaks half of the key
+ - Two iterations leaks ~3/4 of the keys
+ - Depending on the message being signed, even more segments may be revealed
+ - ...
+
+## Benefits
+
+- Simple to implement
+- Cheap to compute
+ - No large primes
+- Quantum resistant
+ - Impacted by grover's algorithm so expect 128 bits of security instead of 256 when facing quantum computers
+ - This is generally considered acceptable
+
+## Implementation
+
+
+```go
+
+package main
+
+import (
+ "crypto/rand"
+ "crypto/sha256"
+ "fmt"
+)
+
+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() {
+
+ publicKey, privateKey := GenerateKeys()
+ message := rand.Text()
+ signature := Sign(privateKey, message)
+ valid := Verify(publicKey, message, signature)
+ fmt.Printf("Verified message matches signature: %v\n", valid)
+
+}
+```
