bignum.java

手机上进行RSA加密的算法

package rsa;

import java.io.PrintStream;
/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2003</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class BigNum //implements myCloneable
{
        private static final String LIBRARY_NAME = "bignum";

        private static boolean native_link_ok = false;
        private static boolean native_lib_loaded = false;
        private static String native_link_err = "Class not loaded";

        private static BigNum staticZero;
        private static BigNum staticOne;

/*
        static
        {
                // load the DLL or shared library that contains the native code
                try
                {
                       System.loadLibrary( LIBRARY_NAME );
                        native_lib_loaded = true;
                        try
                        {
                                //
                                //	Should really do a bit more testing than this ...
                                //
                                if (bignum_test() == 0)
                                {
                                        // create a static BigNum that will be set to one.
                                        native_link_ok = true;
                                        native_link_err = null;

                                        staticOne = new BigNum();
                                        staticOne.setToOne();
                                }
                                else
                                {
                                        native_link_err = "Self test failed";
                                }
                        }
                        catch ( UnsatisfiedLinkError ule )
                        {
                                native_link_err = "Errors linking to " + LIBRARY_NAME + " native library";
                        }
                }
                catch ( UnsatisfiedLinkError ule )
                {
                        native_link_err = "The " + LIBRARY_NAME + " native library was not found";
                }
        }

*/

        public final static boolean
        hasFileLibraryLoaded()
        {
                return native_lib_loaded;
        }

        public final static boolean
        isLibraryCorrect()
        {
                return native_link_ok;
        }

        public final static String
        getLinkErrorString()
        {
                return native_link_err;
        }



        //
        //	Constants
        //

        // If LONG
        // static final int BITS = 62; // Not 63, since we dont have unsigned
        // static final long RADIX = (1L << BITS);
        // static final long MASK = RADIX-1;
        // static final int LBITS = BITS/2;
        // static final long LRADIX = (1L << LBITS);
        // static final long LMASK = LRADIX-1;

        // If not LONG
        static final int BITS = 30;
        static final int RADIX = (1 << BITS);
        static final int MASK = RADIX-1;
        static final int LBITS = BITS/2;
        static final int LRADIX = (1 << LBITS);
        static final int LMASK = LRADIX-1;

        //
        //	Data members for Java implementation
        //

        // If LONG
        // private long n[];
        // If not LONG
        private int n[];

        private int len;
        private boolean negative;

        //
        //	Data members for native implementation
        //
        private int pointer_; // N.B. may need to be long if running on a 64bit machine


        public int byteLength()
        {

                        int r = ((len - 1) * BITS)/8;

                        // If LONG
                        // long i = n[0];
                        // If not LONG
                        int i = n[0];

                        while (i != 0)
                        {
                                i >>>= 8;
                                ++r;
                        }
                        return r;

        }

        public void check_state()
        {
                bitLength(this);
        }

        public static
        int bitLength(BigNum n)
        {


                        int len = n.len;

                        if (len == 0)
                                return 0;

                        int r = (len - 1) * BITS;

                        // If LONG
                        // long i = n.n[len-1];
                        // If not LONG
                        int i = n.n[len-1];

                        // Could probably speed this up with a binary search
                        while (i != 0)
                        {
                                i >>>= 1;
                                ++r;
                        }

// For debugging only
if (r == 0) throw new MathError("Invalid state");

                        return r;

        }

        public static
        boolean bit(BigNum n, int i)
        {

                        int bit = i % BITS;
                        i /= BITS;

                        if (i >= n.len || ((n.n[i] & (1L << bit)) == 0))
                                return false;
                        return true;

        }

        protected BigNum()
        {

                        // If LONG
                        // n = new long[8];	// 512 bits (nearly)
                        // If not LONG
                        n = new int[16];	// 512 bits (nearly)

                        len = 0;
                        negative = false;

        }

        public Object
        clone()
        {
                BigNum r = new BigNum();
                copy(r, this);
                return r;
        }

        public void
        copy(Object src)
        {
                copy(this, (BigNum)src);
        }

        protected static void
        copy(BigNum dst, BigNum src)
        {
                if (dst == src)
                        return;
                        // throw new IllegalArgumentException();

                   // If LONG
                        // dst.n = new long[src.n.length];
                        // If not LONG
                        dst.n = new int[src.n.length];

                        dst.negative = src.negative;
                        dst.len = src.len;
                        if (src.len > 0)
                                System.arraycopy(src.n, 0, dst.n, 0, src.len);

        }

        public static void
        grow(BigNum a, int i)
        {

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

                        if (i <= an.length)
                                return;

                        i += 16; // Add 8 or 16 for efficiency

                        // If LONG
                        // long n[] = new long[i];
                        // If not LONG
                        int n[] = new int[i];

                        System.arraycopy(an, 0, n, 0, an.length);
                        a.n = n;

        }


        public int
        intoBinary(byte buffer[])
        {

                        int len = (bitLength(this)+7)/8;
                        if (buffer.length < (len))
                                throw new MathError("into-binary buffer too small");

                        int pos = 0;
                        int bitpos = 0;

                        // Index in reverse to get LSB first
                        for (int i = len-1; i >= 0; --i)
                        {
                                int b = (int)((n[pos] >>> bitpos) & 0xFFL);
                                bitpos += 8;
                                if (bitpos >= BITS)
                                {
                                        bitpos -= BITS;
                                        pos++;
                                        if (bitpos > 0)
                                                b |= (n[pos] << (8-bitpos)) & 0xFFL;
                                }
                                buffer[i] = (byte)b;
                        }
                        return len;

        }

        protected void
        fromBinary(byte buffer[])
        {

                        negative = false;	// Can't init negatives yet
                        len = ((buffer.length)*8 + BITS-1) / BITS;
                        grow(this, len);

                        int pos = 0;
                        n[pos] = 0;
                        int bitpos = 0;
                        // Index in reverse to get LSB first
                        for (int i = buffer.length-1; i >= 0; --i)
                        {
                                // If LONG
                                // long b = buffer[i] & 0xFF;
                                // If not LONG
                                int b = buffer[i] & 0xFF;

                                n[pos] |= (b << bitpos) & MASK;
                                bitpos += 8;
                                if (bitpos >= BITS)
                                {
                                        pos++;
                                        n[pos] = 0;
                                        bitpos -= BITS;
                                        if (bitpos > 0)
                                                n[pos] = b >>> (8-bitpos);
                                }
                        }
                        while (len > 0 && n[len-1] == 0)
                                len--;

        }

        public static void
        assign(BigNum r, int val)
        {

                        if (val != 0)
                        {
                                r.len = 1;

                                // If LONG
                                // r.n[0] = val & 0x7FFFFFFFL;
                                // If not LONG
                                r.n[0] = val & 0x7FFFFFFF;

                                r.negative = (val < 0);
                        }
                        else
                        {
                                r.len = 0;
                                r.n[0] = 0;
                                r.negative = false;
                        }

        }

        public static void
        zero(BigNum a)
        {

                        a.n[0] = 0;
                        a.negative = false;
                        a.len = 0;

        }

        public static void
        one(BigNum a)
        {

                        a.n[0] = 1;
                        a.negative = false;
                        a.len = 1;

        }

        public static boolean
        isOne(BigNum a)
        {

                        return (a.len == 1 && a.n[0] == 1);

        }

        public static boolean
        even(BigNum a)
        {

                        return !(a.len > 0 && (a.n[0] & 1) == 1);

        }

        public static boolean
        odd(BigNum a)
        {

                        return (a.len > 0 && (a.n[0] & 1) == 1);

        }

        public static boolean
        isZero(BigNum a)
        {

                        if (a.len == 0) return true;
a.check_state();
                        // if (a.len > 1) return false;
                        // return (a.n[0] == 0);
                        return false;

        }

        public static void
        inc(BigNum a)
        {
                add(a, 1);
        }

        public static void
        dec(BigNum a)
        {
                sub(a, 1);
        }

        public static void
        add( BigNum r, int a )
        {
                if (a == 0)
                        return;


                        if (a < 0)
                        {
                                if (r.negative)
                                {
                                        r.negative = false;
                                        add_unsigned(r, -a);
                                        r.negative = true;
                                }
                                else
                                {
                                        sub_unsigned(r, -a);
                                }
                        }
                        else
                        {
                                if (r.negative)
                                {