C#中BigInteger数组与byte数组互转及解密还原问题

我用下面的代码把BigInteger数组转成了byte数组：

var ciphertext = new BigInteger[ciphertextBlocks];
...
byte[] ciphertextBytes = ciphertext.SelectMany(c => c.ToByteArray()).ToArray(); 

现在想还原出原始的BigInteger数组，但转换时每个BigInteger的长度信息丢失了，看起来没法实现。

我知道这可能是个XY问题，我正在实现一个Merkle-Hellman背包密码系统的简易加解密程序。
我清楚不推荐自己实现加密算法，这只是用于学习目的。

因为加密输出通常用byte[]表示，所以我在Encrypt()方法里把生成的密文（BigInteger[]）转成了byte[]。但在Decrypt()方法里，我需要访问原始的BigInteger[]数组来逐个解密每个BigInteger，有没有办法做到？

如果是long这类固定大小的基础类型，我可以这么做：

long[] cipherTextInt = new long[ciphertext.Length / sizeof(long)];
Buffer.BlockCopy(ciphertext, 0, cipherTextInt, 0, ciphertext.Length);

但BigInteger的大小是不固定的，该怎么处理？

附完整的KnapsackCryptosystem类代码：

public class KnapsackCryptosystem
{
    const int BitsPerByte = 8;
    
    public PublicKeyInfo PublicKey { get; }

    private PrivateKeyInfo PrivateKey { get; }

    public byte[] Encrypt(byte[] plaintext)
    {

        var plaintextBits = new BitArray(plaintext);
        var sequence = PublicKey.Sequence;
        
        // Calculate number of ciphertext blocks:
        // Dividing the length of the sequence by the bit length of the plaintext gives
        // the number of ciphertext blocks. If the plaintext bit length is not a multiple of 
        // the sequence length (remainder != 0), an extra block is required.
        var (quotient, remainder) = Math.DivRem(plaintextBits.Count, sequence.Count);
        var ciphertextBlocks = quotient + (remainder == 0 ? 0 : 1);

        // Create a BigInteger array to hold the ciphertext integers
        var ciphertext = new BigInteger[ciphertextBlocks];

        // Apply the sequence to each plaintext block
        for (int i = 0; i < ciphertextBlocks; i++)
        {
            for (int j = 0; j < sequence.Count; j++)
            {
                // Calculate the end index of the current block
                int endIndex = (i + 1) * sequence.Count;
                // Calculate the index of the jth bit from the end; 
                int bitIndex = end - j - 1;

                try
                {
                    var bit = plaintextBits[bitIndex];
                    //Console.WriteLine($"j={j} : idx={rIndex} : bit={(bit ? 1 : 0)} | ");
                    Console.WriteLine($"j={j} : idx={index} : bit={(bit ? 1 : 0)} : ");
                    if (bit)
                    {
                        // Add the jth element to the ith ciphertext block if the bit is set
                        Console.WriteLine($"+{sequence[j]} .");
                        ciphertext[i] += sequence[j];
                    }
                }
                catch (ArgumentOutOfRangeException)
                {
                    // thrown at the last block when the sequence length exceeds the last plaintext block
                    Console.WriteLine(nameof(ArgumentOutOfRangeException) + " " + index);
                    break;
                }
            }
            Console.WriteLine();
        }
        Console.WriteLine("Ciphertext Elements:");
        Array.ForEach(ciphertext, x => Console.WriteLine(x));

        // Convert the BigInteger[] array to byte[]
        var ciphertextBytes = ciphertext.SelectMany(c => c.ToByteArray()).ToArray(); 
        return ciphertextBytes;
    }


