← Back to branch summary

~nskaggs/+junk/xenial-test

« back to all changes in this revision

Viewing changes to src/golang.org/x/crypto/twofish/twofish.go

  • Committer: Nicholas Skaggs
  • Date: 2016-10-24 20:56:05 UTC
  • Revision ID: nicholas.skaggs@canonical.com-20161024205605-z8lta0uvuhtxwzwl
Initi with beta15

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/golang.org/x/crypto/twofish/twofish.go
 
1
// Copyright 2011 The Go Authors. All rights reserved.
 
2
// Use of this source code is governed by a BSD-style
 
3
// license that can be found in the LICENSE file.
 
4
 
 
5
// Package twofish implements Bruce Schneier's Twofish encryption algorithm.
 
6
package twofish // import "golang.org/x/crypto/twofish"
 
7
 
 
8
// Twofish is defined in http://www.schneier.com/paper-twofish-paper.pdf [TWOFISH]
 
9
 
 
10
// This code is a port of the LibTom C implementation.
 
11
// See http://libtom.org/?page=features&newsitems=5&whatfile=crypt.
 
12
// LibTomCrypt is free for all purposes under the public domain.
 
13
// It was heavily inspired by the go blowfish package.
 
14
 
 
15
import "strconv"
 
16
 
 
17
// BlockSize is the constant block size of Twofish.
 
18
const BlockSize = 16
 
19
 
 
20
const mdsPolynomial = 0x169 // x^8 + x^6 + x^5 + x^3 + 1, see [TWOFISH] 4.2
 
21
const rsPolynomial = 0x14d  // x^8 + x^6 + x^3 + x^2 + 1, see [TWOFISH] 4.3
 
22
 
 
23
// A Cipher is an instance of Twofish encryption using a particular key.
 
24
type Cipher struct {
 
25
        s [4][256]uint32
 
26
        k [40]uint32
 
27
}
 
28
 
 
29
type KeySizeError int
 
30
 
 
31
func (k KeySizeError) Error() string {
 
32
        return "crypto/twofish: invalid key size " + strconv.Itoa(int(k))
 
33
}
 
34
 
 
35
// NewCipher creates and returns a Cipher.
 
36
// The key argument should be the Twofish key, 16, 24 or 32 bytes.
 
