D. J. Bernstein
Authenticators and signatures
A state-of-the-art public-key signature system

# Hashing

The input to the hash function H0 is a pair (r,m), where r is an integer in {0,1,...,15} and m is a string of bytes. The output H0(r,m) is an integer in {1,2,...,2^1536} defined as follows.

Define integers h[0],h[1],h[2],h[3],h[4] in {0,1,...,2^32-1} as the 160-bit output of the little-endian variant of SHA-1, where the input is 0 (one byte), m (some number of bytes), and r (one byte).

Define s[5] as floor(2^32 (sqrt(2) mod 1)); s[6] as floor(2^32 (sqrt(5) mod 1)); s[7] as floor(2^32 (sqrt(8) mod 1)); etc.

For n in {5,6,7,...,47}, define h[n] as h[n-5] plus32 ((h[n-2] plus32 s[n]) xor (h[n-1] rotate32 5)). Here plus32 means addition modulo 2^32, rotate32 5 means 5-bit left rotation (multiplication by 2^5) of a 32-bit integer, and xor means exclusive-or.

Define m171 as the integer whose little-endian representation is m followed by 1 if m has at most 171 bytes, or the first 171 bytes of m followed by 1 if m has more than 171 bytes.

Finally, define H0(r,m) as (h[0] + 2^32 h[1] + 2^64 h[2] + ... + 2^1504 h[47]) xor (2^160 m171). This is in {0,1,2,...,2^1536-1}; it cannot be 0, because if h[0],h[1],h[2],h[3],h[4] are all 0 then h[37] has top byte 101.

Note that, starting from H0(r,m), one can recover h[0],h[1],h[2],h[3],h[4], and thus recover h[5],h[6],...,h[47], and thus recover m171.

## Test cases

