使用DeepCover安全微控制器提高模塊化求冪的速度

本應(yīng)用筆記描述了當(dāng)使用具有模塊化算術(shù)加速器（MAA）的MAXQ微控制器時(shí)，如何將模運(yùn)算速度提高50%以上。

介紹

模冪，a^和^模 M 是許多加密函數(shù)中的常見(jiàn)操作。MAXQ微處理器中的模塊化算術(shù)加速器（MAA）可以執(zhí)行高達(dá)2048位的模數(shù)。很容易加載帶有a，e和m的內(nèi)存區(qū)域，然后開(kāi)始操作。

當(dāng)模量是兩個(gè)或多個(gè)素?cái)?shù)的乘積時(shí)，我們可以使用中國(guó)余數(shù)定理 （CRT） 的結(jié)果，通過(guò)執(zhí)行兩個(gè)較小的模冪而不是一個(gè)大的模冪來(lái)減少執(zhí)行時(shí)間。具體來(lái)說(shuō)，我們使用 Garner 的算法進(jìn)行此操作。

描述

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

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.

請(qǐng)注意，現(xiàn)在我們?cè)?c 中的模冪1和 c2項(xiàng)的位數(shù)將是 CT 的一半^d^mod n 操作。

術(shù)語(yǔ) m1和米2兩者都可以預(yù)先計(jì)算。該 p^-1^mod q 是某個(gè)值，比如 y，使得 p × y mod q = 1。例如，如果 p = 11 且 q = 17，則 11^-1^mod 17 = 14，因?yàn)?11 乘以 14 mod 17 = 1。這些反值可以使用擴(kuò)展的歐幾里得算法找到，或者由于 p 和 q 是素?cái)?shù)，因此執(zhí)行函數(shù) p^Q-2^模組問(wèn)。這種求逆的模冪是基于費(fèi)馬小定理的。

該 c1和 c2項(xiàng)很有趣，因?yàn)?ct 和 d 都是它們的模量值 p 和 q 的兩倍。MAA 不能做的一件事是對(duì)大于模量大小的值進(jìn)行操作;我們需要先減小這兩個(gè)值，然后才能使用 MAA 執(zhí)行模冪。指數(shù) d 相對(duì)于 p 和 q 的減少可以預(yù)先計(jì)算。這些新指數(shù)只是 （d - 1） mod p 和 （d - 1） mod q。指數(shù)的約簡(jiǎn)也是基于費(fèi)馬小定理。

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

為了使其余的計(jì)算更容易，我們發(fā)現(xiàn)c之間的哪個(gè)項(xiàng)更大1和 c 2 ，然后選擇我們從大數(shù)中減去較小以避免獲得負(fù)數(shù)的等式?，F(xiàn)在做一個(gè)模乘法，然后將其添加到 c 1 （如果我們乘以 m 1 ） 或 c 2 （如果我們乘以 m 2 ).

代碼說(shuō)明

清單 1 顯示了指向 MAA 中每個(gè)寄存器的無(wú)符號(hào)長(zhǎng)字指針的初始化。給出了采用安全RISC架構(gòu)的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 包含四個(gè)預(yù)先計(jì)算的常量：piqtp（讀作 p 逆 q 乘以 p）、qiptq（讀作 q 逆 p 乘以 q）、dphip（讀作 p 的 d phi）和 dphiq（讀作 q 的 d phi）。常量 diptp 和 piqtq 是 m1和米2上面的術(shù)語(yǔ)。常量 dphip 和 dphiq 是 c 的簡(jiǎn)化解密指數(shù)1和 c2上面的術(shù)語(yǔ)。兩個(gè)載體 ptp 和 ptq 用于臨時(shí)存儲(chǔ)。其他變量 p、q、n、phi、e、d、pt 和 ct 描述了 RSA 所需的所有值。術(shù)語(yǔ) phi 等于 （p - 1） × （q - 1）。

術(shù)語(yǔ) nwords 是 n 中的單詞數(shù)，即鍵的模數(shù)。在此實(shí)現(xiàn)中，假設(shè) p 和 q 將具有正好 16 位× n字，并且 n 將恰好具有 32 位× n字。

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

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 函數(shù)，該函數(shù)使用 p 或 q 中的字?jǐn)?shù)進(jìn)行調(diào)用。例程從創(chuàng)建術(shù)語(yǔ) c 開(kāi)始1和 c2從上面并分別將這些值保存在 PTP 和 PTQ 中。然后我們確定 ptp 和 ptq 哪個(gè)更大，然后調(diào)用將執(zhí)行模塊化乘法和加法的例程。這會(huì)將 pt 留在maa_resw內(nèi)存中。

