Montgomery Modular exponentiation bug when base and/or mod is huge number

[udoya]

Hello,

I found the bug in ippsMontExp when base and mod is about 3000bit.

I follow the way of Developer Reference and still the result(h^r) I is not as correct.

Here is a my sample.

int main(void){
    int size;
    IppStatus status;
    BigNumber r("103"); // 0x67
    BigNumber one("1");

    BigNumber h("5449090679600687578338776553479118872432298572290928870679742785619636479251248346472555605484519059766766426142943941671505318691423762010190011204905135492023945858860836076270189946735341950294912380459398302220712281765893564617971017600510098611246211057367241717916199463844173961482981727611093474025923018806706916795960216328542939868206332039312759954813665101901189378967649376821420777326560330451567666945859000178371403947907603786686500046256486414456769313778048575928152608760588276266254039328617269808551045242705566603173767409280088284054884971357245041886501578972617335981581446994295396547751793228768370034043457439777242000700644619644766564571587108120269499535029074659937837326867261092576715483980869189448882408327575069300981005904989234156147519243200086908742881774483157756059536260466250265073826229131458761517858374892931099939693300493856684195741228344062664515839139164050413718519045");    
    
    const Ipp32u bnuN[] = {0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1c14ce86, 0xa53d1bda, 0x9100b5e4, 0x63485a06, 0x4552d67b, 0x655741b9, 0x28fcbe36, 0xf767a4c8, 0x44ad9154, 0xc266e11e, 0x299c18a1, 0x673c5ba9, 0x259b3b4f, 0xd2a4c300, 0x40585d42, 0x0f1423a6, 0x6ad8c9b1, 0xfc832962, 0x2a9f6381, 0x3c13d85f, 0xfe18ea33, 0x4652a456, 0x6ce0e6c0, 0xf06635c6, 0xe9bc59cd, 0x98fb76ed, 0xeeb7db1b, 0xa0bb225e, 0x839b2f0b, 0x4a91f039, 0x59895b79, 0xaadea763, 0x4b41ce9d, 0xe0470084, 0x56f258fe, 0x7a0e7587, 0x330ad4b2, 0x80d9d652, 0xd95a5920, 0x82d703ea, 0x72d05f65, 0xd624ef27, 0xc8f127af, 0xad3d55fe, 0x435fa2a6, 0x12019c6c, 0x8328b7f9, 0x043f98a3, 0xaba052c8, 0xc1767125, 0x7fcc4bf5, 0x1cbbfbe2, 0xe26c6160, 0xbb3bc200, 0xc6ea6de9, 0x1bea1b44, 0xe8282edf, 0xe078aa61, 0x3ee9b8fd, 0x3f48703f, 0x3b8ca38a, 0x8e6ef425, 0x66c4bd64, 0xa304523d, 0x7600e1cc, 0x3d97d8f2, 0x1557caa4, 0x621ccf30, 0x267d7bdc, 0x54e9d4a4, 0x9d28a5a0, 0x7e290150, 0x820dbcd9, 0x4578d827, 0x9196c051, 0xfe1179d9, 0xe38133e0, 0x3491de1f, 0xcfb2d351, 0x23e2124d, 0x8748f9dd, 0x6fcd7537, 0x8f51255b, 0x982bbbbb, 0xf2afd86d, 0xd87a117a, 0x4f59a94a, 0x1263a9bd};
        // N is "6677164904731211480198614762564282524490300079783629508786233755238546606699285130386011246760995454217650810780142069751608431649427994532073024346032610590505610617144327265491627833906120393616211106862422362408603231819846251505331510002105116783231853430052989509024316354844309903005791619030543283761587066792887302616387926731147270313067968893560808105159110930270953579404986741802359324663644515527138564803093954890858825814283507529994910502037666726157167787396232811351660243447753628398175125156828852031086970913459615089555937911982403705230839638745354172519091210007219203389761302071446848151518675316054644723348124453227516075033887271814552172860998071605178760295533077749272631504170380784580547531733117585471591183664707321531309773888934738066823298415611329111782397860307007283156542665486508997127534956511572601409252015190801796235345298648417283929904567063753968883177075760927687313457153"

    int length = (sizeof(bnuN)/sizeof(Ipp32u));

    status = ippsMontGetSize(IppsSlidingWindows, length, &size);
    IppsMontState* nMont = (IppsMontState*)( new Ipp8u [size] ); 
    status = ippsMontInit(IppsSlidingWindows, length, nMont);
    status = ippsMontSet(bnuN, length, nMont);

    IppsBigNumState* h_r = New_BN(length);

    IppsBigNumState* tmpA = New_BN(length);
    IppsBigNumState* tmpB = New_BN(length);

    // NOTE: want to do h^r
    status = ippsMontForm(h, nMont, tmpA);
    status = ippsMontExp(tmpA, r, nMont, tmpB);
    status = ippsMontMul(tmpB, one, nMont, h_r);

    Type_BN("h = ", h);
    Type_BN("r = ", r);
    Type_BN("h^r = ", h_r); // result is not same as python's pow(h, r, N)
    // it outputs h^r = 000000000e8036d26829ebcb9c6ac6bf40aef30bde8231dd00c61c564e145a768b958110ef862144f95a569258a8b45dd28ee5875ce83119fe23e15ea7d5f2e041c10f743c3aac10dc952e97748d1de748d14db63de5e807f88fd1fdcd06f8efd66bd88e81ce840a8a8b6c08587d9f84b8192b2c50de6a28f887446c6bf94c31dc8d9015a084f0c8cf9fcbde0b743449009ea0ab3e86a08e0d030cbef8c3fec954c6e6ba4d39697450b8d46a4aacad3206309f780110d120291dd96c93e60fbfc0093278e48d5cb8f24f6eb4e88860455f6158a31c4d70a8368af41d169a5168743abb512539d99d009a90dfe6d6647cd4b623db9e5a912ebf448693d90560560c841f1920cb827e6905c3b7a358be3c1ca8daf31fb57498adcb6831657388b1a68480a1b6713bf7b4f4d6588caa0c666d69256eb4a8635f3b056e47a97be758f53dac7b1d68fe839b74293d6ff44cec9253cec02d10f5fe803f9e2f2c0005fb6467f5738f230b271889a9abd71fb809bfaeeefd6a9e9a6b759352f7308e300f6e9f2e6e1dfee601
    // h^r should be 9b55fe83a068fb9cd4cf2a49cc2f110816adb3f4265629b870f5ad0396b31ef755c110f5e74658e92937be2ae30bba9fb29528c52f77a821ce88d91c4e14ff91ed11aca5ed005094d3b71869906131470544b28999e826016d9daf9369c263450dfb48820882a09efa6a32db18010ad82d9af2b99b6a137c64ef3d66451998544b4eb0298c8c3c2d55f77472f9d9fae7a9fa87fdc0dca5231da4af3f99c7675fcc582bf8799eac1ade6fb6fc2e3fd40000f87996e7f56063074402bb6114a51c41a125d9b4596e267ce491766c459175edbf7068f92fe555f12ca6e2e8db3a4eccf275ce923c8f339fd16b0ce7857e9831468637441a17e3558cdfa840c203a78c485ae76a06ebb8e820ce5496f60004fb083893cc58aa1d6973b04877ae7d1206ededeab0bc6d3be8857b555d9dfc38c5fc1ea253e4b36f10a27455d9a49ac5c12648d735de7463d0fcacb8c3336ee1c0c28c0db19b89a4c714b086f52f133d18f9d1b4b7b4d82bcc1c4fae5937082f6a41532d8b5fc68ca1e0144da0c4d85c

    return 0;
}

