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 키값을 닷넷과 호환하는데 별다른 어려움없이 가능할 것입니다.
일단,
위의 모든 내용을 반영한 코드를 실어두었으므로 참고하실 분은 다운로드 받아서 테스트 해보세요. ^^
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]