/**for Stream tools*/
import java.io.*;	

/** 信息系統安全技術作業
 *<P> 這個類用于產生公鑰和私鑰并存于用戶指定的文件.本算法的流程由構造函數控制所以所有mothod的pre都是none.
 * @author 軟件學院 吳丹 00234015
 * @version 1.0
*/
class makeKey 
{
	/**RSA算法中的數據元素
	*pub_n->n
	*pub_q->q
	*pub_p->p
	*pub_e->e
	*pub_d->d
	*/
	long pub_n,pub_q,pub_p,pub_e,pub_d;

	
	/** witness算法(用來檢測一個元素是否是素數
	 *<P>pre:none.
	 *<P>post:dicide whether the number inputed is a element number.
	 *@param n the number to test.
	*/
	boolean witness(long n)
	{
		//測試次數的計數器
		int counter=0;
		//將n-1轉化程二進制字符串b
		String b=Long.toBinaryString(n-1);

		while(true)
		{
			//隨機產生一個a
			long a=(long)((n-1)*Math.random()+1);
			long d=1;
			
			for(int i=b.length()-1;i>=0;i--)
			{
				long x=d;
				d=(x*x)%n;
				if(d==1&&x!=1&&x!=n-1)
					return false;
			    /**測試代碼
				System.out.println("i="+i+" x="+x+" d="+d+" b"+i+"="+b.charAt(b.length()-1-i));
				*/
				if(b.charAt(b.length()-1-i)=='1')
					d=(d*a)%n;
			}
			if(d==1)
				counter++;
			else return false;

			//如果連續100個a都通過檢測，則假設n是一個素數。(經試驗這種算法安全)
			//如果假設錯誤，在構造函數中還有一層保護
			if(counter>=100)
				return true;
		}
	}
	
	/**返回一個指定大小的素數(與參數最接近)
	 *<P>pre:None.
	 *<P>post:return a element number that approximate the parameter.
	 *@param max_num to limit,or to say confin,the generating number.
	*/
	long eleGenerator(long max_num)
	{
		long p=(long)(Math.random()*max_num+1);
		//使p為奇數
		p=p%2==0?p+1:p;
		//用witness算法檢p是否為素數
		while(!witness(p))
			p-=2;
		return p;
	}
	
	/**產生RSA中的p、q、n and e
	 *<P>pre:None.
	 *<P>post:generate "p、q、n、e" in RSA.
	*/
	void PQNEDGenerator()
	{
	//p的范圍定在2^30這個數量級(eleGenerator的具體內容見上)
		pub_p=eleGenerator((long)(Math.random()*Math.pow(2,30)));
	//q的范圍定在2^20這個數量級,與p大概相隔4個十進制以避免受到攻擊(eleGenerator的具體內容見上)
		pub_q=eleGenerator((long)(Math.random()*Math.pow(2,20)));
	//生成n
		pub_n=pub_p*pub_q;
	//e的生成
		pub_e=(long)((pub_p-1)*(pub_q-1)*Math.random());
		//使e為奇數
		pub_e=pub_e%2==0?pub_e-1:pub_e;
		pub_d=stein(pub_e,(pub_p-1)*(pub_q-1));
		while(pub_d==-999)
		{
			pub_e-=2;
			pub_d=stein(pub_e,(pub_p-1)*(pub_q-1));
		}
	}