37
func NewCipher(key []byte) (*Cipher, error) {
 
38
        keylen := len(key)
 
39
 
 
40
        if keylen != 16 && keylen != 24 && keylen != 32 {
 
41
                return nil, KeySizeError(keylen)
 
42
        }
 
43
 
 
44
        // k is the number of 64 bit words in key
 
45
        k := keylen / 8
 
46
 
 
47
        // Create the S[..] words
 
48
        var S [4 * 4]byte
 
49
        for i := 0; i < k; i++ {
 
50
                // Computes [y0 y1 y2 y3] = rs . [x0 x1 x2 x3 x4 x5 x6 x7]
 
51
                for j, rsRow := range rs {
 
52
                        for k, rsVal := range rsRow {
 
53
                                S[4*i+j] ^= gfMult(key[8*i+k], rsVal, rsPolynomial)
 
54
                        }
 
55
                }
 
56
        }
 
57
 
 
58
        // Calculate subkeys
 
59
        c := new(Cipher)
 
60
        var tmp [4]byte
 
61
        for i := byte(0); i < 20; i++ {
 
62
                // A = h(p * 2x, Me)
 
63
                for j := range tmp {
 
64
                        tmp[j] = 2 * i
 
65
                }
 
66
                A := h(tmp[:], key, 0)
 
67
 
 
68
                // B = rolc(h(p * (2x + 1), Mo), 8)
 
69
                for j := range tmp {
 
70
                        tmp[j] = 2*i + 1
 
71
                }
 
72
                B := h(tmp[:], key, 1)
 
73
                B = rol(B, 8)
 
74
 
 
75
                c.k[2*i] = A + B
 
76
 
 
77
                // K[2i+1] = (A + 2B) <<< 9
 
78
                c.k[2*i+1] = rol(2*B+A, 9)
 
79
        }
 
80
 
 
81
        // Calculate sboxes
 
82
        switch k {
 
83
        case 2:
 
84
                for i := range c.s[0] {
 
85
                        c.s[0][i] = mdsColumnMult(sbox[1][sbox[0][sbox[0][byte(i)]^S[0]]^S[4]], 0)
 
86
                        c.s[1][i] = mdsColumnMult(sbox[0][sbox[0][sbox[1][byte(i)]^S[1]]^S[5]], 1)
 
87
                        c.s[2][i] = mdsColumnMult(sbox[1][sbox[1][sbox[0][byte(i)]^S[2]]^S[6]], 2)
 
88
                        c.s[3][i] = mdsColumnMult(sbox[0][sbox[1][sbox[1][byte(i)]^S[3]]^S[7]], 3)
 
89
                }
 
90
        case 3:
 
91
                for i := range c.s[0] {
 
92
                        c.s[0][i] = mdsColumnMult(sbox[1][sbox[0][sbox[0][sbox[1][byte(i)]^S[0]]^S[4]]^S[8]], 0)
 
93
                        c.s[1][i] = mdsColumnMult(sbox[0][sbox[0][sbox[1][sbox[1][byte(i)]^S[1]]^S[5]]^S[9]], 1)
 
94
                        c.s[2][i] = mdsColumnMult(sbox[1][sbox[1][sbox[0][sbox[0][byte(i)]^S[2]]^S[6]]^S[10]], 2)
 
95
                        c.s[3][i] = mdsColumnMult(sbox[0][sbox[1][sbox[1][sbox[0][byte(i)]^S[3]]^S[7]]^S[11]], 3)
 
96
                }
 
97
        default:
 
98
                for i := range c.s[0] {
 
99
                        c.s[0][i] = mdsColumnMult(sbox[1][sbox[0][sbox[0][sbox[1][sbox[1][byte(i)]^S[0]]^S[4]]^S[8]]^S[12]], 0)
 
100
                        c.s[1][i] = mdsColumnMult(sbox[0][sbox[0][sbox[1][sbox[1][sbox[0][byte(i)]^S[1]]^S[5]]^S[9]]^S[13]], 1)
 
101
                        c.s[2][i] = mdsColumnMult(sbox[1][sbox[1][sbox[0][sbox[0][sbox[0][byte(i)]^S[2]]^S[6]]^S[10]]^S[14]], 2)
 
102
                        c.s[3][i] = mdsColumnMult(sbox[0][sbox[1][sbox[1][sbox[0][sbox[1][byte(i)]^S[3]]^S[7]]^S[11]]^S[15]], 3)
 
103
                }
 
104
        }
 
105
 
 
106
        return c, nil
 
107
}
 
108
 
 
109
// BlockSize returns the Twofish block size, 16 bytes.
 
110
func (c *Cipher) BlockSize() int { return BlockSize }
 
111
 
 
112
// store32l stores src in dst in little-endian form.
 
113
func store32l(dst []byte, src uint32) {
 
114
        dst[0] = byte(src)
 
115
        dst[1] = byte(src >> 8)
 
116
        dst[2] = byte(src >> 16)
 
117
        dst[3] = byte(src >> 24)
 
118
        return
 
119
}
 
120
 
 
121
// load32l reads a little-endian uint32 from src.
 
122
func load32l(src []byte) uint32 {
 
123
        return uint32(src[0]) | uint32(src[1])<<8 | uint32(src[2])<<16 | uint32(src[3])<<24
 
124
}
 
125
 
 
126
// rol returns x after a left circular rotation of y bits.
 
127
func rol(x, y uint32) uint32 {
 
128
        return (x << (y & 31)) | (x >> (32 - (y & 31)))
 
129
}
 
130
 
 
131
// ror returns x after a right circular rotation of y bits.
 
132
func ror(x, y uint32) uint32 {
 
133
        return (x >> (y & 31)) | (x << (32 - (y & 31)))
 
134
}
 
135
 
 
136
// The RS matrix. See [TWOFISH] 4.3
 
137
var rs = [4][8]byte{
 
138
        {0x01, 0xA4, 0x55, 0x87, 0x5A, 0x58, 0xDB, 0x9E},
 
139
        {0xA4, 0x56, 0x82, 0xF3, 0x1E, 0xC6, 0x68, 0xE5},
 
140
        {0x02, 0xA1, 0xFC, 0xC1, 0x47, 0xAE, 0x3D, 0x19},
 
141
        {0xA4, 0x55, 0x87, 0x5A, 0x58, 0xDB, 0x9E, 0x03},
 
142
}
 
