bignum_pow_mod_faster

[kingingo]

I am trying to implement the deffie-hellman-group14 but unfortunately bignum_pow_mod_faster gives me 0 back... I got a & b for testing from this site: http://acme.com/dhtest/dhtest.html

#include <string.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "bn.h"

uint32_t P[64] = { // Prime
     0xFFFFFFFF,0xFFFFFFFF,0xC90FDAA2,0x2168C234,0xC4C6628B,0x80DC1CD1
    ,0x29024E08,0x8A67CC74,0x020BBEA6,0x3B139B22,0x514A0879,0x8E3404DD
    ,0xEF9519B3,0xCD3A431B,0x302B0A6D,0xF25F1437,0x4FE1356D,0x6D51C245
    ,0xE485B576,0x625E7EC6,0xF44C42E9,0xA637ED6B,0x0BFF5CB6,0xF406B7ED
    ,0xEE386BFB,0x5A899FA5,0xAE9F2411,0x7C4B1FE6,0x49286651,0xECE45B3D
    ,0xC2007CB8,0xA163BF05,0x98DA4836,0x1C55D39A,0x69163FA8,0xFD24CF5F
    ,0x83655D23,0xDCA3AD96,0x1C62F356,0x208552BB,0x9ED52907,0x7096966D
    ,0x670C354E,0x4ABC9804,0xF1746C08,0xCA18217C,0x32905E46,0x2E36CE3B
    ,0xE39E772C,0x180E8603,0x9B2783A2,0xEC07A28F,0xB5C55DF0,0x6F4C52C9
    ,0xDE2BCBF6,0x95581718,0x3995497C,0xEA956AE5,0x15D22618,0x98FA0510
    ,0x15728E5A,0x8AACAA68,0xFFFFFFFF,0xFFFFFFFF,
};

void bignum_from_uint32(struct bn* n, uint32_t* ar, int length){
    int i;
    bignum_init(n);

    for(i=0; i < length; i++){
        n->array[i] = ar[i];
    }
}

/* O(log n) */
void bignum_pow_mod_faster(struct bn* a, struct bn* b, struct bn* n, struct bn* res){
  bignum_from_int(res, 1); /* r = 1 */

  struct bn tmpa;
  struct bn tmpb;
  struct bn tmp;
  bignum_assign(&tmpa, a);
  bignum_assign(&tmpb, b);
  bignum_init(&tmp);

  while (1)
  {

    if (tmpb.array[0] & 1)     /* if (b % 2) */
    {
      bignum_mul(res, &tmpa, &tmp);  /*   r = r * a % m */
      bignum_mod(&tmp, n, res);
    }
    bignum_rshift(&tmpb, &tmp, 1); /* b /= 2 */
    bignum_assign(&tmpb, &tmp);

    if (bignum_is_zero(&tmpb))
      break;

    bignum_mul(&tmpa, &tmpa, &tmp);
    bignum_mod(&tmp, n, &tmpa);
  }
}

void bignum_rand(struct bn* n){
    int i;
    for(i=0; i < BN_ARRAY_SIZE; i++){
        n->array[i] = rand();
    }
}

