C# - BigInteger 타입이 byte 배열로 직렬화하는 방식
x64 환경의 경우 Little Endian 방식으로 메모리에 저장되는데요, 예를 들어 32764를 보관한 경우를 보면,
int a = 32764; // 16진수 0x00007ffc
byte[] bytes = BitConverter.GetBytes(a);
Console.WriteLine(BitConverter.ToString(bytes)); // 출력 결과: FC-7F-00-00
저렇게, 0x00007ffc 값을 거꾸로 fc-7f-00-00으로 저장해서 다소 혼란스러울 수 있습니다. (어쩔 수 없습니다. Little Endian 시스템을 다루려면 익숙해져야 합니다. ^^;)
사실 int, long과 같은 유형은 시스템의 Endian 지원에 따라 달라질 수 있습니다. 즉, 위의 결과를 (Little Endian이 아닌) Big Endian으로 설정한 ARM64 환경에서 실행하면 00-00-7F-FC가 출력됩니다. (ARM 아키텍처는 원하는 Endian을 선택할 수 있는 Bi-Endian을 지원합니다.)
그렇다면 BigInteger는 어떨까요? Hardware 적으로 CPU가 Word 단위로 4칙 연산을 처리하는 것과는 달리, BigInteger는 소프트웨어적으로 처리하기 때문에 Endian에 자유로울 수 있습니다. 물론, 자유로울 순 있지만 어쨌든 둘 중의 하나는 선택해야만 코드가 복잡해지지 않습니다.
그럼 소스코드와 함께 살펴볼까요? ^^
우선, 내부 자료 구조는 딱 2개인데요,
// https://github.com/microsoft/referencesource/blob/master/System.Numerics/System/Numerics/BigInteger.cs
internal readonly int _sign; // Do not rename (binary serialization)
internal readonly uint[]? _bits; // Do not rename (binary serialization)
_sign은 부호를 위한 변수로써, 양수인 경우 1, 음수인 경우에는 -1을 보관하지만 int32.MaxValue까지의 값을 직접 담는 용도로도 사용합니다. (즉, 0x7FFFFFFF까지는 _sign에 보관하고, 그 이상은 부호값만 _sign에 보관하고 숫자는 _bits에 보관합니다.)
System.Numerics.BigInteger a = 0x7FFFFFFF;
Print(a);
// _sign: 2147483647 (0x7fffffff)
// _bits: (null)
System.Numerics.BigInteger a = (long)0x7FFFFFFF + 1; // 0x80000000
Print(a);
// _sign: 1 (0x1)
// _bits[0]: 00-00-00-80
// -------------------------------------------
static Type _biType = typeof(BigInteger);
private static void Print(System.Numerics.BigInteger number)
{
object? objSign = _biType.GetField("_sign", BindingFlags.NonPublic | BindingFlags.Instance)?.GetValue(number);
object? objData = _biType.GetField("_bits", BindingFlags.NonPublic | BindingFlags.Instance)?.GetValue(number);
if (objSign == null || objData == null)
{
throw new Exception("Invalid BigInteger");
}
int sign = (int)objSign;
uint[] data = (uint[])objData;
Console.WriteLine($"_sign: {sign}");
StringBuilder sb = new StringBuilder();
foreach (uint item in data)
{
byte[] buffer = BitConverter.GetBytes(item);
sb.Append(BitConverter.ToString(buffer));
}
Console.WriteLine($"_data: {sb.ToString()}");
}
사실, 개인적으로 BigInteger의 내부 자료 구조를 byte[]로 예상했었습니다. ^^ 아마도 성능상의 이유일 듯한데 실제로는 uint[]로 처리하고 있으며, 이로 인해 개별 4바이트마다는 Little Endian으로 보관되지만, 전체적인 배열에 대한 정렬은 Big Endian 형식이라고 보면 됩니다.
BigInteger는 내부의 값을 byte[] 배열로 출력할 수 있는 ToByteArray 메서드를 제공하는데요, 재미있는 건 숫자 앞에 0이 붙어 있는 경우 (쓸모없기 때문에) 0에 해당하는 바이트는 제거합니다.
int value = 0x00_00_00_05;
Console.WriteLine(BitConverter.ToString(BitConverter.GetBytes(value)));
// 출력 결과: 05-00-00-00
System.Numerics.BigInteger a = value;
Console.WriteLine(BitConverter.ToString(a.ToByteArray()));
// 출력 결과: 05
이것은 값을 보관할 때도 마찬가지입니다. 설령, "00000000_00000000_00000000_00000005"와 같은 값을 대입해도 앞의 0을 모두 제거한 마지막 5값만 처리하는 식입니다.
System.Numerics.BigInteger b = BigInteger.Parse("00000000000000000000000000000005");
// _sign: 5 (0x5)
// _bits: (null)
그리고,
ToByteArray는 전체 값을 기본적으로 Little Endian 방식으로 반환합니다. (
Big Endian으로 반환하는 오버로드를 제공합니다.)
System.Numerics.BigInteger a = BigInteger.Parse("00002F0000000000000001", NumberStyles.HexNumber);
byte[] bytes = a.ToByteArray();
Console.WriteLine(BitConverter.ToString(bytes));
// 출력 결과: 01-00-00-00-00-00-00-00-2F
위의 예제에서는 의미 있는 숫자가 2F부터 시작하므로 Little Endian 방식으로 01-....-2F로 출력하고 있습니다. 그렇다면, ToByteArray의 반환값으로 2F 다음에 00이 붙는 경우가 있을까요?
Little Endian 방식으로 보관되는 것이 맞는다면, 상위의 의미 없는 0은 모두 제거하므로 2F 이후 00이 붙는 경우는 없습니다. 하지만, 실제로 몇 가지 숫자를 다루다 보면 00이 붙는 경우가 있습니다. 도대체 왜 이런 경우가 발생할까요? ^^
BigInteger의 표현 범위는 음수/양수를 모두 포함합니다. 이를 위해 BigInteger는 _sign, _bits라는 2개의 필드를 내부에 유지하고 있는데요, 그렇다면 직렬화 시 분명히 2개의 필드값을 각각 구분해 반환해야만 합니다.
그런데, 위에서 예를 든 ToByteArray는 음수든 양수든 모두 byte[] 하나로 직렬화해서 반환하고 있는데요, 엄밀히 일반적인 바이트 배열이라면 음수/양수를 구분할 수 없는 문제가 발생합니다. 예를 들어 볼까요? ^^
일례로 [0x04, 0x80] 배열은,
// 16비트 부호 있는 정수인 경우,
0x8004 (16진수)
0b10_00_00_00_00_00_01_00 (2진수)
가장 상위 비트가 1이므로 음수로 해석하면 -32764가 됩니다. 하지만 부호 없는 정수로 해석하면, 즉 최상위 1비트를 부호가 아닌 숫자 1로 해석하면 32772 값이 됩니다.
32772 직렬화 == [0x04, 0x80]
-32764 직렬화 == [0x04, 0x80]
바로 이런 경우를 구분하기 위해, BigInteger는 부호 비트를 위한 특별한 작업을 합니다.
가령, 가장 상위 비트가 부호가 아닌 숫자로 해석해야 한다면 [0x04, 0x80] 이후에 0을 하나 더 추가해 [0x04, 0x08, 0x00]으로 직렬화하는 것입니다. 반대로 최상위 비트가 부호가 맞는다면 그대로 [0x04, 0x80]으로 직렬화합니다.
// 최상위 비트의 부호 판단을 위한 바이트 추가
32772 직렬화 == [0x04, 0x80, 0x00]
-32764 직렬화 == [0x04, 0x80]
정리하면, Little Endian 방식의 경우 마지막 바이트의 값이 (최상위 비트를 1로 만들 수 있는) 0x80 이상의 값이면서 양수인 경우에는 그다음 바이트에 반드시 0x00을 추가해야만 합니다.
위와 같은 직렬화 규칙이 바로
RFC 문서에 정의된 mpint에 해당합니다. 단지, mpint는 바이트 배열에 대해 Big-Endian을 사용하기 때문에 규칙이 살짝 바뀝니다.
// Little Endian인 경우
마지막 바이트의 값이 (최상위 비트를 1로 만들 수 있는) 0x80 이상의 값이면서 양수인 경우에는 그다음 바이트에 반드시 0x00을 추가
// Big Endian인 경우
첫 바이트의 값이 (최상위 비트를 1로 만들 수 있는) 0x80 이상의 값이면서 양수인 경우에는, 선행 바이트 위치에 반드시 0x00을 추가
따라서 32772 값을 mpint 형식으로 직렬화하면, [0x00, 0x80, 0x04]가 됩니다.
{
System.Numerics.BigInteger c = 32772;
byte[] bytes = c.ToByteArray();
Console.WriteLine(BitConverter.ToString(bytes)); // 출력 결과: 04-80-00
bytes = c.ToByteArray(false, true);
Console.WriteLine(BitConverter.ToString(bytes)); // 출력 결과: 00-80-04
}
이렇게 정리하고 보니, 예전에 멋모르고 썼던 글이 다시 재조명되는군요. ^^
RSAParameters와 System.Numerics.BigInteger 이야기
; https://www.sysnet.pe.kr/2/0/1295#code_1
그때 당시에 P, Q 값의 곱인 Modulus가 BigInteger로 계산한 값과 다르게 나오는 경우를 봤는데요,
using System.Numerics;
using System.Security.Cryptography;
namespace ConsoleApp1;
internal class Program
{
static void Main(string[] args)
{
while (true)
{
RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();
Console.WriteLine(rsa.KeySize); // 1024
System.Security.Cryptography.RSAParameters rsaParam = rsa.ExportParameters(true);
Array.Reverse(rsaParam.P);
Array.Reverse(rsaParam.Q);
BigInteger p = new BigInteger(rsaParam.P);
BigInteger q = new BigInteger(rsaParam.Q);
BigInteger calcModulus = p * q;
BigInteger expectModulus = new BigInteger(rsaParam.Modulus);
if (calcModulus != expectModulus)
{
Console.WriteLine($"p == {p}");
Console.WriteLine($"q == {q}");
Console.WriteLine();
Console.WriteLine(calcModulus);
Console.WriteLine();
Console.WriteLine(expectModulus);
break;
}
}
}
}
/* 출력 결과:
p == -771917078019141136720821347241726750410668581599848232475939881531365305238903039710472242880856023043474475696673552382234385226461909061943847158847249
q == -591552401089870086451779731939856898468915714017037171853135244546626051984434467004793626620507154397124506077500055202777164241004896893341338604830729
456629400944499517920256548843421345479633492848402466316248615674337834002368611470981289962455710018580933739939019651614675258155992766629499740794613890398409156492394043268999773886652903619259097246237701510722750217266105556801739881324014598403045910712719835856816598740575550407193429322412314521
-71760519326347099437607946087500320466602787969235384810481655231838696376679836963992543848243052540266002283800387486565243507080800707652861837346519412815792861476233723478604245893243322799439751983297058473801237211178568579367290531051175187090784475576197040348213312330092316434328195812399178605082
*/
RSACryptoServiceProvider가 내부적으로 생성한 RSA KeySize == 1024인 경우인데요, 따라서 P, Q 바이트 배열의 크기는 각각 64바이트입니다. (64 * 8 == 512 * 2 == 1024)
그런데, 위의 경우 P와 Q 값이 음수를 나타내고 있는데, 사실 RSA 키는 양수로 표현돼야 합니다. 그렇다면 직렬화 시 "0x00"이 추가돼 P, Q 배열의 크기는 각각 65바이트여야 하는데, 무조건 64바이트로 표현하고 있습니다. 왜냐하면, RSA 키 자체가 처음부터
표준에 양수라고 명시했으므로,
n the RSA modulus, a positive integer
d the RSA private exponent, a positive integer
p the first factor, a positive integer
q the second factor, a positive integer
dP the first factor's CRT exponent, a positive integer
dQ the second factor's CRT exponent, a positive integer
qInv the (first) CRT coefficient, a positive integer
r_i the i-th factor, a positive integer
d_i the i-th factor's CRT exponent, a positive integer
t_i the i-th factor's CRT coefficient, a positive integer
굳이 "0x00" 바이트 처리를 하지 않아도 되는 것입니다. 그래서 예전 글에서는 이런 문제를 해결하기 위해 rsaParam.P, rsaParam.Q 값 (BigEndian이므로) 앞에
0x00을 무조건 추가한 다음 BigInteger로 변환해 정상적으로 처리할 수 있었습니다.
하지만, 어느새 세월은 흘러 .NET Core가 나오면서 BigInteger의 생성자에 signed와 endian을 지정할 수 있는 오버로드가 추가됐습니다. ^^
BigInteger(ReadOnlySpan, Boolean, Boolean)
; https://learn.microsoft.com/en-us/dotnet/api/system.numerics.biginteger.-ctor?view=net-8.0#system-numerics-biginteger-ctor(system-readonlyspan((system-byte))-system-boolean-system-boolean)
따라서, 새로운 생성자를 이용해 위의 코드를 다시 작성하면 이렇게 간단하게 해결할 수 있습니다.
RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();
Console.WriteLine(rsa.KeySize); // 1024
System.Security.Cryptography.RSAParameters rsaParam = rsa.ExportParameters(true);
BigInteger p = new BigInteger(rsaParam.P, true, true);
BigInteger q = new BigInteger(rsaParam.Q, isUnsigned: true, isBigEndian: true);
BigInteger calcModulus = p * q;
BigInteger expectModulus = new BigInteger(rsaParam.Modulus, true, true);
Debug.Assert(calcModulus == expectModulus); // 언제나 성공!
휴... 이 정도면 대충 정리가 끝난 것 같습니다. ^^
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]