crypto/bn/test.c

   1 /* unused */
   2
   3 #include <stdio.h>
   4 #include "cryptlib.h"
   5 #include "bn_lcl.h"
   6
   7 #define SIZE    32
   8
   9 #define BN_MONT_CTX_set         bn_mcs
  10 #define BN_from_montgomery      bn_fm
  11 #define BN_mod_mul_montgomery   bn_mmm
  12 #undef BN_to_montgomery
  13 #define BN_to_montgomery(r,a,mont,ctx)  bn_mmm(\
  14         r,a,(mont)->RR,(mont),ctx)
  15
  16 main()
  17         {
  18         BIGNUM prime,a,b,r,A,B,R;
  19         BN_MONT_CTX *mont;
  20         BN_CTX *ctx;
  21         int i;
  22
  23         ctx=BN_CTX_new();
  24         BN_init(&prime);
  25         BN_init(&a); BN_init(&b); BN_init(&r);
  26         BN_init(&A); BN_init(&B); BN_init(&R);
  27
  28         BN_generate_prime(&prime,SIZE,0,NULL,NULL,NULL,NULL);
  29         BN_rand(&A,SIZE,1,0);
  30         BN_rand(&B,SIZE,1,0);
  31         BN_mod(&A,&A,&prime,ctx);
  32         BN_mod(&B,&B,&prime,ctx);
  33
  34         i=A.top;
  35         BN_mul(&R,&A,&B,ctx);
  36         BN_mask_bits(&R,i*BN_BITS2);
  37
  38
  39         BN_print_fp(stdout,&A); printf(" <- a\n");
  40         BN_print_fp(stdout,&B); printf(" <- b\n");
  41         BN_mul_high(&r,&A,&B,&R,i);
  42         BN_print_fp(stdout,&r); printf(" <- high(BA*DC)\n");
  43
  44         BN_mask_bits(&A,i*32);
  45         BN_mask_bits(&B,i*32);
  46
  47         BN_mul(&R,&A,&B);
  48         BN_rshift(&R,&R,i*32);
  49         BN_print_fp(stdout,&R); printf(" <- norm BA*DC\n");
  50         BN_sub(&R,&R,&r);
  51         BN_print_fp(stdout,&R); printf(" <- diff\n");
  52         }
  53
  54 #if 0
  55 int bn_mul_high(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *low, 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(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_MONT_CTX *mont,
 155              BN_CTX *ctx)
 156         {
 157         BIGNUM *tmp;
 158
 159         tmp= &(ctx->bn[ctx->tos++]);
 160
 161         if (a == b)
 162                 {
 163                 if (!BN_sqr(tmp,a,ctx)) goto err;
 164                 }
 165         else
 166                 {
 167                 if (!BN_mul(tmp,a,b)) goto err;
 168                 }
 169         /* reduce from aRR to aR */
 170         if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
 171         ctx->tos--;
 172         return(1);
 173 err:
 174         return(0);
 175         }
 176
 177 int BN_from_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx)
 178         {
 179         BIGNUM z1;
 180         BIGNUM *t1,*t2;
 181         BN_ULONG *ap,*bp,*rp;
 182         int j,i,bl,al;
 183
 184         BN_init(&z1);
 185         t1= &(ctx->bn[ctx->tos]);
 186         t2= &(ctx->bn[ctx->tos+1]);
 187
 188         if (!BN_copy(t1,a)) goto err;
 189         /* can cheat */
 190         BN_mask_bits(t1,mont->ri);
 191         if (!BN_mul(t2,t1,mont->Ni)) goto err;
 192         BN_mask_bits(t2,mont->ri);
 193
 194         if (!BN_mul(t1,t2,mont->N)) goto err;
 195         if (!BN_add(t2,t1,a)) goto err;
 196
 197         /* At this point, t2 has the bottom ri bits set to zero.
 198          * This means that the bottom ri bits == the 1^ri minus the bottom
 199          * ri bits of a.
 200          * This means that only the bits above 'ri' in a need to be added,
 201          * and XXXXXXXXXXXXXXXXXXXXXXXX
 202          */
 203 BN_print_fp(stdout,t2); printf("\n");
 204         BN_rshift(r,t2,mont->ri);
 205
 206         if (BN_ucmp(r,mont->N) >= 0)
 207                 BN_usub(r,r,mont->N);
 208
 209         return(1);
 210 err:
 211         return(0);
 212         }
 213
 214 int BN_MONT_CTX_set(BN_MONT_CTX *mont, BIGNUM *mod, BN_CTX *ctx)
 215         {
 216         BIGNUM *Ri=NULL,*R=NULL;
 217
 218         if (mont->RR == NULL) mont->RR=BN_new();
 219         if (mont->N == NULL)  mont->N=BN_new();
 220
 221         R=mont->RR;                                     /* grab RR as a temp */
 222         BN_copy(mont->N,mod);                           /* Set N */
 223
 224         mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
 225         BN_lshift(R,BN_value_one(),mont->ri);                   /* R */
 226         if ((Ri=BN_mod_inverse(NULL,R,mod,ctx)) == NULL) goto err;/* Ri */
 227         BN_lshift(Ri,Ri,mont->ri);                              /* R*Ri */
 228         BN_usub(Ri,Ri,BN_value_one());                          /* R*Ri - 1 */
 229         BN_div(Ri,NULL,Ri,mod,ctx);
 230         if (mont->Ni != NULL) BN_free(mont->Ni);
 231         mont->Ni=Ri;                                    /* Ni=(R*Ri-1)/N */
 232
 233         /* setup RR for conversions */
 234         BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
 235         BN_mod(mont->RR,mont->RR,mont->N,ctx);
 236
 237         return(1);
 238 err:
 239         return(0);
 240         }
 241
 242
 243 #endif