RSA 공격(1)

앞에서 RSA 공격에 대한 내용이 있었다.
이것을 어떻게 하면 될지 간단하게 코드로 만들어 보았다.

• RSA에 대한 공격

‡(1) 수 D를 알면 암호문을 복호화 할 수 있다. 

그렇기 때문에 RSA에 대한 공격 방법으로서, D의 후보가 되는 수를 순서대로 시도해서 복호화한다는 전사공격을 생각할 수 있다. 

전사공격은 D의 비트 수가 크면 클수록 시도해보아야 할 수도 많아지고 계산도 복잡해지므로 점점 더 시간이 걸리며 어려워진다. 

따라서 비트 수가 충분히 크면 전사공격으로 수 D를 찾아내는 것은 현실적으로는 불가능해진다. 

• 수 D를 알면 암호문을 복호화 할 수 있다. Java RSA 공격 예제

이 예제는 암호문과 평문을 N을 알때 D를 구하는 방법이다. 일반적으로 공개키를 가지고 있다는 것은 평문을 암호문으로 바꿀 수 있다는 것을 의미한다.

import java.math.BigInteger;

public class calc {
 private static int mD = 0;
 private static int mN = 0;
 private static int mL = 0;
 private static int mE = 0;
 private static int mEncData[];
 private static int mPlainData[];

 public static void main(String[] args) {
  int plainText[] = {123,100,80};
  processRSA(17,19,plainText);
  attackRSA_case_All(mEncData,mN,plainText);
 }

 private static void processRSA(int p,int q,int PlainText[]) {
  int N = p*q;
  int L = GcdNLcm.lcm(p-1,q-1);
  int findE = -1,findD = -1;
  int i;
  mEncData = new int [PlainText.length];
  System.out.println("(1)N:"+N);
  System.out.println("(2)L:"+L);
  /////////////////////////////
  System.out.println("(3)find E");

  for(i=2;i<L;i++){
   if(GcdNLcm.gcd(i,L)==1){
    System.out.printf("%d ",i);
    if(findE == -1 || Math.random()>0.95){
     findE = i;
    }
   }
  }
  System.out.println("...");
  System.out.println("findE:"+findE);
  /////////////////////////////  
  System.out.println("(4)find D");
  for(i=1;i<L;i++){
   if((findE*i)%L ==1){
    System.out.printf("%d ",i);
    if(findD == -1 || Math.random()>0.8){
     findD = i;
    }
   }
  }
  System.out.println("...");
  System.out.println("findD:"+findD);
  /////////////////////////////
  for(i=0;i<PlainText.length;i++){
   System.out.println("(5)encrypt");
   BigInteger bigPlainText;
   bigPlainText = BigInteger.valueOf(PlainText[i]);

   BigInteger bigEncData = bigPlainText.pow(findE).mod(BigInteger.valueOf(N));
   System.out.println(PlainText[i]+"^"+findE+" mod "+N+"=" + bigEncData.toString());
   /////////////////////////////
   System.out.println("(6)decrypt");
   decRSA(N, findD, bigEncData);
   mEncData[i] = bigEncData.intValue();
  }
  /////////////////////////////
  mD = findD;
  mN = N;
  mL = L;
  mE = findE;
  mPlainData = PlainText;
 }

 private static void decRSA(int N, int findD, BigInteger bigEncData) {
  BigInteger bigDecData = bigEncData.pow(findD).mod(BigInteger.valueOf(N));
  System.out.println(bigEncData.toString()+"^"+findD+" mod "+N+"=" + bigDecData.toString());
 }

 private static int attackRSA_case_All(int encData[],int N,int plainText[]) {
  // 평문 = 암호문^D mod N
  // D=?
  int i;
  System.out.println("********attackRSA_case_All");
  for(i=0;i<plainText.length;i++){
   System.out.println("********find D*******");
   int findD = attackFindD(encData[i], N, plainText[i], 10000, 5);
   System.out.println("********recheck*******");
  }
  return -1;
 }

 private static int attackFindD(int encData, int N, int plainText,int loop, int count) {
  BigInteger bigDecData = BigInteger.valueOf(encData);
  for(int i=0;i<loop;i++){
   if( bigDecData.pow(i).mod(BigInteger.valueOf(N)).intValue() == plainText ){
    System.out.println("Found D:"+i);
    count--;
    if(count <= 0) return i;
   }
  }
  return -1;
 }

 public static class GcdNLcm
 {
  public static int gcd(int left, int right)
  {
   if(left == 0 || right == 0)
    return 0;
   int high = left;
   int low = right;
   if(high < low)
   {
    int temp;
    temp = high;
    high = low;
    low = temp;
   }
   int remain;
   do
   {
    remain = high % low;
    high = low;
    low = remain;
   }
   while(remain != 0);
   return high;
  }
  public static int lcm(int left, int right)
  {
   int gcd = gcd(left,right);
   if(gcd == 0)
    return 0;
   return left * right / gcd;
  }
 }
}

결과는 아래와 같다.
의미하는 바는 D값을 구해내더라도 여러개의 암호문->평문으로 할 수 있는 공통의 D값을 찾아내야 한다는 것이다.

(1)N:323
(2)L:144
(3)find E
5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107 109 113 115 119 121 125 127 131 133 137 139 143 ...
findE:5
(4)find D
29 ...
findD:29
(5)encrypt
123^5 mod 323=225
(6)decrypt
225^29 mod 323=123
(5)encrypt
100^5 mod 323=104
(6)decrypt
104^29 mod 323=100
(5)encrypt
80^5 mod 323=207
(6)decrypt
207^29 mod 323=80
********attackRSA_case_All
********find D*******
Found D:29
Found D:65
Found D:101
Found D:137
Found D:173
********recheck*******
********find D*******
Found D:29
Found D:101
Found D:173
Found D:245
Found D:317
********recheck*******
********find D*******
Found D:29
Found D:173
Found D:317
Found D:461
Found D:605
********recheck*******