철이네집

공개키 암호화 알고리즘

암호의 역사는 로마 시대로 까지 거슬러올라간다고 하지만 인터넷을 통해 수많은 금융 거래가 이루어지있는 요즘 처럼 암호화된 통신이 널리 사용되는 때도 아마 없을 것이다. 실제로 어떤 파일 혹은 문장을 인터넷상의 다른 사용자에게 비밀리에 전송하려고 할 때 어떤 방법을 사용할 수 있을까? 가장 먼저 생각할 수 있는 것은 우리가 흔히 zip 파일을 압축할 때 이용하는 대칭키 알고리즘(혹은 비밀키 알고리즘)이다. 이 방식에서는 암호화하는 측과 암호를 푸는 측이 같은 키를 이용한다. 그러나 인터넷 상의 정보는 언제든지 훔쳐보기가 가능하기 때문에 이 방법은 네트웍상의 통신에 적용하기에 적절하지 않다. 암호(비밀키)를 인터넷을 통해 주고 받는 것이 불가능하기 때문이다.

그리하여 나오게 된 것이 공개키 알고리즘인데 공개키 알고리즘은 암호화 할 때 사용하는 암호와 암호를 풀 때 사용하는 암호가 서로 다르다. 서로 다른 키를 사용함으로서 비밀리에 키를 교환할 필요 자체가 없어졌다. 제 3 자는 암호화키를 알고 있더라도 암호문을 풀 수 없으므로 암호화할 때 사용하는 키는 중간에 누가 가로채도 상관없다. 아니 오히려 사용하기 편하게 잘 보이는 곳에 놔두는 것이 좋을 것이다. 누구든지 이 공개키로 메시지를 암호화해서 보내면 그 메시지를 받는 사람은 숨겨둔 비밀키(혹은 개인키라고도 한다)를 이용하여 이를 풀어볼 수 있다. 얼핏 생각하면 믿기 힘든 이러한 일이 수학의 마술로 인해 가능해 졌다.

소개

공개키 알고리즘의 대표적인 RSA는 1977년에 Ron Rivest, Adi Shamir와 Leonard Adleman에 의해 개발되었다. RSA는 큰 수의 소인수 분해가 매우 어렵다는 사실을 이용한다. 현재 슈퍼컴퓨터와 복잡한 수학적 기법들을 이용해 155자리 합성수가 인수분해 되었는데(1999년 8월) 155를 2진수로 표현하면 512 비트이기 때문에 흔히 RSA에서 사용하는 키는 이보다 길이가 2배 긴 1024비트를 이용한다.

RSA의 원리

집합 {1, 2, ... , n-1} 의 원소들 중에서 n 과 서로소의 관계에 있는 원소들의 개수를 φ(n)으로 나타내고 이를 Euler의 φ-function이라고 한다. 특별히 소수 p에 대해서 φ(p) = p-1 이다. 큰 정수 n에 대해 φ(n)의 값을 알기 위해서는 n의 소인수 분해가 필수적이다. 즉, n이 두 소수 p와 q의 곱일 때 φ(n) = (p-1)(q-1)이다. 따라서 소인수 분해 없이 φ(n)을 구하기는 매우 어렵다. Euler의 정리란, 서로 소인 두 양의 정수 a, n에 대해 aφ(n) ≡ 1 (mod n) 이 성립한다는 것이다.

Step 1
   두개의 큰 소수 p, q를 선정하여 자신의 비밀열쇠로 한다
Step 2
   n = pq인 n을 공개하고 φ(n)과 서로 소인 임의의 정수 e를 선택하여 공개키로 한다.
Step 3
   ed ≡ 1 (mod φ(n)) 이 되는 d를 Euclidean Algorithm등으로 계산하여 비밀 열쇠로 한다.
   즉, p와 q 그리고 d는 비밀 열쇠로, n과 e는 공개키로 한다.

암호화 Step
     평문 M을 공개키 e를 사용하여 Me를 계산한 다음 modular n으로 간단히 한다.
     즉 암호문 C는 다음과 같다. C = Me (mod n)

복호화 Step.
     암호문 C를 비밀열쇠 d를 이용하여 Cd한 다음 modular n으로 간단히 한다.
     다시 평문이 나오게 되는 관계식은 다음과 같다.
                 Cd ≡ (Me)d = Mtφ(n)+1 = Mφ(n)t M ≡ M (mod n)
     여기서 t는 ed ≡ 1 (mod φ(n))에서 유도되는 ed = tφ(n)+1 을 만족하는 정수이다.

실제 사용 예

예를 들어 설명하면 다음과 같다. RSA 암호화 기법에는 private key, public key, modulus가 필요하다.
암호화하는데에는 public key와 modulus, 복호화하는데에는 private key와 modulus가 이용된다.

암호화 : (암호화된문장) = (원래문장)^(public key) mod modulus
암호화 : (원래문장) = (암호화된문장)^(private key) mod modulus

단, 여기서 (원래 문장)의 비트수는 (modulus)의 비트수보다 작아야 한다. 따라서 실제의 메세지를 n보다 작거나 같은 길이로 잘라서 입력해야 한다. 좀 더 구체적인 예를 들기 위해서 이번에는 크기가 매우(!) 작은 수를 이용하여 위의 과정을 따라가 보자
public key = 5
private key = 77
modulus = 119
비밀키를 자신이 소유하고 공개키는 안전한 공개키 디렉토리에 등록한다.
그런 다음 아스키코드 한자리 "a"=65를 전송한다고 해 보자.(아스키코드는 7비트 이내에 있으므로 7비트 짜리 modulus로 전송할 수 있다.)

