本應用筆記描述了當使用具有模塊化算術加速器（MAA）的MAXQ微控制器時，如何將模運算速度提高50%以上。

介紹

模冪，a^和^模 M 是許多加密函數中的常見操作。MAXQ微處理器中的模塊化算術加速器（MAA）可以執行高達2048位的模數。很容易加載帶有a，e和m的內存區域，然后開始操作。

當模量是兩個或多個素數的乘積時，我們可以使用中國余數定理 （CRT） 的結果，通過執行兩個較小的模冪而不是一個大的模冪來減少執行時間。具體來說，我們使用 Garner 的算法進行此操作。

描述

在典型的 RSA 解密操作中，我們通過執行 pt = ct 從密文 （ct） 中恢復純文本 （pt）^d^mod n，其中 d 和 n 構成私鑰。值 d 是我們的解密指數，n 是素數 p 和 q 的乘積。通常，p 和 q 的長度相同，n、pt 和 ct 將是該位數的兩倍。例如，如果 p 和 q 的長度為 1024 位，則 n 在大約 2048% 的時間內將是 60 位的數字。

CRT 將我們的冪減少到以下等式：

Let c1 = ct^d^ mod p, c2 = ct^d^ mod q, and let m1 = p(p^-1^ mod q) and m2 = q(q^-1^ mod p).

ct = (c1 + m 1 (c2 - c 1 )) mod n

or

ct = (c2 + m 2 (c1 - c 2 )) mod n.

請注意，現在我們在 c 中的模冪1和 c2項的位數將是 CT 的一半^d^mod n 操作。

術語 m1和米2兩者都可以預先計算。該 p^-1^mod q 是某個值，比如 y，使得 p × y mod q = 1。例如，如果 p = 11 且 q = 17，則 11^-1^mod 17 = 14，因為 11 乘以 14 mod 17 = 1。這些反值可以使用擴展的歐幾里得算法找到，或者由于 p 和 q 是素數，因此執行函數 p^Q-2^模組問。這種求逆的模冪是基于費馬小定理的。

該 c1和 c2項很有趣，因為 ct 和 d 都是它們的模量值 p 和 q 的兩倍。MAA 不能做的一件事是對大于模量大小的值進行操作;我們需要先減小這兩個值，然后才能使用 MAA 執行模冪。指數 d 相對于 p 和 q 的減少可以預先計算。這些新指數只是 （d - 1） mod p 和 （d - 1） mod q。指數的約簡也是基于費馬小定理。

降低兩個 c 的 ct1和 c2在執行時通過模塊化乘法完成。例如，如果 ct 長 64 位，p 和 q 都是 32 位長，那么我們可以執行以下乘法：ct × 2^32^模組 （P × 2 ^32^ ).這將是一個 64 位模塊化乘法。這實際上比等式看起來更簡單。我們將 64 位、4 字 ct 放入 MAA 寄存器 a 中，并在 MAA 寄存器 b 中清除所有內容。然后，我們設置寄存器b的第32位，使寄存器等于2 ^32^ .在模中，我們將底部的兩個單詞寫為零，然后將 p 的值復制到接下來的兩個單詞中。然后我們將 MAWS 設置為 64 并執行模塊化乘法。我們正在尋找的減少值是結果的第 3 和第 4 字。

為了使其余的計算更容易，我們發現c之間的哪個項更大1和 c 2 ，然后選擇我們從大數中減去較小以避免獲得負數的等式。現在做一個模乘法，然后將其添加到 c 1 （如果我們乘以 m 1 ） 或 c 2 （如果我們乘以 m 2 ).

代碼說明

清單 1 顯示了指向 MAA 中每個寄存器的無符號長字指針的初始化。給出了采用安全RISC架構的DeepCover安全微控制器（MAXQ1103）中MAA的硬編碼地址。^?^

清單 1.指向 MAA 寄存器的指針

typedef unsigned long  int ulong;

// long word pointers to MAA memories in the MAXQ1103
ulong *maa_aw   = (ulong *) 0x8000;
ulong *maa_bw   = (ulong *) 0x8100;
ulong *maa_resw = (ulong *) 0x8200;
ulong *maa_expw = (ulong *) 0x8400;
ulong *maa_modw = (ulong *) 0x8500;

清單 2 包含四個預先計算的常量：piqtp（讀作 p 逆 q 乘以 p）、qiptq（讀作 q 逆 p 乘以 q）、dphip（讀作 p 的 d phi）和 dphiq（讀作 q 的 d phi）。常量 diptp 和 piqtq 是 m1和米2上面的術語。常量 dphip 和 dphiq 是 c 的簡化解密指數1和 c2上面的術語。兩個載體 ptp 和 ptq 用于臨時存儲。其他變量 p、q、n、phi、e、d、pt 和 ct 描述了 RSA 所需的所有值。術語 phi 等于 （p - 1） × （q - 1）。

