crypto/bn/test.c

   1 #include <stdio.h>
   2 #include "cryptlib.h"
   3 #include "bn_lcl.h"
   4
   5 #define SIZE    32
   6
   7 #define BN_MONT_CTX_set         bn_mcs
   8 #define BN_from_montgomery      bn_fm
   9 #define BN_mod_mul_montgomery   bn_mmm
  10 #undef BN_to_montgomery
  11 #define BN_to_montgomery(r,a,mont,ctx)  bn_mmm(\
  12         r,a,(mont)->RR,(mont),ctx)
  13
  14 main()
  15         {
  16         BIGNUM prime,a,b,r,A,B,R;
  17         BN_MONT_CTX *mont;
  18         BN_CTX *ctx;
  19         int i;
  20
  21         ctx=BN_CTX_new();
  22         BN_init(&prime);
  23         BN_init(&a); BN_init(&b); BN_init(&r);
  24         BN_init(&A); BN_init(&B); BN_init(&R);
  25
  26         BN_generate_prime(&prime,SIZE,0,NULL,NULL,NULL,NULL);
  27         BN_rand(&A,SIZE,1,0);
  28         BN_rand(&B,SIZE,1,0);
  29         BN_mod(&A,&A,&prime,ctx);
  30         BN_mod(&B,&B,&prime,ctx);
  31
  32         i=A.top;
  33         BN_mul(&R,&A,&B,ctx);
  34         BN_mask_bits(&R,i*BN_BITS2);
  35
  36
  37         BN_print_fp(stdout,&A); printf(" <- a\n");
  38         BN_print_fp(stdout,&B); printf(" <- b\n");
  39         BN_mul_high(&r,&A,&B,&R,i);
  40         BN_print_fp(stdout,&r); printf(" <- high(BA*DC)\n");
  41
  42         BN_mask_bits(&A,i*32);
  43         BN_mask_bits(&B,i*32);
  44
  45         BN_mul(&R,&A,&B);
  46         BN_rshift(&R,&R,i*32);
  47         BN_print_fp(stdout,&R); printf(" <- norm BA*DC\n");
  48         BN_sub(&R,&R,&r);
  49         BN_print_fp(stdout,&R); printf(" <- diff\n");
  50         }
  51
  52 #if 0
  53 int bn_mul_high(r,a,b,low,words)
  54 BIGNUM *r,*a,*b,*low;
  55 int words;
  56         {
  57         int i;
  58         BIGNUM t1,t2,t3,h,ah,al,bh,bl,m,s0,s1;
  59
  60         BN_init(&al); BN_init(&ah);
  61         BN_init(&bl); BN_init(&bh);
  62         BN_init(&t1); BN_init(&t2); BN_init(&t3);
  63         BN_init(&s0); BN_init(&s1);
  64         BN_init(&h); BN_init(&m);
  65
  66         i=a->top;
  67         if (i >= words)
  68                 {
  69                 al.top=words;
  70                 ah.top=a->top-words;
  71                 ah.d= &(a->d[ah.top]);
  72                 }
  73         else
  74                 al.top=i;
  75         al.d=a->d;
  76
  77         i=b->top;
  78         if (i >= words)
  79                 {
  80                 bl.top=words;
  81                 bh.top=i-words;
  82                 bh.d= &(b->d[bh.top]);
  83                 }
  84         else
  85                 bl.top=i;
  86         bl.d=b->d;
  87
  88         i=low->top;
  89         if (i >= words)
  90                 {
  91                 s0.top=words;
  92                 s1.top=i-words;
  93                 s1.d= &(low->d[s1.top]);
  94                 }
  95         else
  96                 s0.top=i;
  97         s0.d=low->d;
  98
  99 al.max=al.top; ah.max=ah.top;
 100 bl.max=bl.top; bh.max=bh.top;
 101 s0.max=bl.top; s1.max=bh.top;
 102
 103         /* Calculate (al-ah)*(bh-bl) */
 104         BN_sub(&t1,&al,&ah);
 105         BN_sub(&t2,&bh,&bl);
 106         BN_mul(&m,&t1,&t2);
 107
 108         /* Calculate ah*bh */
 109         BN_mul(&h,&ah,&bh);
 110
 111         /* s0 == low(al*bl)
 112          * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
 113          * We know s0 and s1 so the only unknown is high(al*bl)
 114          * high(al*bl) == s1 - low(ah*bh+(al-ah)*(bh-bl)+s0)
 115          */
 116         BN_add(&m,&m,&h);
 117         BN_add(&t2,&m,&s0);
 118         /* Quick and dirty mask off of high words */
 119         t3.d=t2.d;
 120         t3.top=(t2.top > words)?words:t2.top;
 121         t3.neg=t2.neg;
 122 t3.max=t3.top;
 123 // BN_print_fp(stdout,&s1); printf(" s1\n");
 124 // BN_print_fp(stdout,&t2); printf(" middle value\n");
 125 // BN_print_fp(stdout,&t3); printf(" low middle value\n");
 126         BN_sub(&t1,&s1,&t3);
 127
 128         if (t1.neg)
 129                 {
 130 //printf("neg fixup\n"); //BN_print_fp(stdout,&t1); printf(" before\n");
 131                 BN_lshift(&t2,BN_value_one(),words*32);
 132                 BN_add(&t1,&t2,&t1);
 133                 BN_mask_bits(&t1,words*32);
 134 // BN_print_fp(stdout,&t1); printf(" after\n");
 135                 }
 136         /* al*bl == high(al*bl)<<words+s0 */
 137         BN_lshift(&t1,&t1,words*32);
 138         BN_add(&t1,&t1,&s0);
 139
 140         /* We now have
 141          * al*bl                        - t1
 142          * (al-ah)*(bh-bl)+ah*bh        - m
 143          * ah*bh                        - h
 144          */
 145         BN_copy(r,&t1);
 146         BN_mask_bits(r,words*32*2);
 147
 148         /*BN_lshift(&m,&m,words*/
 149
 150         BN_free(&t1); BN_free(&t2);
 151         BN_free(&m); BN_free(&h);
 152         }
 153
 154 int BN_mod_mul_montgomery(r,a,b,mont,ctx)
 155 BIGNUM *r,*a,*b;
 156 BN_MONT_CTX *mont;
 157 BN_CTX *ctx;
 158         {
 159         BIGNUM *tmp;
 160
 161         tmp= &(ctx->bn[ctx->tos++]);
 162
 163         if (a == b)
 164                 {
 165                 if (!BN_sqr(tmp,a,ctx)) goto err;
 166                 }
 167         else
 168                 {
 169                 if (!BN_mul(tmp,a,b)) goto err;
 170                 }
 171         /* reduce from aRR to aR */
 172         if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
 173         ctx->tos--;
 174         return(1);
 175 err:
 176         return(0);
 177         }
 178
 179 int BN_from_montgomery(r,a,mont,ctx)
 180 BIGNUM *r;
 181 BIGNUM *a;
 182 BN_MONT_CTX *mont;
 183 BN_CTX *ctx;
 184         {
 185         BIGNUM z1;
 186         BIGNUM *t1,*t2;
 187         BN_ULONG *ap,*bp,*rp;
 188         int j,i,bl,al;
 189
 190         BN_init(&z1);
 191         t1= &(ctx->bn[ctx->tos]);
 192         t2= &(ctx->bn[ctx->tos+1]);
 193
 194         if (!BN_copy(t1,a)) goto err;
 195         /* can cheat */
 196         BN_mask_bits(t1,mont->ri);
 197         if (!BN_mul(t2,t1,mont->Ni)) goto err;
 198         BN_mask_bits(t2,mont->ri);
 199
 200         if (!BN_mul(t1,t2,mont->N)) goto err;
 201         if (!BN_add(t2,t1,a)) goto err;
 202
 203         /* At this point, t2 has the bottom ri bits set to zero.
 204          * This means that the bottom ri bits == the 1^ri minus the bottom
 205          * ri bits of a.
 206          * This means that only the bits above 'ri' in a need to be added,
 207          * and XXXXXXXXXXXXXXXXXXXXXXXX
 208          */
 209 BN_print_fp(stdout,t2); printf("\n");
 210         BN_rshift(r,t2,mont->ri);
 211
 212         if (BN_ucmp(r,mont->N) >= 0)
 213                 BN_usub(r,r,mont->N);
 214
 215         return(1);
 216 err:
 217         return(0);
 218         }
 219
 220 int BN_MONT_CTX_set(mont,mod,ctx)
 221 BN_MONT_CTX *mont;
 222 BIGNUM *mod;
 223 BN_CTX *ctx;
 224         {
 225         BIGNUM *Ri=NULL,*R=NULL;
 226
 227         if (mont->RR == NULL) mont->RR=BN_new();
 228         if (mont->N == NULL)  mont->N=BN_new();
 229
 230         R=mont->RR;                                     /* grab RR as a temp */
 231         BN_copy(mont->N,mod);                           /* Set N */
 232
 233         mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
 234         BN_lshift(R,BN_value_one(),mont->ri);                   /* R */
 235         if ((Ri=BN_mod_inverse(NULL,R,mod,ctx)) == NULL) goto err;/* Ri */
 236         BN_lshift(Ri,Ri,mont->ri);                              /* R*Ri */
 237         BN_usub(Ri,Ri,BN_value_one());                          /* R*Ri - 1 */
 238         BN_div(Ri,NULL,Ri,mod,ctx);
 239         if (mont->Ni != NULL) BN_free(mont->Ni);
 240         mont->Ni=Ri;                                    /* Ni=(R*Ri-1)/N */
 241
 242         /* setup RR for conversions */
 243         BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
 244         BN_mod(mont->RR,mont->RR,mont->N,ctx);
 245
 246         return(1);
 247 err:
 248         return(0);
 249         }
 250
 251
 252 #endif