C# - Rabin-Miller 소수 생성 방법을 이용하여 RSACryptoServiceProvider의 개인키를 직접 채워보자
이전 글에서 RSAParameters 내의 P, Q, Modulus 값에 대해 알아봤는데요.
RSAParameters와 System.Numerics.BigInteger 이야기
; https://www.sysnet.pe.kr/2/0/1295
P, Q의 값이 각각 64바이트(* 8 == 512비트) 소수로 설정되어 있는데, 그렇다면 실제로 이 값을 직접 구하려면 어떻게 해야 할까요? 혹시, 예전에 살펴본 소수 판정 코드를 이용하면 가능할까요? ^^
소수 판정 및 소인수 분해 소스 코드 - C#
; https://www.sysnet.pe.kr/2/0/1255
불행히도 위의 방법은 64바이트 소수에 대해서는 사용할 수 없습니다. 이유는 매우 간단합니다. 단적인 예로, 4바이트 정수의 최대값(약 21억)으로 아무것도 하지 않는 for 루프를 돌려보는 시간을 재보면 이해가 됩니다.
// 9649ms == 약 10초
for (long i = 0; i < Int32.MaxValue; i++) { }
i7 컴퓨터에서 21억번의 단순 루프를 도는데만 약 10초의 시간이 걸렸으니, 쉽게 8바이트 long.MaxValue 값으로 루프를 돈다면 어림잡아도 long.MaxValue / Int32.MaxValue * 10(초) / 60(초) / 60(분) == 11,930,464시간 == 497,102일 == 1,361년이 걸립니다.
소수 판정을 하는 IsPrime 함수를 보면,
public static bool IsPrime(long candidate)
{
if ((candidate & 1) == 0) // 홀수/짝수 판별은 쉽게 끝나지만,
{
if (candidate == 2)
{
return true;
}
else
{
return false;
}
}
for (int i = 3; (i * i) <= candidate; i += 2) // 3 부터 +2 씩 증가하는 루프
{
if ((candidate % i) == 0)
{
return false;
}
}
return candidate != 1;
}
루프를 도는 수가, 대상 값의 Sqrt(target)에 대해서 짝수 제외하고 홀수만으로 +2 씩 증가하니 이것을 8바이트에 대해서만 해도 Sqrt(long.MaxValue) / 2 수의 루프가 "1,518,500,249"번 정도 됩니다. 21억을 도는데 10초가 걸렸으니 15억 정도는 가뿐히 해내겠지만, 문제는 P, Q 소수값이 64바이트라는 점입니다.
결과적으로, 해당 64바이트 값이 소수인지만 판정하는 것만으로 RSA 알고리즘을 사용한 암호화에 심각한 성능 문제를 야기시킬 수 있습니다.
그렇다면, 이 쯤에서 소수를 판정하는 다른 방법이 있지 않을까 하는 생각이 드는데요.
공개키 암호알고리즘
; http://infosec.kut.ac.kr/sangjin/class/cryptoalgo2010-01/slide10.pdf
위의 문서를 보면 "Rabin-Miller 방법"에 대해서 소개하고 있습니다. 그리고 좀 더 검색해 보면, C# 소스 코드로 공개된 것을 찾을 수 있습니다.
Miller-Rabin primality test
; http://rosettacode.org/wiki/Miller-Rabin_primality_test#C.23
이를 이용하여 certainty 인자를 5로 해서 64바이트 소수를 구하는 코드는 다음과 같습니다. (위의 PDF 자료의 내용을 인용하자면, 합성수가 Rabin-Miller 시험을 5번 통과할 확률은 0.1% 이하라고 합니다.)
BigInteger p, q;
ProducePQ(64, out p);
ProducePQ(64, out q);
private static void ProducePQ(int bytes, out BigInteger p)
{
Random rand = new Random();
byte[] pRand = new byte[bytes];
while (true)
{
rand.NextBytes(pRand);
p = new BigInteger(pRand);
if (p.IsProbablePrime(5) == true)
{
break;
}
}
}
가장 큰 숙제를 끝냈군요. ^^ 이제 RSAParameters의 나머지 값들을 채우는 것은
RSAParameters Structure 문서에 나온데로 적용해 주면 됩니다.
D: the private exponent
DP: d mod (p - 1)
DQ: d mod (q - 1)
Exponent: the public exponent
Modulus: n == (p * q)
이 중에서, 문제는 개인키에 해당하는 "D" 값입니다. 다음의 조건을 만족하는 d 값을 구해야 하는데,
d * e 
1 mod ((p - 1) * (q - 1))
e(the public exponent)값에 대해 무작위(또는 순차적으로) d값을 결정하면서 ((p - 1) * (q - 1)) 값에 대해 나머지 1이 나오는 경우를 찾으려면 한 세월이 걸립니다. 다행히, 이를 구하기 위해서 "확장 유클리드 함수"를 사용할 수 있는데, 이에 대해서는 다음의 문서를 참고하시면 됩니다.
RSA 암호체계를 이해할 때 필수적인 것들은
; http://openness.tistory.com/attachment/491bd9a096adc9Z.doc
그리고 "확장 유클리드 함수"에 대해서는 지난번 글에서 C# 코드로 GetExtendedGcd라는 이름의 메서드로 작성해 둔 것이 있지요. ^^
"유클리드 호제법"과 "Bezout's identity" 구현 코드(C#)
; https://www.sysnet.pe.kr/2/0/1126
그런데, 문제가 하나 더 있습니다. 지난 글을 통해서도 살펴봤지만 d 값으로 음수(-)값이 나오는 경우가 있습니다. 예를 들어, GetExtendedGcd(23, 5)의 경우에 -9가 나오게 되는데요. d값은 0 < d < (p-1) * (q - 1)의 범위여야 하기 때문에 음수가 나와서는 안됩니다. 이 부분에서 많이 헤맸는데요.
다음의 글을 보고 나서야, 음수 값을 양수 값으로 자유롭게 고칠 수 있다는 사실을 알게 되었습니다.
공개키 암호화 - RSA정리
; http://woogistar.egloos.com/1097435
정리해 보면, 23과 5에 대한 값으로 다음과 같이 2, -9의 쌍이 얻어지는데요.
1 == 23 * 2 + 5 * (-9)
이 값을 아래와 같이 서로의 곱셈값으로 빼서 정리해 주면 마찬가지의 결과가 나오게 됩니다.
1 == 23 * -(5-2) + 5 * (23 - 9)
따라서, GetExtendedGcd(23, 5)에서 -9라는 음수값이 나온 경우에는 양수(==14)로 변환할 수 있습니다.
5 * -9 1 mod 23
5 * 14 1 mod 23
자, 이렇게 해서 D, P, Q, DP, DQ, Modulus 값을 모두 구할 수 있게 되었습니다. D 값을 구하기 위해 "public exponent" 값을 구해야 하는 문제가 있긴 한데, .NET Framework의 RSAParameters에서 사용하는 일반적인 "Exponent" 값이 65537 값이기 때문에 이를 그대로 사용할 수 있습니다.
그 외, InverseQ 값이 있긴 한데요.
(InverseQ)(q) 1 mod p
눈치채셨겠지만, D 값을 구하는 것과 마찬가지의 방법을 사용하면 됩니다. 따라서, 이것으로
RSAParameters 구조체를 채울 수 있는 모든 준비가 완료되었습니다.
본격적으로 RSAParameters 인스턴스에 값을 채우기 전에 마지막으로 알아둘 사항이 있습니다.
"RSAParameters 와 System.Numerics.BigInteger 이야기" 글에서도 알아봤지만, 바이트 배열이 Big Endian으로 기록되어야 한다는 것에 주의를 해야 합니다. 그래서, 다음과 같은 식으로 채워주고,
RSAParameters rsaParam = new RSAParameters();
ToBigEndian(d, ref rsaParam.D);
ToBigEndian(p, ref rsaParam.P);
ToBigEndian(q, ref rsaParam.Q);
ToBigEndian(dp, ref rsaParam.DP);
ToBigEndian(dq, ref rsaParam.DQ);
ToBigEndian(inverseQ, ref rsaParam.InverseQ);
ToBigEndian(n, ref rsaParam.Modulus);
ToBigEndian(publicExponent, ref rsaParam.Exponent);
private static void ToBigEndian(BigInteger bytes, ref byte[] target)
{
byte[] contents = bytes.ToByteArray();
Array.Reverse(contents);
target = new byte[contents.Length];
Array.Copy(contents, target, contents.Length);
}
최종적으로, 이렇게 직접 채워준 RSAParameters 값을 RSACryptoServiceProvider에서 사용할 수 있도록 '가져오기' 작업을 할 수 있습니다.
RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();
rsa.ImportParameters(rsaParam);
이후부터는, 일반적인 RSACryptoServiceProvider 암호화 작업을 수행해 주시면 됩니다.
RSACryptoServiceProvider 클래스 (System.Security.Cryptography)
; https://learn.microsoft.com/ko-kr/dotnet/api/system.security.cryptography.rsacryptoserviceprovider
위의 예제 코드에 나온대로 테스트를 해보면, 우리가 생성한 RSA 키를 가지고 아무런 이상없이 암호화/복호화 작업이 수행되는 것을 확인할 수 있습니다.
byte[] dataToEncrypt = ByteConverter.GetBytes("Data to Encrypt");
byte[] encryptedData;
byte[] decryptedData;
encryptedData = RSAEncrypt(dataToEncrypt, rsa.ExportParameters(false), false);
decryptedData = RSADecrypt(encryptedData, rsa.ExportParameters(true), false);
Console.WriteLine("Decrypted plaintext: {0}", ByteConverter.GetString(decryptedData));
그 외, 2가지 정도의 언급을 해야 할 것 같습니다.
우선, 위에 설명한 데로만 테스트를 해보면 RSACryptoServiceProvider.ImportParameters에서 다음과 같은 오류가 발생하는 경우가 있습니다.
System.Security.Cryptography.CryptographicException was unhandled
Message=Bad Key.
Source=mscorlib
StackTrace:
at System.Security.Cryptography.CryptographicException.ThrowCryptographicException(Int32 hr)
at System.Security.Cryptography.Utils._ImportKey(SafeProvHandle hCSP, Int32 keyNumber, CspProviderFlags flags, Object cspObject, SafeKeyHandle& hKey)
at System.Security.Cryptography.RSACryptoServiceProvider.ImportParameters(RSAParameters parameters)
at producePrime.Program.FillRSA(Int32 certainty) in D:\...\Program.cs:line 147
at producePrime.Program.Main(String[] args) in D:\...\Program.cs:line 16
InnerException:
이거 원인 찾는 데에도 ^^; 제법 시간이 걸렸는데요. RSA의 원래 규약인지는 모르겠지만 P, Q 소수값이 RSACryptoServiceProvider에서 사용되기 위해서는 한가지 규칙이 적용되어야 합니다. 다름아닌 크기인데요. 반드시 P 값이 더 커야만 "Bad Key." 예외가 발생하지 않습니다. 따라서, p, q 값을 생성한 후 다음과 같은 후처리를 해주어야 합니다.
BigInteger p, q;
ProducePQ(64, out p, certainty);
ProducePQ(64, out q, certainty);
if (q > p)
{
BigInteger temp = q;
q = p;
p = temp;
}
역시, 본문에서 설명한 데로만 코드를 구성했을 경우 ImportParameters 메서드에서 발생할 수 있는 또 한가지의 예외가 있는데요.
System.Security.Cryptography.CryptographicException was unhandled
Message=Bad Data.
Source=mscorlib
StackTrace:
at System.Security.Cryptography.CryptographicException.ThrowCryptographicException(Int32 hr)
at System.Security.Cryptography.Utils._ImportKey(SafeProvHandle hCSP, Int32 keyNumber, CspProviderFlags flags, Object cspObject, SafeKeyHandle& hKey)
at System.Security.Cryptography.RSACryptoServiceProvider.ImportParameters(RSAParameters parameters)
at producePrime.Program.FillRSA(Int32 certainty) in D:\...\Program.cs:line 147
at producePrime.Program.Main(String[] args) in D:\...\Program.cs:line 16
InnerException:
"Bad Data." 오류는 p * q == Modulus나, d 값 등이 128바이트가 아닌 127바이트이거나, DP, DQ 값이 63바이트가 되는 경우에 발생할 수 있습니다. 왜냐하면, p 와 q가 64바이트이긴 하지만 생성된 난수에 따라서 그 곱이 128바이트의 정수가 안 나올 수도 있기 때문입니다.
이런 것을 보정하기 위해서 Big Endian으로 변환하는 코드를 다음과 같이 변경해 주어야 합니다. (넵... 맞습니다. 아래의 코드는 임시 방편입니다. 이 글의 주제는 RSA 개인키를 채우는 것이므로.)
private static void ToBigEndian(BigInteger bytes, ref byte[] target)
{
List<byte> list = new List<byte>();
list.AddRange(bytes.ToByteArray());
if (list.Count != 3 && list.Count != 64 && list.Count != 128)
{
if (list.Count == 127 || list.Count == 63)
{
list.Add(0);
}
}
list.Reverse();
target = new byte[list.Count];
Array.Copy(list.ToArray(), target, list.Count);
}
이 정도 지식이면... 적어도 다른 언어/플랫폼에서 사용되는 RSA 키값을 닷넷과 호환하는데 별다른 어려움없이 가능할 것입니다.
일단,
위의 모든 내용을 반영한 코드를 실어두었으므로 참고하실 분은 다운로드 받아서 테스트 해보세요. ^^
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]