Well, last time I researched various things about communication.
OK! this time, let’s think about the cipher that is probably used for communication!
Encryption is a reversible transformation
Encryption is, simply say, the conversion of strings. The thing created by the conversion can be restored by the work of decryption.
This kind of “reversible conversion” is called “reversible conversion”.
But being reversible is also a weakness.
Do you think it’s okay if you encrypt the string and save it?
Then I encrypted it. “me@medium.com, zkfNz, lczgdqwer”
It’s a big mistake if you think that you would not know the original string even if this leaks.
“It feels like I typed in the same stroke as the original character string by lowering the home position of the keyboard by one step.” When I got caught, “zkfNz, lczgdqwer = airHakodate1234” is the same end as before.
When you save your password in the database, don’t just encrypt it.
So it’s hashing
This also refers to converting a string to another string, like encryption. However, this is an “irreversible conversion”.
In other words, “medium1234” is converted to “asli3hLiuqywDG23howfa86oDFjf (this is random)”, but “asli3hLiuqywDG23howfa86oDFjf” cannot be converted back to “airHakodate1234”.
I recommend to use hashing for matters like the password above.
It is safe and secure because the original character string cannot be restored when it leaks.
What is hashing?
It is an irreversible conversion of a string using a hash function, a calculation that outputs a unique hash value for the input. (This expression is not very correct)
The hash function is SHA
SHA(Secure Hash Algorithm) is famous hash function.
This is used in various places such as communication and authentication.
Bitcoin wouldn’t be possible without it. To be correct, blockchain, the technology that supports Bitcoin from the root, is made up of SHA.
SHA has a version
The first version is called SHA-1, and it is rarely used anymore. Because a collision was found.
SHA-2 is the current mainstream hash function.
It feels like an enhanced version of SHA-1. The calculation method is quite similar.
SHA256 and SHA512 are often used.
And then SHA-3.
While SHA-1 and SHA-2 had similar algorithms, they took a completely different approach.
SHA-2 hasn’t been broken so far, so I’m still holding my breath.
The calculation method is open to the public. (FIPS180–4)
The strength is that even if you know the calculation method, you do not know the attack method.
Try implementing SHA256 with Go
Entire code:
package main
import (
"fmt"
"os"
)
func main() {
if len(os.Args) != 2 {
os.Exit(1)
}
// initial value of hash
H := []uint32{
0x6a09e667,
0xbb67ae85,
0x3c6ef372,
0xa54ff53a,
0x510e527f,
0x9b05688c,
0x1f83d9ab,
0x5be0cd19,
}
// K constant used for operation
k := []uint32{
0x428a2f98,
0x71374491,
0xb5c0fbcf,
0xe9b5dba5,
0x3956c25b,
0x59f111f1,
0x923f82a4,
0xab1c5ed5,
0xd807aa98,
0x12835b01,
0x243185be,
0x550c7dc3,
0x72be5d74,
0x80deb1fe,
0x9bdc06a7,
0xc19bf174,
0xe49b69c1,
0xefbe4786,
0x0fc19dc6,
0x240ca1cc,
0x2de92c6f,
0x4a7484aa,
0x5cb0a9dc,
0x76f988da,
0x983e5152,
0xa831c66d,
0xb00327c8,
0xbf597fc7,
0xc6e00bf3,
0xd5a79147,
0x06ca6351,
0x14292967,
0x27b70a85,
0x2e1b2138,
0x4d2c6dfc,
0x53380d13,
0x650a7354,
0x766a0abb,
0x81c2c92e,
0x92722c85,
0xa2bfe8a1,
0xa81a664b,
0xc24b8b70,
0xc76c51a3,
0xd192e819,
0xd6990624,
0xf40e3585,
0x106aa070,
0x19a4c116,
0x1e376c08,
0x2748774c,
0x34b0bcb5,
0x391c0cb3,
0x4ed8aa4a,
0x5b9cca4f,
0x682e6ff3,
0x748f82ee,
0x78a5636f,
0x84c87814,
0x8cc70208,
0x90befffa,
0xa4506ceb,
0xbef9a3f7,
0xc67178f2,
}
// Receiving input
input := []byte(os.Args[1])
// Padding process
pad := Padding(input, 64)
// Create a message block by dividing it into 64 bytes
msgblocks := Split(pad, 64)
for _, bl := range msgblocks {
// Create 64 word (uint32) array from message block
words := uint32Array(bl)
for i := 16; i < 64; i++ {
w := SmallSigma1(words[i-2]) + words[i-7] + SmallSigma0(words[i-15]) + words[i-16]
words = append(words, w)
}
// Initial value before rotation processing
a := H[0]
b := H[1]
c := H[2]
d := H[3]
e := H[4]
f := H[5]
g := H[6]
h := H[7]
// Rotation processing
for t, w := range words {
T1 := h + LargeSigma1(e) + Ch(e, f, g) + k[t] + w
T2 := LargeSigma0(a) + Maj(a, b, c)
h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1 + T2
}
// Updata hash value
H[0] = a + H[0]
H[1] = b + H[1]
H[2] = c + H[2]
H[3] = d + H[3]
H[4] = e + H[4]
H[5] = f + H[5]
H[6] = g + H[6]
H[7] = h + H[7]
// Next message block
}
// Display hash value
for _, h := range H {
fmt.Printf("%x", h)
}
}
// Make the input byte array a multiple of length
func Padding(input []byte, length int) []byte {
l := len(input)
bits := l * 8
mod := l % length
padcount := length - mod
if mod > length-8 {
padcount += 64
}
for i := 0; i < padcount; i++ {
if i == 0 {
// Put 0x80 as an input delimiter
input = append(input, 0x80)
} else {
// Others are filled with 0x00
input = append(input, 0x00)
}
}
// The last 8 bytes (uint64) are the number of bits in the input
for i := 1; i <= 8; i++ {
input[len(input)-i] = byte(bits & 0xff)
bits = bits >> 8
}
return input
}
// Divide the input byte array into length pieces
func Split(input []byte, length int) [][]byte {
var barr [][]byte
n := len(input) / length
for i := 0; i < n; i++ {
barr = append(barr, input[i*length:(i+1)*length])
}
return barr
}
// Convert byte array to uint32 array
func uint32Array(b []byte) []uint32 {
var arr []uint32
for i := 0; i < len(b)/4; i++ {
var v uint32
v += uint32(b[i*4]) << 24
v += uint32(b[i*4+1]) << 16
v += uint32(b[i*4+2]) << 8
v += uint32(b[i*4+3])
arr = append(arr, v)
}
return arr
}
func Ch(x, y, z uint32) uint32 {
return (x & y) ^ (^x & z)
}
func Maj(x, y, z uint32) uint32 {
return (x & y) ^ (x & z) ^ (y & z)
}
func SmallSigma0(x uint32) uint32 {
return Rotr(x, 7) ^ Rotr(x, 18) ^ Shr(x, 3)
}
func SmallSigma1(x uint32) uint32 {
return Rotr(x, 17) ^ Rotr(x, 19) ^ Shr(x, 10)
}
func LargeSigma0(x uint32) uint32 {
return Rotr(x, 2) ^ Rotr(x, 13) ^ Rotr(x, 22)
}
func LargeSigma1(x uint32) uint32 {
return Rotr(x, 6) ^ Rotr(x, 11) ^ Rotr(x, 25)
}
// Right rotation
func Rotr(x, n uint32) uint32 {
return x<<(32-n) | x>>n
}
// Right shift
func Shr(x, n uint32) uint32 {
return x >> n
}Let’s follow it little by little!
Initial value of hash H
H := []uint32{
0x6a09e667,
0xbb67ae85,
0x3c6ef372,
0xa54ff53a,
0x510e527f,
0x9b05688c,
0x1f83d9ab,
0x5be0cd19,
}The initial value of the hash.
We will change this value using the input byte array.
Constant K
k := []uint32{
0x428a2f98,
0x71374491,
0xb5c0fbcf,
0xe9b5dba5,
0x3956c25b,
0x59f111f1,
0x923f82a4,
0xab1c5ed5,
0xd807aa98,
0x12835b01,
0x243185be,
0x550c7dc3,
0x72be5d74,
0x80deb1fe,
0x9bdc06a7,
0xc19bf174,
0xe49b69c1,
0xefbe4786,
0x0fc19dc6,
0x240ca1cc,
0x2de92c6f,
0x4a7484aa,
0x5cb0a9dc,
0x76f988da,
0x983e5152,
0xa831c66d,
0xb00327c8,
0xbf597fc7,
0xc6e00bf3,
0xd5a79147,
0x06ca6351,
0x14292967,
0x27b70a85,
0x2e1b2138,
0x4d2c6dfc,
0x53380d13,
0x650a7354,
0x766a0abb,
0x81c2c92e,
0x92722c85,
0xa2bfe8a1,
0xa81a664b,
0xc24b8b70,
0xc76c51a3,
0xd192e819,
0xd6990624,
0xf40e3585,
0x106aa070,
0x19a4c116,
0x1e376c08,
0x2748774c,
0x34b0bcb5,
0x391c0cb3,
0x4ed8aa4a,
0x5b9cca4f,
0x682e6ff3,
0x748f82ee,
0x78a5636f,
0x84c87814,
0x8cc70208,
0x90befffa,
0xa4506ceb,
0xbef9a3f7,
0xc67178f2,
}A constant used for the operation.
Somehow it represents a minority part of the cube root of 64 prime numbers.
Functions required for operations
func Ch(x, y, z uint32) uint32 {
return (x & y) ^ (^x & z)
}
func Maj(x, y, z uint32) uint32 {
return (x & y) ^ (x & z) ^ (y & z)
}
// σ0
func SmallSigma0(x uint32) uint32 {
return Rotr(x, 7) ^ Rotr(x, 18) ^ Shr(x, 3)
}
// σ1
func SmallSigma1(x uint32) uint32 {
return Rotr(x, 17) ^ Rotr(x, 19) ^ Shr(x, 10)
}
// Σ0
func LargeSigma0(x uint32) uint32 {
return Rotr(x, 2) ^ Rotr(x, 13) ^ Rotr(x, 22)
}
// Σ1
func LargeSigma1(x uint32) uint32 {
return Rotr(x, 6) ^ Rotr(x, 11) ^ Rotr(x, 25)
}
// Right rotation
func Rotr(x, n uint32) uint32 {
return x<<(32-n) | x>>n
}
// Right shift
func Shr(x, n uint32) uint32 {
return x >> n
}I made it according to the specifications.
Go is easy and helpful in this area.
Receive input
input := []byte(os.Args[1])The received input (string) is cast to a byte array.
Padding process
// Padding process
pad := Padding(input, 64)
...
...
// Make the input byte array a multiple of length
func Padding(input []byte, length int) []byte {
l := len(input)
bits := l * 8
mod := l % length
padcount := length - mod
if mod > length-8 {
padcount += 64
}
for i := 0; i < padcount; i++ {
if i == 0 {
// Put 0x80 as an input delimiter
input = append(input, 0x80)
} else {
// Others are filled with 0x00
input = append(input, 0x00)
}
}
// The last 8 bytes (uint64) are the number of bits in the input
for i := 1; i <= 8; i++ {
input[len(input)-i] = byte(bits & 0xff)
bits = bits >> 8
}
return input
}If (9 bytes below input bytes +) is less than 64 bytes, fill it with 0x00 to make it 64 bytes. If it exceeds 64 bytes, adjust it so that it is (multiple of 64) bytes.
- Insert 0x80 immediately after input bytes
- Number of input bits with big endian in the last 8 bytes of the byte array (number of input bytes x 8 bits)
- If you enter “aiueo”, the byte array will be as follows.
[ 61 69 75 65 6f 80 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 28 ]0x80 is added immediately after 5 bytes of the input, and 0x28 = 40 is added to the end of the array because the input is 5 bytes = 40 bits. Others are filled with 0 to make an array of 64 bytes.
Divided into message blocks (64bytes)
// Create a message block by dividing it into 64 bytes
msgblocks := Split(pad, 64)
...
...
// Divide the input byte array into length pieces
func Split(input []byte, length int) [][]byte {
var barr [][]byte
n := len(input) / length
for i := 0; i < n; i++ {
barr = append(barr, input[i*length:(i+1)*length])
}
return barr
}Divides the padded message into an array of 64 bytes.
If the padded message is 128 bytes, there will be two message blocks.
“Aiueo” is one message block.
From here, we will calculate the hash value using each message block one by one.
Prepare message schedule
for _, bl := range msgblocks {
// Create 64 word (uint32) array (message schedule) from message block
words := uint32Array(bl)
for i := 16; i < 64; i++ {
w := SmallSigma1(words[i-2]) + words[i-7] + SmallSigma0(words[i-15]) + words[i-16]
words = append(words, w)
}
...
...
// Convert byte array to uint32 array
func uint32Array(b []byte) []uint32 {
var arr []uint32
for i := 0; i < len(b)/4; i++ {
var v uint32
v += uint32(b[i*4]) << 24
v += uint32(b[i*4+1]) << 16
v += uint32(b[i*4+2]) << 8
v += uint32(b[i*4+3])
arr = append(arr, v)
}
return arr
}Create a message schedule (uint32 x 64 = 256bytes) from the message block (64bytes).
First, convert the bytes array to a uint32 array.
Add values to the array using the specified calculation method until the number of elements reaches 64.
This is the message schedule.
Rotation processing
// Initial value before rotation processing
a := H[0]
b := H[1]
c := H[2]
d := H[3]
e := H[4]
f := H[5]
g := H[6]
h := H[7]
// Rotation process
for t, w := range words {
T1 := h + LargeSigma1(e) + Ch(e, f, g) + k[t] + w
T2 := LargeSigma0(a) + Maj(a, b, c)
h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1 + T2
}Initialize the values from a to h with the current hash value, and calculate with the words in the message schedule.
Since the values rotate like d = c, c = b, b = a…, it is called rotation processing. Since operations are added at a and e, it seems that the values of a to h gradually change.
From the left, it is the transition of the value of a b c d e f g h.
You can see that the same value runs diagonally.
6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19
5d71fdb2 6a09e667 bb67ae85 3c6ef372 fa315807 510e527f 9b05688c 1f83d9ab
91955bbe 5d71fdb2 6a09e667 bb67ae85 956a02f3 fa315807 510e527f 9b05688c
cc2250a4 91955bbe 5d71fdb2 6a09e667 178df70 956a02f3 fa315807 510e527f
e53564c2 cc2250a4 91955bbe 5d71fdb2 32a18b68 178df70 956a02f3 fa315807
65fad80f e53564c2 cc2250a4 91955bbe b36e0a0c 32a18b68 178df70 956a02f3
bd82bcd4 65fad80f e53564c2 cc2250a4 778023ca b36e0a0c 32a18b68 178df70
441088 bd82bcd4 65fad80f e53564c2 237d5290 778023ca b36e0a0c 32a18b68
f6b68649 441088 bd82bcd4 65fad80f 22162c7c 237d5290 778023ca b36e0a0c
c1a5a55f f6b68649 441088 bd82bcd4 dd1eb4aa 22162c7c 237d5290 778023ca
6a971132 c1a5a55f f6b68649 441088 1b732e41 dd1eb4aa 22162c7c 237d5290
28c85d94 6a971132 c1a5a55f f6b68649 f6e28f63 1b732e41 dd1eb4aa 22162c7c
d5ede739 28c85d94 6a971132 c1a5a55f 9c3a56e8 f6e28f63 1b732e41 dd1eb4aa
ad7ee204 d5ede739 28c85d94 6a971132 b2e003d 9c3a56e8 f6e28f63 1b732e41
6ca9dbc5 ad7ee204 d5ede739 28c85d94 68614420 b2e003d 9c3a56e8 f6e28f63
74632b10 6ca9dbc5 ad7ee204 d5ede739 8ccf9f92 68614420 b2e003d 9c3a56e8
7e87ce8c 74632b10 6ca9dbc5 ad7ee204 1ed2a2b5 8ccf9f92 68614420 b2e003d
a86b8e0f 7e87ce8c 74632b10 6ca9dbc5 644e6e28 1ed2a2b5 8ccf9f92 68614420
48e21029 a86b8e0f 7e87ce8c 74632b10 4c8bf64 644e6e28 1ed2a2b5 8ccf9f92
f25f26f2 48e21029 a86b8e0f 7e87ce8c a2ac5dbc 4c8bf64 644e6e28 1ed2a2b5
1afc3382 f25f26f2 48e21029 a86b8e0f b97d6b57 a2ac5dbc 4c8bf64 644e6e28
f0c85228 1afc3382 f25f26f2 48e21029 53d3da2b b97d6b57 a2ac5dbc 4c8bf64
16761b05 f0c85228 1afc3382 f25f26f2 e03ec781 53d3da2b b97d6b57 a2ac5dbc
57b3a142 16761b05 f0c85228 1afc3382 f13d940c e03ec781 53d3da2b b97d6b57
9813693c 57b3a142 16761b05 f0c85228 aa22d2b f13d940c e03ec781 53d3da2b
a54087b2 9813693c 57b3a142 16761b05 5d90c822 aa22d2b f13d940c e03ec781
40f9ef88 a54087b2 9813693c 57b3a142 2b80a7de 5d90c822 aa22d2b f13d940c
344e96f8 40f9ef88 a54087b2 9813693c 7fedeb54 2b80a7de 5d90c822 aa22d2b
32e13a3a 344e96f8 40f9ef88 a54087b2 262234a3 7fedeb54 2b80a7de 5d90c822
f67c454b 32e13a3a 344e96f8 40f9ef88 9151dcf9 262234a3 7fedeb54 2b80a7de
39fe2829 f67c454b 32e13a3a 344e96f8 1db673ce 9151dcf9 262234a3 7fedeb54
56ef4563 39fe2829 f67c454b 32e13a3a 60aad314 1db673ce 9151dcf9 262234a3
39bbe364 56ef4563 39fe2829 f67c454b b1e9ecba 60aad314 1db673ce 9151dcf9
68504e80 39bbe364 56ef4563 39fe2829 2a0a8c8a b1e9ecba 60aad314 1db673ce
5f63cd1 68504e80 39bbe364 56ef4563 97cbcd17 2a0a8c8a b1e9ecba 60aad314
899b87a7 5f63cd1 68504e80 39bbe364 379179b8 97cbcd17 2a0a8c8a b1e9ecba
1cc1314c 899b87a7 5f63cd1 68504e80 9b66d31c 379179b8 97cbcd17 2a0a8c8a
b06c2d19 1cc1314c 899b87a7 5f63cd1 8153abab 9b66d31c 379179b8 97cbcd17
af38c3b0 b06c2d19 1cc1314c 899b87a7 6802ec8e 8153abab 9b66d31c 379179b8
ba4a238e af38c3b0 b06c2d19 1cc1314c b237fe87 6802ec8e 8153abab 9b66d31c
b682aad4 ba4a238e af38c3b0 b06c2d19 7e72582d b237fe87 6802ec8e 8153abab
bb433f70 b682aad4 ba4a238e af38c3b0 3bf67c7b 7e72582d b237fe87 6802ec8e
b8c6635c bb433f70 b682aad4 ba4a238e d4142410 3bf67c7b 7e72582d b237fe87
3c6c0957 b8c6635c bb433f70 b682aad4 e9ad58a d4142410 3bf67c7b 7e72582d
9616c1c6 3c6c0957 b8c6635c bb433f70 5ecb8382 e9ad58a d4142410 3bf67c7b
9a7d5297 9616c1c6 3c6c0957 b8c6635c a8c43612 5ecb8382 e9ad58a d4142410
8b2aafc3 9a7d5297 9616c1c6 3c6c0957 1e0af822 a8c43612 5ecb8382 e9ad58a
671f9dac 8b2aafc3 9a7d5297 9616c1c6 d2e2e6b3 1e0af822 a8c43612 5ecb8382
ca557cd6 671f9dac 8b2aafc3 9a7d5297 4a5a310a d2e2e6b3 1e0af822 a8c43612
def4e40 ca557cd6 671f9dac 8b2aafc3 db7c8c5a 4a5a310a d2e2e6b3 1e0af822
7e1f0350 def4e40 ca557cd6 671f9dac eda79972 db7c8c5a 4a5a310a d2e2e6b3
45cfa22a 7e1f0350 def4e40 ca557cd6 e5867fb2 eda79972 db7c8c5a 4a5a310a
bc3df39 45cfa22a 7e1f0350 def4e40 c9a0e9ef e5867fb2 eda79972 db7c8c5a
ce4eabfd bc3df39 45cfa22a 7e1f0350 d82a2906 c9a0e9ef e5867fb2 eda79972
e5e6ece6 ce4eabfd bc3df39 45cfa22a fd64154a d82a2906 c9a0e9ef e5867fb2
253fd2c7 e5e6ece6 ce4eabfd bc3df39 554b755b fd64154a d82a2906 c9a0e9ef
6d2b1770 253fd2c7 e5e6ece6 ce4eabfd f34249e7 554b755b fd64154a d82a2906
3aeedb2e 6d2b1770 253fd2c7 e5e6ece6 97794315 f34249e7 554b755b fd64154a
6e11a3a 3aeedb2e 6d2b1770 253fd2c7 d2f15a64 97794315 f34249e7 554b755b
63fe16a5 6e11a3a 3aeedb2e 6d2b1770 86523495 d2f15a64 97794315 f34249e7
ce0b482e 63fe16a5 6e11a3a 3aeedb2e 2ba359a 86523495 d2f15a64 97794315
a2844a3f ce0b482e 63fe16a5 6e11a3a b6b3f1d6 2ba359a 86523495 d2f15a64
1a1a19d6 a2844a3f ce0b482e 63fe16a5 95f7f1ba b6b3f1d6 2ba359a 86523495
35c33dbe 1a1a19d6 a2844a3f ce0b482e ef65fd58 95f7f1ba b6b3f1d6 2ba359a
8ffcac06 35c33dbe 1a1a19d6 a2844a3f bf0e40d5 ef65fd58 95f7f1ba b6b3f1d6Hash value update
// Hash value update
H[0] = a + H[0]
H[1] = b + H[1]
H[2] = c + H[2]
H[3] = d + H[3]
H[4] = e + H[4]
H[5] = f + H[5]
H[6] = g + H[6]
H[7] = h + H[7]
// Next message block
}Add a to h calculated by rotation processing to H [0 to 7], and do the same for the next message block.
Output!!
// Output hash value
for _, h := range H {
fmt.Printf("%x", h)
}The hash value updated by the rotation processing in all message blocks is output in hexadecimal.
If the input is “aiueo”, “fa06926df12aec4356890d4847d43f79101c93548a6b65e4b57bcb651294beef” will be output, and it is completed.
Happy coding!
