--- /dev/null
+#include <stdio.h>
+#include "cryptlib.h"
+#include "bn_lcl.h"
+
+#define SIZE 128
+
+#define BN_MONT_CTX_set bn_mcs
+#define BN_from_montgomery bn_fm
+#define BN_mod_mul_montgomery bn_mmm
+#undef BN_to_montgomery
+#define BN_to_montgomery(r,a,mont,ctx) bn_mmm(\
+ r,a,(mont)->RR,(mont),ctx)
+
+main()
+ {
+ BIGNUM prime,a,b,r,A,B,R;
+ BN_MONT_CTX *mont;
+ BN_CTX *ctx;
+ int i;
+
+ ctx=BN_CTX_new();
+ BN_init(&prime);
+ BN_init(&a); BN_init(&b); BN_init(&r);
+ BN_init(&A); BN_init(&B); BN_init(&R);
+
+ BN_generate_prime(&prime,SIZE,0,NULL,NULL,NULL,NULL);
+ BN_rand(&A,SIZE,1,0);
+ BN_rand(&B,SIZE,1,0);
+ BN_mod(&A,&A,&prime,ctx);
+ BN_mod(&B,&B,&prime,ctx);
+
+ mont=BN_MONT_CTX_new();
+ BN_MONT_CTX_set(mont,&prime,ctx);
+
+ BN_to_montgomery(&a,&A,mont,ctx);
+ BN_to_montgomery(&b,&B,mont,ctx);
+
+ BN_mul(&r,&a,&b);
+ BN_print_fp(stdout,&r); printf("\n");
+ BN_from_montgomery(&r,&r,mont,ctx);
+ BN_print_fp(stdout,&r); printf("\n");
+ BN_from_montgomery(&r,&r,mont,ctx);
+ BN_print_fp(stdout,&r); printf("\n");
+
+ BN_mod_mul(&R,&A,&B,&prime,ctx);
+
+ BN_print_fp(stdout,&a); printf("\n");
+ BN_print_fp(stdout,&b); printf("\n");
+ BN_print_fp(stdout,&prime); printf("\n");
+ BN_print_fp(stdout,&r); printf("\n\n");
+
+ BN_print_fp(stdout,&A); printf("\n");
+ BN_print_fp(stdout,&B); printf("\n");
+ BN_print_fp(stdout,&prime); printf("\n");
+ BN_print_fp(stdout,&R); printf("\n\n");
+
+ BN_mul(&r,&a,&b);
+ BN_print_fp(stdout,&r); printf(" <- BA*DC\n");
+ BN_copy(&A,&r);
+ i=SIZE/2;
+ BN_mask_bits(&A,i*2);
+// BN_print_fp(stdout,&A); printf(" <- low(BA*DC)\n");
+ bn_do_lower(&r,&a,&b,&A,i);
+// BN_print_fp(stdout,&r); printf(" <- low(BA*DC)\n");
+ }
+
+int bn_mul_low(r,a,b,low,i)
+BIGNUM *r,*a,*b,*low;
+int i;
+ {
+ int w;
+ BIGNUM Kh,Km,t1,t2,h,ah,al,bh,bl,l,m,s0,s1;
+
+ BN_init(&Kh); BN_init(&Km); BN_init(&t1); BN_init(&t2); BN_init(&l);
+ BN_init(&ah); BN_init(&al); BN_init(&bh); BN_init(&bl); BN_init(&h);
+ BN_init(&m); BN_init(&s0); BN_init(&s1);
+
+ BN_copy(&al,a); BN_mask_bits(&al,i); BN_rshift(&ah,a,i);
+ BN_copy(&bl,b); BN_mask_bits(&bl,i); BN_rshift(&bh,b,i);
+
+
+ BN_sub(&t1,&al,&ah);
+ BN_sub(&t2,&bh,&bl);
+ BN_mul(&m,&t1,&t2);
+ BN_mul(&h,&ah,&bh);
+
+ BN_copy(&s0,low); BN_mask_bits(&s0,i);
+ BN_rshift(&s1,low,i);
+
+ BN_add(&t1,&h,&m);
+ BN_add(&t1,&t1,&s0);
+
+ BN_copy(&t2,&t1); BN_mask_bits(&t2,i);
+ BN_sub(&t1,&s1,&t2);
+ BN_lshift(&t1,&t1,i);
+ BN_add(&t1,&t1,&s0);
+ if (t1.neg)
+ {
+ BN_lshift(&t2,BN_value_one(),i*2);
+ BN_add(&t1,&t2,&t1);
+ BN_mask_bits(&t1,i*2);
+ }
+
+ BN_free(&Kh); BN_free(&Km); BN_free(&t1); BN_free(&t2);
+ BN_free(&ah); BN_free(&al); BN_free(&bh); BN_free(&bl);
+ }
+
+int BN_mod_mul_montgomery(r,a,b,mont,ctx)
+BIGNUM *r,*a,*b;
+BN_MONT_CTX *mont;
+BN_CTX *ctx;
+ {
+ BIGNUM *tmp;
+
+ tmp= &(ctx->bn[ctx->tos++]);
+
+ if (a == b)
+ {
+ if (!BN_sqr(tmp,a,ctx)) goto err;
+ }
+ else
+ {
+ if (!BN_mul(tmp,a,b)) goto err;
+ }
+ /* reduce from aRR to aR */
+ if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
+ ctx->tos--;
+ return(1);
+err:
+ return(0);
+ }
+
+int BN_from_montgomery(r,a,mont,ctx)
+BIGNUM *r;
+BIGNUM *a;
+BN_MONT_CTX *mont;
+BN_CTX *ctx;
+ {
+ BIGNUM z1;
+ BIGNUM *t1,*t2;
+ BN_ULONG *ap,*bp,*rp;
+ int j,i,bl,al;
+
+ BN_init(&z1);
+ t1= &(ctx->bn[ctx->tos]);
+ t2= &(ctx->bn[ctx->tos+1]);
+
+ if (!BN_copy(t1,a)) goto err;
+ /* can cheat */
+ BN_mask_bits(t1,mont->ri);
+ if (!BN_mul(t2,t1,mont->Ni)) goto err;
+ BN_mask_bits(t2,mont->ri);
+
+ if (!BN_mul(t1,t2,mont->N)) goto err;
+ if (!BN_add(t2,t1,a)) goto err;
+
+ /* At this point, t2 has the bottom ri bits set to zero.
+ * This means that the bottom ri bits == the 1^ri minus the bottom
+ * ri bits of a.
+ * This means that only the bits above 'ri' in a need to be added,
+ * and XXXXXXXXXXXXXXXXXXXXXXXX
+ */
+BN_print_fp(stdout,t2); printf("\n");
+ BN_rshift(r,t2,mont->ri);
+
+ if (BN_ucmp(r,mont->N) >= 0)
+ bn_qsub(r,r,mont->N);
+
+ return(1);
+err:
+ return(0);
+ }
+
+int BN_MONT_CTX_set(mont,mod,ctx)
+BN_MONT_CTX *mont;
+BIGNUM *mod;
+BN_CTX *ctx;
+ {
+ BIGNUM *Ri=NULL,*R=NULL;
+
+ if (mont->RR == NULL) mont->RR=BN_new();
+ if (mont->N == NULL) mont->N=BN_new();
+
+ R=mont->RR; /* grab RR as a temp */
+ BN_copy(mont->N,mod); /* Set N */
+
+ mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
+ BN_lshift(R,BN_value_one(),mont->ri); /* R */
+ if ((Ri=BN_mod_inverse(NULL,R,mod,ctx)) == NULL) goto err;/* Ri */
+ BN_lshift(Ri,Ri,mont->ri); /* R*Ri */
+ bn_qsub(Ri,Ri,BN_value_one()); /* R*Ri - 1 */
+ BN_div(Ri,NULL,Ri,mod,ctx);
+ if (mont->Ni != NULL) BN_free(mont->Ni);
+ mont->Ni=Ri; /* Ni=(R*Ri-1)/N */
+
+ /* setup RR for conversions */
+ BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
+ BN_mod(mont->RR,mont->RR,mont->N,ctx);
+
+ return(1);
+err:
+ return(0);
+ }
+
+
projects / openssl.git / blobdiff