bignum.java

手机上进行RSA加密的算法

                                if ((a.n[0] & 1) != 0)	// a odd
                                        if ((b.n[0] & 1) != 0)	// b odd
                                        {
                                                sub(a, a, b);
                                                shiftRightOnce(a, a);
                                                if (cmp(a, b) < 0)
                                                {
                                                        BigNum t = a;
                                                        a = b;
                                                        b = t;
                                                }
                                        }
                                        else
                                        {
                                                shiftRightOnce(b, b);
                                                if (cmp(a, b) < 0)
                                                {
                                                        BigNum t = a;
                                                        a = b;
                                                        b = t;
                                                }
                                        }
                                else
                                        if ((b.n[0] & 1) != 0)	// b odd
                                        {
                                                shiftRightOnce(a, a);
                                                if (cmp(a, b) < 0)
                                                {
                                                        BigNum t = a;
                                                        a = b;
                                                        b = t;
                                                }
                                        }
                                        else
                                        {
                                                shiftRightOnce(a, a);
                                                shiftRightOnce(b, b);
                                                shifts++;
                                        }
                        }
                        if (shifts > 0)
                                shiftLeft(r, a, shifts);
                        else
                                copy(r, a);

        }

        public static void
        gcd( BigNum r, BigNum a, BigNum b )
        {

                        if (cmp(a, b) > 0)
                                euclid(r, a, b);
                        else
                                euclid(r, b, a);

        }

        public static void
        modMulRecip(BigNum r, BigNum x, BigNum y, BigNum m, BigNum i, short nb )
        {
                    BigNum a = new BigNum();
                        BigNum b = new BigNum();
                        BigNum c = new BigNum();
                        BigNum d = new BigNum();

                        mul(a, x, y);
                        shiftRight(d, a, nb-1);
                        mul(b, d, i);
                        shiftRight(c, b, nb-1);
                        mul(b, m, c);
                        sub(r, a, b);

                        int j = 0;
                        while (cmp(r, m) >= 0)
                        {
                                if (j++ > 2)
                                        throw new MathError("modulo reciprical failed");
                                sub(r, r, m);
                        }

        }

//
//	Doesn't seem to work at present
//	(either implementation)
//
        public static void
        extended_euclid(BigNum u1, BigNum u2, BigNum u3, BigNum a, BigNum b)
        {
/*
                        BigNum t;
//			BigNum in1 = u1;
//			BigNum in2 = u2;
//			BigNum in3 = u3;
                        BigNum t1 = new BigNum();
                        BigNum t2 = new BigNum();
                        BigNum t3 = new BigNum();

                        if (cmp(a, b) < 0)
                        {
                                t = a; a = b; b = t;
                        }

                        int k;
                        for (k = 0; ((1 & a.n[0] & b.n[0]) == 0); ++k)
                        {
                                shiftRightOnce(a, a);
                                shiftRightOnce(b, b);
                        }

                        one(u1);
                        zero(u2);
                        copy(u3, a);
                        copy(t1, b);
                        copy(t2, a); dec(t2);
                        copy(t3, b);


                        do {
                                do {
                                        if (even(u3))
                                        {
                                                if (odd(u1) || odd(u2))
                                                {
                                                        add(u1, u1, b);
                                                        add(u2, u2, a);
                                                }
                                                shiftRightOnce(u1, u1);
                                                shiftRightOnce(u2, u2);
                                                shiftRightOnce(u3, u3);
                                        }
                                        if (even(t3) || (cmp(u3, t3) < 0))
                                        {
                                                t = u1; u1 = t1; t1 = t;
                                                t = u2; u2 = t2; t2 = t;
                                                t = u3; u3 = t3; t3 = t;
                                        }
                                } while (even(u3));

                                while (cmp(u1, t1) < 0 || cmp(u2, t2) < 0)
                                {
                                        add(u1, u1, b);
                                        add(u2, u2, a);
                                }
                                sub(u1, u1, t1);
                                sub(u2, u2, t2);
                                sub(u3, u3, t3);
                        } while (t3.len > 0 && !t3.negative);

                        while (cmp(u1, b) >= 0 && cmp(u2, a) >= 0)
                        {
                                sub(u1, u1, b);
                                sub(u2, u2, a);
                        }

                        shiftLeft(a, a, k);
                        shiftLeft(b, b, k);
                        shiftLeft(u3, u3, k);

//			copy(in1, u1);
//			copy(in2, u2);
//			copy(in3, u3);

/*
                        if (isZero(b))
                        {
                                copy(u3, a);
                                one(u1);
                                zero(u2);
                                return;
                        }

                        BigNum A = new BigNum();
                        mod(A, a, b);

                        extended_euclid(u1, u2, u3, b, A);

                        BigNum t = new BigNum();
                        copy(t, u1);
                        copy(u1, u2);
                        div(A, null, a, b);

                        BigNum B = new BigNum();
                        mul(B, u2, A);
                        mul(A, t, B);
                        copy(t, A);
                        copy(u2, t);
*/

        }