術語 nwords 是 n 中的單詞數，即鍵的模數。在此實現中，假設 p 和 q 將具有正好 16 位× n字，并且 n 將恰好具有 32 位× n字。

這些向量中的單詞從最低有效單詞保存到最有效單詞。它們從低字到高字加載到 MAA 寄存器中。需要明確的是，下面是一個 p × q = n 的示例，使用清單 2 中的常量和粗體的交替長字。

0xF22F213FE34B717B × 0xC9446776B381BFB9 = 0xBE67B781405A57697217C6CFBB2AC6E3

清單 2.RSA 常量

int   nwords = 0x4;
ulong ptp[0x2];
ulong ptq[0x2];

// complete set of RSA constants
ulong p[0x2] =     { 0xE34B717B, 0xF22F213F };
ulong q[0x2] =     { 0xB381BFB9, 0xC9446776 };
ulong n[0x4] =     { 0xBB2AC6E3, 0x7217C6CF, 0x405A5769, 0xBE67B781 };
ulong phi[0x4] =   { 0x245D95B0, 0xB6A43E19, 0x405A5767, 0xBE67B781 };
// keys
ulong e[0x4] =     { 0x00000005, 0x00000000, 0x00000000, 0x00000000 };
ulong d[0x4] =     { 0xB6B1448D, 0xC55031AD, 0x337B791F, 0x9852F934 };
// sample plain text and corresponding cipher text
ulong pt[0x4] =    { 0x90ABCDEF, 0x12345678, 0x90ABCDEF, 0x12345678 };
ulong ct[0x4] =    { 0xDA3C591A, 0xC131AD9D, 0x40A51B30, 0x361958DF };

// the four pre-computed values used in crt computation.
ulong piqtp[0x4] = { 0x50995949, 0x4D355F7A, 0x907F8CC5, 0x1F0F60BF };
ulong qiptq[0x4] = { 0x6A916D9B, 0x24E26755, 0xAFDACAA4, 0x9F5856C1 };
ulong dphip[0x2] = { 0x5AEAFA31, 0x60DFA6E6 };
ulong dphiq[0x2] = { 0x6BB43FD5, 0x78C2A47A };

清單 3 具有 do_crt 函數，該函數使用 p 或 q 中的字數進行調用。例程從創建術語 c 開始1和 c2從上面并分別將這些值保存在 PTP 和 PTQ 中。然后我們確定 ptp 和 ptq 哪個更大，然后調用將執行模塊化乘法和加法的例程。這會將 pt 留在maa_resw內存中。

清單 3.do_crt例程

void do_crt(int nwords)
{  // nwords is the number of 32 bit words in p or in q.
   int i;

   mod_reduction(ct, p, dphip, nwords, ptp);
   mod_reduction(ct, q, dphiq, nwords, ptq);
   
   for (i = nwords - 1; i >= 0; --i)
      if (ptp[i] > ptq[i])
      {
         sum_mul_sub(2*nwords, ptp, ptq, qiptq, n);
         break;
      }
      else
      {
         sum_mul_sub(2*nwords, ptq, ptp, piqtp, n);
         break;
      }
}

清單 4 包含初始化 MAA 的詳細信息。在這里，我們清除MAA中的所有384個單詞，初始化存儲器選擇寄存器MAMS，然后告訴MAA哪個是模數中最重要的位，MAWS。

清單 4.init_maa例程

void init_maa(int mod_size)
{
   int i;

   for (i = 0; i < 384; ++i)
      maa_aw[i] = 0;          // clear the entire MAA
   MAMS = 0x6420;             // memory select register
   MAWS = mod_size;           // position of the most significant bit of modulus.
}

清單 5 包含對 ptp = ct 形式的表達式進行模塊化約簡的詳細信息^德菲普^莫德·此例程要做的第一件事是通過使用移位模數 p 進行模乘法，并讓乘法成為移位值，將 ct 減小到其大小的一半。這些例程使用長單詞的移動，而不是一次移動幾個單詞。（一個長字的距離移動就像移動32次。完成模乘法后，我們的簡化答案在maa_resw寄存器中向左移動。

隨著ct的減少，我們接下來進行模冪運算，以獲得這個子程序應該得到的結果，ptp。

清單 5.mod_reduction例程

