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(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *low, int words)
  54         {
  55         int i;
  56         BIGNUM t1,t2,t3,h,ah,al,bh,bl,m,s0,s1;
  57
  58         BN_init(&al); BN_init(&ah);
  59         BN_init(&bl); BN_init(&bh);
  60         BN_init(&t1); BN_init(&t2); BN_init(&t3);
  61         BN_init(&s0); BN_init(&s1);
  62         BN_init(&h); BN_init(&m);
  63
  64         i=a->top;
  65         if (i >= words)
  66                 {
  67                 al.top=words;
  68                 ah.top=a->top-words;
  69                 ah.d= &(a->d[ah.top]);
  70                 }
  71         else
  72                 al.top=i;
  73         al.d=a->d;
  74
  75         i=b->top;
  76         if (i >= words)
  77                 {
  78                 bl.top=words;
  79                 bh.top=i-words;
  80                 bh.d= &(b->d[bh.top]);
  81                 }
  82         else
  83                 bl.top=i;
  84         bl.d=b->d;
  85
  86         i=low->top;
  87         if (i >= words)
  88                 {
  89                 s0.top=words;
  90                 s1.top=i-words;
  91                 s1.d= &(low->d[s1.top]);
  92                 }
  93         else
  94                 s0.top=i;
  95         s0.d=low->d;
  96
  97 al.max=al.top; ah.max=ah.top;
  98 bl.max=bl.top; bh.max=bh.top;
  99 s0.max=bl.top; s1.max=bh.top;
 100
 101         /* Calculate (al-ah)*(bh-bl) */
 102         BN_sub(&t1,&al,&ah);
 103         BN_sub(&t2,&bh,&bl);
 104         BN_mul(&m,&t1,&t2);
 105
 106         /* Calculate ah*bh */
 107         BN_mul(&h,&ah,&bh);
 108
 109         /* s0 == low(al*bl)
 110          * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
 111          * We know s0 and s1 so the only unknown is high(al*bl)
 112          * high(al*bl) == s1 - low(ah*bh+(al-ah)*(bh-bl)+s0)
 113          */
 114         BN_add(&m,&m,&h);
 115         BN_add(&t2,&m,&s0);
 116         /* Quick and dirty mask off of high words */
 117         t3.d=t2.d;
 118         t3.top=(t2.top > words)?words:t2.top;
 119         t3.neg=t2.neg;
 120 t3.max=t3.top;
 121 /* BN_print_fp(stdout,&s1); printf(" s1\n"); */
 122 /* BN_print_fp(stdout,&t2); printf(" middle value\n"); */
 123 /* BN_print_fp(stdout,&t3); printf(" low middle value\n"); */
 124         BN_sub(&t1,&s1,&t3);
 125
 126         if (t1.neg)
 127                 {
 128 /*printf("neg fixup\n"); BN_print_fp(stdout,&t1); printf(" before\n"); */
 129                 BN_lshift(&t2,BN_value_one(),words*32);
 130                 BN_add(&t1,&t2,&t1);
 131                 BN_mask_bits(&t1,words*32);
 132 /* BN_print_fp(stdout,&t1); printf(" after\n"); */
 133                 }
 134         /* al*bl == high(al*bl)<<words+s0 */
 135         BN_lshift(&t1,&t1,words*32);
 136         BN_add(&t1,&t1,&s0);
 137
 138         /* We now have
 139          * al*bl                        - t1
 140          * (al-ah)*(bh-bl)+ah*bh        - m
 141          * ah*bh                        - h
 142          */
 143         BN_copy(r,&t1);
 144         BN_mask_bits(r,words*32*2);
 145
 146         /*BN_lshift(&m,&m,words*/
 147
 148         BN_free(&t1); BN_free(&t2);
 149         BN_free(&m); BN_free(&h);
 150         }
 151
 152 int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_MONT_CTX *mont,
 153              BN_CTX *ctx)
 154         {
 155         BIGNUM *tmp;
 156
 157         tmp= &(ctx->bn[ctx->tos++]);
 158
 159         if (a == b)
 160                 {
 161                 if (!BN_sqr(tmp,a,ctx)) goto err;
 162                 }
 163         else
 164                 {
 165                 if (!BN_mul(tmp,a,b)) goto err;
 166                 }
 167         /* reduce from aRR to aR */
 168         if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
 169         ctx->tos--;
 170         return(1);
 171 err:
 172         return(0);
 173         }
 174
 175 int BN_from_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx)
 176         {
 177         BIGNUM z1;
 178         BIGNUM *t1,*t2;
 179         BN_ULONG *ap,*bp,*rp;
 180         int j,i,bl,al;
 181
 182         BN_init(&z1);
 183         t1= &(ctx->bn[ctx->tos]);
 184         t2= &(ctx->bn[ctx->tos+1]);
 185
 186         if (!BN_copy(t1,a)) goto err;
 187         /* can cheat */
 188         BN_mask_bits(t1,mont->ri);
 189         if (!BN_mul(t2,t1,mont->Ni)) goto err;
 190         BN_mask_bits(t2,mont->ri);
 191
 192         if (!BN_mul(t1,t2,mont->N)) goto err;
 193         if (!BN_add(t2,t1,a)) goto err;
 194
 195         /* At this point, t2 has the bottom ri bits set to zero.
 196          * This means that the bottom ri bits == the 1^ri minus the bottom
 197          * ri bits of a.
 198          * This means that only the bits above 'ri' in a need to be added,
 199          * and XXXXXXXXXXXXXXXXXXXXXXXX
 200          */
 201 BN_print_fp(stdout,t2); printf("\n");
 202         BN_rshift(r,t2,mont->ri);
 203
 204         if (BN_ucmp(r,mont->N) >= 0)
 205                 BN_usub(r,r,mont->N);
 206
 207         return(1);
 208 err:
 209         return(0);
 210         }
 211
 212 int BN_MONT_CTX_set(BN_MONT_CTX *mont, BIGNUM *mod, BN_CTX *ctx)
 213         {
 214         BIGNUM *Ri=NULL,*R=NULL;
 215
 216         if (mont->RR == NULL) mont->RR=BN_new();
 217         if (mont->N == NULL)  mont->N=BN_new();
 218
 219         R=mont->RR;                                     /* grab RR as a temp */
 220         BN_copy(mont->N,mod);                           /* Set N */
 221
 222         mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
 223         BN_lshift(R,BN_value_one(),mont->ri);                   /* R */
 224         if ((Ri=BN_mod_inverse(NULL,R,mod,ctx)) == NULL) goto err;/* Ri */
 225         BN_lshift(Ri,Ri,mont->ri);                              /* R*Ri */
 226         BN_usub(Ri,Ri,BN_value_one());                          /* R*Ri - 1 */
 227         BN_div(Ri,NULL,Ri,mod,ctx);
 228         if (mont->Ni != NULL) BN_free(mont->Ni);
 229         mont->Ni=Ri;                                    /* Ni=(R*Ri-1)/N */
 230
 231         /* setup RR for conversions */
 232         BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
 233         BN_mod(mont->RR,mont->RR,mont->N,ctx);
 234
 235         return(1);
 236 err:
 237         return(0);
 238         }
 239
 240
 241 #endif