143
 
 
144
// sbox tables
 
145
var sbox = [2][256]byte{
 
146
        {
 
147
                0xa9, 0x67, 0xb3, 0xe8, 0x04, 0xfd, 0xa3, 0x76, 0x9a, 0x92, 0x80, 0x78, 0xe4, 0xdd, 0xd1, 0x38,
 
148
                0x0d, 0xc6, 0x35, 0x98, 0x18, 0xf7, 0xec, 0x6c, 0x43, 0x75, 0x37, 0x26, 0xfa, 0x13, 0x94, 0x48,
 
149
                0xf2, 0xd0, 0x8b, 0x30, 0x84, 0x54, 0xdf, 0x23, 0x19, 0x5b, 0x3d, 0x59, 0xf3, 0xae, 0xa2, 0x82,
 
150
                0x63, 0x01, 0x83, 0x2e, 0xd9, 0x51, 0x9b, 0x7c, 0xa6, 0xeb, 0xa5, 0xbe, 0x16, 0x0c, 0xe3, 0x61,
 
151
                0xc0, 0x8c, 0x3a, 0xf5, 0x73, 0x2c, 0x25, 0x0b, 0xbb, 0x4e, 0x89, 0x6b, 0x53, 0x6a, 0xb4, 0xf1,
 
152
                0xe1, 0xe6, 0xbd, 0x45, 0xe2, 0xf4, 0xb6, 0x66, 0xcc, 0x95, 0x03, 0x56, 0xd4, 0x1c, 0x1e, 0xd7,
 
153
                0xfb, 0xc3, 0x8e, 0xb5, 0xe9, 0xcf, 0xbf, 0xba, 0xea, 0x77, 0x39, 0xaf, 0x33, 0xc9, 0x62, 0x71,
 
154
                0x81, 0x79, 0x09, 0xad, 0x24, 0xcd, 0xf9, 0xd8, 0xe5, 0xc5, 0xb9, 0x4d, 0x44, 0x08, 0x86, 0xe7,
 
155
                0xa1, 0x1d, 0xaa, 0xed, 0x06, 0x70, 0xb2, 0xd2, 0x41, 0x7b, 0xa0, 0x11, 0x31, 0xc2, 0x27, 0x90,
 
156
                0x20, 0xf6, 0x60, 0xff, 0x96, 0x5c, 0xb1, 0xab, 0x9e, 0x9c, 0x52, 0x1b, 0x5f, 0x93, 0x0a, 0xef,
 
157
                0x91, 0x85, 0x49, 0xee, 0x2d, 0x4f, 0x8f, 0x3b, 0x47, 0x87, 0x6d, 0x46, 0xd6, 0x3e, 0x69, 0x64,
 
158
                0x2a, 0xce, 0xcb, 0x2f, 0xfc, 0x97, 0x05, 0x7a, 0xac, 0x7f, 0xd5, 0x1a, 0x4b, 0x0e, 0xa7, 0x5a,
 
159
                0x28, 0x14, 0x3f, 0x29, 0x88, 0x3c, 0x4c, 0x02, 0xb8, 0xda, 0xb0, 0x17, 0x55, 0x1f, 0x8a, 0x7d,
 
160
                0x57, 0xc7, 0x8d, 0x74, 0xb7, 0xc4, 0x9f, 0x72, 0x7e, 0x15, 0x22, 0x12, 0x58, 0x07, 0x99, 0x34,
 
161
                0x6e, 0x50, 0xde, 0x68, 0x65, 0xbc, 0xdb, 0xf8, 0xc8, 0xa8, 0x2b, 0x40, 0xdc, 0xfe, 0x32, 0xa4,
 
162
                0xca, 0x10, 0x21, 0xf0, 0xd3, 0x5d, 0x0f, 0x00, 0x6f, 0x9d, 0x36, 0x42, 0x4a, 0x5e, 0xc1, 0xe0,
 
163
        },
 
164
        {
 
165
                0x75, 0xf3, 0xc6, 0xf4, 0xdb, 0x7b, 0xfb, 0xc8, 0x4a, 0xd3, 0xe6, 0x6b, 0x45, 0x7d, 0xe8, 0x4b,
 
166
                0xd6, 0x32, 0xd8, 0xfd, 0x37, 0x71, 0xf1, 0xe1, 0x30, 0x0f, 0xf8, 0x1b, 0x87, 0xfa, 0x06, 0x3f,
 
167
                0x5e, 0xba, 0xae, 0x5b, 0x8a, 0x00, 0xbc, 0x9d, 0x6d, 0xc1, 0xb1, 0x0e, 0x80, 0x5d, 0xd2, 0xd5,
 
168
                0xa0, 0x84, 0x07, 0x14, 0xb5, 0x90, 0x2c, 0xa3, 0xb2, 0x73, 0x4c, 0x54, 0x92, 0x74, 0x36, 0x51,
 
169
                0x38, 0xb0, 0xbd, 0x5a, 0xfc, 0x60, 0x62, 0x96, 0x6c, 0x42, 0xf7, 0x10, 0x7c, 0x28, 0x27, 0x8c,
 
170
                0x13, 0x95, 0x9c, 0xc7, 0x24, 0x46, 0x3b, 0x70, 0xca, 0xe3, 0x85, 0xcb, 0x11, 0xd0, 0x93, 0xb8,
 
171
                0xa6, 0x83, 0x20, 0xff, 0x9f, 0x77, 0xc3, 0xcc, 0x03, 0x6f, 0x08, 0xbf, 0x40, 0xe7, 0x2b, 0xe2,
 
172
                0x79, 0x0c, 0xaa, 0x82, 0x41, 0x3a, 0xea, 0xb9, 0xe4, 0x9a, 0xa4, 0x97, 0x7e, 0xda, 0x7a, 0x17,
 
173
                0x66, 0x94, 0xa1, 0x1d, 0x3d, 0xf0, 0xde, 0xb3, 0x0b, 0x72, 0xa7, 0x1c, 0xef, 0xd1, 0x53, 0x3e,
 
174
                0x8f, 0x33, 0x26, 0x5f, 0xec, 0x76, 0x2a, 0x49, 0x81, 0x88, 0xee, 0x21, 0xc4, 0x1a, 0xeb, 0xd9,
 
175
                0xc5, 0x39, 0x99, 0xcd, 0xad, 0x31, 0x8b, 0x01, 0x18, 0x23, 0xdd, 0x1f, 0x4e, 0x2d, 0xf9, 0x48,
 
176
                0x4f, 0xf2, 0x65, 0x8e, 0x78, 0x5c, 0x58, 0x19, 0x8d, 0xe5, 0x98, 0x57, 0x67, 0x7f, 0x05, 0x64,
 
177
                0xaf, 0x63, 0xb6, 0xfe, 0xf5, 0xb7, 0x3c, 0xa5, 0xce, 0xe9, 0x68, 0x44, 0xe0, 0x4d, 0x43, 0x69,
 
178
                0x29, 0x2e, 0xac, 0x15, 0x59, 0xa8, 0x0a, 0x9e, 0x6e, 0x47, 0xdf, 0x34, 0x35, 0x6a, 0xcf, 0xdc,
 
179
                0x22, 0xc9, 0xc0, 0x9b, 0x89, 0xd4, 0xed, 0xab, 0x12, 0xa2, 0x0d, 0x52, 0xbb, 0x02, 0x2f, 0xa9,
 
180
                0xd7, 0x61, 0x1e, 0xb4, 0x50, 0x04, 0xf6, 0xc2, 0x16, 0x25, 0x86, 0x56, 0x55, 0x09, 0xbe, 0x91,
 
181
        },
 
182
}
 