void mod_reduction(ulong *ct, ulong *p, ulong *dphip, int nwords, ulong *ptp)
{  
   int i;

   // nwords as passed is the length of p. (rather than n)
   // we are going to do a modmul, with a shifted p as the modulus
   // init_maa is initializing MAWS with the correct modulus size.
   init_maa(nwords*64);

   // reducing ct mod p by doing the modmul ct * 2^(nwords*32) mod (p * (2^(nword*32))
   // load a with ct
   for (i = 0; i < 2*nwords; ++i)
      maa_aw[i] = ct[i];
   // load b with 2^(nwords*32) which is simply a bit set
   maa_bw[nwords] = 1;
   // load modulus with p*2^(nwords*32) which is simply a load shifted by nwords.
   for (i = 0; i < nwords; ++i)
      maa_modw[i + nwords] = p[i];

   // this multiply gives us the reduction in ct and 
   // the answer in maa_resw shifted by nwords.
   MACT = 0x05;      // mod multiply and start
   while (MACT & 1)  // wait for the multiply to finish
      ;
   // load registers to do ct^dphip mod p
   // notice that we are coping the shifted result of maa_resw to maa_aw.
   for (i = 0; i < nwords; ++i)
   {
      maa_aw[i] = maa_resw[nwords + i];
      maa_bw[i] = 0;
      maa_expw[i] = dphip[i];
      maa_modw[i] = p[i];
   }
   maa_b[0] = 1;      // the b reg is always 1 for modexp
   MAWS = 32*nwords;  // the most important step is setting MAWS to the correct size

   MACT = 0x1;        // mod exp and start
   while (MACT & 1)
      ;
   // copy our result to the ptp argument.
   for (i = 0; i < nwords; ++i)
       ptp[i] = maa_resw[i];
}

清單 6 描述了將所有內容組合在一起的函數。我們將計算方程 ct = （c 1 + 米 1 （c 2 ， B 1 ）） mod n if c2大于 c1或 ct = （c 2 + 米 2 （c 1 ， B 2 ）） 否則。它從減法開始。請注意，我們使用 n 作為模數，我們將處于乘法和加法的完整鍵長度。減法后，我們將結果從 maa_resw 移動到 maa_aw，并復制我們的乘數 m1或米 2 ，我們的參數 c 成maa_bw，并開始模乘法。在最后一步中，我們將乘法的結果從 maa_resw 復制到 maa_aw，然后復制 c1或 c 2 ，我們的參數 b，進入maa_bw并進行模塊化加法。完成后，我們的純文本是maa_resw的。

清單 6.sum_mul_sub例程

void sum_mul_sub(int nwords, ulong *a, ulong *b, ulong *c, ulong *n)
{
   int i;

   // prepare to subtract b from a
   for (i = 0; i < nwords/2; ++i)
   {
       maa_aw[i]   = a[i];
       maa_bw[i]   = b[i];
       maa_modw[i] = n[i];
   }
   // clear the upper words of maa_a and maa_b and copy the rest of n
   for (i = nwords/2; i < nwords; ++i)
   {
       maa_aw[i]   = 0;
       maa_bw[i]   = 0;
       maa_modw[i] = n[i];
   }
   // this is a full size operation.
   // start the subtraction
   MAWS = 32*nwords;
   MACT = 0xB;    // subtract and start
   while (MACT & 1)
      ;
   // copy the result over to maa_aw and
   // put or multiplicand into maa_bw
   for (i = 0; i < nwords; ++i)
   {
       maa_aw[i] = maa_resw[i];
       maa_bw[i] = c[i];
   }
   MACT = 5;    // multiply and start
   while (MACT & 1)
      ;
   for (i = 0; i < nwords/2; ++i)
   {
      maa_aw[i] = maa_resw[i];
      maa_bw[i] = b[i];
   }
   for (i = nwords/2; i < nwords; ++i)
   {
      maa_aw[i] = maa_resw[i];
      maa_bw[i] = 0;
   }
   MACT = 0x9;    // add and start
   while (MACT & 1)
      ;
}

業績和結論

表 1 和表 2 給出了使用上述算法可以實現的速度改進的指示。隨著模量尺寸的增加，我們得到的時間減少更大。

這里介紹的 C 實現旨在證明使用此算法可以提高速度。該代碼還顯示了如何操作 MAA。可以做很多事情來提高算法的速度，包括循環展開、循環優化、使用編譯器優化的數據移動例程以及使用匯編語言。

最快和最簡單的速度改進是操作MAA的MAMS寄存器，這將消除一些數據移動。MAMS 寄存器允許我們重命名內存段。為簡單起見，此應用程序中未完成此操作。

從理論上講，通過使用這種算法，應該可以在提高速度的情況下接近 4 比 1 的時序比。

