crypt_biginteger.c

ralink 2870 usb无线网卡 最新驱动

    } /* End of for */
    if (Carry64 > 0)
        Point_Of_Result[0] = (UINT32) (Carry64 & 0xffffffffUL);

    /*
     * Step3. calculate
     *           a_1*{a_2, a_3, a_4, ..., a_n}
     *           a_2*{a_3, a_4, a_5, ..., a_n}
     *           a_3*{a_4, a_5, a_6, ..., a_n}
     *           a_4*{a_5, a_6, a_7, ..., a_n}
     *           ...
     *           a_n-1*{a_n}
     */
    Point_Of_BI = pBI->pIntegerArray;
    for (BIFirstIndex=1; BIFirstIndex < (pBI->ArrayLength - 1); BIFirstIndex++)
    {
        Point_Of_Result = (*pBI_Result)->pIntegerArray;
        Point_Of_Result += (BIFirstIndex*2) + 1;
        TempValue64 = (UINT64) Point_Of_BI[BIFirstIndex];
        Carry64 = 0;
        for (BISecondIndex=(BIFirstIndex + 1); BISecondIndex < pBI->ArrayLength; BISecondIndex++)
        {
            Result64_1 = ((UINT64) Point_Of_Result[0]) + Carry64;
            Result64_2 = (UINT64) Point_Of_BI[BISecondIndex]*TempValue64;            
            Carry64 = (Result64_1 >> 32);
            Result64_1 = (Result64_1 & 0xffffffffUL);
            Result64_1 = Result64_1 + Result64_2;
            Carry64 += (Result64_1 >> 32);    
            Point_Of_Result[0] = (UINT32) (Result64_1 & 0xffffffffUL); 
            Point_Of_Result++;
        } /* End of for */
        if (Carry64 > 0)
            Point_Of_Result[0] += (UINT32) (Carry64 & 0xffffffffUL);
    } /* End of for */
    
    BigInteger_ClearHighBits(*pBI_Result);
    BigInteger_Copy(*pBI_Result, &pBI_O);
    
    Carry32 = 0;
	for (BIFirstIndex=0; BIFirstIndex < pBI_O->ArrayLength; BIFirstIndex++) {
        pBI_O->pIntegerArray[BIFirstIndex] = (pBI_O->pIntegerArray[BIFirstIndex] << 1) | Carry32;
        if (pBI_O->pIntegerArray[BIFirstIndex] < (*pBI_Result)->pIntegerArray[BIFirstIndex])
            Carry32 = 1;
        else
            Carry32 = 0;
    } /* End of for */
    pBI_O->pIntegerArray[BIFirstIndex] = Carry32;
    pBI_O->IntegerLength++;
    pBI_O->ArrayLength++;
    BigInteger_ClearHighBits(pBI_O);
    
    BigInteger_Add(pBI_O, pBI_S, pBI_Result);    
output:
    (*pBI_Result)->Signed = 1;
    BigInteger_ClearHighBits(*pBI_Result);
} /* End of BigInteger_Square */ 


