文章/答案/技术大牛

发布

社区首页 >问答首页 >RSA硬件实现:基-2 montgomery乘法问题

问RSA硬件实现:基-2 montgomery乘法问题
EN

Stack Overflow用户

提问于 2017-01-10 22:48:37

回答 2查看 754关注 0票数 3

我正在硬件中实现RSA 1024 (xilinx )，并且无法找出一些奇怪的问题。最值得注意的是，我发现我的实现只适用于某些基/指数/模数组合，但没有找到任何理由来解释这种情况。

注意:我正在使用Xilinx实现该算法(本质上是将C代码合成到硬件中)。为了这篇文章，把它当作一个标准的C实现，除了我可以有高达4096位宽的变量之外。我还没有将它并行化，所以它的行为应该像标准C代码一样。

问题

我的问题是，对于某些模块指数测试问题，我能够得到正确的答案，但前提是基、指数和模数的值可以用比实际的1024位操作数宽少得多的位来写出(即它们是零填充的)。

当我使用从SSH生成的实际1024位值时，我不再得到正确的结果。

例如，如果我的输入参数是

uint1024_t base     = 1570
uint1024_t exponent = 1019
uint1024_t modulus  = 3337

我正确地得到了1570^1029 mod(3337) = 688的结果

但是，当我实际使用占用所有(或大约全部) 1024位的值作为输入时.

uint1024_t base     = 0x00be5416af9696937b7234421f7256f78dba8001c80a5fdecdb4ed761f2b7f955946ec920399f23ce9627f66286239d3f20e7a46df185946c6c8482e227b9ce172dd518202381706ed0f91b53c5436f233dec27e8cb46c4478f0398d2c254021a7c21596b30f77e9886e2fd2a081cadd3faf83c86bfdd6e9daad12559f8d2747
uint1024_t exponent = 0x6f1e6ab386677cdc86a18f24f42073b328847724fbbd293eee9cdec29ac4dfe953a4256d7e6b9abee426db3b4ddc367a9fcf68ff168a7000d3a7fa8b9d9064ef4f271865045925660fab620fad0aeb58f946e33bdff6968f4c29ac62bd08cf53cb8be2116f2c339465a64fd02517f2bafca72c9f3ca5bbf96b24c1345eb936d1
uint1024_t modulus  = 0xb4d92132b03210f62e52129ae31ef25e03c2dd734a7235efd36bad80c28885f3a9ee1ab626c30072bb3fd9906bf89a259ffd9d5fd75f87a30d75178b9579b257b5dca13ca7546866ad9f2db0072d59335fb128b7295412dd5c43df2c4f2d2f9c1d59d2bb444e6dac1d9cef27190a97aae7030c5c004c5aea3cf99afe89b86d6d

I错误地得到了一个庞大的数字，而不是29 (0x1D)的正确答案

我已经对这两种算法进行了上百万次的检查，并对不同的初始值和循环边界进行了实验，但似乎没有什么效果。

我的实施

我使用的标准平方和乘法的模指数，我选择了天丝-Koc基-2算法用于蒙哥马利乘法，详细说明以下伪码.

/* Tenca-Koc radix2 montgomery multiplication */
Z = 0
for i = 0 to n-1
    Z = Z + X[i]*Y
    if Z is odd then Z = Z + M
    Z = Z/2  // left shift in radix2
if (S >= M) then S = S - M

我的Montgomery乘法实现如下：

void montMult(uint1024_t X, uint1024_t Y, uint1024_t M, uint1024_t* outData)
{
    ap_uint<2*NUM_BITS> S = 0; 

    for (int i=0; i<NUM_BITS; i++)
    {
        // add product of X.get_bit(i) and Y to partial sum
        S += X[i]*Y; 

        // if S is even, add modulus to partial sum
        if (S.test(0))  
            S += M;     

        // rightshift 1 bit (divide by 2)
        S = S >> 1;
    }

    // bring back to under 1024 bits by subtracting modulus
    if (S >= M)
        S -= M;

    // write output data
    *outData = S.range(NUM_BITS-1,0);

}

我的顶层模指数如下(切换符号！)

// k: number of bits
// r = 2^k (radix)
// M: base
// e: exponent
// n: modulus
// Mbar: (precomputed residue) M*r mod(n)
// xbar: (precomputed initial residue) 1*r mod(n)

void ModExp(uint1024_t M, uint1024_t e, uint1024_t n, 
            uint1024_t Mbar, uint1024_t xbar, uint1024_t* out)
{
    for (int i=NUM_BITS-1; i>=0; i--)
    {
        // square
        montMult(xbar,xbar,n,&xbar);

        // multiply   
        if (e.test(i)) // if (e.bit(i) == 1)
            montMult(Mbar,xbar,n,&xbar);
    }
        // undo montgomery residue transformation
        montMult(xbar,1,n,out);
}

在我的一生中，我无法弄明白为什么这个方法适用于所有的东西，除了一个实际的1024位值。任何帮助都将不胜感激。

rsa

montgomery-multiplication

回答 2

Stack Overflow用户

回答已采纳

发布于 2017-01-15 18:19:59

更新:在我将设计移植到Java以检查调试器中的中间值之后，我终于能够修复这个问题。该设计在Java中运行得完美无缺，没有对代码结构进行任何修改，这让我了解了出了什么问题。