	/**Stein算法(計算(e,m),又在(e,m)=1的情況下算出e對于模m的逆元)
	 *<P>pre:none.
	 *<P>post:判斷(e,m)是否等于1。如果不等于1返回-999，如果等于1返回e對于模m的逆元。
	 *@param e Stein算法中的"e".
	 *@param m Stein算法中的"m".
	*/
	long stein(long e,long m)
	{
		long s0,s,r,r0,x,y,u,v;
		s0=s=e;
		r0=r=m;
		x=v=0;
		y=u=1;

		while(r!=0)
		{
			/**調試代碼
			System.out.println("r="+r);
			System.out.println("u="+u);
			*/
			if(r%2==1)
			{
				if(s>r)
				{
					long temp=s;s=r;r=temp;
					temp=x;x=u;u=temp;
					temp=y;y=v;v=temp;
				}
				r-=s;x-=u;y-=v;
			}
			else
				if(y%2==0)
				{
					r/=2;x/=2;y/=2;
				}
				else
				{
					if(y<0)
					{
						r/=2;
						y=(y+s0)/2;
						x=(x-r0)/2;
					}
					else
					{
						r/=2;
						y=(y-s0)/2;
						x=(x+r0)/2;
					}
				}
		}
		if(s==1)
			return u%m<0?u%m+m:u%m;
		else return -999;
	}
	/**計算有可能溢出的模m的整數冪的算法
	 *<P>pre:none.
	 *<P>post:返回a^t(mod n);
	 *@param a a^t(mod n)中的a
	 *@param t a^t(mod n)中的t
	 *@param n a^t(mod n)中的n
	*/
	long powMod(long a,long t,long n)
	{
		long c=0;
		long d=1;
		String b=Long.toBinaryString(t);
		
		for(int i=b.length()-1;i>=0;i--)
		{
			c*=2;
			d=(d*d)%n;
			if(b.charAt((b.length()-1-i))=='1')
			{
				c+=1;
				d=(d*a)%n;
			}
			/**調試代碼
			System.out.print("i="+i);
			System.out.print(" c="+c);
			System.out.print(" d="+d);
			System.out.println();
			*/
		}
		return d;
	}
		

	/**構造函數
	 *<P>作用是控制程序的流程，依次作了以下工作：
	 *<P>1,模擬加密解密50次，以防止p,q不是素數(witness算法的不足性).
	 *<P>2,產生RSA算法中的p,q,r,s.
	 *<P>3,保存公鑰(e和n)，私鑰(d和n).
	*/
	makeKey()
	{
		/**witness函數的測試代碼
		long test=(long)(Math.pow(2,13)-1);
		System.out.println(witness(test));
		*/

		/**elementGenerator函數的測試代碼
		long test=eleGenerator((long)(Math.random()*Math.pow(2,30)));
		System.out.println(test);
		System.out.println(witness(test));
		*/
		
		/**PQNEDGenerator函數的測試代碼
		PQNEDGenerator();
		System.out.println("p="+pub_p);
		System.out.println("q="+pub_q);
		System.out.println("n="+pub_n);
		System.out.println("e="+pub_e);
		System.out.println("d="+pub_d);
		*/
				
		/**stein函數的測試代碼
		System.out.println(stein(5,96));
		*/
		
		//模擬加密解密50次，以防止p,q不是素數(witness算法的不足性)
		boolean secure=false;
		while(!secure)
		{
			PQNEDGenerator();
			for(int i=0;i<50;i++)
			{
				long test=(long)(Math.pow(2,20)*Math.random());
				long c=powMod(test,pub_e,pub_n);
				long m=powMod(c,pub_d,pub_n);
				if(test==m)
				{
					secure=true;
				}
				else 
				{
					secure=false;
					break;
				}
			}
		}
		System.out.println("密鑰成功產生");
		
		//以下是保存公鑰私鑰的io操作
		String filename=" ";
		try{
			BufferedReader in1=new BufferedReader(
				new InputStreamReader(System.in));

			System.out.println("請輸入公鑰存放的文件名:");
			filename=in1.readLine();
			DataOutputStream key=new DataOutputStream(
				new BufferedOutputStream(
					new FileOutputStream(filename)));
			key.writeLong(pub_e);
			key.writeLong(pub_n);
			key.close();
			System.out.println("公鑰已保存!");

			System.out.println("請輸入私鑰存放的文件名:");
			filename=in1.readLine();
			key=new DataOutputStream(
				new BufferedOutputStream(
					new FileOutputStream(filename)));
			key.writeLong(pub_d);
			key.writeLong(pub_n);
			key.close();

			System.out.println("公鑰和私鑰生成完畢");
		}
		catch(IOException e){
			System.err.println("文件寫入錯誤，請檢查輸入格式!\n正確格式：data.dat或c:\\data.dat");
		}
	}

	public static void main(String args[])
	{
		new makeKey();
	}
}