VOID BigInteger_Div (
    IN PBIG_INTEGER pFirstOperand, 
    IN PBIG_INTEGER pSecondOperand, 
    OUT PBIG_INTEGER *pBI_Result,
    OUT PBIG_INTEGER *pBI_Remainder)
{
    INT CompareResult;
    INT Index, MulIndex, ComputeSize;
    UINT32 MulStart;
    UINT AllocLength, ArrayIndex, ShiftIndex;
    PBIG_INTEGER pTempBI = NULL, pTempBI2 = NULL, pMulBI = NULL;
    UINT8 SecondHighByte;

    if  ((pFirstOperand == NULL) || (pFirstOperand->pIntegerArray == NULL)
      || (pSecondOperand == NULL) || (pSecondOperand->pIntegerArray == NULL)) {
        DEBUGPRINT("BigInteger_Div: first or second operand is NULL.\n");
        return;
    } /* End of if */

    /* The second operand is zero */
    if ((pSecondOperand->IntegerLength == 1) && (pSecondOperand->pIntegerArray[0] == 0)) {
        DEBUGPRINT("BigInteger_Div: second operand is zero.\n");
        return;
    } /* End of if */

    if (*pBI_Result == NULL)
        BigInteger_Init(pBI_Result);
    if (*pBI_Remainder == NULL)
        BigInteger_Init(pBI_Remainder);

    /* The second operand is one */
    if  ((pSecondOperand->IntegerLength  == 1) && (pSecondOperand->pIntegerArray[0]  == 1)) {
        BigInteger_Copy(pFirstOperand, pBI_Result);
        BigInteger_Bin2BI(Value_0, 1, pBI_Remainder);        
        goto output;
    } /* End of if */

    CompareResult = BigInteger_UnsignedCompare(pFirstOperand, pSecondOperand);
    if (CompareResult == 0) {
        BigInteger_Bin2BI(Value_1, 1, pBI_Result);
        BigInteger_Bin2BI(Value_0, 1, pBI_Remainder);
        goto output;
    } else if (CompareResult == -1) {
        BigInteger_Bin2BI(Value_0, 1, pBI_Result);
        BigInteger_Copy(pFirstOperand, pBI_Remainder);
        goto output;
    } /* End of if */
    BigInteger_AllocSize(pBI_Result, pFirstOperand->IntegerLength - pSecondOperand->IntegerLength + 1);
    BigInteger_AllocSize(pBI_Remainder, pSecondOperand->IntegerLength);

    AllocLength = (UINT) (pFirstOperand->IntegerLength << 1);
    BigInteger_AllocSize(&pTempBI, AllocLength);
    BigInteger_AllocSize(&pTempBI2, AllocLength);
    BigInteger_AllocSize(&pMulBI, AllocLength);

    BigInteger_Copy(pFirstOperand, pBI_Remainder);
    SecondHighByte = BigInteger_GetByteValue(pSecondOperand, pSecondOperand->IntegerLength);   
    ComputeSize = (INT) pFirstOperand->IntegerLength - pSecondOperand->IntegerLength + 1;
    for (Index = (INT) ComputeSize;Index >= 0;Index--) {
        if (BigInteger_UnsignedCompare(*pBI_Remainder, pSecondOperand) == -1)
            break;        

        if (((pSecondOperand->IntegerLength + Index) - (*pBI_Remainder)->IntegerLength) <= 1) {
            BigInteger_AllocSize(&pMulBI, Index + 1);
            ArrayIndex = 0;
            if (Index > 0)
                ArrayIndex = (UINT) (Index - 1) >> 2 ;
            ShiftIndex = (Index & 0x03);
            if (ShiftIndex == 0)
                ShiftIndex = 4;
            ShiftIndex--;
            MulStart = 0;
            MulStart = (BigInteger_GetByteValue((*pBI_Remainder), pFirstOperand->IntegerLength + Index - ComputeSize + 1) & 0xFF) << 8;
            MulStart = MulStart | (BigInteger_GetByteValue((*pBI_Remainder), pFirstOperand->IntegerLength + Index - ComputeSize) & 0xFF);
            if (MulStart < (UINT32) SecondHighByte)
                continue;

            MulStart = MulStart / (UINT32) SecondHighByte;

            if (MulStart > 0xFF)
                MulStart = 0x100;

            for (MulIndex = (INT) MulStart;MulIndex <= 0x101;MulIndex++) { /* 0xFFFF / 0xFF = 0x101 */
                if ((MulIndex > 0xFF) && (ShiftIndex == 3))
                        pMulBI->pIntegerArray[ArrayIndex + 1] = 0x01;
                pMulBI->pIntegerArray[ArrayIndex] = ((UINT) MulIndex << (8*ShiftIndex));
                BigInteger_Mul(pSecondOperand, pMulBI , &pTempBI);
                CompareResult = BigInteger_UnsignedCompare(*pBI_Remainder, pTempBI);
                if (CompareResult < 1) {
                    if (MulIndex > 1) {
                        if (CompareResult != 0) {                            
                            if ((MulIndex == 0x100) && (ShiftIndex == 3))
                                   pMulBI->pIntegerArray[ArrayIndex + 1] = 0;
                            pMulBI->pIntegerArray[ArrayIndex] = ((UINT) (MulIndex - 1) << (8*ShiftIndex));
                        } /* End of if */
                        
                        BigInteger_Mul(pSecondOperand, pMulBI, &pTempBI);                        
                        BigInteger_Sub(*pBI_Remainder, pTempBI, &pTempBI2);
                        BigInteger_Copy(pTempBI2, pBI_Remainder);
                        BigInteger_Add(*pBI_Result, pMulBI, &pTempBI2);
                        BigInteger_Copy(pTempBI2, pBI_Result);
                    } /* End of if */
                    break;
                } /* End of if */

                if ((MulIndex >= 0x100) && (ShiftIndex == 3))
                   pMulBI->pIntegerArray[ArrayIndex++] = 0;
                pMulBI->pIntegerArray[ArrayIndex] = 0;
            } /* End of for */
        } /* End of if */
    } /* End of for */        

    BigInteger_Free(&pTempBI);
    BigInteger_Free(&pTempBI2);
    BigInteger_Free(&pMulBI);
output:
    (*pBI_Result)->Signed = pFirstOperand->Signed * pSecondOperand->Signed;
    (*pBI_Remainder)->Signed = pFirstOperand->Signed * pSecondOperand->Signed;
    BigInteger_ClearHighBits(*pBI_Result);
    BigInteger_ClearHighBits(*pBI_Remainder);    
} /* End of BigInteger_Div */


