仿射加密（java）

仿射加密的加密過程是一個線性變換：

在仿射加密中，可設0-25對應 'a '-‘z’ 這26個字母。

• 設y為密文，x為明文，則：

  y(x)=(k1x+k2) mod 26

  并且要求gcd(k1，26)=1；（即k1與26的最大公約數為1）

  要求k1和26互素，不然y(x)就不是一個單射函數

  在求解仿射解密函數時，需要求k1在Z26上的乘法逆元a-1∈Z26，這可由擴充歐幾裡得算法求解

  解密 x=（ (k1-1)(y(x)-k2) )%26

  下面是仿射加密的java實作：（附有注釋）

  • KeyInput隻是一個輔助類，用來控制台輸入，完全可以用scanner代替

  • 本程式假設隻輸入a-z這26個字母

    擴充的歐幾裡得算法：

  26=a1*q1+c1; //注意 第一次的a1是我們加密過程中的k1

  a1=a2*q2+c2; //a2=c1;

  a2=a3*q3+c3; //a3=c2;

  · · · · · · //直到cj==1時停止

  b-1=0;

  b0=1;

  bj=(-1)*bj-1*qj+bj-2 //當cj==1時求出bj

  k3=bj%26 //k3是解密時需要的數

  ``

  package AffineEncryp;
  
  import link_about.KeyInput;
  
  public class AffineEncryp {
      static int k1,k2,k3;
  
      public static void main(String[] args) {
          int t=0;
          while(true){
              System.out.println("1.仿射加密程式 \n0.exit");
              t= KeyInput.readInt();
              if(t==0) {
                  break;
              }
              AffineEncryption();
          }
      }
  
      public static char affine(char c){//加密
          int c1=c-97;
          int c2=(c1*k1+k2)%26;//加密過程就是将字母從0-25編碼，然後進行函數變化得到另一個字母
          return (char)(c2+97);
      }
  
      public static char de_affine(char c){//解密
          int m=(k3*((int)c-97)-((k3*k2))%26);//解密過程運用解密函數，其中的k3要用擴充的歐幾裡得算法得出，
          if(m<0){//此處判斷m是否為0是因為當m為負數的時候無法按照算法的要求進行mod運算，否則會出錯
              m+=26;
          }
          c=(char)((m%26)+97);
          return c;
      }
  
      public static void AffineEncryption(){
          System.out.println("請給定兩個參數k1,k2");
           k1=KeyInput.readInt();
           k2=KeyInput.readInt();
          while( new Gcd().gcd(k1,k2)!=1){
              System.out.println("映射不唯一，請重新給定k1,k2");
               k1=KeyInput.readInt();
               k2=KeyInput.readInt();
          }
          k3=new ExtenedEuclid().get_k(k1,26);//計算k3
          System.out.println("ps:k3的值為"+k3 +"");
          System.out.println("請輸入要加密的字元串");
          String s=KeyInput.readString();
          String s1="";
          for(char c:s.toCharArray()){//加密
              s1+=affine(c);
          }
          System.out.println("加密後字元串為");
          System.out.println(s1);
          System.out.println("解密：");
          for(char c:s1.toCharArray()){
              System.out.print(de_affine(c));
          }
          System.out.println();
          return;
      }
  }
  
             

  ``

  ``

  package AffineEncryp;
  
  public class ExtenedEuclid {//擴充的歐幾裡得算法
      public int get_k(int a,int mod){
          if(a==1){
              return 1;
          }
          int[] b=new int[99];
          int c=mod%a;
          int q=mod/a;
          b[0]=0;
          b[1]=1;
          for(int i=2;;i++){//從2開始，事實上這個位置可以優化，隻需要一個長度為3的數組就可以，為了友善了解我這裡沒有進行優化
              b[i] = (-1) * q * b[i - 1] + b[i - 2];
              if(c==1){
                  if(b[i]<0)//同樣的道理，如果按照标準算法直接進行mod運算會出錯，是以改成 '+'
                      return b[i]+mod;
                  else
                      return b[i]%mod;
              }
              q = a / c;
              int c1 = c;
              c = a % c;
              a = c1;
          }
      }
  }
  
             

  ``

``

package AffineEncryp;

public class Gcd {
    public  int gcd(int a,int b){//求最大公約數
        int gcd=0;
        if(a<b){//確定a更大，否則交換a、b的值
            a+=b;
            b=a-b;
            a-=b;
        }
        if(a%b==0){ //直接相除沒有餘數，且a>b,說明b即是最大公約數
            return b;
        }
        while(a%b>0){//否則就輾轉相除,再重複上面的過程,直到二者相等,此時 a%b==0一定成立,a==b==最大公約數
            a=a%b;
            if(a<b){
                a+=b;
                b=a-b;
                a-=b;
            }
            if(a%b==0){
                return b;
            }
        }
        return gcd;
    }
}

           

我是一定會回私信的兔子~