gpt4 book ai didi

c++ - 在RSA蒙哥马利乘法的不同MWR2MM算法中,Bizzare的错误结果相同

转载 作者:太空狗 更新时间:2023-10-29 21:13:09 25 4
gpt4 key购买 nike

背景

我正在尝试使用各种不同的蒙哥马利方法在硬件(xilinx ZYNQ FPGA)中实现RSA 2048。我正在使用Xilinx HLS(本质上是合成为硬件的C++代码)实现该算法。

注意:为了这篇文章的缘故,将其像标准C++实现一样对待,除了我可以使变量像位 vector 一样起作用,最大宽度为4096位,并使用foo[bit]foo.range(7,0)语法访问各个位。我尚未并行化它,因此它的行为应与标准C++代码一样。请不要害怕,不要停止阅读,因为我说的是FPGA和HLS。就像对待C++代码一样对待它。

我已经能够获得一个工作原型(prototype),该原型(prototype)使用标准的平方乘运算进行模幂运算,并使用标准的radix-2 MM算法进行模乘运算,但是它在FPGA上占用了太多空间,我需要使用较少的资源密集型算法。

为了节省空间,我正在尝试实现 Tenka-koc可伸缩多字基数2蒙哥马利乘法(MWR2MM)建议的here。我一直在努力一个月,但无济于事。然而,由于我的挣扎而产生了一个有趣的问题,我无法弄清。

问题

我的问题是执行Montgomery乘法时MWR2MM没有返回正确的答案。但是,我开始认为这不是编码错误,相反,我只是误解了有关算法使用的一些关键信息。

MWR2MM算法有多种变体,其实现方式也大不相同,我已经尝试实现其中的许多方法。我目前有4种不同的MWR2MM实现编码,所有这些实现都是基于对多篇论文中提出的算法的修改。 是什么让我认为我的实现实际上是正确的,是算法的所有这些不同版本都返回相同的INCORRECT答案! 我不认为这是巧合,但我也不认为已发布的算法是错误的...。因此,我认为实际上更有害的是,我的算法实现是正确的。

例子1