VOID BigInteger_Montgomery_Reduction (
    IN PBIG_INTEGER pBI_A,
    IN PBIG_INTEGER pBI_P,
     IN PBIG_INTEGER pBI_R,
    OUT PBIG_INTEGER *pBI_Result)
{
    UINT32 *Point_P, *Point_Result;
    UINT32 LoopCount;
    UINT64 Result64_1, Result64_2, Carry64, TempValue64;  
    INT FirstLoop, SecondLoop; 

    BigInteger_AllocSize(pBI_Result, pBI_A->IntegerLength+ pBI_P->IntegerLength + 20);
    BigInteger_Copy(pBI_A, pBI_Result);
    
    Point_P = pBI_P->pIntegerArray;
    Point_Result = (*pBI_Result)->pIntegerArray;
    
    LoopCount = Bits_Of_R >> 0x5;
    for (FirstLoop = 0;FirstLoop < LoopCount;FirstLoop++) {
        Carry64 = 0;
        TempValue64 = (UINT64) Point_Result[0];
        for (SecondLoop = 0;SecondLoop < pBI_P->ArrayLength;SecondLoop++) {
            Result64_1 = ((UINT64) Point_Result[SecondLoop]) + Carry64;
            Result64_2 = (UINT64) Point_P[SecondLoop]*TempValue64;            
            Carry64 = (Result64_1 >> 32);
            Result64_1 = (Result64_1 & 0xffffffffUL);
            Result64_1 = Result64_1 + Result64_2;            
            Carry64 += (Result64_1 >> 32);    
            Point_Result[SecondLoop] = (UINT32) (Result64_1 & 0xffffffffUL);            
        } /* End of for */
        while (Carry64 != 0) {
          Result64_1 = ((UINT64) Point_Result[SecondLoop]) + Carry64;
          Carry64 = Result64_1 >> 32;
          Point_Result[SecondLoop] = (UINT32) (Result64_1 & 0xffffffffUL);            
          SecondLoop++;
        } /* End of while */
        Point_Result++;
    } /* End of for */    

    for (FirstLoop = 0;FirstLoop <= LoopCount;FirstLoop++) {
        (*pBI_Result)->pIntegerArray[FirstLoop] = (*pBI_Result)->pIntegerArray[FirstLoop + LoopCount];
    } /* End of for */   
    if ((*pBI_Result)->pIntegerArray[LoopCount] != 0)
        (*pBI_Result)->ArrayLength = LoopCount + 1;
    else
        (*pBI_Result)->ArrayLength = LoopCount;

    (*pBI_Result)->IntegerLength = (*pBI_Result)->ArrayLength*4;
    BigInteger_ClearHighBits(*pBI_Result); 

    if (BigInteger_UnsignedCompare(*pBI_Result, pBI_P) >= 0) {
        BigInteger_Sub(*pBI_Result, pBI_P, &pBI_U);
        BigInteger_Copy(pBI_U, pBI_Result);
    } /* End of if */
    BigInteger_ClearHighBits(*pBI_Result); 
} /* End of BigInteger_Montgomery_Reduction */ 