//
//	And this is in a state - only one of the three implementations
//	seems to go ...
//
        public static void
        inverseModN(BigNum r, BigNum a, BigNum n)
        {

                        if (a.negative || n.negative)
                                throw new MathError("invalid negative argument");

/*
System.out.println("a = "+ a.toString());
System.out.println("n = "+ n.toString());
                        BigNum x = new BigNum();
                        BigNum y = new BigNum();
                        BigNum u = new BigNum();
                        BigNum v = new BigNum();
                        BigNum gcd = new BigNum();

                        copy(x, a);
                        copy(y, n);

System.out.println("a = "+ a.toString());
System.out.println("n = "+ n.toString());
                        extended_euclid(u, v, gcd, y, x);
copy(r, gcd); System.out.println("gcd = "+ r.toString());
copy(r, u); System.out.println("u = "+ r.toString());
copy(r, v); System.out.println("v = "+ r.toString());
copy(r, y); System.out.println("a = "+ r.toString());
copy(r, x); System.out.println("n = "+ r.toString());

//			if (v.negative)
//				add(v, v, n);

                        // GCD should be 1 if successful
//			if (!(gcd.len == 1 && gcd.n[0] == 1))
//				throw new MathError("inverse modulo n failed");

                        sub(r, n, v);
return;/*
//			mod(r, v, n);

// Now test
BigNum t = new BigNum();
modMul(t, a, r, n);
if (t.len != 1 || t.n[0] == 1)
{
        System.out.println("a = "+ a.toString());
        System.out.println("n = "+ n.toString());
        System.out.println("r = "+ r.toString());
        throw new MathError("inverse modulo n failed");
}
else
        System.out.println("Inverse worked");

*/
                        BigNum x1 = new BigNum();
                        BigNum x2 = new BigNum();
                        BigNum x3 = a;
                        BigNum y1 = new BigNum();
                        BigNum y2 = new BigNum();
                        BigNum y3 = n;

                        one(x1); one(y2);
                        zero(x2); zero(y1);

                        while (y3.len != 0)
                        {
                                BigNum t1 = new BigNum();
                                BigNum t2 = new BigNum();
                                BigNum t3 = new BigNum();
                                BigNum q = new BigNum();
                                BigNum p = new BigNum();

                                div(q, t3, x3, y3);
                                mul(t1, q, y2);
                                sub(t2, x2, t1);
                                mul(p, q, y1);
                                sub(t1, x1, p);

                                x1 = y1; x2 = y2; x3 = y3;
                                y1 = t1; y2 = t2; y3 = t3;
                        }

                        if (x1.negative)
                                add(x1, x1, n);

// copy(r, x1); System.out.println("x1 = "+ r.toString());
// copy(r, x3); System.out.println("x3 = "+ r.toString());

//			if (!x3.negative && x3.len == 1 && x3.n[0] == 1)
//				mod(r, x1, n);
//			else
//				throw new MathError("inverse modulo n failed");

                        copy(r, x1);

/*

// Now test
BigNum t = new BigNum();
modMul(t, a, r, n);
if (t.len != 1 || t.n[0] != 1)
        throw new MathError("inverse modulo n failed");
else
System.out.println("Inverse worked");




// Alternative again ...
                        BigNum d = new BigNum();
                        BigNum x = new BigNum();
                        BigNum y = new BigNum();

                        extended_euclid(d, x, y, n, a);

                        if (b.len == 0)
                        {
                                copy(rd, a);
                                one(rx);
                                zero(ry);
                                return;
                        }

                        BigNum A = new BigNum();
                        mod(A, a, b);

                        extended_euclid(rd, rx, ry, b, A);

                        BigNum t = new BigNum();
                        copy(t, rx);
                        copy(rx, ry);
                        div(a, null, a, b);

                        BigNum B = new BigNum();
                        mul(B, ry, A);
                        mul(A, t, B);
                        copy(t, A);
                        copy(ry, t);


                        if (y.negative)
                                add(y, y, n);

                        if (!d.negative && d.len == 1 && d.n[0] == 1)
                                throw new MathError("inverse modulo n failed");

                        mod(r, y, n);
*/

        }



        public String
        toString()
        {
                throw new MathError("BigNums can not natively be strings.");
        }

  //      protected void finalize()
  //      {
       /*         if (native_link_ok)
                {
                        bignum_free();
                }*/
   //     }


        //
        //	Test code
        //
        public static void
        main(String argv[])
        {
                try {
                        self_test(System.out, argv);
                }
                catch(Throwable t)
                {
                        t.printStackTrace();
                }
        }

        public static void
        self_test(PrintStream out, String argv[])
        throws Exception
        {
        }

        public static void
        display(PrintStream out, BigNum x)
        {
                out.println("Length: "+x.len);
                out.println("Sign flag: "+ x.negative);
        }