The first column of this table shows s[5],s[6],...,s[47]. Each subsequent column shows a possible h[0],h[1],...,h[47].
```                0x6b8b4567 0x19495cff 0x3d1b58ba 0x7545e146 0x0216231b
0x327b23c6 0x2ae8944a 0x507ed7ab 0x515f007c 0x1f16e9e8
0x643c9869 0x625558ec 0x2eb141f2 0x5bd062c2 0x1190cde7
0x66334873 0x238e1f29 0x41b71efb 0x12200854 0x66ef438d
0x74b0dc51 0x46e87ccd 0x79e2a9e3 0x4db127f8 0x140e0f76
0x6a09e667 0xb1b1ea5b 0x69e0f937 0xd4af91c7 0x3f52f2f8 0x534eea51
0x3c6ef372 0xab589f1b 0xea30eb1c 0x2cdb31fa 0xb1dd44e9 0x58b732aa
0xd413cccf 0x75664428 0xe66bb367 0x6256a3c5 0x33023fd3 0x4315b052
0x510e527f 0xb6e1bd07 0x2d44cdb0 0x78f51bd0 0x74cc7562 0x3262d2ee
0xbddd422d 0x853cb594 0x53b9c05e 0xb87349e0 0xb7025646 0x60b6bf2f
0x1f83d9ab 0x3fbec61d 0xa5d1a5c8 0x3e9dc853 0xcb386b33 0x9a8033c6
0x78dde6e5 0xb51afef9 0x738dccd3 0x0fc36c9c 0x68efe99b 0xcf2453d1
0xcbbb9d5d 0xcd4087d4 0xe6a08cb2 0x548b99f6 0xbe0b7bd0 0xc064054c
0x195957c4 0x507d10cb 0xd44e1adb 0x3165167a 0x31a63a0a 0x4d65d0db
0x629a292a 0xa5b55f28 0x92bfd1a4 0x53fa5646 0xcb653c02 0xeefaf44e
0xa827999f 0xf1af76bb 0x7a4224d0 0xe5644126 0x15ce1743 0x6fac500d
0xea843464 0x0f43ba0b 0xa88e68da 0x7cccbe32 0x751b819f 0xfc197cf0
0x2a17093d 0xc0f1c66d 0x310c576a 0xeb782622 0x5aa08f3e 0xa5773e01
0x67332667 0xe82ee2f5 0x02997ce2 0xa469f59e 0xba0589d7 0x7fba6d5e
0xa21ca4ff 0x3ee32959 0x12c731cd 0x534fdd5b 0x0f592d2c 0x9fd93d1d
0xdb0c2e0d 0x110db0e0 0xff85b81d 0xfbf1c9e7 0x940229a8 0xcdcb1745
0x12318007 0x7fe66f6d 0xd43eb665 0x61145caf 0xd34be960 0xf0b1276d
0x47b5481d 0x6500dbbf 0x701e8aca 0x4ca4ae0a 0xa7d6317d 0xa1d28b3d
0x7bba845a 0x43ea6720 0x4ec1e0d3 0xecc515de 0x044547c5 0x297fa0f1
0xae5f9156 0xad0fb276 0xd9093816 0xefa958b8 0xedf6679f 0x1f9f3fd3
0xdfbefae3 0x8eae8416 0xefdddeaa 0xc242c223 0x3939785d 0xc8a478fc
0x0ff01fb0 0x16b71e84 0xc0fc33e0 0xa953209f 0xae157648 0xb5b0e767
0x3f07b357 0x8056c3ae 0x3eba9cc3 0x21764779 0xece64ebe 0xf021ca82
0x6d1826ca 0xbad3369e 0x4809a3a0 0x2568be2b 0x7c60fcf4 0x028f4280
0x9a31fd1b 0x6c219f74 0xb2e225ed 0x0668daa8 0xf8fe3cf5 0xfb5ad770
0xc66410eb 0x93b32d1a 0x9db4d587 0xe91a5c39 0xdc36e4dd 0x24fabb90
0xf1bbcdcb 0xeafe5011 0xaef4f08b 0xcde3f14d 0x41aee4e3 0x27f2bea6
0x1c456002 0x9024346f 0xd75677df 0x6854b1db 0xba872775 0xaf3999d8
0x460bdc99 0x85469556 0x283b6cde 0x3ee2b4b6 0xa502cd1f 0x77c1a24a
0x6f196331 0x14326204 0xf3e466c2 0x11a15e73 0x6f0513a7 0xe1c18bb7
0x97773abb 0x2ea4bdad 0xda7655ae 0xcb8c7d4c 0xb90f5814 0xedf10fa9
0xbf2dea07 0xf2f649bf 0xb11c0b7d 0x2ca30f50 0x31d4e5bc 0x09243e09
0xe6454cd7 0x4600f709 0xf41baab2 0x8e04d201 0x604f3ae2 0x9feb3779
0x0cc4a611 0xc4eaa44e 0xe9a5850e 0x44e4bf66 0xdc81a4a0 0x8f339713
0x32b2af89 0x2e4b32ae 0xe1656ac8 0x6dc1cbb5 0x6bcf9537 0xacd2864a
0x6b8b4567 0x19495cff 0x3d1b58ba 0x7545e146 0x0216231b 0x8d02fa78
0x327b23c6 0x2ae8944a 0x507ed7ab 0x515f007c 0x1f16e9e8 0x8a1158ea
0x643c9869 0x625558ec 0x2eb141f2 0x5bd062c2 0x1190cde7 0xecd6a7c9
0x66334873 0x238e1f29 0x41b71efb 0x12200854 0x66ef438d 0x24a33e93
0x74b0dc51 0x46e87ccd 0x79e2a9e3 0x4db127f8 0x140e0f76 0xa2b2dcc8
0xb1b1ea5b 0x69e0f937 0xd4af91c7 0x3f52f2f8 0x534eea51 0x0cf44892
0xab589f1b 0xea30eb1c 0x2cdb31fa 0xb1dd44e9 0x58b732aa 0x5a93c28c
0x75664428 0xe66bb367 0x6256a3c5 0x33023fd3 0x4315b052 0xbcf984fa
```