void main(void){
    int i;
    struct bn prime, 
    a,b,
    A,B,
    g,      //generator
    K_a,    //B^a mod prime
    K_b;    //A^b mod prime

    bignum_init(&a);
    bignum_init(&b);
    bignum_init(&A);
    bignum_init(&B);
    bignum_init(&K_a);
    bignum_init(&K_b);

    bignum_from_uint32(&prime, P, 64);
    print(&prime, "P");
    bignum_from_int(&g, 2);
    print(&g, "G");

    uint32_t ta[] = {
        0xfcc9a5d7,0x391df8fd,0x5e772975,0x8936c474,0xaa30b981,0xd17b1c92,0x194b11a9,0xa76ef75b,0xdf8b50dd,0xe5969ce,0x8068c602,0x13935eaf,0x82fc4d8d,0xb3bfb2c5,0x6f8f84cb,0x8e1966b2,0x1c45cd44,0x74c71ddc,0x428cf7d,0xa9e20c48,0xe2f178cb,0xe61b2e06,0x782373b6,0xe7ca18b4,0xeb60289a,0x5b76374d,0x72d301f5,0x196cbb6d,0x2b4e42d1,0x6575a616,0x2612a4f3,0x59cf2c7,0xdcf78046,0x51f0019,0x2d95f717,0x18542fc3,0x26788c6a,0x5ad9fb26,0xec644d3a,0x63824f53,0x73bf6e57,0x7e9adc44,0xadbd4f78,0x964e3add,0xed2ae2df,0xcf427594,0x4f2c52a7,0xde4f9a45,0xf3603134,0x857a7ef9,0x970d0a41,0xe2926f5e,0x5777022a,0x1c53f04,0xac36066a,0xf74a100,0x2d11b509,0xb6ef5cc0,0xe45e3744,0xc75a23e,0x8c4665ed,0x7382d0f5,0x87089069,0x4c580147
    };
    uint32_t tb[] = {
        0x43de3fb1,0x372a4b9f,0xab988c39,0xec229c26,0xc61e0a5b,0x923b467e,0x77b292a,0x329005a1,0xeb82f955,0xc08bf84d,0x19a57ab9,0xe2c3253b,0x4f933610,0xfd6b699f,0x62123379,0xf91fbf9a,0x63eafcab,0xa52d6e2e,0x4caa7ba7,0xf5024552,0x572becf3,0x528120af,0xd97ef711,0xa1cca982,0xc4ec3c59,0x8b9f2736,0xb6892085,0xc28a5366,0x64a594d,0xf8ac64a6,0x38d8e027,0x82937858,0x895bfb6e,0x787e51c6,0xda608660,0x359700d1,0xe23c56d2,0x5330b327,0xceafc4d3,0x76154cb3,0xf23c135a,0xe0e84f21,0x8a5caa5,0x929bccb9,0x23721701,0xa3d8a39a,0xf907e59d,0xc1880e42,0xaa6867b8,0x99ebd1ad,0x8403defc,0x40aa57f,0xe96830e,0x15cfbd39,0x66494f76,0x85a3c463,0xbd2143dd,0xeab6c439,0xde7987c9,0x94e2ce83,0x8e7802c5,0x44ad04a6,0x14f89058,0xe7c5f096
    };

    bignum_from_uint32(&a, ta, 64);
    print(&a, "a");

    bignum_from_uint32(&b, tb, 64);
    print(&b, "b");

    bignum_pow_mod_faster(&g, &a, &prime, &A); // g^a mod prime = A
    print(&A, "A");

    bignum_pow_mod_faster(&g, &b, &prime, &B); // g^b mod prime = B         
    print(&B, "B");

    bignum_pow_mod_faster(&B, &a, &prime, &K_a); // B^a mod prime = K
    print(&K_a, "K_a");
    bignum_pow_mod_faster(&A, &b, &prime, &K_b); // B^b mod prime = K
    print(&K_b, "K_b");

    printf("COMP K_a == K_b = %s\n", (bignum_cmp(&K_a,&K_b)==0?"EQUAL":"NOT EQUAL"));
    printf("K_a is %s\n", (bignum_is_zero(&K_a)==1?"ZERO":"NOT ZERO"));
    printf("K_b is %s\n", (bignum_is_zero(&K_b)==1?"ZERO":"NOT ZERO"));
}

void print(struct bn* n, char* c){
    int i;
    printf("%s: ",c);
    for(i=0; i < BN_ARRAY_SIZE; i++)
        printf("%02x ",n->array[i]);
    printf("\n");
    printf("\n");
}

[kokke]

Hi @kingingo and thanks for the question :)

A quick guess is that your calculations are overflowing.

---

From the pasted code, it looks like you are working with 2048 bit integers.

If you increment the integer size to, say 2080 bits or larger (260 bytes instead of 256 bytes), your calculations seem to work correctly.

At least, if I run the code with 2048 bit integers, I get this final result:

COMP K_a == K_b = EQUAL
K_a is ZERO
K_b is ZERO

... and with 2080 bit integers, it's this:

COMP K_a == K_b = NOT EQUAL
K_a is NOT ZERO
K_b is NOT ZERO

Let me know if you have any questions :)

EDIT:

The code in rsa.c is just for fun and games. It could probably be made much faster with Karatsuba-multiplication etc.