/*
        private native static int bignum_test();

        private native int bignum_new();
        private native void bignum_free();

        private native static int bignum_copy(BigNum a, BigNum b);
        private native static int bignum_iszero(BigNum a);
        private native static int bignum_grow(BigNum a, int i);
        private native static int bignum_bytelen();
        private native static int bignum_bitlen(BigNum a);

        private native int bignum_into_bytes(byte[] buffer);
        private native int bignum_from_bytes(byte[] buffer);

        private native int setToOne();
        private native int setToZero();

        private native static int bignum_add_word(BigNum a, int w);
        private native static int bignum_set_word(BigNum a, int w);
        private native static int bignum_add(BigNum r, BigNum a, BigNum b);
        private native static int bignum_sub(BigNum r, BigNum a, BigNum b);
        private native static int bignum_cmp(BigNum a, BigNum b);
        private native static int bignum_ucmp(BigNum a, BigNum b);




        public native int hashCode(); // just returns the MSB word but this allows use in hashtables etc.

        private native static int bignum_mul( BigNum r, BigNum a, BigNum b );
        private native static int bignum_mod( BigNum rem, BigNum m, BigNum d );
        private native static int bignum_div( BigNum dv, BigNum rem, BigNum m, BigNum d );
        private native static int bignum_lshift( BigNum r, BigNum a, short n );
        private native static int bignum_lshift1( BigNum r, BigNum a );
        private native static int bignum_rshift( BigNum r, BigNum a, short n );
        private native static int bignum_rshift1( BigNum r, BigNum a );
        private native static int bignum_mod_exp( BigNum r, BigNum a, BigNum p, BigNum m );
        private native static int bignum_modmul_recip( BigNum r, BigNum x, BigNum y, BigNum m, BigNum i, short nb );
        private native static int bignum_mod_mul( BigNum r, BigNum a, BigNum b, BigNum m );
        private native static int bignum_reciprical( BigNum r, BigNum m );
        private native static int bignum_gcd( BigNum r, BigNum a, BigNum b );
        private native static int bignum_inverse_modn( BigNum r, BigNum a, BigNum n );
*/
}