crypto/bn/old/test.works

   1 #include <stdio.h>
   2 #include "cryptlib.h"
   3 #include "bn_lcl.h"
   4
   5 #define SIZE    128
   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         mont=BN_MONT_CTX_new();
  33         BN_MONT_CTX_set(mont,&prime,ctx);
  34
  35         BN_to_montgomery(&a,&A,mont,ctx);
  36         BN_to_montgomery(&b,&B,mont,ctx);
  37
  38         BN_mul(&r,&a,&b);
  39         BN_print_fp(stdout,&r); printf("\n");
  40         BN_from_montgomery(&r,&r,mont,ctx);
  41         BN_print_fp(stdout,&r); printf("\n");
  42         BN_from_montgomery(&r,&r,mont,ctx);
  43         BN_print_fp(stdout,&r); printf("\n");
  44
  45         BN_mod_mul(&R,&A,&B,&prime,ctx);
  46
  47         BN_print_fp(stdout,&a); printf("\n");
  48         BN_print_fp(stdout,&b); printf("\n");
  49         BN_print_fp(stdout,&prime); printf("\n");
  50         BN_print_fp(stdout,&r); printf("\n\n");
  51
  52         BN_print_fp(stdout,&A); printf("\n");
  53         BN_print_fp(stdout,&B); printf("\n");
  54         BN_print_fp(stdout,&prime); printf("\n");
  55         BN_print_fp(stdout,&R); printf("\n\n");
  56
  57         BN_mul(&r,&a,&b);
  58         BN_print_fp(stdout,&r); printf(" <- BA*DC\n");
  59         BN_copy(&A,&r);
  60         i=SIZE/2;
  61         BN_mask_bits(&A,i*2);
  62 //      BN_print_fp(stdout,&A); printf(" <- low(BA*DC)\n");
  63         bn_do_lower(&r,&a,&b,&A,i);
  64 //      BN_print_fp(stdout,&r); printf(" <- low(BA*DC)\n");
  65         }
  66
  67 int bn_mul_low(r,a,b,low,i)
  68 BIGNUM *r,*a,*b,*low;
  69 int i;
  70         {
  71         int w;
  72         BIGNUM Kh,Km,t1,t2,h,ah,al,bh,bl,l,m,s0,s1;
  73
  74         BN_init(&Kh); BN_init(&Km); BN_init(&t1); BN_init(&t2); BN_init(&l);
  75         BN_init(&ah); BN_init(&al); BN_init(&bh); BN_init(&bl); BN_init(&h);
  76         BN_init(&m); BN_init(&s0); BN_init(&s1);
  77
  78         BN_copy(&al,a); BN_mask_bits(&al,i); BN_rshift(&ah,a,i);
  79         BN_copy(&bl,b); BN_mask_bits(&bl,i); BN_rshift(&bh,b,i);
  80
  81
  82         BN_sub(&t1,&al,&ah);
  83         BN_sub(&t2,&bh,&bl);
  84         BN_mul(&m,&t1,&t2);
  85         BN_mul(&h,&ah,&bh);
  86
  87         BN_copy(&s0,low); BN_mask_bits(&s0,i);
  88         BN_rshift(&s1,low,i);
  89
  90         BN_add(&t1,&h,&m);
  91         BN_add(&t1,&t1,&s0);
  92
  93         BN_copy(&t2,&t1); BN_mask_bits(&t2,i);
  94         BN_sub(&t1,&s1,&t2);
  95         BN_lshift(&t1,&t1,i);
  96         BN_add(&t1,&t1,&s0);
  97         if (t1.neg)
  98                 {
  99                 BN_lshift(&t2,BN_value_one(),i*2);
 100                 BN_add(&t1,&t2,&t1);
 101                 BN_mask_bits(&t1,i*2);
 102                 }
 103
 104         BN_free(&Kh); BN_free(&Km); BN_free(&t1); BN_free(&t2);
 105         BN_free(&ah); BN_free(&al); BN_free(&bh); BN_free(&bl);
 106         }
 107
 108 int BN_mod_mul_montgomery(r,a,b,mont,ctx)
 109 BIGNUM *r,*a,*b;
 110 BN_MONT_CTX *mont;
 111 BN_CTX *ctx;
 112         {
 113         BIGNUM *tmp;
 114
 115         tmp= &(ctx->bn[ctx->tos++]);
 116
 117         if (a == b)
 118                 {
 119                 if (!BN_sqr(tmp,a,ctx)) goto err;
 120                 }
 121         else
 122                 {
 123                 if (!BN_mul(tmp,a,b)) goto err;
 124                 }
 125         /* reduce from aRR to aR */
 126         if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
 127         ctx->tos--;
 128         return(1);
 129 err:
 130         return(0);
 131         }
 132
 133 int BN_from_montgomery(r,a,mont,ctx)
 134 BIGNUM *r;
 135 BIGNUM *a;
 136 BN_MONT_CTX *mont;
 137 BN_CTX *ctx;
 138         {
 139         BIGNUM z1;
 140         BIGNUM *t1,*t2;
 141         BN_ULONG *ap,*bp,*rp;
 142         int j,i,bl,al;
 143
 144         BN_init(&z1);
 145         t1= &(ctx->bn[ctx->tos]);
 146         t2= &(ctx->bn[ctx->tos+1]);
 147
 148         if (!BN_copy(t1,a)) goto err;
 149         /* can cheat */
 150         BN_mask_bits(t1,mont->ri);
 151         if (!BN_mul(t2,t1,mont->Ni)) goto err;
 152         BN_mask_bits(t2,mont->ri);
 153
 154         if (!BN_mul(t1,t2,mont->N)) goto err;
 155         if (!BN_add(t2,t1,a)) goto err;
 156
 157         /* At this point, t2 has the bottom ri bits set to zero.
 158          * This means that the bottom ri bits == the 1^ri minus the bottom
 159          * ri bits of a.
 160          * This means that only the bits above 'ri' in a need to be added,
 161          * and XXXXXXXXXXXXXXXXXXXXXXXX
 162          */
 163 BN_print_fp(stdout,t2); printf("\n");
 164         BN_rshift(r,t2,mont->ri);
 165
 166         if (BN_ucmp(r,mont->N) >= 0)
 167                 bn_qsub(r,r,mont->N);
 168
 169         return(1);
 170 err:
 171         return(0);
 172         }
 173
 174 int BN_MONT_CTX_set(mont,mod,ctx)
 175 BN_MONT_CTX *mont;
 176 BIGNUM *mod;
 177 BN_CTX *ctx;
 178         {
 179         BIGNUM *Ri=NULL,*R=NULL;
 180
 181         if (mont->RR == NULL) mont->RR=BN_new();
 182         if (mont->N == NULL)  mont->N=BN_new();
 183
 184         R=mont->RR;                                     /* grab RR as a temp */
 185         BN_copy(mont->N,mod);                           /* Set N */
 186
 187         mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
 188         BN_lshift(R,BN_value_one(),mont->ri);                   /* R */
 189         if ((Ri=BN_mod_inverse(NULL,R,mod,ctx)) == NULL) goto err;/* Ri */
 190         BN_lshift(Ri,Ri,mont->ri);                              /* R*Ri */
 191         bn_qsub(Ri,Ri,BN_value_one());                          /* R*Ri - 1 */
 192         BN_div(Ri,NULL,Ri,mod,ctx);
 193         if (mont->Ni != NULL) BN_free(mont->Ni);
 194         mont->Ni=Ri;                                    /* Ni=(R*Ri-1)/N */
 195
 196         /* setup RR for conversions */
 197         BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
 198         BN_mod(mont->RR,mont->RR,mont->N,ctx);
 199
 200         return(1);
 201 err:
 202         return(0);
 203         }
 204
 205