topic Alen, in Intel® Integrated Performance Primitives

Undefined Behaviour with ippsModInv_BN

Alen_Stojanov — Sat, 07 May 2016 01:28:34 GMT

Dear Intel Community,

I am trying to compute the multiplicative inverse of two numbers, using ippsModInv_BN. However, I get an undefined behaviour, and incorrect results. The issue occurs when executing the following:

#include <iostream>
#include <ippcore.h>
#include <ippcp.h>
#include <ipps.h>
#include <ippdefs.h>
#include <ippch.h>

// Use the BigNumber class available at https://software.intel.com/en-us/node/503848
// And initialize the values similarly to https://software.intel.com/en-us/node/503498
#include "xsample_bignum.h"

using namespace std;

void modInv (BigNumber& P, BigNumber& Q)
{

//  Calculate the multiplicative inverse of a positive integer - big number Q
//  with respect to specified modulus P, using the same routine as implemented
//  in xsample_bignum.cpp
//
//  BigNumber BigNumber::InverseMul(const BigNumber& a) const
//  {
//      BigNumber r(*this);
//      ippsModInv_BN(BN(a), BN(*this), BN(r));
//      return r;
//  }

    BigNumber R(P);
    IppStatus status = ippsModInv_BN(BN(Q), BN(P), BN(R));

    cout << "Status: ";
    switch (status) {
        case ippStsNoErr         : cout << "ippStsNoErr"         << endl; break;
        case ippStsBadArgErr     : cout << "ippStsBadArgErr"     << endl; break;
        case ippStsNullPtrErr    : cout << "ippStsNullPtrErr"    << endl; break;
        case ippStsBadModulusErr : cout << "ippStsBadModulusErr" << endl; break;
        case ippStsOutOfRangeErr : cout << "ippStsOutOfRangeErr" << endl; break;
        default:
            cout << "Unknown error code: " << status << endl;
    }

    cout << "P: " << P << endl;
    cout << "Q: " << Q << endl;
    cout << "R: " << R << endl;
    cout << endl << endl;
}

void test1 ()
{
    BigNumber P("0x098A0803974924E2671D9091044FE4ED0A6BA0978A9651D84EC5D2F97E3615CD555D504DD81B5832F884829D914ABD8AFEE8608A851AF569C3520C47E4D35646F");
    BigNumber Q("0x0BC612FF163A36AD648521120507CD2D4ADFC5DAC68856F6B45BBF101EFDB4A8D4656E8E2099C1DC3B7CFA16F57192ACA707E0C41E499837758E7A28E54BA6317");
    modInv(P, Q);

    // Expected:
    // 0x7F705DA34BC5CD9030BB4B5D0E4B2DEAC5734DD140076FA07C09B913F9C92B707247245BD0A96BD03EF1A84B11856519F8AB9247DC331C7B11A6B1636125AD16

    // Obtained:
    // 0x98A0803974924E2671D9091044FE4ED0A6BA0978A9651D84EC5D2F97E3615CD555D504DD81B5832F884829D914ABD8AFEE8608A851AF569C3520C47E4D35646F
}

void test2 ()
{
    BigNumber P("0x0BC612FF163A36AD648521120507CD2D4ADFC5DAC68856F6B45BBF101EFDB4A8D4656E8E2099C1DC3B7CFA16F57192ACA707E0C41E499837758E7A28E54BA6317");
    BigNumber Q("0x0B7EE5771917C2E470D42E54F8D40BE052BFA0413CC90E8DF14D983E1F490B6FE4B1856996417A0A5BDE8383BE18638D1A9DEC06E2E9386A289D6A1250D492973");
    modInv(P, Q);

    // Expected:
    // 0x5E73BECF77A0BE120FC9A1F7DBB69719755630772A95B840344737429CCAAB7E9D291B3E6E569EEDAEB92C88A389D4A50C8EEA795C5BB10401CA355878C72432

    // Obtained:
    // 0x5E73BECF77A0BE120FC9A1F7DBB69719755630772A95B840344737429CCAAB7E9D291B3E6E569EEDAEB92C88A389D4A50C8EEA795C5BB10401CA355878C72432
}

int main () {

    ippInit();
    cout << "Using Intel IPP Crypto" << endl;
    const IppLibraryVersion * version = ippsGetLibVersion ();
    printf("%s %s %s\n", version->Name, version->Version, version->BuildDate);
    cout << "================================================" << endl;

    test1 ();
    test2 ();
    return 0;
}

The problem occurs in the first test case (test1), and instead of the correct result, I get the same value of P. Furthermore, the status that is returned by ippsModInv_BN is -13, which does not correspond to the expected return values. The output that I obtain is the following:

Using Intel IPP Crypto
ippSP AVX (e9) 9.0.3 (r51269) Apr  8 2016
================================================

Uknown error code: -13
P:  0x98A0803974924E2671D9091044FE4ED0A6BA0978A9651D84EC5D2F97E3615CD555D504DD81B5832F884829D914ABD8AFEE8608A851AF569C3520C47E4D35646F
Q:  0xBC612FF163A36AD648521120507CD2D4ADFC5DAC68856F6B45BBF101EFDB4A8D4656E8E2099C1DC3B7CFA16F57192ACA707E0C41E499837758E7A28E54BA6317
R:  0x98A0803974924E2671D9091044FE4ED0A6BA0978A9651D84EC5D2F97E3615CD555D504DD81B5832F884829D914ABD8AFEE8608A851AF569C3520C47E4D35646F

