path: root/raw-wiki-dump/GitRepositories%2Fuser%2Fshatov%2Fmodexpng.trac

{{{
#!htmlcomment

This page is maintained automatically by a script.  Don't modify this page by hand,
your changes will just be overwritten the next time the script runs.  Talk to your
Friendly Neighborhood Repository Maintainer if you need to change something here.

}}}

{{{
#!html
<h1>ModExpNG</h1>

<h2>Core Description</h2>

<p>This "next-generation" IP core implements the modular exponentiation math primitive using the specialized DSP slices present in the Artix-7 FPGA found on the CrypTech Alpha board. It can be used during RSA operations such as encryption/decryption and signing. Given a pair of blinding factors, the core internally blinds the message before signing and then unblinds it afterwards. The blinding factors are automatically mutated during each exponentiation for later reuse. Another prominent feature is the full support for Chinese Remainder Theorem. Given smaller moduli P and Q, the core can do the mixed-radix conversion variant of the algorithm ("Garner's formula") for faster computation. Due to limitations of the underlying hardware (primarily the capacity of the BlockRAM tile in the 7-Series Xilinx devices) the largest supported key length is 4096 bits.</p>

<h2>Compile-Time Settings</h2>

<p>The core has one synthesis-time parameter:</p>

<ul>
<li><strong>NUM_MULTS</strong> - Sets the number of DSP slices to use per modular multiplier, which must be a power of 2. Each multiplier consumes NUM_MULTS + 1 slices, since one additional multiplier is required to eliminate the final conditional subtraction step of the Montgomery modular multiplication routine. The core internally consists of a pair of <em>dual modular multipliers</em>, thus the total number of occupied DSP slices is 4 * (NUM_MULTS + 1). When in CRT mode, both <em>dual multipliers</em> operate simultaneously, each with its own modulus. The two multipliers inside of the <em>dual multiplier</em> simultaneously do the squaring and multiplication operations, which constitute one step of the Montgomery powering ladder.</li>
</ul>

<p>Combined DSP slice utilization is outlined in the following table:</p>

<table border rules="groups" cellpadding="5">
<colgroup><col></colgroup><colgroup><col></colgroup>
<thead>              <tr><th> NUM_MULTS </th><th> DSP Usage </th></tr></thead>
<tbody align="right"><tr><td>         8 </td><td>        36 </td></tr></tbody>
<tbody align="right"><tr><td>        16 </td><td>        68 </td></tr></tbody>
<tbody align="right"><tr><td>        32 </td><td>       132 </td></tr></tbody>
<tbody align="right"><tr><td>        64 </td><td>       260 </td></tr></tbody>
</table>

<p>Currently the core has been tested in hardware with a balanced setting of NUM_MULTS = 8. Larger values should decreate latency, but proportionally increase DSP slice usage. The core takes advantage of the dedicated high-speed cascade paths between DSP slices, thus all the NUM_MULTS slices must be placed in the same DSP column. Given that the column height for the Artix-7 FPGA is 100 DSP slices, the upper limit on NUM_MULTS is 64. This has not been yet tested in hardware and may require floorplanning or additional operand "broadcast" tree, which is a topic for future research.</p>

<h2>API Specification</h2>

<p>The interface of the core is similar to other CrypTech cores. FMC memory map is split into four regions (REGISTERS, INPUT_0, INPUT_1 and OUTPUT), each region is 32 kilobits (4 kilobytes). The first one (REGISTERS) contains core registers and looks like the following:</p>

<table border rules="groups" cellpadding="5">
<colgroup><col></colgroup>
<thead><tr><th colspan=2> REGISTERS Memory Map </th></tr></thead>
<colgroup><col></colgroup><colgroup><col></colgroup>
<thead><tr><th> Offset </th><th> Register      </th></tr></thead>
<tbody><tr><td> 0x0000 </td><td> NAME0         </td></tr></tbody>
<tbody><tr><td> 0x0004 </td><td> NAME1         </td></tr></tbody>
<tbody><tr><td> 0x0008 </td><td> VERSION       </td></tr></tbody>
<tbody><tr><td> 0x0020 </td><td> CONTROL       </td></tr></tbody>
<tbody><tr><td> 0x0024 </td><td> STATUS        </td></tr></tbody>
<tbody><tr><td> 0x0040 </td><td> MODE          </td></tr></tbody>
<tbody><tr><td> 0x0044 </td><td> MODULUS_BITS  </td></tr></tbody>
<tbody><tr><td> 0x0048 </td><td> EXPONENT_BITS </td></tr></tbody>
<tbody><tr><td> 0x004C </td><td> BANK_BITS     </td></tr></tbody>
<tbody><tr><td> 0x0050 </td><td> NUM_MULTS     </td></tr></tbody>
</table>

<p>The core has the following registers:</p>

<ul>
<li><p><strong>NAME0</strong>, <strong>NAME1</strong></p>

<p>Read-only core name ("<code>mode</code>", "<code>xpng</code>").</p></li>
<li><p><strong>VERSION</strong></p>

<p>Read-only core version, currently "<code>0.10</code>".</p></li>
<li><p><strong>CONTROL</strong></p>

<p>Register bits: <br />
<code>[31:2]</code> Don't care, always read as 0 <br />
<code>[1]</code> "<strong>next</strong>" control bit <br />
<code>[0]</code> Don't care, always read as 0</p>

<p>The "<strong>next</strong>" control bit is used to start an exponentiation. The core is edge-triggered, this way if the bit is currently set, it must be cleared first and then set to 1 again to start a new exponentiation.</p></li>
<li><p><strong>STATUS</strong></p>

<p>Read-only register bits: <br />
<code>[31:2]</code> Don't care, always read as 0 <br />
<code>[1]</code> "<strong>valid</strong>" status bit <br />
<code>[0]</code> "<strong>ready</strong>" status bit, always read as 1  </p>

<p>The "<strong>valid</strong>" status bit is cleared as soon as the core starts exponentiation, and gets set after the operation is finished.</p></li>
<li><p><strong>MODE</strong></p>

<p>Mode register bits: <br />
<code>[31:2]</code> Don't care, always read as 0 <br />
<code>[1]</code> "<strong>CRT enable</strong>" control bit <br />
<code>[0]</code> Don't care, always read as 0  </p>

<p>The "<strong>CRT enable</strong>" control bit allows the core to take advantage of the Chinese remainder theorem to speed up RSA operations.</p></li>
<li><p><strong>MODULUS_BITS</strong></p>

<p>Length of modulus in bits. Smallest allowed value is 64 * NUM_MULTS (currently 64 * 8 = 512), largest allowed value is 4096. The core rounds MODULUS_BITS down to the nearest multiple of 32 * NUM_MULTS (currently 32 * 8 = 256). Thus, allowed key lengths are 512, 768, 1024, 1280, ..., 4096. If the modulus is eg. 1000 bits wide, MODULUS_BITS must be set to 1024 and the modulus must be prepended with 24 zero bits to match the allowed length. Always set this to the length of the public key, do not use twice smaller value when CRT is enabled, the core automatically takes care of that.</p></li>
<li><p><strong>EXPONENT_BITS</strong></p>

<p>Length of exponent in bits. Smallest allowed value is 4, largest allowed value is 4096.</p></li>
<li><p><strong>BANK_BITS</strong></p>

<p>Length of operand bank in bits. This read-only parameter returns the length of internal operand bank and allows the largest supported operand width to be determined at run-time. Currently BANK_BITS is hardwired to always return 4096.</p></li>
<li><p><strong>NUM_MULTS</strong></p>

<p>This read-only parameter returns the width of the internal parallel multiplier, that was specified at compile-time. This parameter is currently 8.</p></li>
</ul>

<p>The two following memory regions (INPUT_0 and INPUT_1) contain input quantities, each region is split into eight banks, each bank is 4096 bits (512 bytes). The least significat byte of an input quantity should be written to offset 0 in a bank, i.e. one should start filling banks by writing the least significant word at the lowest offset.</p>

<p>The second region (INPUT_0) contains the following banks:</p>

<table border rules="groups" cellpadding="5">
<colgroup><col></colgroup>
<thead><tr><th colspan=2> INPUT_0 Memory Map </th></tr></thead>
<colgroup><col></colgroup><colgroup><col></colgroup>
<thead><tr><th> Offset </th><th> Bank     </th></tr></thead>
<tbody><tr><td> 0x1000 </td><td> M        </td></tr></tbody>
<tbody><tr><td> 0x1200 </td><td> N        </td></tr></tbody>
<tbody><tr><td> 0x1400 </td><td> N_FACTOR </td></tr></tbody>
<tbody><tr><td> 0x1600 </td><td> N_COEFF  </td></tr></tbody>
<tbody><tr><td> 0x1A00 </td><td> X        </td></tr></tbody>
<tbody><tr><td> 0x1C00 </td><td> Y        </td></tr></tbody>
</table>

<ul>
<li><p><strong>M</strong> is the message to be signed (base).</p></li>
<li><p><strong>N</strong> is the modulus (public key).</p></li>
<li><p><strong>N_FACTOR</strong> is the <strong>N</strong> Montgomery factor and must be precomputed (described later).</p></li>
<li><p><strong>N_COEFF</strong> is the <strong>N</strong> modulus-dependent speed-up coefficient and must be precomputed (described later). Note, that the bank for <strong>N_COEFF</strong> is twice larger than normal banks.</p></li>
<li><p>(<strong>X</strong>, <strong>Y</strong>) are a pair of blinding factors. Blinding is always enabled, there's no way to disable it, thus a pair of blinding factors is required for exponentiation. Note, that a pair of (<strong>X</strong>, <strong>Y</strong>) = (1, 1) works just fine, but you effectively aren't doing any blinding this way. The message is blinded using <strong>Y</strong> and unblinded using <strong>X</strong>, thus the relationship between the two must be <strong>Y = (X ** -1) ** e</strong>. Note, that this scheme won't work for encryption, either a pair of (1, 1) must be used, or <strong>X</strong> and <strong>Y</strong> must be swapped. The overhead form blinding is four additional modular multiplications (two to blind-unblind the message and two to mutate the blinding factors) which is &lt;1% for 1024-bit keys and even lower for longer keys.</p></li>
</ul>

<p>The third region (INPUT_1) contains the following banks. Note, that since the third region contains secret components, it is "write-only", any reads from the region will return 0xDEADCODE.</p>

<table border rules="groups" cellpadding="5">
<colgroup><col></colgroup>
<thead><tr><th colspan=2> INPUT_1 Memory Map </th></tr></thead>
<colgroup><col></colgroup><colgroup><col></colgroup>
<thead><tr><th> Offset </th><th> Bank     </th></tr></thead>
<tbody><tr><td> 0x2000 </td><td> D        </td></tr></tbody>
<tbody><tr><td> 0x2200 </td><td> P        </td></tr></tbody>
<tbody><tr><td> 0x2300 </td><td> DP       </td></tr></tbody>
<tbody><tr><td> 0x2400 </td><td> P_FACTOR </td></tr></tbody>
<tbody><tr><td> 0x2600 </td><td> P_COEFF  </td></tr></tbody>
<tbody><tr><td> 0x2800 </td><td> Q        </td></tr></tbody>
<tbody><tr><td> 0x2900 </td><td> DQ       </td></tr></tbody>
<tbody><tr><td> 0x2A00 </td><td> Q_FACTOR </td></tr></tbody>
<tbody><tr><td> 0x2C00 </td><td> Q_COEFF  </td></tr></tbody>
<tbody><tr><td> 0x2E00 </td><td> QINV     </td></tr></tbody>
</table>

<ul>
<li><p><strong>D</strong> is the exponent (secret exponent for signing, F4 is commonly used for encryption).</p></li>
<li><p><strong>P</strong>, <strong>Q</strong> are the smaller moduli, they must be supplied when CRT mode is enabled. Note, that their banks are twice smaller than normal banks.</p></li>
<li><p><strong>DP</strong>, <strong>DQ</strong> are private key components, they must be supplied when CRT mode is enabled. Note, that their banks are twice smaller than normal banks.</p></li>
<li><p><strong>P_FACTOR</strong>, <strong>Q_FACTOR</strong> are the <strong>P</strong> and <strong>Q</strong> Montgomery factors and must be precomputed (described later).</p></li>
<li><p><strong>P_COEFF</strong>, <strong>Q_COEFF</strong> are the <strong>P</strong> and <strong>Q</strong> moduli-dependent speed-up coefficients and must be precomputed (described later).</p></li>
<li><p><strong>QINV</strong> is the private key compoment, it must be supplided when CRT mode is enabled.</p></li>
</ul>

<p>The fourth region (OUTPUT) contains three banks where the core will store the output quantities:</p>

<table border rules="groups" cellpadding="5">
<colgroup><col></colgroup>
<thead><tr><th colspan=2> OUTPUT Memory Map </th></tr></thead>
<colgroup><col></colgroup><colgroup><col></colgroup>
<thead><tr><th> Offset </th><th> Bank </th></tr></thead>
<tbody><tr><td> 0x3000 </td><td> S    </td></tr></tbody>
<tbody><tr><td> 0x3200 </td><td> XM   </td></tr></tbody>
<tbody><tr><td> 0x3400 </td><td> YM   </td></tr></tbody>
</table>

<ul>
<li><p><strong>S</strong> is the signature (or ciphertext after encryption).</p></li>
<li><p>(<strong>XM</strong>, <strong>YM</strong>) are a pair of mutated blinding factors.</p></li>
</ul>

<h2>Montgomery Factors and Modulus-dependent Speed-up Coefficients</h2>

<p>The core uses the Montgomery modular multiplier, which can only operate on numbers in the so called Montgomery domain. Bringing input numbers into Montgomery domain and converting output numbers out of Montgomery domain requires a special quantity called Montgomery factor: <strong>FACTOR</strong> = 2 ** (2 * (<strong>MODULUS_BITS</strong> + <strong>WORD_WIDTH</strong>)) mod <strong>N</strong>. This quantity has at most as many bits as the modulus and should be precomputed during key generation. The core's internal data buses are 16-bit wide, so for the formula above <strong>WORD_WIDTH</strong> = 16. The following pseudocode calculates the Montgomery factor given modulus <strong>N</strong>:</p>

<pre><code>F = 1
for i from 0 to 2 * (MODULUS_BITS + 16) - 1
    F1 = F &lt;&lt; 1
    F2 = F1 - N
    F = (F2 &lt; 0) ? F1 : F2
return F
</code></pre>

<p>The final step of Montgomery modular multiplication is Montgomery modular reduction. It is done by adding a multiple of the modulus to the intermediate product. The multiple is selected in such a way, that the lower half of the sum is all zero bits, so it can be safely reduced by just a trivial right shift. This speeds things up, since there's no more need to do computationally difficult division anymore. To determine the multiple of the modulus, another quantity is required, which is the so called modulus-dependent speed-up coefficient: <strong>COEFF</strong> = -<strong>N</strong> ** -1 mod 2 ** (<strong>MODULUS_BITS</strong> + <strong>WORD_WIDTH</strong>). The number of bits needed to store the coefficient exceeds the width of the modulus by one word. The core internally operates on 16-bit words, so the coefficient is wider than the modulus by two bytes. This non-obvious and somewhat inconvenient feature is required to skip the final conditional subtraction step of the "classic" Montgomery modular reduction. Since a selected multiple of the modulus is <em>added</em> to the intermediate product, the result after shifting it to the right can exceed the modulus, so the traditional solution is to do a conditional subtraction as the very last step. The more precise analysis indicates, that the conditional subtraction can be eliminated, if the main loop of the reduction is repeated for at least three additional times, i.e. <strong>MODULUS_BITS</strong> + 3 total iterations. The model operates on entire words internally, so it can only do <strong>MODULUS_BITS</strong> + <strong>WORD_WIDTH</strong> iterations and thus needs 16 extra bits of the speed-up factor. The following pseudocode calculates the modulus-dependent speed-up coefficient:</p>

<pre><code>R = 1
B = 1
NN = ~N + 1
for i from 1 to (MODULUS_BITS + 16 - 1)
    B = B &lt;&lt; 1
    T = R * NN mod 2 ** (MODULUS_BITS + 16)
    if T[i] then
        R = R + B
return R
</code></pre>

<p>The <code>stm32/modexpng_util.c</code> file also has reference C code, that computes the Montgomery factor and the speed-up coeficient. Note that each keypair ideally requires three pairs of precomputed numbers: one for the public key <strong>N</strong> and one for each of the smaller secret moduli <strong>P</strong> and <strong>Q</strong>.</p>

<h2>References</h2>

<ol>
<li><a href="https://eprint.iacr.org/2017/1115.pdf">Hardware Aspects of Montgomery Modular Multiplication</a></li>
</ol>
}}}

[[RepositoryIndex(format=table,glob=user/shatov/modexpng)]]

|| Clone `https://git.cryptech.is/user/shatov/modexpng.git` ||