성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
[정성태] "props[i].GetValue(props[i])" 코드에서 ...
[정성태] 저렇게 조각 코드 말고, 실제로 재현이 되는 예제 프로젝트를 압...
[정성태] Modules 창(Ctrl+Shift+U)을 띄워서, 해당 Op...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>C# - Rabin-Miller 소수 생성 방법을 이용하여 RSACryptoServiceProvider의 개인키를 직접 채워보자</h1> <p> <br /> 이전 글에서 <a target='tab' href='https://learn.microsoft.com/en-us/dotnet/api/system.security.cryptography.rsaparameters'>RSAParameters</a> 내의 P, Q, Modulus 값에 대해 알아봤는데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > RSAParameters와 System.Numerics.BigInteger 이야기 ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/1295'>http://www.sysnet.pe.kr/2/0/1295</a> </pre> <br /> P, Q의 값이 각각 64바이트(* 8 == 512비트) 소수로 설정되어 있는데, 그렇다면 실제로 이 값을 직접 구하려면 어떻게 해야 할까요? 혹시, 예전에 살펴본 소수 판정 코드를 이용하면 가능할까요? ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 소수 판정 및 소인수 분해 소스 코드 - C# ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/1255'>http://www.sysnet.pe.kr/2/0/1255</a> </pre> <br /> 불행히도 위의 방법은 64바이트 소수에 대해서는 사용할 수 없습니다. 이유는 매우 간단합니다. 단적인 예로, 4바이트 정수의 최대값(약 21억)으로 아무것도 하지 않는 for 루프를 돌려보는 시간을 재보면 이해가 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > // 9649ms == 약 10초 for (long i = 0; i < Int32.MaxValue; i++) { } </pre> <br /> i7 컴퓨터에서 21억번의 단순 루프를 도는데만 약 10초의 시간이 걸렸으니, 쉽게 8바이트 long.MaxValue 값으로 루프를 돈다면 어림잡아도 long.MaxValue / Int32.MaxValue * 10(초) / 60(초) / 60(분) == 11,930,464시간 == 497,102일 == 1,361년이 걸립니다.<br /> <br /> 소수 판정을 하는 IsPrime 함수를 보면,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; } </pre> <br /> 루프를 도는 수가, 대상 값의 Sqrt(target)에 대해서 짝수 제외하고 홀수만으로 +2 씩 증가하니 이것을 8바이트에 대해서만 해도 Sqrt(long.MaxValue) / 2 수의 루프가 "1,518,500,249"번 정도 됩니다. 21억을 도는데 10초가 걸렸으니 15억 정도는 가뿐히 해내겠지만, 문제는 P, Q 소수값이 64바이트라는 점입니다.<br /> <br /> 결과적으로, 해당 64바이트 값이 소수인지만 판정하는 것만으로 RSA 알고리즘을 사용한 암호화에 심각한 성능 문제를 야기시킬 수 있습니다.<br /> <br /> <hr style='width: 50%' /><br /> <br /> 그렇다면, 이 쯤에서 소수를 판정하는 다른 방법이 있지 않을까 하는 생각이 드는데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 공개키 암호알고리즘 ; <a target='tab' href='http://infosec.kut.ac.kr/sangjin/class/cryptoalgo2010-01/slide10.pdf'>http://infosec.kut.ac.kr/sangjin/class/cryptoalgo2010-01/slide10.pdf</a> </pre> <br /> 위의 문서를 보면 "Rabin-Miller 방법"에 대해서 소개하고 있습니다. 그리고 좀 더 검색해 보면, C# 소스 코드로 공개된 것을 찾을 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Miller-Rabin primality test ; <a target='tab' href='http://rosettacode.org/wiki/Miller-Rabin_primality_test#C.23'>http://rosettacode.org/wiki/Miller-Rabin_primality_test#C.23</a> </pre> <br /> 이를 이용하여 certainty 인자를 5로 해서 64바이트 소수를 구하는 코드는 다음과 같습니다. (위의 PDF 자료의 내용을 인용하자면, 합성수가 Rabin-Miller 시험을 5번 통과할 확률은 0.1% 이하라고 합니다.)<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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); <span style='color: blue; font-weight: bold'>if (p.IsProbablePrime(5) == true)</span> { break; } } } </pre> <br /> 가장 큰 숙제를 끝냈군요. ^^ 이제 RSAParameters의 나머지 값들을 채우는 것은 <a target='tab' href='https://learn.microsoft.com/en-us/dotnet/api/system.security.cryptography.rsaparameters'>RSAParameters Structure</a> 문서에 나온데로 적용해 주면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > D: the private exponent DP: d mod (p - 1) DQ: d mod (q - 1) Exponent: the public exponent Modulus: n == (p * q) </pre> <br /> 이 중에서, 문제는 개인키에 해당하는 "D" 값입니다. 다음의 조건을 만족하는 d 값을 구해야 하는데,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > d * e <img alt='rsa_net_1.png' src='/SysWebRes/bbs/rsa_net_1.png' /> 1 mod ((p - 1) * (q - 1)) </pre> <br /> e(the public exponent)값에 대해 무작위(또는 순차적으로) d값을 결정하면서 ((p - 1) * (q - 1)) 값에 대해 나머지 1이 나오는 경우를 찾으려면 한 세월이 걸립니다. 다행히, 이를 구하기 위해서 "확장 유클리드 함수"를 사용할 수 있는데, 이에 대해서는 다음의 문서를 참고하시면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > RSA 암호체계를 이해할 때 필수적인 것들은 ; <a target='tab' href='http://openness.tistory.com/attachment/491bd9a096adc9Z.doc'>http://openness.tistory.com/attachment/491bd9a096adc9Z.doc</a> </pre> <br /> 그리고 "확장 유클리드 함수"에 대해서는 지난번 글에서 C# 코드로 GetExtendedGcd라는 이름의 메서드로 작성해 둔 것이 있지요. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > "유클리드 호제법"과 "Bezout's identity" 구현 코드(C#) ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/1126'>http://www.sysnet.pe.kr/2/0/1126</a> </pre> <br /> 그런데, 문제가 하나 더 있습니다. 지난 글을 통해서도 살펴봤지만 d 값으로 음수(-)값이 나오는 경우가 있습니다. 예를 들어, GetExtendedGcd(23, 5)의 경우에 -9가 나오게 되는데요. d값은 0 < d < (p-1) * (q - 1)의 범위여야 하기 때문에 음수가 나와서는 안됩니다. 이 부분에서 많이 헤맸는데요.<br /> <br /> 다음의 글을 보고 나서야, 음수 값을 양수 값으로 자유롭게 고칠 수 있다는 사실을 알게 되었습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 공개키 암호화 - RSA정리 ; <a target='tab' href='http://woogistar.egloos.com/1097435'>http://woogistar.egloos.com/1097435</a> </pre> <br /> 정리해 보면, 23과 5에 대한 값으로 다음과 같이 2, -9의 쌍이 얻어지는데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 1 == 23 * 2 + 5 * (-9) </pre> <br /> 이 값을 아래와 같이 서로의 곱셈값으로 빼서 정리해 주면 마찬가지의 결과가 나오게 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 1 == 23 * -(5-2) + 5 * (23 - 9) </pre> <br /> 따라서, GetExtendedGcd(23, 5)에서 -9라는 음수값이 나온 경우에는 양수(==14)로 변환할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 5 * -9 <img alt='rsa_net_1.png' src='/SysWebRes/bbs/rsa_net_1.png' /> 1 mod 23 5 * 14 <img alt='rsa_net_1.png' src='/SysWebRes/bbs/rsa_net_1.png' /> 1 mod 23 </pre> <br /> <hr style='width: 50%' /><br /> <br /> 자, 이렇게 해서 D, P, Q, DP, DQ, Modulus 값을 모두 구할 수 있게 되었습니다. D 값을 구하기 위해 "public exponent" 값을 구해야 하는 문제가 있긴 한데, .NET Framework의 RSAParameters에서 사용하는 일반적인 "Exponent" 값이 65537 값이기 때문에 이를 그대로 사용할 수 있습니다.<br /> <br /> 그 외, InverseQ 값이 있긴 한데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > (InverseQ)(q) <img alt='rsa_net_1.png' src='/SysWebRes/bbs/rsa_net_1.png' /> 1 mod p </pre> <br /> 눈치채셨겠지만, D 값을 구하는 것과 마찬가지의 방법을 사용하면 됩니다. 따라서, 이것으로 <a target='tab' href='https://learn.microsoft.com/en-us/dotnet/api/system.security.cryptography.rsaparameters'>RSAParameters</a> 구조체를 채울 수 있는 모든 준비가 완료되었습니다.<br /> <br /> 본격적으로 RSAParameters 인스턴스에 값을 채우기 전에 마지막으로 알아둘 사항이 있습니다. <a target='tab' href='http://www.sysnet.pe.kr/2/0/1295'>"RSAParameters 와 System.Numerics.BigInteger 이야기"</a> 글에서도 알아봤지만, 바이트 배열이 Big Endian으로 기록되어야 한다는 것에 주의를 해야 합니다. 그래서, 다음과 같은 식으로 채워주고,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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); } </pre> <br /> 최종적으로, 이렇게 직접 채워준 RSAParameters 값을 RSACryptoServiceProvider에서 사용할 수 있도록 '가져오기' 작업을 할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(); rsa.ImportParameters(rsaParam); </pre> <br /> 이후부터는, 일반적인 RSACryptoServiceProvider 암호화 작업을 수행해 주시면 됩니다. <br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > RSACryptoServiceProvider 클래스 (System.Security.Cryptography) ; <a target='tab' href='https://learn.microsoft.com/ko-kr/dotnet/api/system.security.cryptography.rsacryptoserviceprovider'>https://learn.microsoft.com/ko-kr/dotnet/api/system.security.cryptography.rsacryptoserviceprovider</a> </pre> <br /> 위의 예제 코드에 나온대로 테스트를 해보면, 우리가 생성한 RSA 키를 가지고 아무런 이상없이 암호화/복호화 작업이 수행되는 것을 확인할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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)); </pre> <br /> <hr style='width: 50%' /><br /> <br /> 그 외, 2가지 정도의 언급을 해야 할 것 같습니다.<br /> <br /> 우선, 위에 설명한 데로만 테스트를 해보면 RSACryptoServiceProvider.ImportParameters에서 다음과 같은 오류가 발생하는 경우가 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <span style='color: blue; font-weight: bold'>System.Security.Cryptography.CryptographicException was unhandled Message=Bad Key.</span> 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: </pre> <br /> 이거 원인 찾는 데에도 ^^; 제법 시간이 걸렸는데요. RSA의 원래 규약인지는 모르겠지만 P, Q 소수값이 RSACryptoServiceProvider에서 사용되기 위해서는 한가지 규칙이 적용되어야 합니다. 다름아닌 크기인데요. 반드시 P 값이 더 커야만 "Bad Key." 예외가 발생하지 않습니다. 따라서, p, q 값을 생성한 후 다음과 같은 후처리를 해주어야 합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > BigInteger p, q; ProducePQ(64, out p, certainty); ProducePQ(64, out q, certainty); <span style='color: blue; font-weight: bold'>if (q > p) { BigInteger temp = q; q = p; p = temp; }</span> </pre> <br /> 역시, 본문에서 설명한 데로만 코드를 구성했을 경우 ImportParameters 메서드에서 발생할 수 있는 또 한가지의 예외가 있는데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <span style='color: blue; font-weight: bold'>System.Security.Cryptography.CryptographicException was unhandled Message=Bad Data.</span> 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: </pre> <br /> "Bad Data." 오류는 p * q == Modulus나, d 값 등이 128바이트가 아닌 127바이트이거나, DP, DQ 값이 63바이트가 되는 경우에 발생할 수 있습니다. 왜냐하면, p 와 q가 64바이트이긴 하지만 생성된 난수에 따라서 그 곱이 128바이트의 정수가 안 나올 수도 있기 때문입니다.<br /> <br /> 이런 것을 보정하기 위해서 Big Endian으로 변환하는 코드를 다음과 같이 변경해 주어야 합니다. (넵... 맞습니다. 아래의 코드는 임시 방편입니다. 이 글의 주제는 RSA 개인키를 채우는 것이므로.)<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > private static void ToBigEndian(BigInteger bytes, ref byte[] target) { List<byte> list = new List<byte>(); list.AddRange(bytes.ToByteArray()); <span style='color: blue; font-weight: bold'> if (list.Count != 3 && list.Count != 64 && list.Count != 128) { if (list.Count == 127 || list.Count == 63) { list.Add(0); } }</span> list.Reverse(); target = new byte[list.Count]; Array.Copy(list.ToArray(), target, list.Count); } </pre> <br /> 이 정도 지식이면... 적어도 다른 언어/플랫폼에서 사용되는 RSA 키값을 닷넷과 호환하는데 별다른 어려움없이 가능할 것입니다.<br /> <br /> 일단, <a target='tab' href='https://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=732&boardid=331301885'>위의 모든 내용을 반영한 코드를 실어두었으므로 참고하실 분은 다운로드</a> 받아서 테스트 해보세요. ^^<br /> </p><br /> <br /> <br /> <br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
3990
(왼쪽의 숫자를 입력해야 합니다.)