在使用BigInteger java包获得正确的中间值之后，问题就暴露了出来。HLS任意精度库具有固定的位宽(很明显，因为它是由硬件合成的)，而软件BigInteger库是灵活的位宽。事实证明，如果这两个参数是不同的位宽，加法运算符会将它们视为有符号值，尽管我将它们声明为无符号值。因此，当MSB中存在中间值为1时，我试图将其添加到更大的值中，它将MSB视为符号位，并试图对其进行签名扩展。

Java BigInt库没有出现这种情况，它很快就指出了问题所在。

如果有人感兴趣的话，您可以在这里找到下面的代码：https://github.com/bigbrett/MontModExp-radix2，如果有人感兴趣的话，您可以在蒙哥马利乘法中使用modular radix2算法实现模幂。

票数 1

Stack Overflow用户

发布于 2017-01-11 19:17:03

我代替了我的答案，因为我错了。你的原始代码是完全正确的。我使用自己的BigInteger库(包括蒙哥马利算法)对其进行了测试，一切都很有魅力。这是我的代码：

const
  base1     =
 '0x00be5416af9696937b7234421f7256f78dba8001c80a5fdecdb4ed761f2b7f955946ec9203'+
 '99f23ce9627f66286239d3f20e7a46df185946c6c8482e227b9ce172dd518202381706ed0f91'+
 'b53c5436f233dec27e8cb46c4478f0398d2c254021a7c21596b30f77e9886e2fd2a081cadd3f'+
 'af83c86bfdd6e9daad12559f8d2747';
  exponent1 =
 '0x6f1e6ab386677cdc86a18f24f42073b328847724fbbd293eee9cdec29ac4dfe953a4256d7e'+
 '6b9abee426db3b4ddc367a9fcf68ff168a7000d3a7fa8b9d9064ef4f271865045925660fab62'+
 '0fad0aeb58f946e33bdff6968f4c29ac62bd08cf53cb8be2116f2c339465a64fd02517f2bafc'+
 'a72c9f3ca5bbf96b24c1345eb936d1';
  modulus1  =
 '0xb4d92132b03210f62e52129ae31ef25e03c2dd734a7235efd36bad80c28885f3a9ee1ab626'+
 'c30072bb3fd9906bf89a259ffd9d5fd75f87a30d75178b9579b257b5dca13ca7546866ad9f2d'+
 'b0072d59335fb128b7295412dd5c43df2c4f2d2f9c1d59d2bb444e6dac1d9cef27190a97aae7'+
 '030c5c004c5aea3cf99afe89b86d6d';

function MontMult(X, Y, N: BigInteger): BigInteger;
var
  I: Integer;
begin
  Result:= 0;
  for I:= 0 to 1023 do begin
    if not X.IsEven then Result:= Result + Y;
    if not Result.IsEven then Result:= Result + N;
    Result:= Result shr 1;
    X:= X shr 1;
  end;
  if Result >= N then Result:= Result - N;
end;

function ModExp(B, E, N: BigInteger): BigInteger;
var
  R, MontB: BigInteger;
  I: Integer;

begin
  R:= BigInteger.PowerOfTwo(1024) mod N;
  MontB:= (B * R) mod N;
  for I:= 1023 downto 0 do begin
    R:= MontMult(R, R, N);
    if not (E shr I).IsEven then
      R:= MontMult(MontB, R, N);
  end;
  Result:= MontMult(R, 1, N);
end;

procedure TestMontMult;
var
  Base, Expo, Modulus: BigInteger;
  MontBase, MontExpo: BigInteger;
  X, Y, R: BigInteger;
  Mont: TMont;

begin
// convert to BigInteger
  Base:= BigInteger.Parse(base1);
  Expo:= BigInteger.Parse(exponent1);
  Modulus:= BigInteger.Parse(modulus1);

  R:= BigInteger.PowerOfTwo(1024) mod Modulus;
// Convert into Montgomery form
  MontBase:= (Base * R) mod Modulus;
  MontExpo:= (Expo * R) mod Modulus;
  Writeln;

// MontMult test, all 3 versions output
//  '0x146005377258684F3FFD8D9A70D723BDD3A2E3A160E11B7AD35A7106D4D903AB9D14A9201'+
//  'D0907CE2FC2E04A69656C38CE64AA0BADF2376AEFB19D8732CE2B3650466E31BB78CF24F4E3'+
//  '774A78575738B668DA0E40C8DDDA972CE101E0CADC5D4CCFF6EF2E4E97AF02F34E3AB7258A7'+
//  '323E472FC051825FFC72ADC53B0DAF3C4';
  Writeln('Using MontMult');
  Writeln(MontMult(MontMult(MontBase, MontExpo, Modulus), 1, Modulus).ToHexString);
// same using TMont instance
  Writeln('Using TMont.Multiply');
  Mont:= TMont.GetInstance(Modulus);
  Writeln(Mont.Reduce(Mont.Multiply(MontBase, MontExpo)).ToHexString);
  Writeln('Using TMont.ModMul');
  Writeln(Mont.ModMul(Base,Expo).ToHexString);

// ModExp test, all 3 versions output 29
  Writeln('Using ModExp');
  Writeln(ModExp(Base, Expo, Modulus).ToString);
  Writeln('Using BigInteger.ModPow');
  Writeln(BigInteger.ModPow(Base, Expo, Modulus).ToString);
  Writeln('Using TMont.ModPow');
  Writeln(Mont.ModPow(Base, Expo).ToString);
end;

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/41580311

复制

相似问题

问RSA硬件实现:基-2 montgomery乘法问题
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问RSA硬件实现:基-2 montgomery乘法问题EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问RSA硬件实现:基-2 montgomery乘法问题
EN