例如,以tenca-koc的论文中提出的最初提出的MWR2MM为例,我们将其称为MWR2MM_CSA,因为当以硬件实现时,算法的加法运算都使用进位加法器(CSA)。

  • S是部分和
  • M是模量
  • Y是被乘数
  • X是乘数,而x_i(下标)是单个位(例如X =(x_n,.​​..,x_1,x_0)。
  • 上标是单词 vector (例如M =(0,M ^ {e-1},...,M ^ 1,M ^ 0)
  • (A,B)是两个位 vector 的串联。
  • m是操作数宽度
  • w是所选单词的宽度
  • e是完成 vector 所需的w位字的数量,(e = ceil((m + 1)/ w))

  • enter image description here

    我对该算法的实现使用以下参数:
  • MWR2MM_m = 2048 (operand size, m from above)
  • MWR2MM_w = 8 (word size, w from above)
  • MWR2MM_e = ceil( (e+1)/w ) = 257 (number of words + 1 per operand, e from above)
  • ap_uint<NUM_BITS>是如何在HLS中声明位 vector

  • 我的代码:
    void mwr2mm_csa( ap_uint<MWR2MM_m> X,
    ap_uint<MWR2MM_w> Y[MWR2MM_e+1],
    ap_uint<MWR2MM_w> M[MWR2MM_e+1],
    ap_uint<MWR2MM_m> *out)
    {
    // Declare and zero partial sum S
    ap_uint<MWR2MM_w> S[MWR2MM_e] = 0;
    for (int i=0; i<MWR2MM_e; i++)
    S[i] = 0;

    // Two Carry bits
    ap_uint<1> Ca=0, Cb=0;

    for (int i=0; i<MWR2MM_m; i++)
    {
    (Ca,S[0]) = X[i]*Y[0] + S[0]; // this is how HLS concatenates vectors, just like in the paper!
    if (S[0][0] == 1) // if the 0th bit of the 0th word is 1
    {
    (Cb,S[0]) = S[0] + M[0];
    for (int j=1; j<=MWR2MM_e; j++)
    {
    (Ca, S[j]) = Ca + X[i]*Y[j] + S[j];
    (Cb, S[j]) = Cb + M[j] + S[j];
    S[j-1] = ( S[j][0], S[j-1].range(MWR2MM_w-1,1) );
    }
    }
    else
    {
    for (int j=1; j<=MWR2MM_e; j++)
    {
    (Ca, S[j]) = Ca + X[i]*Y[j] + S[j];
    S[j-1] = ( S[j][0], S[j-1].range(MWR2MM_w-1,1) );
    }
    }
    }

    // copy the result to the output pointer
    for (int i=0; i<MWR2MM_e-1; i++)
    out->range(MWR2MM_w*i+(MWR2MM_w-1), MWR2MM_w*i) = S[i].to_uchar();
    }

    现在,据我了解(引用上面的论文)

    the Montgomery Multiplication (MM) algorithm on two integers X and Y , with required parameters for n bits of precision, will result in the number MM(X,Y,M) = XY(2^-n) (modulo m), where r=2^n and M is an integer in the range (2^(n-1), 2^(n)) such that gcd(r,M)=1. Since r=2^n , it is sufficient that the modulus M be an odd integer.



    因此,我们应该期待以下结果(经过软件库验证):
    X = 0xABA5E025B607AA14F7F1B8CC88D6EC01C2D17C536508E7FA10114C9437D9616C9E1C689A4FC54744FA7DFE66D6C2FCF86E332BFD6195C13FE9E331148013987A947D9556A27A326A36C84FB38BFEFA0A0FFA2E121600A4B6AA4F9AD2F43FB1D5D3EB5EABA13D3B382FED0677DF30A089869E4E93943E913D0DC099AA320B8D8325B2FC5A5718B19254775917ED48A34E86324ADBC8549228B5C7BEEEFA86D27A44CEB204BE6F315B138A52EC714888C8A699F6000D1CD5AB9BF261373A5F14DA1F568BE70A0C97C2C3EFF0F73F7EBD47B521184DC3CA932C91022BF86DD029D21C660C7C6440D3A3AE799097642F0507DFAECAC11C2BD6941CBC66CEDEEAB744
    Y = 0xD091BE9D9A4E98A172BD721C4BC50AC3F47DAA31522DB869EB6F98197E63535636C8A6F0BA2FD4C154C762738FBC7B38BDD441C5B9A43B347C5B65CFDEF4DCD355E5E6F538EFBB1CC161693FA2171B639A2967BEA0E3F5E429D991FE1F4DE802D2A1D600702E7D517B82BFFE393E090A41F57E966A394D34297842552E15550B387E0E485D81C8CCCAAD488B2C07A1E83193CE757FE00F3252E4BD670668B1728D73830F7AE7D1A4C02E7AFD913B3F011782422F6DE4ED0EF913A3A261176A7D922E65428AE7AAA2497BB75BFC52084EF9F74190D0D24D581EB0B3DAC6B5E44596881200B2CE5D0FB2831D65F036D8E30D5F42BECAB3A956D277E3510DF8CBA9
    M = 0xD27BF9F01E2A901DB957879F45F697330D21A21095DA4FA7D3AAB75454A8E9F0F4EA531ECE34F0C3BA9E02EB27D8F0DBE78EEDE4AC84061BEEF162D00B55C0DD772D28F23E994899AA19B9BEA7B12A8027A32A92190A3630E249544675488121565A23548FCD36F5382EEB993DB9CE3F526F20AB355E82D963D59541BC1161E211A03E3B372560840C57E12BD2F40EAC5FFCEC01B3F07C378C0A60B74BEF7B572764C88A4F98B61FA8CCD905AFAE779E6193378304D8EB17695CE71A173AC3DE11271753C48DB58546E5AF9917C1CEBBA5BB1AF3FCE3DF9516C0C95C9BC14BB65D1C53078C06C81AC0F3ED0D8634260E47BF780CF4F4996084DF732935194417
    MM(X,Y,M) = 0x444682CC199679928F5971191ACCB8EAA5C76CF743E54FC28FD8DCFF57BD198677A26A5C1A6254810A91049FA85CBE3EDDFDCDF12ED3FBB204DE249C389CDEE3FA6DB65441AFE03F1148660EA0E756E038891CEF098F2A009FB443685202FAC40D8FE7B82A1F643020EA31F5A8F4B253AD2F30028C59F1E2DCF3902BBC48E73ECA7BDC22BB92E8A70BC535584BF644CAF24EF39A1899F18C05937446AACC5C64762AFAD2B73EEDF3AA96C9A4CFF836A551A26AED46279328EDD4B9BBBC182B9E408640D058926882B3A0FAA043F726EF96E07B7960D586E2648534EB15C23FE152D0D088F1742E023715E3ABAEC8128B51CC86E8BC207D69F1E6BA7067D44429

    但是,我的算法返回了
    MWR2MM_csa(X,Y,M) = 0x16C27CBC37C109B048B0F8B860C3501DB2E90F07D9BF9F6A63839453AC6603776C8CBD7AE8974544C52F078AD035AF1AC58CBBD5DB5801CDF3CF876C43F29FC1719ADF46804928D8BB621FCD48988160602C47812299603181FD97AEC74B7BE563EA0B0CB9EC9B2559191D8EE6AE8092FF9E50ADC1B874BC40C9256D785A4920DC1C1A5DF2B8492B181D16841EEA5377524BDF9BCC8A6DC3919DD4FDF6BBD7BB9D8FC35D06D7A4135363A2AA7FA6AE43B335A2704B007E405731A0D5D352EF7C51AD58241D201E07FA86AA395BB8F5AB3C9B966D5DB966777B45FE47B1838B97AFED23907D7AF61CF809D0B934FC3899998BFEF5B11516CA76C62D999CED8840

    例子2

    好的,所以也许实现是错误的。让我们尝试另一个修改版本,即MWR2MM_CPA算法(以硬件中使用的进位传播加法器命名):
    enter image description here

    而我的MWR2MM_CSA实现:
    void mwr2mm_cpa(rsaSize_t X, rsaSize_t Yin, rsaSize_t Min, rsaSize_t* out)
    {
    // extend operands to 2 extra words longer
    ap_uint<MWR2MM_m+2*MWR2MM_w> Y = Yin;
    ap_uint<MWR2MM_m+2*MWR2MM_w> M = Min;
    ap_uint<MWR2MM_m+2*MWR2MM_w> S = 0;

    ap_uint<2> C = 0;
    bit_t qi = 0;

    // unlike the previous example, we store the concatenations in a temporary variable
    ap_uint<10> temp_concat=0;

    for (int i=0; i<MWR2MM_m; i++)
    {
    qi = (X[i]*Y[0]) xor S[0];

    // C gets top two bits of temp_concat, j'th word of S gets bottom 8 bits of temp_concat
    temp_concat = X[i]*Y.range(MWR2MM_w-1,0) + qi*M.range(MWR2MM_w-1,0) + S.range(MWR2MM_w-1,0);
    C = temp_concat.range(9,8);
    S.range(MWR2MM_w-1,0) = temp_concat.range(7,0);

    for (int j=1; j<=MWR2MM_e; j++)
    {
    temp_concat = C + X[i]*Y.range(MWR2MM_w*j+(MWR2MM_w-1), MWR2MM_w*j) + qi*M.range(MWR2MM_w*j+(MWR2MM_w-1), MWR2MM_w*j) + S.range(MWR2MM_w*j+(MWR2MM_w-1), MWR2MM_w*j);
    C = temp_concat.range(9,8);
    S.range(MWR2MM_w*j+(MWR2MM_w-1), MWR2MM_w*j) = temp_concat.range(7,0);

    S.range(MWR2MM_w*(j-1)+(MWR2MM_w-1), MWR2MM_w*(j-1)) = (S.bit(MWR2MM_w*j), S.range( MWR2MM_w*(j-1)+(MWR2MM_w-1), MWR2MM_w*(j-1)+1));
    }
    S.range(S.length()-1, S.length()-MWR2MM_w) = 0;
    C=0;
    }

    *out = S;

    }

    当使用相同的X,Y和M运行时,即使位级操作不同,它也返回与MWR2MM_CSA完全相同的错误结果。
    MWR2MM_cpa(X,Y,M) = 0x16C27CBC37C109B048B0F8B860C3501DB2E90F07D9BF9F6A63839453AC6603776C8CBD7AE8974544C52F078AD035AF1AC58CBBD5DB5801CDF3CF876C43F29FC1719ADF46804928D8BB621FCD48988160602C47812299603181FD97AEC74B7BE563EA0B0CB9EC9B2559191D8EE6AE8092FF9E50ADC1B874BC40C9256D785A4920DC1C1A5DF2B8492B181D16841EEA5377524BDF9BCC8A6DC3919DD4FDF6BBD7BB9D8FC35D06D7A4135363A2AA7FA6AE43B335A2704B007E405731A0D5D352EF7C51AD58241D201E07FA86AA395BB8F5AB3C9B966D5DB966777B45FE47B1838B97AFED23907D7AF61CF809D0B934FC3899998BFEF5B11516CA76C62D999CED8840

    为简便起见,我将为您省去另外两个也会返回相同错误结果的算法。我应该注意,当使用4位操作数大小和2位字大小时,这两种算法都可以正常工作。但是,任何其他操作数大小/字长组合都不正确,但是对于所有四个不同的位级实现,其结果都相同。

    我一生都无法弄清楚为什么所有四种算法都返回相同的错误结果。我在第一个示例中的代码从字面上逐字地与tenca-koc论文中提出的算法相同!

    我是否认为MWR2MM算法应返回与标准radix-2 MM算法相同的结果(在蒙哥马利域中)是否错误?它们具有相同的基数,因此无论字长如何,结果都应相同。我是否应该不能互换这些算法?

    对于冗长的帖子,我们深表歉意,但是我想非常准确,连贯地解释问题所在。 我不是在寻求调试我的代码的帮助,而是试图弄清楚我是否误解了蒙哥马利乘法算法的基本功能。也很好奇为什么不同的实现会给出相同的 和WRONG 结果。

    谢谢!

    最佳答案

    问题是您的算法实际上返回:

    0x116c27cbc37...
    ^

    大于M。如果从中减去M,则会得到预期的答案:

    两种算法都返回0到2 * M范围内的值,因此,如果答案大于或等于M,则需要最后的减法阶段。

    换句话说,如果您使用随机选择的X和Y来测试算法,则应该发现有一半的时间给出了正确的答案。

    从本文的第2节:

    Thus only one conditional subtraction is necessary to bring S[n] to the required range 0 ≤ S[n] < M. This subtraction will be omitted in the subsequent discussion since it is independent of the specific algorithm and architecture and can be treated as a part of post processing.

    关于c++ - 在RSA蒙哥马利乘法的不同MWR2MM算法中,Bizzare的错误结果相同,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45361318/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com