package myCode.rsaCryptography;

//這是RSA原型加密算法，實際應用時還應當加入一些隨機化的技術。
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class RsaEncrypt {
	private byte[] N_num = null;
	private byte[] E_num = null;
	private byte[] D_num = null;
	
	public byte[] encrypt (byte[] mess) {
		byte[] out = null;
		out = this.exp(mess, this.E_num, this.N_num);
		return out;
	}
	
	public byte[] decrypt (byte[] enc) {
		byte[] out = null;
		out = this.exp(enc, this.D_num, this.N_num);
		return out;
	}
	
	public byte[] decrypt2 (byte[] enc) {
		byte[] out = null;
		byte[] temp = null;
		int m, n, k;
		out = this.exp(enc, this.D_num, this.N_num);
		m = out.length;
		if (out[0] != 0x2) {
			System.out.println("解碼錯誤!");
			return null;
		}
		for (n=1; n<m; n++) {
			if (out[n] == 0)
				break;
		}
		if (n < 9) {
			System.out.println("解碼錯誤!");
			return null;
		}
		if (n >= (m-1)) {
			System.out.println("解碼錯誤!");
			return null;
		}
		temp = out;
		m = m-n-1;
		out = new byte[m];
		for (k=0; k<m; k++) {
			out[k] = temp[k+n+1];
		}
		return out;
	}
	
	private byte[] sha1 (byte[] mess) {
		byte[] out = null;
		MessageDigest md;
		try {
			md = MessageDigest.getInstance("sha1");
			md.reset();
			md.update(mess);
			out = md.digest();
		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		}
		return out;
	}
	
	private byte[] md5 (byte[] mess) {
		byte[] out = null;
		MessageDigest md;
		try {
			md = MessageDigest.getInstance("md5");
			md.reset();
			md.update(mess);
			out = md.digest();
		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		}
		return out;
	}
	
	private byte[] yihuo (byte[] in1, byte[] in2) {
		byte[] out = null;
		int n = in1.length;
		int k;
		out =  new byte[n];
		for (k=0; k<n; k++) {
			out[k] = (byte)(in1[k] ^ in2[k]);
		}
		return out;
	}
	
	public byte[] add (byte[] in1, byte[] in2) {
		byte[] out = null;
		byte[] add = null;
		int n, n1, n2, k, temp, carry;
		n1 = in1.length;
		n2 = in2.length;
		if (n1 < n2)
			n = n2;
		else
			n = n1;
		out = new byte[n];
		add = new byte[n];
		for (k=0; k<n; k++) {
			out[k] = 0;
			add[k] = 0;
		}
		for (k=0; k<n1; k++) {
			out[k+n-n1] = in1[k];
		}
		for (k=0; k<n2; k++) {
			add[k+n-n2] = in2[k];
		}
		carry = 0;
		for (k=n-1; k>=0; k--) {
			temp = (out[k] & 0xFF) + (add[k] & 0xFF) + carry;
			out[k] = (byte) (temp & 0xFF);
			carry = temp >> 8;
		}
		if (carry > 0) {
			add = out;
			out = new byte[n+1];
			for (k=1; k<=n; k++) {
				out[k] = add[k-1];
			}
			out[0] = (byte) carry;
		}
		n1 = out.length;
		n2 = 0;
		for (n2=0; n2<n1-1; n2++) {
			if (out[n2] != 0)
				break;
		}
		if (n2>0) {
			add = out;
			n1 = n1-n2;
			out = new byte[n1];
			for (k=0; k<n1; k++) {
				out[k] = add[k+n2];
			}
		}
		return out;
	}
	
	public byte[] subtract (byte[] in1, byte[] in2) {
		/*if (!this.biggerEqual(in1, in2)) {
			System.out.println("被減數"+this.byte2hex(in1)+" 減數"+this.byte2hex(in2));
			System.out.println("錯誤：減數大于了被減數。");
			return null;
		}*/
		byte[] out = null;
		byte[] sub = null;
		int n1 = in1.length;
		int n2 = in2.length;
		int k;
		sub = new byte[n1];
		for (k=0; k<n1; k++) 
			sub[k] = (byte) 0xFF;
		for (k=0; k<n2; k++)
			sub[k+n1-n2] = (byte)(0xFF - (in2[k] & 0xFF));
		byte[] one = new byte[1];
		one[0] = 1;
		sub = add(sub, one);
		sub = add(sub, in1);
		if (sub.length != (n1+1))
			out = sub;
		else {
			out = new byte[n1];
			for (k=0; k<n1; k++) {
				out[k] = sub[k+1];
			}
		}
		n2 = 0;
		for (n2=0; n2<n1-1; n2++) {
			if (out[n2] != 0)
				break;
		}
		if (n2>0) {
			sub = out;
			n1 = n1-n2;
			out = new byte[n1];
			for (k=0; k<n1; k++) {
				out[k] = sub[k+n2];
			}
		}
		return out;
	}
	
	public boolean biggerEqual (byte[] in1, byte[]in2) {
		int n1, n2, k;
		byte[] temp = null;
		if (in1[0] == 0) {
			n2 = 0;
			n1 = in1.length;
			for (n2=0; n2<n1-1; n2++) {
				if (in1[n2] != 0)
					break;
			}
			if (n2>0) {
				temp = in1;
				n1 = n1-n2;
				in1 = new byte[n1];
				for (k=0; k<n1; k++) {
					in1[k] = temp[k+n2];
				}
			}
		}
		if (in2[0] == 0) {
			n2 = 0;
			n1 = in2.length;
			for (n2=0; n2<n1-1; n2++) {
				if (in2[n2] != 0)
					break;
			}
			if (n2>0) {
				temp = in2;
				n1 = n1-n2;
				in2 = new byte[n1];
				for (k=0; k<n1; k++) {
					in2[k] = temp[k+n2];
				}
			}
		}
		if (in1.length > in2.length)
			return true;
		else if (in1.length < in2.length)
			return false;
		n1 = in1.length;
		for (k=0; k<n1; k++) {
			if ((in1[k]&0xFF)<(in2[k]&0xFF))
				return false;
			else if ((in1[k]&0xFF)>(in2[k]&0xFF))
				return true;
		}
		return true;
	}
	
	public byte[] multiply (byte[] in1, byte[] in2) {
		byte[] out = null;
		byte[] mul = null;
		int n, n1, n2, k1, k2, temp, carry;
		if (in1[0] == 0) {
			n2 = 0;
			n1 = in1.length;
			for (n2=0; n2<n1-1; n2++) {
				if (in1[n2] != 0)
					break;
			}
			if (n2>0) {
				out = in1;
				n1 = n1-n2;
				in1 = new byte[n1];
				for (k1=0; k1<n1; k1++) {
					in1[k1] = out[k1+n2];
				}
			}
		}
		if (in2[0] == 0) {
			n2 = 0;
			n1 = in2.length;
			for (n2=0; n2<n1-1; n2++) {
				if (in2[n2] != 0)
					break;
			}
			if (n2>0) {
				out = in2;
				n1 = n1-n2;
				in2 = new byte[n1];
				for (k1=0; k1<n1; k1++) {
					in2[k1] = out[k1+n2];
				}
			}
		}
		n1 = in1.length;
		n2 = in2.length;
		n = n1 + n2;
		mul = new byte[n];
		for (k1=0; k1<n; k1++) {
			mul[k1] = 0;
		}
		carry = 0;
		for (k1=n1-1; k1>=0; k1--) {
			for (k2=n2-1; k2>=0; k2--) {
				temp = (in1[k1] & 0xFF) * (in2[k2] & 0xFF) + carry + (mul[k1+k2+1] & 0xFF);
				mul[k1+k2+1] = (byte)(temp & 0xFF);
				carry = temp >> 8;
			}
			for (; carry>0;) {
				temp = carry + (mul[k1+k2+1] & 0xFF);
				mul[k1+k2+1] = (byte)(temp & 0xFF);
				carry = temp >> 8;
				k2--;
			}
		}
		if (mul[0] == 0) {
			out = new byte[n-1];
			for (k1=n-2; k1>=0; k1--)
				out[k1] = mul[k1+1];
		}
		else
			out = mul;
		return out;
	}
	
	// = (a mod m)
	public byte[] mod (byte[] a, byte[] m) {
		byte[] out = null;
		byte[] temp = null;
		int n1, n2, k, temp2;
		if (a[0] == 0) {
			n2 = 0;
			n1 = a.length;
			for (n2=0; n2<n1-1; n2++) {
				if (a[n2] != 0)
					break;
			}
			if (n2>0) {
				out = a;
				n1 = n1-n2;
				a = new byte[n1];
				for (k=0; k<n1; k++) {
					a[k] = out[k+n2];
				}
			}
		}
		if (m[0] == 0) {
			n2 = 0;
			n1 = m.length;
			for (n2=0; n2<n1-1; n2++) {
				if (m[n2] != 0)
					break;
			}
			if (n2>0) {
				out = m;
				n1 = n1-n2;
				m = new byte[n1];
				for (k=0; k<n1; k++) {
					m[k] = out[k+n2];
				}
			}
		}
		while (this.biggerEqual(a, m)) {
			temp2 = (a[0] & 0xFF) - (m[0] & 0xFF);
			if (temp2 <= 0) {
				if (a.length > m.length) {
					n1 = a.length - m.length;
					temp2 = ((a[0] & 0xFF)*0x100 + (a[1] & 0xFF)) / ((m[0] & 0xFF)+1);
					temp = new byte[n1];
					for (k=1; k<n1; k++)
						temp[k] = 0;
					temp[0] = (byte) (temp2 & 0xFF);
				}
				else {
					temp = new byte[1];
					temp[0] = 1;
				}
			}
			else {
				temp2 = (a[0] & 0xFF) / ((m[0] & 0xFF)+1);
				n1 = a.length - m.length + 1;
				temp = new byte[n1];
				for (k=1; k<n1; k++)
					temp[k] = 0;
				temp[0] = (byte) temp2;
			}
			//System.out.println("a:"+this.byte2hex(a)+" temp:"+this.byte2hex(temp)+" m:"+this.byte2hex(m));
			a = this.subtract(a, this.multiply(temp, m));
		}
		out = a;
		return out;
	}
	
	// = a exp e mod m
	public byte[] exp (byte[] a, byte[] e, byte[] m) {
		byte[] out = null;
		byte[] temp = null;
		int n1, n2, k;
		if (a[0] == 0) {
			n2 = 0;
			n1 = a.length;
			for (n2=0; n2<n1-1; n2++) {
				if (a[n2] != 0)
					break;
			}
			if (n2>0) {
				out = a;
				n1 = n1-n2;
				a = new byte[n1];
				for (k=0; k<n1; k++) {
					a[k] = out[k+n2];
				}
			}
		}
		if (e[0] == 0) {
			n2 = 0;
			n1 = e.length;
			for (n2=0; n2<n1-1; n2++) {
				if (e[n2] != 0)
					break;
			}
			if (n2>0) {
				out = e;
				n1 = n1-n2;
				e = new byte[n1];
				for (k=0; k<n1; k++) {
					e[k] = out[k+n2];
				}
			}
		}
		if (m[0] == 0) {
			n2 = 0;
			n1 = m.length;
			for (n2=0; n2<n1-1; n2++) {
				if (m[n2] != 0)
					break;
			}
			if (n2>0) {
				out = m;
				n1 = n1-n2;
				m = new byte[n1];
				for (k=0; k<n1; k++) {
					m[k] = out[k+n2];
				}
			}
		}
		a = this.mod(a, m);
		out = new byte[1];
		out[0] = 1;
		byte[] one = new byte[8];
		for (k=0; k<8; k++) {
			one[k] = (byte)(0x1 << (7-k));
		}
		temp = a;
		for (n1=e.length - 1; n1>=0; n1--) {
			for (n2=7; n2>=0; n2--) {
				if ((e[n1] & one[n2]) != 0) {
					out = this.multiply(temp, out);
					out = this.mod(out, m);
				}
				temp = this.multiply(temp, temp);
				temp = this.mod(temp, m);
			}
		}
		return out;
	}
	
	private byte[] hex2byte(String strhex) {
		if (strhex == null) {
			return null;
		}
		int l = strhex.length();
		if (l % 2 == 1) {
			return null;
		}
		byte[] b = new byte[l / 2];
		for (int i = 0; i < (l / 2); i++) {
			b[i] = (byte) Integer.parseInt(strhex.substring(i * 2, i * 2 + 2), 16);
		}
		return b;
	}
	
	private String byte2hex(byte[] b) {
		String hs = "";
		String stmp = "";
		for (int n = 0; n < b.length; n++) {
			stmp = (java.lang.Integer.toHexString(b[n] & 0XFF));
			if (stmp.length() == 1) {
				hs =  hs + "0" + stmp;
			} else {
				hs = hs + stmp;
			}
		}
		return hs.toUpperCase();
	}
	
	public void setN (byte[] N) {
		this.N_num = N;
		return;
	}
	public byte[] getN () {
		return this.N_num;
	}
	
	public void setE (byte[] E) {
		this.E_num = E;
		return;
	}
	public byte[] getE () {
		return this.E_num;
	}
	
	public void setD (byte[] D) {
		this.D_num = D;
		return;
	}
	public byte[] getD () {
		return this.D_num;
	}
	
	public static void main(String[] args) {
		RsaEncrypt rsa = new RsaEncrypt();
		rsa.setN(rsa.hex2byte("A97436BDB83C2AB67350371CFF9CAB6B892E0A5AA5F1FEFAA9BCC04AD0EF136CB7FE296336C4D84BFFE70F9BBFA036EA8D126C9F46BD6E09EDDC065770DDCB57E494DEB53F2CB435AF3C0C68F419522CDDED758D1C2B1C8371D869194CDCFA28937EF5EA9775E29B8DA6265D31DB21D1C0773CBA62A2BD780E57C418A8AAEF27"));
		rsa.setE(rsa.hex2byte("010001"));
		rsa.setD(rsa.hex2byte("27DECC327F72C8A9FD1FD697E01CC0C8A09250A55B7E40FC418BC3C2D6BE29D7DEC2D2822194D73FAA8A7745B224C44713C24E047BE47E4B9FC7B14649AC25F7B8D91B1CC5BA3366A89F9807F0BB4EF951C59DCCA48DD994EB33B40B3D243C0310BFD53C039E2350725F9B3FCD0CD183C133B33C4FD0999677FE087F17ADA541"));
		byte[] mess = rsa.hex2byte("0102030405060708090A0B0C0D0E0F");//原文必須是一個十六進制數
		byte[] enc = null;
		byte[] dec = null;
		enc = rsa.encrypt(mess);
		enc = rsa.encrypt(mess);
		dec = rsa.decrypt(enc);
		System.out.println("原文："+rsa.byte2hex(mess));
		System.out.println("密文："+rsa.byte2hex(enc));
		System.out.println("解密："+rsa.byte2hex(dec));
	}
}