bignum.java

手机上进行RSA加密的算法

                        // but we're never sure of the sign flag on a zero
                        if (a.len == 0 && b.len == 0) return 0;

                        if (a.negative)
                        {
                                if (b.negative)
                                {
                                        return ucmp(b, a);
                                }
                                else
                                {
                                        return -1;
                                }
                        }
                        else
                        {
                                if (b.negative)
                                {
                                        return 1;
                                }
                                else
                                {
                                        return ucmp(a, b);
                                }
                        }

        }

        public static int
        ucmp(BigNum a, BigNum b)
        {

                        int alen = a.len;
                        int blen = b.len;

                        if (alen < blen) return -1;
                        if (alen > blen) return 1;

                        // If LONG
                        // long an[] = a.n;
                        // long bn[] = b.n;
                        // If not LONG
                        int an[] = a.n;
                        int bn[] = b.n;


                        for (int i = alen-1; i >= 0; --i)
                        {
                                if (an[i] < bn[i]) return -1;
                                if (an[i] > bn[i]) return 1;
                        }
                        return 0;

        }

        public static void
        shiftLeft(BigNum r, BigNum a, int n)
        {
                shiftLeft(r, a, (short)n);
        }

        public static void
        shiftLeft(BigNum r, BigNum a, short n)
        {

                        if (a.len == 0)
                        {
                                zero(r);
                                return;
                        }
                        int rem = n % BITS;
                        int blocks = n / BITS;
                        int len = a.len;

                        r.len = len + blocks;
                        grow(r, r.len);

                        // If LONG
                        // long rn[] = r.n;
                        // If not LONG
                        int rn[] = r.n;

                        System.arraycopy(a.n, 0, rn, blocks, len);

                        if (blocks > 0)
                                for (int i = blocks-1; i >= 0 ; --i) { rn[i] = 0; }

                        if (rem != 0)
                        {
                                // If LONG
                                // long carry = 0;
                                // If not LONG
                                int carry = 0;

                                int rlen = r.len;
                                for (int i = blocks; i < rlen; ++i)
                                {
                                        // If LONG
                                        // long l = rn[i];
                                        // If not LONG
                                        int l = rn[i];

                                        rn[i] = ((l << rem) | carry) & MASK;
                                        carry = l >>> (BITS-rem);
                                }
                                if (carry != 0)
                                {
                                        rlen += 1;
                                        grow(r, rlen);
                                        r.n[rlen-1] = carry;
                                        r.len = rlen;
                                }
                        }

        }

        public static void
        shiftLeftOnce(BigNum r, BigNum a)
        {

                        shiftLeft(r, a, (short)1);

        }

        public static void
        shiftRight(BigNum r, BigNum a, int n)
        {
                shiftRight(r, a, (short)n);
        }

        public static void
        shiftRight(BigNum r, BigNum a, short n)
        {

                        int rem = n % BITS;
                        int blocks = n / BITS;

                        if (blocks >= a.len)
                        {
                                zero(r);
                                return;
                        }

                        r.len = a.len - blocks;
                        grow(r, r.len);

                        System.arraycopy(a.n, blocks, r.n, 0, r.len);

                        if (rem != 0)
                        {
                                // If LONG
                                // long carry = 0;
                                // long rn[] = r.n;
                                // If not LONG
                                int carry = 0;
                                int rn[] = r.n;

                                int rlen = r.len;
                                for (int i = rlen-1; i > 0; --i)
                                {
                                        // If LONG
                                        // long l = r.n[i];
                                        // If not LONG
                                        int l = rn[i];

                                        rn[i] = (l >>> rem) | carry;
                                        carry = (l << (BITS-rem)) & MASK;
                                }
                                // If LONG
                                // long l = rn[0];
                                // If not LONG
                                int l = rn[0];

                                rn[0] = (l >>> rem) | carry;
                                if (rlen > 0 && rn[rlen-1] == 0)
                                        r.len--;
                        }

        }

        public static void
        shiftRightOnce(BigNum r, BigNum a)
        {

                        shiftRight(r, a, (short)1);

        }


        /**
         * r must not be the same object as a or b
         */
        public static void
        mul(BigNum r ,BigNum a, BigNum b)
        {
                if ( r == a || r == b )
                        throw new MathError( "Result must not be either Parameter ( a or b )" );


                        //
                        //	Test for zeroes
                        //
                        if (a.len == 0 || b.len == 0)
                        {
                                zero(r);
                                return;
                        }

                        r.negative = a.negative ^ b.negative;
                        r.len = a.len + b.len;
                        grow(r, r.len);

                        // If LONG
                        // long an[] = a.n;
                        // long bn[] = b.n;
                        // long rn[] = r.n;
                        // If not LONG
                        int an[] = a.n;
                        int bn[] = b.n;
                        int rn[] = r.n;

                        int alen = a.len;
                        int blen = b.len;
                        int rlen = r.len;

                        for (int i = rlen-1; i >= 0; --i) { rn[i] = 0; }

        // If LONG
        //		for (int i = 0; i < a.len; ++i)
        //		{
        //			long carry = 0;
        //			long al = a.n[i] & LMASK;
        //			long ah = (a.n[i] >>> LBITS) & LMASK;
        //			int ri = i;

        //			for (int j = 0; j < b.len; ++j)
        //			{
        //				long bl = b.n[j] & LMASK;
        //				long bh = (b.n[j] >>> LBITS) & LMASK;

        //				long m1 = ah * bl;
        //				long l = al * bl;
        //				long m2 = al * bh;
        //				long h = ah * bh;

        //				m1 += m2;
        //				if ((m1 & MASK) < m2)
        //					h += LRADIX;
        //				h += (m1 >>> LBITS) & LMASK;

        //				m2 = (m1 & LMASK) << LBITS;
        //				l += m2;
        //				if ((l & MASK) < m2)
        //					h++;

        //				m1 = r.n[ri];
        //				l += m1;
        //				if ((l & MASK) < m1)
        //					h++;
        //				l += carry;
        //				if ((l & MASK) < carry)
        //					h++;
        //				carry = h & MASK;
        //				r.n[ri++] = l & MASK;
        //			}
        //			r.n[ri] = carry;
        //		}
        // If not LONG
                        for (int i = 0; i < a.len; ++i)
                        {
                                long carry = 0;
                                long m1 = an[i];
                                int ri = i;

                                for (int j = 0; j < b.len; ++j)
                                {
                                        long m2 = rn[ri];
                                        m2 += bn[j] * m1 + carry;
                                        carry = m2 >>> BITS;
                                        rn[ri++] = (int)m2 & MASK;
                                }
                                rn[ri] = (int)carry;
                        }


                        if (rn[rlen-1] == 0)
                                r.len--;

        }

        //
        //	r cannot be m
        //
        public static void
        mod(BigNum r, BigNum m, BigNum d)
        {

                        copy(r, m);
                        if (ucmp(m, d) < 0)
                                return;

                        int i = bitLength(m) - bitLength(d);

                        BigNum ds = new BigNum();
                        shiftLeft(ds, d, i);

                        for (; i>= 0; --i)
                        {
                                if (cmp(r, ds) >= 0)
                                        sub(r, r, ds);
                                shiftRight(ds, ds, (short)1);
                        }

        }

        public static void
        div(BigNum dv ,BigNum m, BigNum d)
        {

                        div(dv, null, m, d);

        }

        public static void
        div(BigNum dv ,BigNum rem, BigNum m, BigNum d)
        {

                        if (d.len == 0)
                                throw new MathError("divide by zero");

                        if (cmp(m, d) < 0)
                        {
                                if (rem != null)
                                        copy(rem, m);
                                if (dv != null)
                                        zero(dv);
                                return;
                        }

                        if (dv == null)
                                dv = new BigNum();
                        if (rem == null)
                                rem = new BigNum();

                        BigNum ds = new BigNum();
                        copy(rem, m);
                        zero(dv);

                        int i = bitLength(m) - bitLength(d);
                        shiftLeft(ds, d, i);

                        for (; i >= 0; --i)
                        {
                                if (dv.len == 0)
                                {
                                        if (cmp(rem, ds) >= 0)
                                        {
                                                one(dv);
                                                sub(rem, rem, ds);
                                        }
                                }
                                else
                                {
                                        shiftLeftOnce(dv, dv);
                                        if (cmp(rem, ds) >= 0)
                                        {
                                                dv.n[0] |= 1;
                                                sub(rem, rem, ds);
                                        }
                                }
                                shiftRightOnce(ds, ds);
                        }
                        dv.negative = m.negative ^ d.negative;

        }

        public static void
        modExp( BigNum r, BigNum a, BigNum power, BigNum modulo)
        {

                        BigNum d = new BigNum();
                        BigNum v = new BigNum();

                        mod(v, a, modulo);
                        int bits = bitLength(power);

                        if ((power.n[0] & 1) != 0)
                                mod(r, a, modulo);
                        else
                                one(r);

                        int nb = recip(d, modulo);
                        for (int i = 1; i < bits; i++)
                        {
                                modMulRecip(v, v, v, modulo, d, (short)nb);
                                if (bit(power, i))
                                        modMulRecip(r, r, v, modulo, d, (short)nb);
                        }

        }

        public static void
        modMul( BigNum r, BigNum a, BigNum b, BigNum modulo)
        {

                        BigNum t = new BigNum();
                        mul(t, a, b);
                        mod(r, t, modulo);

        }

        public static int
        recip( BigNum r, BigNum m )
        {

                        BigNum t = new BigNum();
                        one(t);

                        int mbits = bitLength(m);

                        shiftLeft(t, t, 2*mbits);
                        div(r, null, t, m);
                        return mbits+1;

        }

        public static void
        euclid(BigNum r, BigNum x, BigNum y )
        {

                        BigNum a = new BigNum();
                        BigNum b = new BigNum();

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

                        int shifts = 0;

                        while (b.len != 0)
                        {