始終使用加密環作為您的加密時鐘源。這是通過清除電源管理寄存器 （PMR） 中的主加密源選擇（MCSS、PMR.7）來實現的。解密時，建議將模塊化算術加速器控制寄存器（MACT）的優化計算控制（OCALC，MACT.4）清除為零，禁用該功能。

表 1.MAXQ1103 在25MHz，MAA運行在加密環路| 大小 | ModExp （ms） | 顯像管（毫秒） | 率 |

| ------------------------------------------- | --------------- | ---------------- | ---- |

| 2048 | 549 | 166 | 3.3 |

| 1024 | 82.0 | 29.6 | 2.8 |

| 512 | 14.2 | 7.25 | 2.0 |

| 256 | 3.37 | 3.08 | 1.1 |

Table 2. DeepCover Secure Microcontroller (MAXQ1050) at 24MHz with the MAA Running with Crypto Ring| Size | ModExp (ms) | CRT (ms) | Ratio |

| -------------------------------------- | ------------- | ---------- | ------- |

| 2048 | 1760 | 492 | 3.6 |

| 1024 | 244 | 75.7 | 3.2 |

| 512 | 37.1 | 14.3 | 2.6 |

| 256 | 6.80 | 4.49 | 1.5 |

Numerical Example of RSA Using the CRT to Recover the Plain Text

This example goes through the steps of constructing the public and private keys for RSA, then taking a sample message, encrypting it, and decrypting it. Then we show how the same encrypted message can be decrypted using the CRT.

我們首先找到幾個質數。設 p = 0xE747 和 q = 0xC7A5。兩者都是 16 位質數。

這給了我們 n = p × q = 0xB45D41C3 和 phi = （p - 1）（q - 1） = 0xB45B92D8。兩者都是 32 位。

我們可以選擇 e = 0x10001，因為 gcd（e， phi） = 1。這給了我們公鑰。我們的私鑰被選中，因此 e × d mod phi = 1。使用擴展的歐幾里得算法，我們計算d = 0x9B111CC9。

我們任意選擇我們的純文本，pt = 0xABCDEF12。我們的密文，ct = pt^和^mod n = 0x87CCFE27。要恢復純文本，請執行 ct^d^莫德·這是一個 32 位模冪。這原則上是 RSA 加密/解密過程。

現在我們將使用中文余數定理恢復純文本。

離線時，我們預先計算四個常量。第一個是 piqtp = 0x9E1D261C，即 （p^-1^Mod Q） × p.第二個是 qiptq = 0x16401BA8，即 （q^-1^mod p） times q.它們都是 32 位長。您可以使用擴展的歐幾里得算法或執行 p^Q-2^模組 q 和 q^P-2^mod p 找到逆數。我們還需要 dphip = d mod phi（p） = 0x9B111CC9 mod （0xE747 - 1） = 0x4AAB 和 dphiq = d mod phi（q） = 0x9B111CC9 mod （0xC7A5 - 1） = 0x9A0D。這些數字都是 16 位，大小是 n 的一半。

在線計算從通過 mod p 減少密文開始。密文長 32 位，模長 16 位。為了使用 MAA 進行歸約，我們將模數 p 向左移動 16 位并將密文乘以 216。這看起來像0x87CCFE27 × 0x10000 mod 0xE7470000 = 0x36B00000。現在我們將答案向右移動 16 位，或者只抓住單詞的上部 16 位。我們需要這個值來執行 16 位模冪0x36B0^德菲普^mod p，看起來像0x36B0^0x4AAB^模組 0xE747 = 0x6425 = PTP。

使用密文 mod q 的第二個模塊化約簡隨著 mod 0xC87A27 = 0x10000D0 7x50000CCFE0 × 543x0000而擴展。將答案向右移動 16 位，或者只是抓住上面的單詞，得到減少，0x543D。使用此結果并執行模冪0x543D^德菲克^mod q，看起來像0x543D^0x9A0D^模組0xC7A5 = 0x1671 = ptq.

如果 ptp 大于 ptq，我們計算 （ptq + （ptp - ptq） × qiptq） mod n，否則我們計算 （ptp + （ptq - ptp） × piqtp） mod n。請記住，piqtp 和 qiptq 是預先計算的，長度為 32 位。

我們看到 ptp 大于 ptq。差值，ptp - ptq = 0x4DB4。（（ptp - ptq） 和 qiptq） mod n 和 （0x4DB4 × 0x16401BA8） mod 0xB45D41C3 的乘積是0xABCDD8A1。添加 ptq，0x1671會給我們返回純文本，0xABCDEF12，我們就完成了。

審核編輯：郭婷