    public byte[] Decrypt(byte[] ciphertext)
    {
        var sequence = PrivateKey.Sequence;
        int wInverse = ModularArithmetic.MultiplicativeInverse(PrivateKey.W, PrivateKey.M);
        Console.WriteLine($"wInverse: {wInverse}");

        // RESTORE BigInteger[] FROM byte[] ciphertext. How to achieve this?
        // cipherTextInts is the restored BigInteger array containing the ciphertext for each block
        var ciphertextInts = BACK_TO_BIG_INTEGER_ARRAY(ciphertext);
        var plaintextBits = new BitArray(<UNKNOWN_LENGTH>);


        for (int i = 0; i < ciphertextInts.Length; i++)
        {
            var ciphertextElement = (wInverse * ciphertextInts[i]) % PrivateKey.M;

            // Solve the subset sum problem
            for (int j = PrivateKey.Sequence.Count - 1; j >= 0; j--)
            {
                if (PrivateKey.Sequence[j] <= ciphertextElement)
                {
                    // Calculate the end index of the current block
                    int endIndex = (i + 1) * sequence.Count;
                    // Calculate the index of the jth bit from the end; 
                    int bitIndex = end - j - 1;

                    plaintextBits[bitIndex] = true;
                    ciphertextElement -= PrivateKey.Sequence[j];
                    //Console.WriteLine($"    Minus {PrivateKey.Sequence[j]}. element: {ciphertextElement}");
                }
            }
        }

        // Copy BitArray data to byte[] array and return
        var (quotient1, remainder1) = Math.DivRem(plaintextBits.Length, BitsPerByte);
        byte[] bytes = new byte[quotient1 + (remainder1 == 0 ? 0 : 1)];
        plaintextBits.CopyTo(bytes, 0);
        return bytes;
    }


    public static KnapsackCryptosystem Create(
        IReadOnlyList<int> sequence, int m, int w)
    {
        if (sequence.Count == 0)
        {
            throw new ArgumentException(
                "Sequence must be non-empty.", 
                nameof(sequence));
        }
        int sum = sequence[0];
        for (int i = 1; i < sequence.Count; i++)
        {
            if (sequence[i] <= sum)
            {
                throw new ArgumentException(
                    "Not a superincreasing sequence.", 
                    nameof(sequence));
            }
            sum += sequence[i];
        }
        if (m <= sum)
        {
            throw new ArgumentOutOfRangeException(
                nameof(m), 
                "m must be greater than the sum of the sequence.");
        }

        if (MathHelpers.Gcd(m, w) != 1)
        {
            throw new ArgumentException(
                "w must be coprime to m.", 
                nameof(w));
        }

        IReadOnlyList<int> publicSequence = GeneratePublicSequence(sequence, m, w);

        return new KnapsackCryptosystem(
            new PublicKeyInfo(publicSequence),
            new PrivateKeyInfo(sequence, m, w)
        );
    }

    private static IReadOnlyList<int> GeneratePublicSequence(
        IReadOnlyList<int> sequence, int m, int w) => (
            from item in sequence
            select (w * item) % m)
            .ToList()
            .AsReadOnly();    // Multiply each item in the sequence by w and mod by m


    public readonly record struct PublicKeyInfo(IReadOnlyList<int> Sequence);

    // M is the modulus greater than sum of public sequence
    // W is the integer coprime to M
    private readonly record struct PrivateKeyInfo(IReadOnlyList<int> Sequence, int M, int W);

    private KnapsackCryptosystem(PublicKeyInfo publicKey, PrivateKeyInfo privateKey)
    {
        PublicKey = publicKey;
        PrivateKey = privateKey;
    }
}

针对你的问题，有两种可行的思路，结合Merkle-Hellman的特性，推荐第二种更贴合场景的方案：

方案一：加密时附加每个BigInteger的长度信息 #

在将BigInteger[]转成byte[]时，先记录每个BigInteger对应的字节数组长度，再拼接长度数据和字节内容，解密时按长度拆分还原。

修改Encrypt方法的转换逻辑 #

// 替换原有的转换代码
var ciphertextByteArrays = ciphertext.Select(c => c.ToByteArray()).ToList();
// 计算总字节数：每个元素的长度用4字节int存储，加上所有BigInteger的字节数据
int totalLength = ciphertextByteArrays.Count * sizeof(int);
foreach (var bytes in ciphertextByteArrays)
{
    totalLength += bytes.Length;
}
byte[] ciphertextBytes = new byte[totalLength];
int offset = 0;

// 逐个写入长度和字节数据
foreach (var bytes in ciphertextByteArrays)
{
    // 写入当前BigInteger的字节长度
    byte[] lengthBytes = BitConverter.GetBytes(bytes.Length);
    Buffer.BlockCopy(lengthBytes, 0, ciphertextBytes, offset, lengthBytes.Length);
    offset += lengthBytes.Length;
    // 写入BigInteger的字节内容
    Buffer.BlockCopy(bytes, 0, ciphertextBytes, offset, bytes.Length);
    offset += bytes.Length;
}
return ciphertextBytes;

