import java.util.Random;
import java.awt.*;
import java.awt.event.*;
import java.math.*;

class Method
{ 
 
  //隨機生成素數p,調Random類，設長度256 bits(十進制78位)概率確定性n＝50
  BigInteger S1() 
  { 
    BigInteger one=new BigInteger("1");
    Random rnd1=new Random();
    BigInteger p=new BigInteger(256,1000,rnd1);
    return p;
  }

  

  //隨機生成素數q,調Random類，設長度256 bits(十進制78位)概率確定性n＝50
  BigInteger S2() 
  { 
    BigInteger one=new BigInteger("1");   
    Random rnd2=new Random();
    BigInteger q=new BigInteger(256,1000,rnd2);
    return q;
  }

  //求a,b的最大公約數
 BigInteger EA(BigInteger a,BigInteger b)
  {
    BigInteger r0=a;
    BigInteger r1=b;
    BigInteger r2=null;
    BigInteger q=null;
    BigInteger y=new BigInteger("0");
    while(r1.compareTo(y)!=0)
    {
      q=r0.divide(r1);
      r2=r0.subtract(q.multiply(r1));
      r0=r1;
      r1=r2;                                     
    }
     return r0;
  }


  //求b模a的逆
  BigInteger MI(BigInteger a,BigInteger b)
  {
    BigInteger m=a;   
    BigInteger n=b;
    BigInteger h=new BigInteger("0"); 
    BigInteger t=new BigInteger("1");
    BigInteger k=new BigInteger("1");    
    BigInteger q=m.divide(n);                             
    BigInteger r=m.subtract(q.multiply(n));
    BigInteger temp=null;
    BigInteger y=new BigInteger("0");
    while(r.compareTo(y)>0)
    {
      temp=h.subtract(q.multiply(t)).mod(a);
      h=t;
      t=temp;
     m=n;
      n=r;
      q=m.divide(n);
      r=m.subtract(q.multiply(n));
    }
/*    if(n.compareTo(k)!=1)
    {System.out.println(b+"沒有模"+a+"的逆");}
    else */   
    if(t.compareTo(y)<0)
    {t=a.add(t);}
    return t;
   }
}
                  
//主類
public class kmov
{
     
  public static void main(String[] args) throws Exception
  {
     BigInteger a=new BigInteger("2"); 
     BigInteger b=new BigInteger("1");
  
    //生成p,q并計算N
    
    BigInteger d=null;
    
    Method met=new Method();
    
    BigInteger p=met.S1();
    BigInteger q=met.S2();
    BigInteger n=p.multiply(q);

     BigInteger z=new BigInteger("0");
   
    //計算e,并輸出公鑰     
    BigInteger N=((p.add(b)).multiply(q.add(b))).divide(a);
  
     Random rnd=new Random();  
     BigInteger e=new BigInteger(10,rnd);  
     System.out.println("e和N的最大公約數為:"+met.EA(e,N)); 
  
   if(met.EA(e,N).compareTo(b)!=0)
    {
       System.out.println("不符合參數所需條件,請重新運行程序!");  
    }
    else
    { 


 /*  Random rnd=new Random();  
     BigInteger e=new BigInteger(512,rnd); 

   System.out.println(met.EA(e,N).compareTo(b));  
    int i;

    for(BigInteger e=new BigInteger(512,rnd),BigInteger h;met.EA(e,N).compareTo(b)!=0;BigInteger h=e)
    {   
      h=new BigInteger(512,rnd); 
    }
  */
   
   System.out.println("公鑰n="+n+",a="+a+",b="+b+",e="+e);
    
    //計算d
    d=met.MI(N,e);
  
    BigInteger m=n.divide(a);

    BigInteger i=b;
    double s1=0,s2=0;
  
    
    System.out.println("待加密明文m為:"+m);
    BigInteger t0=m;

    BigInteger x=(b.multiply(met.MI(n,(t0.multiply(t0)).subtract(a)))).mod(n); 
    BigInteger y=((b.multiply(t0)).multiply(met.MI(n,(t0.multiply(t0)).subtract(a)))).mod(n);
  
    //System.out.println("r0="+y); 
   
     BigInteger j=met.EA(x,n);  
   
   //System.out.println("r1="+j);

  if(j.equals(p)||j.equals(q))
    {
      System.out.println("太巧了，重選一個m吧!");
    }
    else
  {    
     
    //計算簽名
     while(i.compareTo(d)<0)
     {
      t0=((t0.multiply(m)).add(a)).multiply(met.MI(n,t0.add(m))).mod(n);
      x=(b.multiply(met.MI(n,(t0.multiply(t0)).subtract(a)))).mod(n);
      y=((b.multiply(t0)).multiply(met.MI(n,(t0.multiply(t0)).subtract(a)))).mod(n);
      i=i.add(b); 
     }
    
    BigInteger r=x;
    BigInteger s=y;
    BigInteger t=t0;
    
   //簽名驗證
    while(i.compareTo(e)<0)
     {
      t=((t.multiply(t0)).add(a)).multiply(met.MI(n,t.add(t0))).mod(n);
      x=(b.multiply(met.MI(n,(t.multiply(t)).subtract(a)))).mod(n);
      y=((b.multiply(t)).multiply(met.MI(n,(t.multiply(t)).subtract(a)))).mod(n);
      i=i.add(b); 
     }
     
    if(x.equals(r)||y.equals(s))
    {System.out.println("簽名驗證正確!");}

     // BigInteger Xm=met.MI(n,x);
    }  
 } 
}
}