1// Copyright 2012 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 5package poly1305 6 7import "encoding/binary" 8 9// sumGeneric generates an authenticator for msg using a one-time key and 10// puts the 16-byte result into out. This is the generic implementation of 11// Sum and should be called if no assembly implementation is available. 12func sumGeneric(out *[TagSize]byte, msg []byte, key *[32]byte) { 13 var ( 14 h0, h1, h2, h3, h4 uint32 // the hash accumulators 15 r0, r1, r2, r3, r4 uint64 // the r part of the key 16 ) 17 18 r0 = uint64(binary.LittleEndian.Uint32(key[0:]) & 0x3ffffff) 19 r1 = uint64((binary.LittleEndian.Uint32(key[3:]) >> 2) & 0x3ffff03) 20 r2 = uint64((binary.LittleEndian.Uint32(key[6:]) >> 4) & 0x3ffc0ff) 21 r3 = uint64((binary.LittleEndian.Uint32(key[9:]) >> 6) & 0x3f03fff) 22 r4 = uint64((binary.LittleEndian.Uint32(key[12:]) >> 8) & 0x00fffff) 23 24 R1, R2, R3, R4 := r1*5, r2*5, r3*5, r4*5 25 26 for len(msg) >= TagSize { 27 // h += msg 28 h0 += binary.LittleEndian.Uint32(msg[0:]) & 0x3ffffff 29 h1 += (binary.LittleEndian.Uint32(msg[3:]) >> 2) & 0x3ffffff 30 h2 += (binary.LittleEndian.Uint32(msg[6:]) >> 4) & 0x3ffffff 31 h3 += (binary.LittleEndian.Uint32(msg[9:]) >> 6) & 0x3ffffff 32 h4 += (binary.LittleEndian.Uint32(msg[12:]) >> 8) | (1 << 24) 33 34 // h *= r 35 d0 := (uint64(h0) * r0) + (uint64(h1) * R4) + (uint64(h2) * R3) + (uint64(h3) * R2) + (uint64(h4) * R1) 36 d1 := (d0 >> 26) + (uint64(h0) * r1) + (uint64(h1) * r0) + (uint64(h2) * R4) + (uint64(h3) * R3) + (uint64(h4) * R2) 37 d2 := (d1 >> 26) + (uint64(h0) * r2) + (uint64(h1) * r1) + (uint64(h2) * r0) + (uint64(h3) * R4) + (uint64(h4) * R3) 38 d3 := (d2 >> 26) + (uint64(h0) * r3) + (uint64(h1) * r2) + (uint64(h2) * r1) + (uint64(h3) * r0) + (uint64(h4) * R4) 39 d4 := (d3 >> 26) + (uint64(h0) * r4) + (uint64(h1) * r3) + (uint64(h2) * r2) + (uint64(h3) * r1) + (uint64(h4) * r0) 40 41 // h %= p 42 h0 = uint32(d0) & 0x3ffffff 43 h1 = uint32(d1) & 0x3ffffff 44 h2 = uint32(d2) & 0x3ffffff 45 h3 = uint32(d3) & 0x3ffffff 46 h4 = uint32(d4) & 0x3ffffff 47 48 h0 += uint32(d4>>26) * 5 49 h1 += h0 >> 26 50 h0 = h0 & 0x3ffffff 51 52 msg = msg[TagSize:] 53 } 54 55 if len(msg) > 0 { 56 var block [TagSize]byte 57 off := copy(block[:], msg) 58 block[off] = 0x01 59 60 // h += msg 61 h0 += binary.LittleEndian.Uint32(block[0:]) & 0x3ffffff 62 h1 += (binary.LittleEndian.Uint32(block[3:]) >> 2) & 0x3ffffff 63 h2 += (binary.LittleEndian.Uint32(block[6:]) >> 4) & 0x3ffffff 64 h3 += (binary.LittleEndian.Uint32(block[9:]) >> 6) & 0x3ffffff 65 h4 += (binary.LittleEndian.Uint32(block[12:]) >> 8) 66 67 // h *= r 68 d0 := (uint64(h0) * r0) + (uint64(h1) * R4) + (uint64(h2) * R3) + (uint64(h3) * R2) + (uint64(h4) * R1) 69 d1 := (d0 >> 26) + (uint64(h0) * r1) + (uint64(h1) * r0) + (uint64(h2) * R4) + (uint64(h3) * R3) + (uint64(h4) * R2) 70 d2 := (d1 >> 26) + (uint64(h0) * r2) + (uint64(h1) * r1) + (uint64(h2) * r0) + (uint64(h3) * R4) + (uint64(h4) * R3) 71 d3 := (d2 >> 26) + (uint64(h0) * r3) + (uint64(h1) * r2) + (uint64(h2) * r1) + (uint64(h3) * r0) + (uint64(h4) * R4) 72 d4 := (d3 >> 26) + (uint64(h0) * r4) + (uint64(h1) * r3) + (uint64(h2) * r2) + (uint64(h3) * r1) + (uint64(h4) * r0) 73 74 // h %= p 75 h0 = uint32(d0) & 0x3ffffff 76 h1 = uint32(d1) & 0x3ffffff 77 h2 = uint32(d2) & 0x3ffffff 78 h3 = uint32(d3) & 0x3ffffff 79 h4 = uint32(d4) & 0x3ffffff 80 81 h0 += uint32(d4>>26) * 5 82 h1 += h0 >> 26 83 h0 = h0 & 0x3ffffff 84 } 85 86 // h %= p reduction 87 h2 += h1 >> 26 88 h1 &= 0x3ffffff 89 h3 += h2 >> 26 90 h2 &= 0x3ffffff 91 h4 += h3 >> 26 92 h3 &= 0x3ffffff 93 h0 += 5 * (h4 >> 26) 94 h4 &= 0x3ffffff 95 h1 += h0 >> 26 96 h0 &= 0x3ffffff 97 98 // h - p 99 t0 := h0 + 5 100 t1 := h1 + (t0 >> 26) 101 t2 := h2 + (t1 >> 26) 102 t3 := h3 + (t2 >> 26) 103 t4 := h4 + (t3 >> 26) - (1 << 26) 104 t0 &= 0x3ffffff 105 t1 &= 0x3ffffff 106 t2 &= 0x3ffffff 107 t3 &= 0x3ffffff 108 109 // select h if h < p else h - p 110 t_mask := (t4 >> 31) - 1 111 h_mask := ^t_mask 112 h0 = (h0 & h_mask) | (t0 & t_mask) 113 h1 = (h1 & h_mask) | (t1 & t_mask) 114 h2 = (h2 & h_mask) | (t2 & t_mask) 115 h3 = (h3 & h_mask) | (t3 & t_mask) 116 h4 = (h4 & h_mask) | (t4 & t_mask) 117 118 // h %= 2^128 119 h0 |= h1 << 26 120 h1 = ((h1 >> 6) | (h2 << 20)) 121 h2 = ((h2 >> 12) | (h3 << 14)) 122 h3 = ((h3 >> 18) | (h4 << 8)) 123 124 // s: the s part of the key 125 // tag = (h + s) % (2^128) 126 t := uint64(h0) + uint64(binary.LittleEndian.Uint32(key[16:])) 127 h0 = uint32(t) 128 t = uint64(h1) + uint64(binary.LittleEndian.Uint32(key[20:])) + (t >> 32) 129 h1 = uint32(t) 130 t = uint64(h2) + uint64(binary.LittleEndian.Uint32(key[24:])) + (t >> 32) 131 h2 = uint32(t) 132 t = uint64(h3) + uint64(binary.LittleEndian.Uint32(key[28:])) + (t >> 32) 133 h3 = uint32(t) 134 135 binary.LittleEndian.PutUint32(out[0:], h0) 136 binary.LittleEndian.PutUint32(out[4:], h1) 137 binary.LittleEndian.PutUint32(out[8:], h2) 138 binary.LittleEndian.PutUint32(out[12:], h3) 139} 140