VOID BigInteger_Montgomery_ExpMod (
    IN PBIG_INTEGER pBI_G,
    IN PBIG_INTEGER pBI_E,
    IN PBIG_INTEGER pBI_P,
    OUT PBIG_INTEGER *pBI_Result)
{
    UINT Bits_Of_P;
    UINT32 Index, Index2, AllocLength;
	UINT32 Sliding_Value , Sliding_HighValue, Sliding_LowValue;
    PBIG_INTEGER pBI_Temp1 = NULL, pBI_Temp2 = NULL;
    PBIG_INTEGER pBI_X = NULL, pBI_R = NULL, pBI_RR = NULL, pBI_1 = NULL;
    BIG_INTEGER *pBI_A[SLIDING_WINDOW];
    UINT8 *pRValue = NULL;

    AllocLength = (pBI_G->IntegerLength + pBI_E->IntegerLength + pBI_P->IntegerLength + 300);
    BigInteger_AllocSize(&pBI_Temp1, AllocLength);
    BigInteger_AllocSize(&pBI_Temp2, AllocLength);

    /* Calculate the bits of P and E, the highest bit is 1 */
    BigInteger_BitsOfBI(pBI_P, &Bits_Of_P);    

    if ((pBI_E->IntegerLength == 1) && (pBI_E->pIntegerArray[0] == 1)) {
        BigInteger_Div(pBI_G, pBI_P, &pBI_Temp1, pBI_Result);
        goto memory_free;
    } /* End of if */

    if ((pBI_E->IntegerLength == 1) && (pBI_E->pIntegerArray[0] == 2)) {
        BigInteger_Mul(pBI_G, pBI_G, &pBI_Temp1);
        BigInteger_Div(pBI_Temp1, pBI_P, &pBI_Temp2, pBI_Result);
        goto memory_free;
    } /* End of if */

    /*
     * Main algorithm
     */   
    BigInteger_Init(&pBI_R);
    BigInteger_Init(&pBI_RR);
    BigInteger_Bin2BI(Value_1, 1, &pBI_1);
    BigInteger_AllocSize(&pBI_X, AllocLength);
    BigInteger_AllocSize(&pBI_U, AllocLength); // for BigInteger_Montgomery_Reduction
    BigInteger_AllocSize(&pBI_S, AllocLength); // for BigInteger_Square    
    BigInteger_AllocSize(&pBI_O, AllocLength); // for BigInteger_Square
    
    for (Index = 0; Index < SLIDING_WINDOW; Index++) {
        pBI_A[Index] = NULL;
		BigInteger_AllocSize(&pBI_A[Index], 193);
    } /* End of for */
    BigInteger_Bin2BI(WPS_DH_P_VALUE, 192, &pBI_Temp1);
    if (NdisCmpMemory(pBI_P->pIntegerArray, pBI_Temp1->pIntegerArray, pBI_P->IntegerLength) == 0) {
        BigInteger_Bin2BI(WPS_DH_X_VALUE, 184, &pBI_X);
        BigInteger_Bin2BI(WPS_DH_R_VALUE, 193, &pBI_R);
        BigInteger_Bin2BI(WPS_DH_RRModP_VALUE, 192, &pBI_RR);
        Bits_Of_R = 1537;
    } else {
        if ((Bits_Of_P % 8) == 0) {
            AllocLength = pBI_P->IntegerLength + 1;
        } else {
            AllocLength = pBI_P->IntegerLength;
        } /* End of if */
        pRValue = (UINT8 *) kmalloc(sizeof(UINT8)*AllocLength, GFP_ATOMIC);
	if (pRValue == NULL)
	{
		DBGPRINT(RT_DEBUG_ERROR, ("%s():Alloc memory failed\n", __FUNCTION__));
		goto memory_free;
	}
        NdisZeroMemory(pRValue, sizeof(UINT8)*AllocLength);
        pRValue[0] = (UINT8) (1 << (Bits_Of_P & 0x7));
        BigInteger_Bin2BI(pRValue, AllocLength , &pBI_R);

        BigInteger_Mul(pBI_R, pBI_R, &pBI_Temp1);
        BigInteger_Div(pBI_Temp1, pBI_P, &pBI_A[1], &pBI_RR);	
        
        /* X = 1*R (mod P) */
        BigInteger_Div(pBI_R, pBI_P, &pBI_Temp2, &pBI_X);        
    } /* End of if */ 

    /* A = G*R (mod P) => A = MonMod(G, R^2 mod P) */	
    BigInteger_Mul(pBI_G, pBI_RR, &pBI_Temp1);
    BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P , pBI_R, &pBI_A[1]);
    for (Index = 2; Index < SLIDING_WINDOW; Index++) {
        BigInteger_Mul(pBI_A[Index - 1], pBI_A[1], &pBI_Temp1);
	    BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_A[Index]);
    } /* End of for */	

    for (Index = pBI_E->IntegerLength ; Index > 0 ; Index--) {	 	
        for (Index2 = 0; Index2 < 4 ; Index2++) {
            BigInteger_Square(pBI_X, &pBI_Temp1);
			BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_X);
	    } /* End of for */

		Sliding_Value = BigInteger_GetByteValue(pBI_E, Index);
		Sliding_HighValue = (Sliding_Value >> 4);
	 	if (Sliding_HighValue != 0) {
            BigInteger_Mul(pBI_A[Sliding_HighValue], pBI_X, &pBI_Temp1);
			BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_X);
	 	} /* End of if */

        for (Index2 = 0; Index2 < 4 ; Index2++) {
            BigInteger_Square(pBI_X, &pBI_Temp1);
			BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_X);
	    } /* End of for */

		Sliding_LowValue = Sliding_Value & 0x0f;
	 	if (Sliding_LowValue != 0) {
            BigInteger_Mul(pBI_A[Sliding_LowValue], pBI_X, &pBI_Temp1);
			BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_X);
	 	} /* End of if */
    } /* End of for */
    BigInteger_Montgomery_Reduction(pBI_X, pBI_P , pBI_R, pBI_Result);

    BigInteger_Free(&pBI_X);
    BigInteger_Free(&pBI_R);
    BigInteger_Free(&pBI_RR);
    BigInteger_Free(&pBI_1);
    BigInteger_Free(&pBI_U);
    BigInteger_Free(&pBI_S);
    BigInteger_Free(&pBI_O);
    for(Index = 0; Index < SLIDING_WINDOW; Index++)
			BigInteger_Free(&pBI_A[Index]);			
    if (pRValue != NULL)    
        kfree(pRValue);

memory_free:
    BigInteger_Free(&pBI_Temp1);
    BigInteger_Free(&pBI_Temp2);
} /* End of BigInteger_Montgomery_ExpMod */

/* End of crypt_biginteger.c */