서비의 다락방

공개 키 암호화(public key encryption)는 사용자가 암호화(encrypt)한 메시지를 복호화(decrypt)하거나 복호화만이 가능한 메시지를 암호화하는데 사용되는 공개 키(public key)를 제공할 수 있도록 해준다. Dr. Ronald L. Rivest, Dr. Adi Shamir, 그리고 Dr. Leonard M. Adleman가 RSA 암호화 코드의 R, S, A에 해당한다. 이들은 공개 키 암호기법(cryptography)으로 ACM's 2002 Turing Award Winners를 수상하였고, ACM Turing Award Winners웹페이지에서 "Early Days of RSA", "Cryptology: A Status Report", "Pre-RSA."에 관한 이들의 프리젠테이션을 볼 수 있다.

RSA 암호화 알고리즘(RSA encryption algorithm)은 임의적이고 상호 독립적인, 가령 p=11, q=31과 같은 크기가 큰 두 개의 소인수를 선택하는 것으로부터 시작한다. 다음으로 N=(p)(q)를 계산하는데, p=11, q=31인 경우에는 N=(11)(31)=341이다. 그리고는 정수 e를 하나 선택하는데 (p-1)(q-1)와 공통인수가 없는 3과 N-1 사이의 범위에서 선택한다. 수 300은 (2)(2)(3)(5)(5)으로 소인수분해 되기 때문에 2, 3, 혹은 5의 배수는 정수 e의 선택범위에서 제외된다. 이 알고리즘에 대입하는 수는 꼭 소인수가 아니어도 되기 때문에 49나 77과 같은 수도 가능하다. 간단하게 e= 7을 대입해보자.

다음으로 (d)(e)=1 (mod(p-1)(q-1))을 성립하는 정수 d가 필요하다. 여기서 mod는 나머지 연산이다. 위의 예제에서 e = 7 이고 (p -1)(q-1) = 300이기 때문에 d는 7d % 300 = 1을 통해 구한다. 연산의 방법은 300의 배수를 하나 이상 찾고 이 중, 7로 나누어 떨어지는 첫번째 숫자를 찾아내면 된다. 다시 말하면, 301, 601, 901 등이 가능한 값들이다. 이중 301은 7로 나누어 떨어지기 때문에(43*7은 301이다.) d는 43이다.

여기서 2쌍의 숫자들이 중요한데, RSA 모듈에 따르면 N = (p)(q)이고, 이 두 쌍의 숫자들이 이 식의 컴포넌트들이다. 첫번째 숫자쌍이 RSA 비밀 키(private key)인 (N,d)이고, 두 번째 숫자쌍이 RSA 공개키(public key)인 (N,e)이다. D는 RSA 비밀 지수(private exponent) (d=7)이고 e는 RSA 공개 지수(public exponent) (e=43)이다. 이미 알고 있는 공개 키는 공개하자. 그렇지만 비밀 키(특히 d)와 최초의 소인수들(p와 q)은 비밀로 유지해야 한다.

그렇다면 자바 프로그래밍 랭귀지가 RSA 구성의 어느 부분에서 쓰여지는 것일까? 이는 java.security 패키지를 통해 쓰여진다. 이 패키지를 이용하면 위에서 설명한 RSA 알고리즘에 필요한 쌍으로 이뤄진 키를 생성할 수 있다. 먼저 KeyPairGenerator의 인스턴스를 생성하고 그것을 비트형식의 원하는 키 사이즈로 초기화한다. 그리고 generateKeyPair()메소드를 호출하면 한 쌍의 RSA 키를 생성할 수 있다.

   KeyPairGenerator generator =
                   KeyPairGenerator.getInstance("RSA");
   generator.initialize(1024);
   KeyPair keyPair = generator.generateKeyPair();

이 알고리즘에서는 factory getInstance() 메소드에 스트링을 입력한다. 알고리즘이 인스톨된 제공자(provider)에 의해 지원되지 않으면 NoSuchAlgorithmException이 발생한다.

각각의 제공자는 반드시 디폴트 초기화를 공급하고 이를 문서화해야한다. 제공자 디폴트(provider default)가 사용자의 요구와 맞아 떨어지면, 중간 KeyPairGenerator 객체 (intermediate KeyPairGenerator object)를 저장할 필요가 없다. 한 줄의 코드로 키 쌍을 간단하게 생성할 수는 있지만 하나 이상의 키 쌍을 생성해야 한다면, KeyPairGenerator 객체를 재사용하는 것이 낫다. 왜냐하면 이는 새로운 KeyPairGenerator 객체를 매번 생성하는 것보다 훨씬 나은 퍼포먼스를 주기 때문이다.

스트링 RSA는 rsa, Rsa 혹은 어떤 형태이든지 상관이 없다. 다음과 같은 프로그램을 실행하면

   java AsymmetricKeyMaker RSA