ippStsNoErr
P:  0xBC612FF163A36AD648521120507CD2D4ADFC5DAC68856F6B45BBF101EFDB4A8D4656E8E2099C1DC3B7CFA16F57192ACA707E0C41E499837758E7A28E54BA6317
Q:  0xB7EE5771917C2E470D42E54F8D40BE052BFA0413CC90E8DF14D983E1F490B6FE4B1856996417A0A5BDE8383BE18638D1A9DEC06E2E9386A289D6A1250D492973
R:  0x5E73BECF77A0BE120FC9A1F7DBB69719755630772A95B840344737429CCAAB7E9D291B3E6E569EEDAEB92C88A389D4A50C8EEA795C5BB10401CA355878C72432

Is there any workaround for this issue ?

Thanks,
Alen

Alen,

Chao_Y_Intel — Mon, 09 May 2016 03:22:27 GMT

Alen,

Thanks for checking it. We are looking at this problem, and will provide you an update.

Thanks,
Chao

Hi Alen,

Chao_Y_Intel — Tue, 10 May 2016 07:59:21 GMT

Hi Alen,

It looks it has some issues in the code.
- In this case we deal with the ring Z/(p)
- So, any element x of that ring should satisfy 0<=x<p

In test1 we have:
p=0x098A0803974924E2671D9091044FE4ED0A6BA0978A9651D84EC5D2F97E3615CD555D504DD81B5832F884829D914ABD8AFEE8608A851AF569C3520C47E4D35646F
and
x=0x0BC612FF163A36AD648521120507CD2D4ADFC5DAC68856F6B45BBF101EFDB4A8D4656E8E2099C1DC3B7CFA16F57192ACA707E0C41E499837758E7A28E54BA6317

x>p (and so x is not belongs to ring)
- That is why the sample returns error status.

The following code (similar to customer’s one, but correct with IPP’s point of view) looks the following:
   // test1
   BigNumber P1("0x098A0803974924E2671D9091044FE4ED0A6BA0978A9651D84EC5D2F97E3615CD555D504DD81B5832F884829D914ABD8AFEE8608A851AF569C3520C47E4D35646F");
   BigNumber Q1("0x0BC612FF163A36AD648521120507CD2D4ADFC5DAC68856F6B45BBF101EFDB4A8D4656E8E2099C1DC3B7CFA16F57192ACA707E0C41E499837758E7A28E54BA6317");

   // make sure, that Q1 belongs to P1 ring
   BigNumber R1 = P1.Modulo(Q1);
   // compute multiplicative inversion
   R1 = P1.InverseMul(R1);
   cout <<"1/Q1 mod P1:" <<endl;
   cout <<R1 <<endl;
   // and test the result (R1*Q1) == 1 mod P1
   BigNumber T1 = Q1*R1;
   T1 = P1.Modulo(T1);
   cout <<"T1 = (Q1*R1) mod P1:" <<endl;
   cout <<T1 <<endl;

   // test2
   BigNumber P2("0x0BC612FF163A36AD648521120507CD2D4ADFC5DAC68856F6B45BBF101EFDB4A8D4656E8E2099C1DC3B7CFA16F57192ACA707E0C41E499837758E7A28E54BA6317");
   BigNumber Q2("0x0B7EE5771917C2E470D42E54F8D40BE052BFA0413CC90E8DF14D983E1F490B6FE4B1856996417A0A5BDE8383BE18638D1A9DEC06E2E9386A289D6A1250D492973");

   // make sure, that Q2 belongs to P2 ring
   BigNumber R2 = P2.Modulo(Q2);
   // compute multiplicative inversion
   R2 = P2.InverseMul(R2);
   cout <<"1/Q2 mod P2:" <<endl;
   cout <<R2 <<endl;
// and test the result (R2*Q2) == 1 mod P2
   BigNumber T2 = Q2*R2;
   T2 = P2.Modulo(T2);
   cout <<"T2 = (Q2*R2) mod P2:" <<endl;
   cout <<T2 <<endl;

In result of execution we get
1/Q1 mod P1:
0x7F705DA34BC5CD9030BB4B5D0E4B2DEAC5734DD140076FA07C09B913F9C92B707247245BD0A96BD03EF1A84B11856519F8AB9247DC331C7B11A6B1636125AD16
T1 = (Q1*R1) mod P1:
0x00000001
1/Q2 mod P2:
0x5E73BECF77A0BE120FC9A1F7DBB69719755630772A95B840344737429CCAAB7E9D291B3E6E569EEDAEB92C88A389D4A50C8EEA795C5BB10401CA355878C72432
T2 = (Q2*R2) mod P2:
0x00000001

so,
- the inversion values (R1 and R2) are equals to expected
- 1==R1*Q1 mod P1 and 1== R2*Q2 mod P2 – so the computed values are correct

ippsModInv_BN() function itself is fine.

That interpretation of “error” status is not very clear. we will look at how we can improve on this.

Thanks,
Chao