183
 
 
184
// gfMult returns a·b in GF(2^8)/p
 
185
func gfMult(a, b byte, p uint32) byte {
 
186
        B := [2]uint32{0, uint32(b)}
 
187
        P := [2]uint32{0, p}
 
188
        var result uint32
 
189
 
 
190
        // branchless GF multiplier
 
191
        for i := 0; i < 7; i++ {
 
192
                result ^= B[a&1]
 
193
                a >>= 1
 
194
                B[1] = P[B[1]>>7] ^ (B[1] << 1)
 
195
        }
 
196
        result ^= B[a&1]
 
197
        return byte(result)
 
198
}
 
199
 
 
200
// mdsColumnMult calculates y{col} where [y0 y1 y2 y3] = MDS · [x0]
 
201
func mdsColumnMult(in byte, col int) uint32 {
 
202
        mul01 := in
 
203
        mul5B := gfMult(in, 0x5B, mdsPolynomial)
 
204
        mulEF := gfMult(in, 0xEF, mdsPolynomial)
 
205
 
 
206
        switch col {
 
207
        case 0:
 
208
                return uint32(mul01) | uint32(mul5B)<<8 | uint32(mulEF)<<16 | uint32(mulEF)<<24
 
209
        case 1:
 
210
                return uint32(mulEF) | uint32(mulEF)<<8 | uint32(mul5B)<<16 | uint32(mul01)<<24
 
211
        case 2:
 
212
                return uint32(mul5B) | uint32(mulEF)<<8 | uint32(mul01)<<16 | uint32(mulEF)<<24
 
213
        case 3:
 
214
                return uint32(mul5B) | uint32(mul01)<<8 | uint32(mulEF)<<16 | uint32(mul5B)<<24
 
215
        }
 
216
 
 
217
        panic("unreachable")
 
218
}
 
