I've got stuck with ex4.1 for the book which says:
Write a function that counts the number of bits that are different in two SHA256 hashes.
The partial solution I came up with is pasted below, but it's wrong - it counts number of different bytes not bits. Could you please point me in the right direction?
package main
import (
"crypto/sha256"
"fmt"
)
var s1 string = "unodostresquatro"
var s2 string = "UNODOSTRESQUATRO"
var h1 = sha256.Sum256([]byte(s1))
var h2 = sha256.Sum256([]byte(s2))
func main() {
fmt.Printf("s1: %s h1: %X h1 type: %T
", s1, h1, h1)
fmt.Printf("s2: %s h2: %X h2 type: %T
", s2, h2, h2)
fmt.Printf("Number of different bits: %d
", 8 * DifferentBits(h1, h2))
}
func DifferentBits(c1 [32]uint8, c2 [32]uint8) int {
var counter int
for x := range c1 {
if c1[x] != c2[x] {
counter += 1
}
}
return counter
}
Alan A. A. Donovan · Brian W.Kernighan
Exercise 4.1: Write a function that counts the number of bits that are different in two SHA256 hashes.
Brian W.Kernighan · Dennis M. Ritchie
Exercise 2-9. In a two's complement number system,
x &= (x-1)deletes the rightmost 1-bit inx. Use this observation to write a faster version ofbitcount.
Sean Eron Anderson
Counting bits set, Brian Kernighan's way
unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set }
For exercise 4.1, you are counting the number of bytes that are different. Count the number of bits that are different. For example,
package main
import (
"crypto/sha256"
"fmt"
)
func BitsDifference(h1, h2 *[sha256.Size]byte) int {
n := 0
for i := range h1 {
for b := h1[i] ^ h2[i]; b != 0; b &= b - 1 {
n++
}
}
return n
}
func main() {
s1 := "unodostresquatro"
s2 := "UNODOSTRESQUATRO"
h1 := sha256.Sum256([]byte(s1))
h2 := sha256.Sum256([]byte(s2))
fmt.Println(BitsDifference(&h1, &h2))
}
Output:
139
Here is how I would do it
package main
import (
"crypto/sha256"
"fmt"
)
var (
s1 string = "unodostresquatro"
s2 string = "UNODOSTRESQUATRO"
h1 = sha256.Sum256([]byte(s1))
h2 = sha256.Sum256([]byte(s2))
)
func main() {
fmt.Printf("s1: %s h1: %X h1 type: %T
", s1, h1, h1)
fmt.Printf("s2: %s h2: %X h2 type: %T
", s2, h2, h2)
fmt.Printf("Number of different bits: %d
", DifferentBits(h1, h2))
}
// bitCount counts the number of bits set in x
func bitCount(x uint8) int {
count := 0
for x != 0 {
x &= x - 1
count++
}
return count
}
func DifferentBits(c1 [32]uint8, c2 [32]uint8) int {
var counter int
for x := range c1 {
counter += bitCount(c1[x] ^ c2[x])
}
return counter
}