修改Decrypt方法的还原逻辑 #

// 替换原有的BACK_TO_BIG_INTEGER_ARRAY部分
List<BigInteger> ciphertextInts = new List<BigInteger>();
int offset = 0;

while (offset < ciphertext.Length)
{
    // 读取当前BigInteger的字节长度
    byte[] lengthBytes = new byte[sizeof(int)];
    Buffer.BlockCopy(ciphertext, offset, lengthBytes, 0, lengthBytes.Length);
    offset += lengthBytes.Length;
    int byteLength = BitConverter.ToInt32(lengthBytes, 0);
    
    // 读取对应长度的字节数组并转换为BigInteger
    byte[] bigIntBytes = new byte[byteLength];
    Buffer.BlockCopy(ciphertext, offset, bigIntBytes, 0, byteLength);
    offset += byteLength;
    ciphertextInts.Add(new BigInteger(bigIntBytes));
}

// 补充明文比特长度的读取（解决<UNKNOWN_LENGTH>问题）
// 需在Encrypt最开头写入plaintextBits.Count，示例：
// byte[] bitLengthBytes = BitConverter.GetBytes(plaintextBits.Count);
// 插入到ciphertextBytes的最前面，这里对应读取：
// int plaintextBitLength = BitConverter.ToInt32(ciphertext, 0);
// offset += sizeof(int); // 上面的循环从offset=sizeof(int)开始
// var plaintextBits = new BitArray(plaintextBitLength);

方案二：利用Merkle-Hellman的特性固定每个BigInteger的字节长度 #

Merkle-Hellman中，每个密文元素是公钥序列的子集和，其最大值不会超过公钥序列的总和，而公钥序列的元素均小于m（私钥中的模数），因此每个密文BigInteger的字节长度有固定上限。我们可以统一用这个上限长度来存储每个密文元素，解密时直接按固定长度拆分。

修改Encrypt方法的转换逻辑 #

// 计算单个密文元素的最大字节长度
int sumPrivate = PrivateKey.Sequence.Sum();
// 密文元素最大值小于m，计算m所需的字节数，加1是BigInteger的符号位
int maxByteLength = (BitLength(PrivateKey.M) + 7) / 8 + 1;

byte[] ciphertextBytes = new byte[ciphertext.Length * maxByteLength];
int offset = 0;

foreach (var c in ciphertext)
{
    byte[] bytes = c.ToByteArray();
    // 将字节数组复制到固定长度的位置，不足部分在末尾补0（小端字节序，高位在数组末尾）
    Buffer.BlockCopy(bytes, 0, ciphertextBytes, offset, bytes.Length);
    if (bytes.Length < maxByteLength)
    {
        Array.Fill(ciphertextBytes, (byte)0, offset + bytes.Length, maxByteLength - bytes.Length);
    }
    offset += maxByteLength;
}
return ciphertextBytes;

// 辅助方法：计算整数的二进制位数
private int BitLength(int value)
{
    if (value == 0) return 1;
    return 32 - BitOperations.LeadingZeroCount((uint)value);
}

修改Decrypt方法的还原逻辑 #

// 计算固定的字节长度
int maxByteLength = (BitLength(PrivateKey.M) + 7) / 8 + 1;
int blockCount = ciphertext.Length / maxByteLength;
BigInteger[] ciphertextInts = new BigInteger[blockCount];

for (int i = 0; i < blockCount; i++)
{
    int offset = i * maxByteLength;
    byte[] bigIntBytes = new byte[maxByteLength];
    Buffer.BlockCopy(ciphertext, offset, bigIntBytes, 0, maxByteLength);
    ciphertextInts[i] = new BigInteger(bigIntBytes);
}

// 解决<UNKNOWN_LENGTH>问题：用blockCount * sequence.Count初始化，解密后截断多余位即可
var plaintextBits = new BitArray(blockCount * sequence.Count);

内容的提问来源于stack exchange，提问作者Amal K