219
 
 
220
// h implements the S-box generation function. See [TWOFISH] 4.3.5
 
221
func h(in, key []byte, offset int) uint32 {
 
222
        var y [4]byte
 
223
        for x := range y {
 
224
                y[x] = in[x]
 
225
        }
 
226
        switch len(key) / 8 {
 
227
        case 4:
 
228
                y[0] = sbox[1][y[0]] ^ key[4*(6+offset)+0]
 
229
                y[1] = sbox[0][y[1]] ^ key[4*(6+offset)+1]
 
230
                y[2] = sbox[0][y[2]] ^ key[4*(6+offset)+2]
 
231
                y[3] = sbox[1][y[3]] ^ key[4*(6+offset)+3]
 
232
                fallthrough
 
233
        case 3:
 
234
                y[0] = sbox[1][y[0]] ^ key[4*(4+offset)+0]
 
235
                y[1] = sbox[1][y[1]] ^ key[4*(4+offset)+1]
 
236
                y[2] = sbox[0][y[2]] ^ key[4*(4+offset)+2]
 
237
                y[3] = sbox[0][y[3]] ^ key[4*(4+offset)+3]
 
238
                fallthrough
 
239
        case 2:
 
240
                y[0] = sbox[1][sbox[0][sbox[0][y[0]]^key[4*(2+offset)+0]]^key[4*(0+offset)+0]]
 
241
                y[1] = sbox[0][sbox[0][sbox[1][y[1]]^key[4*(2+offset)+1]]^key[4*(0+offset)+1]]
 
242
                y[2] = sbox[1][sbox[1][sbox[0][y[2]]^key[4*(2+offset)+2]]^key[4*(0+offset)+2]]
 
243
                y[3] = sbox[0][sbox[1][sbox[1][y[3]]^key[4*(2+offset)+3]]^key[4*(0+offset)+3]]
 
244
        }
 
245
        // [y0 y1 y2 y3] = MDS . [x0 x1 x2 x3]
 
246
        var mdsMult uint32
 
247
        for i := range y {
 
248
                mdsMult ^= mdsColumnMult(y[i], i)
 
249
        }
 
250
        return mdsMult
 
251
}
 
252
 
 
253
// Encrypt encrypts a 16-byte block from src to dst, which may overlap.
 
254
// Note that for amounts of data larger than a block,
 
255
// it is not safe to just call Encrypt on successive blocks;
 
256
// instead, use an encryption mode like CBC (see crypto/cipher/cbc.go).
 