암호화 : 65^5 mod 119 = 46
복호화 : 46^77 mod 119 = 65

잘 작동한다는 것을 알 수 있다.

키를 생성하기

이러한 RSA 암호화 알고리즘을 이용하기 위해서는 자신만의 공개키, 비밀키, modulus의 쌍을 필요로 한다. 이러한 숫자 쌍을 생성하는 프로그램을 제작해 보았다.(첨부 파일에 있는 RSAKeyGen.exe 실행)

php 소스 코드

php에서 RSA 암호화 알고리즘을 이용할 수 있도록 함수 및 예제를 아래에 첨부하였다.
<?
// PHP의 BCMath 기능을 필요로합니다. --enable-bcmath 옵션을 붙여 컴파일 해야합니다.
// 최신 버젼의 PHP에는 BCMath가 기본으로 들어가 있습니다.
// GPL에 의거하여 http://www.edsko.net/phpsource.php?file=projects/rsa.php
// 를 수정하였습니다. 수정 날짜 : 2005/04/29
// Calculate (p ^ q) mod r
function pow_mod($p, $q, $r)
{
    // Extract powers of 2 from $q
   $factors = array();
   $div = $q;
   $power_of_two = 0;

    // BCCOMP_LARGER == 1
   while(bccomp($div, "0") == 1)
   {
      $rem = bcmod($div, 2);
      $div = bcdiv($div, 2);

      if($rem) array_push($factors, $power_of_two);
      $power_of_two++;
   }

   // Calculate partial results for each factor, using each partial result as a
   // starting point for the next. This depends of the factors of two being
   // generated in increasing order.
   $partial_results = array();
   $part_res = $p;
   $idx = 0;
   foreach($factors as $factor)
   {
      while($idx < $factor)
      {
           $part_res = bcpow($part_res, "2");
           $part_res = bcmod($part_res, $r);

           $idx++;
      }

      array_push($partial_results, $part_res);
   }

   // Calculate final result
   $result = "1";
   foreach($partial_results as $part_res)
   {
      $result = bcmul($result, $part_res);
      $result = bcmod($result, $r);
   }

   return $result;
}

// Function to add padding to a decrypted string
// We need to know if this is a private or a public key operation
function add_PKCS1_padding($data, $isPublicKey, $blocksize)
{
   $pad_length = $blocksize - 3 - strlen($data);
   if($isPublicKey)
   {
      $block_type = "x02";
      $padding = "";
      for($i = 0; $i < $pad_length; $i++)
      {
           $rnd = mt_rand(1, 255);
           $padding .= chr($rnd);
      }
   }
   else
   {
      $block_type = "x01";
      $padding = str_repeat("xFF", $pad_length);
   }

   return "x00" . $block_type . $padding . "x00" . $data;
}

// Remove padding from a decrypted string
function remove_PKCS1_padding($data, $blocksize)
{
   assert(strlen($data) == $blocksize);
   $data = substr($data, 1);

   // We cannot deal with block type 0
   if($data{0} == "\0")
      die("Block type 0 not implemented.");

   // Then the block type must be 1 or 2
   assert(($data{0} == "x01") || ($data{0} == "x02"));

   // Remove the padding
   $offset = strpos($data, "\0", 1);
   return substr($data, $offset + 1);
}

function hex_to_number($data)
{
    $len = strlen($data);
    $result = "0";
   for($i = 0; $i < $len - 1; $i++)
   {
      $result = bcadd($result, hexdec($data{$i}));
        $result = bcmul($result, 16);
   }
    $result = bcadd($result, hexdec($data{$len-1}));
   return $result;
}

// Convert binary data to a decimal number
function binary_to_number($data)
{
   $base = "256";
   $radix = "1";
   $result = "0";
   for($i = strlen($data) - 1; $i >= 0; $i--)
   {
      $digit = ord($data{$i});
      $part_res = bcmul($digit, $radix);
      $result = bcadd($result, $part_res);
      $radix = bcmul($radix, $base);
   }
   return $result;
}

// Convert a number back into binary form
function number_to_binary($number, $blocksize)
{
   $base = "256";
   $result = "";
   $div = $number;
   while($div > 0)
   {
      $mod = bcmod($div, $base);
      $div = bcdiv($div, $base);
      $result = chr($mod) . $result;
   }
   return str_pad($result, $blocksize, "x00", STR_PAD_LEFT);
}

function rsa_encrypt($message, $public_key, $modulus, $keylength)
{
    $padded = add_PKCS1_padding($message, true, $keylength / 8);
   $number = binary_to_number($padded);
   $encrypted = pow_mod($number, $public_key, $modulus);
    return $encrypted;
}

function rsa_decrypt($message, $private_key, $modulus, $keylength)
{
   $decrypted = pow_mod($message, $private_key, $modulus);
    $result = number_to_binary($decrypted, $keylength / 8);
   return remove_PKCS1_padding($result, $keylength / 8);
}

$public_key = hex_to_number("9E649FF1");
$private_key = hex_to_number("7C0732C4379EDE1FB6E6CF2E7B262B41");
$modulus = hex_to_number("95C3BE09B678F8BD55F859CC24B4797B");

$enc = rsa_encrypt("메롱 약오르지롱~", $public_key, $modulus, 128);
echo rsa_decrypt($enc, $private_key, $modulus, 128);
?>

위의 예제에서는 128 비트 암호화를 이용하였으나 충분히 512 비트 1024비트로 확장할 수 있다. 비트수가 늘어날수록 암호는 깨기 어려워지는 대신 속도가 느려지는 단점이 있다.