[udoya]

Can anybody help me with this?

[paveldyakov]

Hi @udoya,
Thank you for submitting the issue and sorry for the delay in response.
We need some time to investigate the provided reproducer.

[udoya]

I’m sorry that I incorrectly defined bnuN array (= [0x1, … , 0x1263a9bd] in my sample code.

Here shows the correct bnuN regarding N (= 667716…..457153).

const Ipp32u bnuN[] = { 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xc14ce860, 0x53d1bda1,
						0x100b5e4a, 0x3485a069, 0x552d67b6, 0x55741b94, 0x8fcbe366, 0x767a4c82, 0x4ad9154f, 0x266e11e4, 0x99c18a1c, 0x73c5ba92,
						0x59b3b4f6, 0x2a4c3002, 0x0585d42d, 0xf1423a64, 0xad8c9b10, 0xc8329626, 0xa9f6381f, 0xc13d85f2, 0xe18ea333, 0x652a456f,
						0xce0e6c04, 0x06635c66, 0x9bc59cdf, 0x8fb76ede, 0xeb7db1b9, 0x0bb225ee, 0x39b2f0ba, 0xa91f0398, 0x9895b794, 0xadea7635,
						0xb41ce9da, 0x04700844, 0x6f258fee, 0xa0e75875, 0x30ad4b27, 0x0d9d6523, 0x95a59208, 0x2d703ead, 0x2d05f658, 0x624ef277,
						0x8f127afd, 0xd3d55fec, 0x35fa2a6a, 0x2019c6c4, 0x328b7f91, 0x43f98a38, 0xba052c80, 0x1767125a, 0xfcc4bf5c, 0xcbbfbe27,
						0x26c61601, 0xb3bc200e, 0x6ea6de9b, 0xbea1b44c, 0x8282edf1, 0x078aa61e, 0xee9b8fde, 0xf48703f3, 0xb8ca38a3, 0xe6ef4253,
						0x6c4bd648, 0x304523d6, 0x600e1cca, 0xd97d8f27, 0x557caa43, 0x21ccf301, 0x67d7bdc6, 0x4e9d4a42, 0xd28a5a05, 0xe2901509,
						0x20dbcd97, 0x578d8278, 0x196c0514, 0xe1179d99, 0x38133e0f, 0x491de1fe, 0xfb2d3513, 0x3e2124dc, 0x748f9dd2, 0xfcd75378,
						0xf51255b6, 0x82bbbbb8, 0x2afd86d9, 0x87a117af, 0xf59a94ad, 0x263a9bd4]

Unfortunately, I'm still facing challenges in obtaining correct MontExp results even after this correction.

A colleague suggested that padding bnuN with [0x1] or [0x0, 0x1] might resolve the issue, which surprisingly led to the correct outcomes, although the reason behind its effectiveness remains unclear to us:

const Ipp32u bnuN[] = { 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xc14ce860, 0x53d1bda1,
                                                // elements omitted for brevity
						0xf51255b6, 0x82bbbbb8, 0x2afd86d9, 0x87a117af, 0xf59a94ad, 0x263a9bd4, 0x1]
// or 
const Ipp32u bnuN[] = { 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xc14ce860, 0x53d1bda1,
                                                // Elements omitted for brevity
						0xf51255b6, 0x82bbbbb8, 0x2afd86d9, 0x87a117af, 0xf59a94ad, 0x263a9bd4, 0x0, 0x1]

I would be deeply grateful for any insights or advice you could provide regarding why this padding approach works and whether it's a recommended practice for ensuring accuracy in calculations.