출력값은 이하와 같다.

   SunJSSE RSA public key:
      public exponent:
        010001
      modulus:
        b24a9b5b ba01c0cd 65096370 0b5a1b92 08f8555e
        7c1b5017 ec444c58 422b4109
        59f2e15d 43714d92 031db66c 7f5d48cd 17ecd74c
        39b17be2 bf9677be d0a0f02d
        6b24aa14 ba827910 9b166847 8154a2fa 919e0a2a
        53a6e79e 7d2933d8 05fc023f
        bdc76eed aa306c5f 52ed3565 4b0ec8a7 12105637
        af11fa21 0e99fffa 8c658e6d

   SunJSSE RSA private CRT key:
      private exponent:
        78417240 9059965d f3843d99 d94e51c2 52628dd2
        490b731e 6fb2317c 66451e7c
        dc3ac25f 519a1ea4 198df4f9 817ebe17 f7c73c00
        a1f96082 348f9cfd 0b63421b
        7f45f131 c363475c c1b25f57 ee029f5e 0848ba74
        ba81b730 ac4c0135 ce46478c
        e462361a 650e3356 f9b7a0c4 b682557d 3655c052
        5e3554bd 970100bf 10dc1b51
      modulus:
        b24a9b5b ba01c0cd 65096370 0b5a1b92 08f8555e
        7c1b5017 ec444c58 422b4109
        59f2e15d 43714d92 031db66c 7f5d48cd 17ecd74c
        39b17be2 bf9677be d0a0f02d
        6b24aa14 ba827910 9b166847 8154a2fa 919e0a2a
        53a6e79e 7d2933d8 05fc023f
        bdc76eed aa306c5f 52ed3565 4b0ec8a7 12105637
        af11fa21 0e99fffa 8c658e6d
      public exponent:
        010001
      prime p:
        e768033e 21646824 7bd031a0 a2d9876d 79818f8f
        2d7a952e 559fd786 2993bd04
        7e4fdb56 f175d04b 003ae026 f6ab9e0b 2af4a8d7
        ffbe01eb 9b81c75f 0273e12b
      prime q:
        c53d78ab e6ab3e29 fd98d0a4 3e58ee48 45a366ac
        e94dbd60 ea24ffed 0c67c5fd
        3628ea74 88d1d1ad 58d7f067 20c1e3b3 db52adf3
        c421d88c 4c4127db d03592c7
      prime exponent p:
        e09942b4 76029755 f9da3ba0 d70edcf4 337fbdcf
        d0eb6e89 f74f5a07 7ca94947
        6835a805 3dfd047b 17310dc8 a39834a0 504400f1
        0ce6e5c4 413df83d 4e0b1cdb
      prime exponent q:
        829b8afd a1984168 c2d1df4e f32e2653 5b31b17a
        cc5ebb09 a2e26f4a 040def90
        15be104a ac92ebda 72db4308 b72b4ce1 bb58cb71
        80adbcdc 625e3ecb 92daf6df
      crt coefficient:
        4d8190c5 7730b729 00a8f1b4 ae526300 b22d3e7d
        d64df98a c1b19889 5240141b
        0e618ff4 be597979 95195c51 0866c142 30b37a86
        9f3ef519 a3ae6469 14075097

자바 프로그래밍이 처음이라면 위에서 적절하게 오버로딩된 toString() 메소드의 출력값을 주목할 필요가 있다. "SunJSSE RSA public key:"으로 시작하는 텍스트가 RSAPublicKey 클래스 내의 toString() 메소드를 호출한 결과값이다. 이는 e라고 불리는 공개 지수(public exponent)와 모듈러스(modulus) N으로 구성되어 있다. "SunJSSE RSA private key:"로 시작하는 텍스트는 RSAPrivateKey 클래스 내의 동일한 메소드를 호출한 결과이다. 이는 비밀 지수 d, 모듈러스 N, 공개 지수 e 뿐만 아니라 생성되는 소인수들에 대한 정보도 포함하고 있다. 만약 데이터를 암호화하고 있는 중이라면, 공개 키 값을 전송할 때 주의해야 한다. 하지만, 이 값들이 전송을 인증하는데 사용되는 중이라면, 다른 사람들이 파일을 조회 혹은 검증할 수 있도록 이를 공개로 해 놓아야 한다.

코드를 재실행하고 스트링 DSA 를 입력하면 공개 키와 비밀 키 모두에서 p, q 와g의 값을 찾을 수가 있다. y 값은 공개 키에서, x값은 비밀 키에서 제공된다. 하지만 알고리즘이 다르기 때문에 이러한 정보는 다른 방법으로 계산되고 공유되어야 한다.

그렇다면 암호화에서 이 키 쌍을 어떻게 사용할 것인가? RSA의 경우를 먼저 살펴보면, 암호화하고 싶은 텍스트를 정하고 그것을 모듈러스보다 작은 수 m으로 바꾼다. 이에 관해서는 후에 더 언급하도록 하겠다. 여기에서 크기가 큰 소인수를 선택하는 이유를 알 수 있는데, 이는 소인수의 곱이 암호화 될 수 있는 것들의 사이즈를 결정하기 때문이다. 예를 들면 m=2라고 가정하자. 그러면 사용자는 c=m^e (mod N)를 계산해서 암호화하기 시작한다. 바꾸어 말하자면, 암호화하는 수를 공개 지수의 거듭제곱까지 증가시키고 이를 모듈러스로 나눈 나머지를 구한다. 이 예에서 2^43 는 341의 배수보다 8이 더 크기 때문에 c = 8이라는 암호화된 메시지를 전송해야 한다.

복호화(decryption)는 비밀 키를 이용해서 프로세스를 반복함으로써 이뤄진다. c^d(mod N)를 이용하자. 예를 통해 살펴보면, 먼저 8^7 을 계산하고 이를 341으로 나눈다. 나머지를 구해보면 2라는 메시지를 받게 된다. 이것은 우연히 나온 값이 아니다. 이는 m^(e d) = m (mod N)를 나타내는 Fermat의 정리 애플리케이션을 따른 것이다. 보안을 위해서 각각의 파티는 다른 파티의 공개 키를 이용해서 암호화하게 된다.

RSA 알고리즘에 대한 정보는 RSA, DSA 알고리즘에 대한 정보는 DSA를 참고하기 바란다.

from http://kr.sun.com/developers/techtips/c2004_01_16.htm