JAVA 공개키 암호화의 수학적 알고리즘과 자바 구현

  1.DES암호화 시스템과 RSA공개 암호화 시스템의 차이점

    DES암호화 시스템

     DES는 송신자와 수신자만이 알고 있는 동일한 대칭키를 이용하여 메시지를 암호화하고

     복호화하고 있다.

     <문제점>

       ① 키의 사전분배 문제

          - 단체와 기업같은 폐쇄적인 사용자들은 용이하나 인터넷같은 개방형 시스템에서는

             동일한 대칭키를 고유하는 것이 위험성이 잇다.

       ② 여러 사용자와 사용하려면 많은 수의(n*(n-1)/2)의 대칭키가 필요하게 되고 대칭키의

           생성과 분배는 시스템의 효울성을 저하시키고, 많은 수의 대칭키의 유지, 관리가 어렵다.

     RSA공개 암호시스템

        ① 서로 연관성이 있는 상이한 두 개의 키를 각각 암호화와 복호화에 이용

        ② 송신자는 메시지 m을 공개키로 암호화하여 수신자에게 보내면 수신자는 자기만이 알고

            있는 개인키로 복호화 함

        ③ 모든 사용자는 자기만의 한쌍의 공개키와 개인키를 가지며 공개키는 자기에게 메시지를

            보내려는 사람에게 모두 제공해 주고, 개인키는 자신만이 알고 있어야 함

        ④ 공개키 암호 시스템은 키의 사전분배문제를 해결하고, 디지털 서명과 같은 새로운 개념을

            출현시킴

  2. 공개키 암호 시스템은 일방향 함수를 이용

        ① 일방향 함수

            x가 주어지면 y=f(x)의 계산이 용이한 반면, y가 주어졌을 때 x를 구하기 위한 f(x)의 역

            함수를 구하는 것이 불가능한 함수 f(x)를 말한다.

         ex) 두 개의 매우 큰 소수의 곱

               p와 q가 매우 큰 소수이면 n=p*q의 계산은 용이한 반면, 합성수인 n에서 p와 q를 구

               하는 것이 아주 어려운 작업이다. - RSA공개 암호 시스템

        ② 공개키 암호 시스템은 이 일방향 함수를 이용한다. 즉 공개키로 암호화하는 것은 f(x)는

            용이하고, 수신자만이 알고 있는 비밀키는 f(x)의 역함수를 구하는 비밀통로의 역할을

            한다.

         - 비밀통로 일방향 함수

  3. RSA공개 암호 시스템을 구현하기 위한 수학적 알고리즘

   최대공약수

     ① a,b ∈ z(실수)에 대해 a = (b * q) + r이다.

         만약, r=0 이면 b를 a의 약수 또는 인수라 한다. b|a로 표시

     ② a,b,c ∈ z에 대해 c|a, c|b 이면 c는 a와 b의 공약수

     ③ 공약수 중 가장 큰수를 최대 공약수(Greatest Common Divisor)라 하고, gcd(a,b)로 표시

     ④ 임의의 정수 p≥2에 대한 약수가 1과 p밖에 없다면 p를 소수(Prime)라 하고,  그렇지 않을

         경우 합성수(Composite)라 함

     [정 리]

       ① a|b, b|c이면 a|c이다.

       ② a|b, a|c이면 a|(bx*cy)이다.

       ③ p가 소수이고 p|(a*b)이면 p|a 또는 p|b이다.

  유클리드 알고리즘(Euclidean algorithm)

    - 최대 공약수를 구하는 가장 효울적인 방법

       a≥b의 관계에 있는 양의정수 gcd(a,b)를 구하는 알고리즘(java로 구현)

       s = a;                                    ex) a=252, b=198이면 gcd(252,198)=?

       t = b;                                          a=252=(198*1) + 54

       while(t>0) {                                 198=(54*3) + 36

             r = s % t;                               54=(36*1)+18

             s = t;                                     36=(18*2)+0

             t = r;                            

            }                                                ∴ gcd(252,198) = 18이다.

  확장된 유클리드 알고리즘

   위에서 gcd(252,198)=18에서 18을 가지고 252와 198을 찾아낼 수 있다.

      18 = 54 - 1*36 = 54 - (198 - (3 *54)) = 4 * 54 - 198 = 4 ( 252 - 198 ) - 198

          = 4 * 252 - 5 * 198

   252와 198을 찾아낼수 있다.

     - 이 알고리즘은 RSA암호 시스템에서

        (공개키*비밀키) mod ((p -1) * (q - 1)) = 1 에서 공개키를 구해 낼 때 사용되는 알고리즘

        이다.

  RSA에서 쓰이는 전반적인 Modulus연산(mod)

    ① 양의 정수 n에 대하여 두 정수 a,b의 차 a-b가 n의 배수 일 때,

        즉 n|((a-b)이면 a와 b는 Modulus n에 합동이라 하고 a≡b (mod n)으로 나타냄

        또한, 정수 a를 n으로 나누었을 때의 나머지는 a mod n = r로 표현한다.

        그러므로 a mod n = r이면 a≡b (mod n)이 만족된다.

        이때 r을 Modulus n에 대한 a의 잉여하 한다.

    ② 임의 정수 a는 {0,1,2,3,…,n-1} 중의 어느 한 정수와 Modulus n에 대하여 합동이다.

    ③ Modulus에서의 곱셈상의 역원(확장된 유클리드 알고리즘으로 구한다.)

        a/b (mod n)과 같은 나눗셈의 경우 x * b ≡ 1 (mod n)인 x를 찾을 수만 있다면 x = 1/b

        이기 때문에 a * x mod n의 곱셈이 가능하다.

        이때 x를 b의 곱셈상의 역원이라고 한다.

      ex) 4/3 mod 5에서 x * 3 ≡ 1 (mod 5)인 x가 2이기 때문에 4/3 mod 5 = 4 * 2 ≡ 3 (mod 5)

            이다.  하지만, 0이 아닌 모든 정수 b의 곱셈상의 역훤이 존재하는 것은 아니다. n과 b가

            서로 소의 관계에  있을 경우에만 b의 곱셈상의 역원이 존재한다.

      ex) x * 5 mod 23 = 1에서 5의 곱셈상의 역원 x는 gcd(23,5)=1을 구하는 과정을 통한

            "확장된 유클리드 알고리즘"을 통해 구한다.

            23 = (5 * 4) + 3, 5 = (3 * 1) + 2, 3 = (2 * 1) + 1, 2 = (1 * 2) + 0

            1 = 3 - 2 = 3 - (5 - 3) = 2(23 - (5 * 4)) - 5 = 2 * 23 - 9 * 5

            따라서 x = -9 = 23 - 9 = 14이다.

  오일러 정리

     n이 소수이면 PI(n) = n -1이 된다.

     만약, n이 두 소수 p와 q의 곱이면

        PI(n) = p * q - [(p - 1) + (q - 1) + 1] = (p - 1)(q - 1)

       ∴ a ^ PI(n) mod n = 1

   Fermat 정리

     p가 소수이고, a와 p가 서로 소이면

       a ^ (p - 1) mod p = 1     

   4. 이제까지의 이론을 바탕으로 RSA공개 암호 시스템의 키값의 구현

       - RSA공개키 암호에 사용될 공개키 {N,E}와 개인키{N,D}를 생성하기 위해서는 먼저 모든

         사용자들은 각각 다음의 작업을 수행

       ① 두 개의 큰 소수 p와 q를 선정한 다음에 Modulus N = p * q와 PI(N)을 계산한다.

       ② 공개키 E는 PI(N) = (p - 1)(q - 1)과 서로 소의 관계가 되게 임의로 선정

       ③ E * D mon PI(N) = 1의 관계에 있는 개인키 D를 "확장된 유클리드 알고리즘"으로 구한다.

       ④ {E,N}을 공개키로 공개하고, {D,N}을 개인키로 자신이 안전하게 보관한다.

       - RSA암호화 (암호화 하려는 수는 M)

          E(M) = M ^ E mod N = C

       - RSA복호화

          D(C) = C ^ D mod N = ((M ^ E) ^ D) mod N = M

       ex) n = p * q = 47 * 71 = 3337 공개키 e는 (p - 1)(q - 1) = 46 * 70 = 3220과 서로 소의

             관계에 있는 임의의 정수 79로 선정한다. 따라서, 개인키는 "확장된 유클리드 알고리즘"

             을 이용하여  d = 1019가 된다. 평문 m = 688d은 암호문 c = 688 ^ 79 mod 3337 = 1570

             으로 암호화된다.

             개인키 d = 1019를 사용하여 다시 암호문 c = 1570은 평문 m = 1570 ^ 1019 mod 3337로

             복호화가 된다.

  5. Java로 구현시 또 다른 문제점   Go to the Experiment

  M ^ E mod N의 계산

    - 이 계산은 M과 E가 아주 큰 수이면 프로그램 언어로 실제로 구현하는데는 문제가 생기게

       된다.

      ∵ float or double형은 암호화한 수를 산출할 때에 제한된 자리수를 초과하게되면 반올림

          후 지수의 형태로 표시하지 때문에 long형을 사용해야 한다.

    - 계산 시간적으로 비효율적이다.("반복 제곱-곱셈"알고리즘을 사용)

  반복 제곱-곱셈 알고리즘

     ① 영이 아닌 e에 대해서 이 것을 이용하려면 먼저 e를 k비트의 2진수의 형태로 변형한다.

     ② ei의 값이 0이면 제곱, 1이면 제곱-곱셈의 연산을 수행한다.

     ③ 실제적 Java로 구현( ei는 i번째 비트의 값이다.)

            z = 1;

            for(int i=k-1;i>=0;i++)

            {

                    z = z ^ 2 mod n;

                    if(ei == 1)

                          z = (z * m) mod n;

             }

             return z;

  확룔적 소수 판정법(Miller-Rabin 알고리즘) - miller_rabin(n,k)

     n - 1 = (2 ^ s) * r에서 s와 r을 구해낸다.      

            boolean flag = true;

            for(int i= 1;i >= k;i++)

            {

                      a = (long)(Math.random() * (n - 2));

                      y = a ^ r % n;

                      if(y != 1 && y !=n-1)

                      {

                                j = 1;

                                while(j<=s-1 && y != n-1)

                                {

                                         y = y ^ 2 % n;

                                         if(y==1)

                                               flag = false;

                                         j++;

                                 }

                                 if(y!=n-1)

                                         flag = false;

                        }

            }

            return flag;