security/nss/lib/freebl/mpi/doc/redux.txt@b8a032363ba2 (annotated)
security/nss/lib/freebl/mpi/doc/redux.txt
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
| michael@0 | 1 | Modular Reduction |
| michael@0 | 2 | |
| michael@0 | 3 | Usually, modular reduction is accomplished by long division, using the |
| michael@0 | 4 | mp_div() or mp_mod() functions. However, when performing modular |
| michael@0 | 5 | exponentiation, you spend a lot of time reducing by the same modulus |
| michael@0 | 6 | again and again. For this purpose, doing a full division for each |
| michael@0 | 7 | multiplication is quite inefficient. |
| michael@0 | 8 | |
| michael@0 | 9 | For this reason, the mp_exptmod() function does not perform modular |
| michael@0 | 10 | reductions in the usual way, but instead takes advantage of an |
| michael@0 | 11 | algorithm due to Barrett, as described by Menezes, Oorschot and |
| michael@0 | 12 | VanStone in their book _Handbook of Applied Cryptography_, published |
| michael@0 | 13 | by the CRC Press (see Chapter 14 for details). This method reduces |
| michael@0 | 14 | most of the computation of reduction to efficient shifting and masking |
| michael@0 | 15 | operations, and avoids the multiple-precision division entirely. |
| michael@0 | 16 | |
| michael@0 | 17 | Here is a brief synopsis of Barrett reduction, as it is implemented in |
| michael@0 | 18 | this library. |
| michael@0 | 19 | |
| michael@0 | 20 | Let b denote the radix of the computation (one more than the maximum |
| michael@0 | 21 | value that can be denoted by an mp_digit). Let m be the modulus, and |
| michael@0 | 22 | let k be the number of significant digits of m. Let x be the value to |
| michael@0 | 23 | be reduced modulo m. By the Division Theorem, there exist unique |
| michael@0 | 24 | integers Q and R such that: |
| michael@0 | 25 | |
| michael@0 | 26 | x = Qm + R, 0 <= R < m |
| michael@0 | 27 | |
| michael@0 | 28 | Barrett reduction takes advantage of the fact that you can easily |
| michael@0 | 29 | approximate Q to within two, given a value M such that: |
| michael@0 | 30 | |
| michael@0 | 31 | 2k |
| michael@0 | 32 | b |
| michael@0 | 33 | M = floor( ----- ) |
| michael@0 | 34 | m |
| michael@0 | 35 | |
| michael@0 | 36 | Computation of M requires a full-precision division step, so if you |
| michael@0 | 37 | are only doing a single reduction by m, you gain no advantage. |
| michael@0 | 38 | However, when multiple reductions by the same m are required, this |
| michael@0 | 39 | division need only be done once, beforehand. Using this, we can use |
| michael@0 | 40 | the following equation to compute Q', an approximation of Q: |
| michael@0 | 41 | |
| michael@0 | 42 | x |
| michael@0 | 43 | floor( ------ ) M |
| michael@0 | 44 | k-1 |
| michael@0 | 45 | b |
| michael@0 | 46 | Q' = floor( ----------------- ) |
| michael@0 | 47 | k+1 |
| michael@0 | 48 | b |
| michael@0 | 49 | |
| michael@0 | 50 | The divisions by b^(k-1) and b^(k+1) and the floor() functions can be |
| michael@0 | 51 | efficiently implemented with shifts and masks, leaving only a single |
| michael@0 | 52 | multiplication to be performed to get this approximation. It can be |
| michael@0 | 53 | shown that Q - 2 <= Q' <= Q, so in the worst case, we can get out with |
| michael@0 | 54 | two additional subtractions to bring the value into line with the |
| michael@0 | 55 | actual value of Q. |
| michael@0 | 56 | |
| michael@0 | 57 | Once we've got Q', we basically multiply that by m and subtract from |
| michael@0 | 58 | x, yielding: |
| michael@0 | 59 | |
| michael@0 | 60 | x - Q'm = Qm + R - Q'm |
| michael@0 | 61 | |
| michael@0 | 62 | Since we know the constraint on Q', this is one of: |
| michael@0 | 63 | |
| michael@0 | 64 | R |
| michael@0 | 65 | m + R |
| michael@0 | 66 | 2m + R |
| michael@0 | 67 | |
| michael@0 | 68 | Since R < m by the Division Theorem, we can simply subtract off m |
| michael@0 | 69 | until we get a value in the correct range, which will happen with no |
| michael@0 | 70 | more than 2 subtractions: |
| michael@0 | 71 | |
| michael@0 | 72 | v = x - Q'm |
| michael@0 | 73 | |
| michael@0 | 74 | while(v >= m) |
| michael@0 | 75 | v = v - m |
| michael@0 | 76 | endwhile |
| michael@0 | 77 | |
| michael@0 | 78 | |
| michael@0 | 79 | In random performance trials, modular exponentiation using this method |
| michael@0 | 80 | of reduction gave around a 40% speedup over using the division for |
| michael@0 | 81 | reduction. |
| michael@0 | 82 | |
| michael@0 | 83 | ------------------------------------------------------------------ |
| michael@0 | 84 | This Source Code Form is subject to the terms of the Mozilla Public |
| michael@0 | 85 | # License, v. 2.0. If a copy of the MPL was not distributed with this |
| michael@0 | 86 | # file, You can obtain one at http://mozilla.org/MPL/2.0/. |