257
func (c *Cipher) Encrypt(dst, src []byte) {
 
258
        S1 := c.s[0]
 
259
        S2 := c.s[1]
 
260
        S3 := c.s[2]
 
261
        S4 := c.s[3]
 
262
 
 
263
        // Load input
 
264
        ia := load32l(src[0:4])
 
265
        ib := load32l(src[4:8])
 
266
        ic := load32l(src[8:12])
 
267
        id := load32l(src[12:16])
 
268
 
 
269
        // Pre-whitening
 
270
        ia ^= c.k[0]
 
271
        ib ^= c.k[1]
 
272
        ic ^= c.k[2]
 
273
        id ^= c.k[3]
 
274
 
 
275
        for i := 0; i < 8; i++ {
 
276
                k := c.k[8+i*4 : 12+i*4]
 
277
                t2 := S2[byte(ib)] ^ S3[byte(ib>>8)] ^ S4[byte(ib>>16)] ^ S1[byte(ib>>24)]
 
278
                t1 := S1[byte(ia)] ^ S2[byte(ia>>8)] ^ S3[byte(ia>>16)] ^ S4[byte(ia>>24)] + t2
 
279
                ic = ror(ic^(t1+k[0]), 1)
 
280
                id = rol(id, 1) ^ (t2 + t1 + k[1])
 
281
 
 
282
                t2 = S2[byte(id)] ^ S3[byte(id>>8)] ^ S4[byte(id>>16)] ^ S1[byte(id>>24)]
 
283
                t1 = S1[byte(ic)] ^ S2[byte(ic>>8)] ^ S3[byte(ic>>16)] ^ S4[byte(ic>>24)] + t2
 
284
                ia = ror(ia^(t1+k[2]), 1)
 
285
                ib = rol(ib, 1) ^ (t2 + t1 + k[3])
 
286
        }
 
287
 
 
288
        // Output with "undo last swap"
 
289
        ta := ic ^ c.k[4]
 
290
        tb := id ^ c.k[5]
 
291
        tc := ia ^ c.k[6]
 
292
        td := ib ^ c.k[7]
 
293
 
 
294
        store32l(dst[0:4], ta)
 
295
        store32l(dst[4:8], tb)
 
296
        store32l(dst[8:12], tc)
 
297
        store32l(dst[12:16], td)
 
298
}
 
299
 
 
300
// Decrypt decrypts a 16-byte block from src to dst, which may overlap.
 
301
func (c *Cipher) Decrypt(dst, src []byte) {
 
302
        S1 := c.s[0]
 
303
        S2 := c.s[1]
 
304
        S3 := c.s[2]
 
305
        S4 := c.s[3]
 
306
 
 
307
        // Load input
 
308
        ta := load32l(src[0:4])
 
309
        tb := load32l(src[4:8])
 
310
        tc := load32l(src[8:12])
 
311
        td := load32l(src[12:16])
 
312
 
 
313
        // Undo undo final swap
 
314
        ia := tc ^ c.k[6]
 
315
        ib := td ^ c.k[7]
 
316
        ic := ta ^ c.k[4]
 
317
        id := tb ^ c.k[5]
 
318
 
 
319
        for i := 8; i > 0; i-- {
 
320
                k := c.k[4+i*4 : 8+i*4]
 
321
                t2 := S2[byte(id)] ^ S3[byte(id>>8)] ^ S4[byte(id>>16)] ^ S1[byte(id>>24)]
 
322
                t1 := S1[byte(ic)] ^ S2[byte(ic>>8)] ^ S3[byte(ic>>16)] ^ S4[byte(ic>>24)] + t2
 
323
                ia = rol(ia, 1) ^ (t1 + k[2])
 
324
                ib = ror(ib^(t2+t1+k[3]), 1)
 
325
 
 
326
                t2 = S2[byte(ib)] ^ S3[byte(ib>>8)] ^ S4[byte(ib>>16)] ^ S1[byte(ib>>24)]
 
327
                t1 = S1[byte(ia)] ^ S2[byte(ia>>8)] ^ S3[byte(ia>>16)] ^ S4[byte(ia>>24)] + t2
 
328
                ic = rol(ic, 1) ^ (t1 + k[0])
 
329
                id = ror(id^(t2+t1+k[1]), 1)
 
330
        }
 
331
 
 
332
        // Undo pre-whitening
 
333
        ia ^= c.k[0]
 
334
        ib ^= c.k[1]
 
335
        ic ^= c.k[2]
 
336
        id ^= c.k[3]
 
337
 
 
338
        store32l(dst[0:4], ia)
 
339
        store32l(dst[4:8], ib)
 
340
        store32l(dst[8:12], ic)
 
341
        store32l(dst[12:16], id)
 
342
}