清單 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 的詳細(xì)信息。在這里，我們清除MAA中的所有384個(gè)單詞，初始化存儲(chǔ)器選擇寄存器MAMS，然后告訴MAA哪個(gè)是模數(shù)中最重要的位，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 包含對(duì) ptp = ct 形式的表達(dá)式進(jìn)行模塊化約簡(jiǎn)的詳細(xì)信息^德菲普^莫德·此例程要做的第一件事是通過(guò)使用移位模數(shù) p 進(jìn)行模乘法，并讓乘法成為移位值，將 ct 減小到其大小的一半。這些例程使用長(zhǎng)單詞的移動(dòng)，而不是一次移動(dòng)幾個(gè)單詞。（一個(gè)長(zhǎng)字的距離移動(dòng)就像移動(dòng)32次。完成模乘法后，我們的簡(jiǎn)化答案在maa_resw寄存器中向左移動(dòng)。

隨著ct的減少，我們接下來(lái)進(jìn)行模冪運(yùn)算，以獲得這個(gè)子程序應(yīng)該得到的結(jié)果，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 描述了將所有內(nèi)容組合在一起的函數(shù)。我們將計(jì)算方程 ct = （c 1 + 米 1 （c 2 ， B 1 ）） mod n if c2大于 c1或 ct = （c 2 + 米 2 （c 1 ， B 2 ）） 否則。它從減法開(kāi)始。請(qǐng)注意，我們使用 n 作為模數(shù)，我們將處于乘法和加法的完整鍵長(zhǎng)度。減法后，我們將結(jié)果從 maa_resw 移動(dòng)到 maa_aw，并復(fù)制我們的乘數(shù) m1或米 2 ，我們的參數(shù) c 成maa_bw，并開(kāi)始模乘法。在最后一步中，我們將乘法的結(jié)果從 maa_resw 復(fù)制到 maa_aw，然后復(fù)制 c1或 c 2 ，我們的參數(shù) b，進(jìn)入maa_bw并進(jìn)行模塊化加法。完成后，我們的純文本是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)
      ;
}

業(yè)績(jī)和結(jié)論

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

這里介紹的 C 實(shí)現(xiàn)旨在證明使用此算法可以提高速度。該代碼還顯示了如何操作 MAA。可以做很多事情來(lái)提高算法的速度，包括循環(huán)展開(kāi)、循環(huán)優(yōu)化、使用編譯器優(yōu)化的數(shù)據(jù)移動(dòng)例程以及使用匯編語(yǔ)言。

最快和最簡(jiǎn)單的速度改進(jìn)是操作MAA的MAMS寄存器，這將消除一些數(shù)據(jù)移動(dòng)。MAMS 寄存器允許我們重命名內(nèi)存段。為簡(jiǎn)單起見(jiàn)，此應(yīng)用程序中未完成此操作。

從理論上講，通過(guò)使用這種算法，應(yīng)該可以在提高速度的情況下接近 4 比 1 的時(shí)序比。

始終使用加密環(huán)作為您的加密時(shí)鐘源。這是通過(guò)清除電源管理寄存器 （PMR） 中的主加密源選擇（MCSS、PMR.7）來(lái)實(shí)現(xiàn)的。解密時(shí)，建議將模塊化算術(shù)加速器控制寄存器（MACT）的優(yōu)化計(jì)算控制（OCALC，MACT.4）清除為零，禁用該功能。

表 1.MAXQ1103 在25MHz，MAA運(yùn)行在加密環(huán)路| 大小 | 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.

我們首先找到幾個(gè)質(zhì)數(shù)。設(shè) p = 0xE747 和 q = 0xC7A5。兩者都是 16 位質(zhì)數(shù)。

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

我們可以選擇 e = 0x10001，因?yàn)?gcd（e， phi） = 1。這給了我們公鑰。我們的私鑰被選中，因此 e × d mod phi = 1。使用擴(kuò)展的歐幾里得算法，我們計(jì)算d = 0x9B111CC9。

我們?nèi)我膺x擇我們的純文本，pt = 0xABCDEF12。我們的密文，ct = pt^和^mod n = 0x87CCFE27。要恢復(fù)純文本，請(qǐng)執(zhí)行 ct^d^莫德·這是一個(gè) 32 位模冪。這原則上是 RSA 加密/解密過(guò)程。

現(xiàn)在我們將使用中文余數(shù)定理恢復(fù)純文本。

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

在線計(jì)算從通過(guò) mod p 減少密文開(kāi)始。密文長(zhǎng) 32 位，模長(zhǎng) 16 位。為了使用 MAA 進(jìn)行歸約，我們將模數(shù) p 向左移動(dòng) 16 位并將密文乘以 216。這看起來(lái)像0x87CCFE27 × 0x10000 mod 0xE7470000 = 0x36B00000?，F(xiàn)在我們將答案向右移動(dòng) 16 位，或者只抓住單詞的上部 16 位。我們需要這個(gè)值來(lái)執(zhí)行 16 位模冪0x36B0^德菲普^mod p，看起來(lái)像0x36B0^0x4AAB^模組 0xE747 = 0x6425 = PTP。

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

如果 ptp 大于 ptq，我們計(jì)算 （ptq + （ptp - ptq） × qiptq） mod n，否則我們計(jì)算 （ptp + （ptq - ptp） × piqtp） mod n。請(qǐng)記住，piqtp 和 qiptq 是預(yù)先計(jì)算的，長(zhǎng)度為 32 位。

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

審核編輯：郭婷