RSA.cpp

//
// RSA Algorithm Implementation
//

#include "RSA.h"
#include "BigIntegerParallel.h"
#include "Montgomery.h"
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdexcept>
#include <cstdio>
#include <cstring>
#include <map>
#include <chrono>
#include <limits>
std::mt19937_64& RSA::rng()
{
    thread_local std::mt19937_64 engine(
        static_cast<uint64_t>(std::random_device{}()) ^
        static_cast<uint64_t>(std::chrono::high_resolution_clock::now().time_since_epoch().count()) ^
        static_cast<uint64_t>(std::hash<std::thread::id>{}(std::this_thread::get_id())));
    return engine;
}

uint32_t RSA::randomWord32()
{
    static thread_local std::uniform_int_distribution<uint32_t> dist(
        0, std::numeric_limits<uint32_t>::max());
    return dist(rng());
}

BigInteger RSA::randomBits(size_t bitLength, bool ensureTopBit)
{
    if (bitLength == 0)
        return BigInteger(0);

    size_t limbCount = (bitLength + 31) / 32;
    BigInteger result;
    result.digits.assign(limbCount, 0);

    for (size_t i = 0; i < limbCount; ++i)
        result.digits[i] = randomWord32();

    size_t extraBits = limbCount * 32 - bitLength;
    if (extraBits > 0)
    {
        uint32_t mask = static_cast<uint32_t>(0xFFFFFFFFu >> extraBits);
        result.digits.back() &= mask;
    }

    if (ensureTopBit)
    {
        size_t bitIndex = bitLength - 1;
        size_t limbIndex = bitIndex / 32;
        size_t bitOffset = bitIndex % 32;
        result.digits[limbIndex] |= (1U << bitOffset);
    }

    result.sign = false;
    result.normalize();
    return result;
}

BigInteger RSA::randomBelow(const BigInteger& limit)
{
    if (limit.isZero())
        return BigInteger(0);

    size_t bits = MontgomeryReducer::bitLength(limit);
    BigInteger candidate;
    do
    {
        candidate = randomBits(bits, false);
        candidate.normalize();
    }
    while (candidate > limit);
    return candidate;
}

// Extended modulo operation for BigInteger (supports large modulus)
// Uses optimized binary long division
BigInteger RSA::mod(const BigInteger& a, const BigInteger& modulus) {
    if (modulus.isZero()) {
        throw runtime_error("Modulus cannot be zero");
    }

    BigInteger modAbs = modulus.getSign() ? modulus.absolute() : modulus;
    BigInteger result = a % modAbs;

    if (result.getSign()) {
        result = result + modAbs;
    }

    return result;
}

// Modular exponentiation (fast exponentiation with parallel optimization)
BigInteger RSA::modPow(const BigInteger& base, const BigInteger& exp, const BigInteger& modulus) {
    if (modulus.isZero()) {
        throw runtime_error("Modulus cannot be zero");
    }
    MontgomeryReducer reducer(modulus);
    return reducer.modPow(base, exp);
}

// Greatest Common Divisor
BigInteger RSA::gcd(const BigInteger& a, const BigInteger& b) {
    BigInteger zero(0);
    BigInteger x = a;
    BigInteger y = b;
    
    // Get absolute values
    bool xSign = x.getSign();
    bool ySign = y.getSign();
    if (xSign) {
        x = x.absolute();
    }
    if (ySign) {
        y = y.absolute();
    }
    
    while (y != zero) {
        BigInteger temp = y;
        y = mod(x, y);
        x = temp;
    }
    
    return x;
}

// Extended Euclidean Algorithm
pair<BigInteger, pair<BigInteger, BigInteger>> RSA::extendedGcd(const BigInteger& a, const BigInteger& b) {
    BigInteger zero(0);
    BigInteger one(1);
    BigInteger b_copy = b;
    
    if (b_copy == zero) {
        BigInteger a_abs = a;
        bool aSign = a_abs.getSign();
        if (aSign) {
            a_abs = a_abs.absolute();
        }
        return make_pair(a_abs, make_pair(one, zero));
    }
    
    BigInteger a_abs = a;
    BigInteger b_abs = b;
    bool aSign = a_abs.getSign();
    bool bSign = b_abs.getSign();
    if (aSign) {
        a_abs = a_abs.absolute();
    }
    if (bSign) {
        b_abs = b_abs.absolute();
    }
    
    auto result = extendedGcd(b_abs, mod(a_abs, b_abs));
    BigInteger gcd_val = result.first;
    BigInteger x1 = result.second.first;
    BigInteger y1 = result.second.second;
    
    BigInteger quotient = a_abs / b_abs;
    BigInteger x = y1;
    BigInteger quotient_times_y1 = quotient * y1;
    BigInteger y = x1 - quotient_times_y1;
    
    return make_pair(gcd_val, make_pair(x, y));
}

// Modular inverse using extended Euclidean algorithm
BigInteger RSA::modInverse(const BigInteger& a, const BigInteger& modulus) {
    BigInteger one(1);
    BigInteger zero(0);
    
    auto result = extendedGcd(a, modulus);
    BigInteger gcd_val = result.first;
    
    if (gcd_val != one) {
        throw runtime_error("Modular inverse does not exist");
    }
    
    BigInteger x = result.second.first;
    BigInteger m_abs = modulus;
    bool mSign = m_abs.getSign();
    if (mSign) {
        m_abs = m_abs.absolute();
    }
    
    // Make sure result is positive
    x = mod(x, m_abs);
    bool xSign = x.getSign();
    if (xSign) {
        x = x + m_abs;
    }
    bool xNeg = x < zero;
    if (xNeg) {
        x = x + m_abs;
    }
    
    return x;
}

// Generate random BigInteger with specified bit length
BigInteger RSA::randomBigInteger(int bitLength) {
    if (bitLength <= 0) {
        return BigInteger(0);
    }
    
    return randomBits(static_cast<size_t>(bitLength), true);
}

// Generate random BigInteger in range [min, max]
BigInteger RSA::randomBigInteger(const BigInteger& minVal, const BigInteger& maxVal) {
    BigInteger zero(0);
    BigInteger one(1);
    
    BigInteger min_copy = minVal;
    BigInteger max_copy = maxVal;
    if (max_copy < min_copy) {
        return min_copy;
    }
    
    BigInteger range = max_copy - min_copy;
    if (range == zero) {
        return min_copy;
    }
    
    BigInteger rangeInclusive = range;
    BigInteger candidate;
    do {
        candidate = randomBelow(rangeInclusive);
    } while (candidate > rangeInclusive);
    return min_copy + candidate;
}

// Optimized Miller-Rabin primality test
bool RSA::millerRabin(const BigInteger& n, int iterations) {
    BigInteger two(2);
    BigInteger three(3);
    BigInteger one(1);
    BigInteger n_copy = n;
    
    if (n_copy == two || n_copy == three) {
        return true;
    }
    
    if (n_copy < two || !n_copy.isOdd()) {
        return false;
    }
    
    BigInteger n_minus_one = n_copy - one;
    BigInteger d = n_minus_one;
    int r = 0;
    while (!d.isOdd()) {
        d = d / two;
        ++r;
    }
    
    size_t nBits = n_copy.bitLength();
    if (nBits >= 1536) {
        iterations = std::max(iterations, 64);
    } else if (nBits >= 1024) {
        iterations = std::max(iterations, 48);
    } else if (nBits >= 512) {
        iterations = std::max(iterations, 40);
    } else if (nBits >= 256) {
        iterations = std::max(iterations, 32);
    } else {
        iterations = std::max(iterations, 16);
    }
    
    vector<BigInteger> testBases;
    if (nBits <= 64 && iterations <= 12) {
        static const vector<int> deterministicBases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for (int i = 0; i < min(iterations, (int)deterministicBases.size()); ++i) {
            testBases.push_back(BigInteger(deterministicBases[i]));
        }
    } else {
        BigInteger n_minus_two = n_copy - two;
        if (n_minus_two < two) {
            n_minus_two = two;
        }
        for (int i = 0; i < iterations; ++i) {
            BigInteger a = randomBigInteger(two, n_minus_two);
            testBases.push_back(a);
        }
    }
    
    MontgomeryReducer reducer(n_copy);
    BigInteger montOne = reducer.toMontgomery(one);
    BigInteger montNMinusOne = reducer.toMontgomery(n_minus_one);
    
    for (const BigInteger& base : testBases) {
        BigInteger candidate = base;
        if (candidate >= n_copy) {
            candidate = mod(candidate, n_copy);
        }
        if (candidate <= one) {
            continue;
        }
        
        BigInteger baseMont = reducer.toMontgomery(candidate);
        BigInteger xMont = reducer.powMontgomery(baseMont, d);
        
        if (xMont == montOne || xMont == montNMinusOne) {
            continue;
        }
        
        bool witnessComposite = true;
        BigInteger xTempMont = xMont;
        for (int j = 0; j < r - 1; ++j) {
            xTempMont = reducer.multiply(xTempMont, xTempMont);
            if (xTempMont == montNMinusOne) {
                witnessComposite = false;
                break;
            }
            if (xTempMont == montOne) {
                return false;
            }
        }
        
        if (witnessComposite) {
            return false;
        }
    }
    
    return true;
}

// Quick trial division with extended small primes
bool RSA::quickTrialDivision(const BigInteger& n, int maxDivisor) {
    BigInteger zero(0);
    BigInteger n_copy = n;
    
    // Extended list of small primes for faster pre-screening
    // First 168 primes (all primes < 1000)
    static const vector<int> smallPrimes = {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
        73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
        157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
        239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
        331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
        421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
        509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
        613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
        709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
        821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
        919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
    };
    
    for (int p : smallPrimes) {
        if (p > maxDivisor) break;
        BigInteger p_big(p);
        if (n_copy == p_big) {
            return true; // It's a small prime
        }
        if (mod(n_copy, p_big) == zero) {
            return false; // Divisible by small prime
        }
    }
    
    return true; // Passed trial division
}

// Fast prime check with optimized pre-screening
bool RSA::isPrimeFast(const BigInteger& n, int iterations) {
    BigInteger two(2);
    BigInteger zero(0);
    BigInteger n_copy = n;
    
    // Quick checks
    if (n_copy < two) {
        return false;
    }
    if (n_copy == two) {
        return true;
    }
    if (!n_copy.isOdd()) {
        return false;
    }
    
    // Fast trial division with extended small primes
    if (!quickTrialDivision(n_copy, 1000)) {
        return false;
    }
    
    // For very small numbers, use deterministic test
    // If n < 2^64, we can use deterministic Miller-Rabin
    // For our purposes, if bit length < 64, use more iterations for high confidence
    int adjustedIterations = iterations;
    if (n_copy.bitLength() <= 64) {
        adjustedIterations = min(iterations * 2, 50);
    }
    
    return millerRabin(n_copy, adjustedIterations);
}

// Check if number is prime (using fast version)
bool RSA::isPrime(const BigInteger& n, int iterations) {
    return isPrimeFast(n, iterations);
}

// Generate a prime number with specified bit length
BigInteger RSA::generatePrime(int bitLength,
                              std::chrono::steady_clock::time_point deadline) {
    auto checkDeadline = [&]() {
        if (std::chrono::steady_clock::now() >= deadline) {
            throw runtime_error("RSA key generation timed out");
        }
    };

    checkDeadline();

    if (bitLength < 2) {
        return BigInteger(2);
    }
    
    if (bitLength == 2) {
        return BigInteger(3); // Only odd prime with 2 bits
    }
    
    // Calculate min and max values
    BigInteger minVal("1");
    for (int i = 0; i < bitLength - 1; i++) {
        minVal = minVal * BigInteger(2);
    }
    
    BigInteger maxVal("1");
    for (int i = 0; i < bitLength; i++) {
        maxVal = maxVal * BigInteger(2);
    }
    maxVal = maxVal - BigInteger(1);
    
    int maxAttempts = 5000; // Increased attempts for better success rate
    int millerRabinIterations;
    if (bitLength <= 64) {
        millerRabinIterations = 16;
    } else if (bitLength <= 128) {
        millerRabinIterations = 24;
    } else if (bitLength <= 256) {
        millerRabinIterations = 32;
    } else {
        millerRabinIterations = 40;
    }
    
    for (int attempt = 0; attempt < maxAttempts; attempt++) {
        checkDeadline();
        BigInteger candidate = randomBigInteger(bitLength);
        
        // Ensure candidate is in range and odd
        if (candidate < minVal) {
            candidate = minVal;
        }
        if (candidate > maxVal) {
            candidate = maxVal;
        }
        
        if (!candidate.isOdd()) {
            if (candidate < maxVal) {
                candidate = candidate + BigInteger(1);
            } else {
                candidate = candidate - BigInteger(1);
            }
        }
        
        checkDeadline();

        // Test for primality
        if (isPrime(candidate, millerRabinIterations)) {
            return candidate;
        }
        
        // Try next odd number
        if (attempt % 10 == 0 && candidate < maxVal - BigInteger(2)) {
            candidate = candidate + BigInteger(2);
        }
    }
    
    throw runtime_error("Failed to generate prime after maximum attempts");
}

// Optimized candidate generation using wheel sieve concept
BigInteger RSA::generateCandidateOptimized(int bitLength, const BigInteger& minVal,
                                           const BigInteger& maxVal, mt19937& gen,
                                           int attempt,
                                           std::chrono::steady_clock::time_point deadline) {
    if (std::chrono::steady_clock::now() >= deadline) {
        throw runtime_error("RSA key generation timed out");
    }

    (void)gen;
    (void)attempt;

    BigInteger candidate = randomBigInteger(bitLength);

    if (candidate < minVal) {
        candidate = minVal;
    }
    if (candidate > maxVal) {
        candidate = maxVal;
    }

    BigInteger two(2);
    if (!candidate.isOdd()) {
        if (candidate < maxVal) {
            candidate = candidate + BigInteger(1);
        } else if (candidate > minVal) {
            candidate = candidate - BigInteger(1);
        }
    }

    return candidate;
}

// Generate prime with specific seed for parallel generation (optimized)
BigInteger RSA::generatePrimeWithSeed(int bitLength,
                                      unsigned int seed,
                                      std::chrono::steady_clock::time_point deadline) {
    auto checkDeadline = [&]() {
        if (std::chrono::steady_clock::now() >= deadline) {
            throw runtime_error("RSA key generation timed out");
        }
    };

    checkDeadline();

    if (bitLength < 2) {
        return BigInteger(2);
    }
    
    if (bitLength == 2) {
        return BigInteger(3);
    }
    
    // Calculate min and max values (cache these calculations)
    static mutex cacheMutex;
    static map<int, pair<BigInteger, BigInteger>> rangeCache;
    
    BigInteger minVal, maxVal;
    {
        lock_guard<mutex> lock(cacheMutex);
        auto it = rangeCache.find(bitLength);
        if (it != rangeCache.end()) {
            minVal = it->second.first;
            maxVal = it->second.second;
        } else {
            minVal = BigInteger("1");
            for (int i = 0; i < bitLength - 1; i++) {
                minVal = minVal * BigInteger(2);
            }
            
            maxVal = BigInteger("1");
            for (int i = 0; i < bitLength; i++) {
                maxVal = maxVal * BigInteger(2);
            }
            maxVal = maxVal - BigInteger(1);
            rangeCache[bitLength] = make_pair(minVal, maxVal);
        }
    }
    
    // Optimized: reduce iterations for smaller keys, adjust based on bit length
    int millerRabinIterations;
    if (bitLength <= 64) {
        millerRabinIterations = 16;
    } else if (bitLength <= 128) {
        millerRabinIterations = 24;
    } else if (bitLength <= 256) {
        millerRabinIterations = 32;
    } else {
        millerRabinIterations = 40;
    }
    
    int maxAttempts = 3000; // Reduced attempts due to better pre-screening
    // int batchSize = min(BigIntegerParallel::getMaxThreads(), 6); // Batch size for parallel testing
    // if (batchSize < 2) batchSize = 2;
    int batchSize=16;
    
    // Use thread-specific random number generator with seed
    hash<thread::id> hasher;
    size_t threadHash = hasher(this_thread::get_id());
    auto now = chrono::high_resolution_clock::now();
    auto nanos = chrono::duration_cast<chrono::nanoseconds>(now.time_since_epoch()).count();
    unsigned int threadSeed = seed ^ (static_cast<unsigned int>(threadHash) << 16);
    threadSeed ^= static_cast<unsigned int>(nanos % 1000000);
    mt19937 gen(threadSeed);
    
    BigInteger two(2);
    BigInteger one(1);
    
    // Wheel sieve: skip numbers divisible by small primes
    // Use increments that avoid small prime factors
    // For RSA primes, we mainly need to avoid 2 (already handled), 3, 5, 7
    // Pattern: +2, +4, +2, +4, +2, +4, +6, +2, +6 (avoids 3, 5, 7)
    static const vector<int> wheelIncrements = {2, 4, 2, 4, 2, 4, 6, 2, 6};
    int wheelIndex = 0;
    BigInteger currentCandidate;
    bool hasCandidate = false;
    
    int attempt = 0;
    while (attempt < maxAttempts) {
        checkDeadline();
        vector<BigInteger> candidateBatch;
        candidateBatch.reserve(batchSize);
        
        // Generate a batch of candidates
        for (int batch = 0; batch < batchSize && attempt < maxAttempts; ++batch, ++attempt) {
            checkDeadline();
            BigInteger candidate;
            
            if (!hasCandidate || attempt % 10 == 0) {
                // Generate new candidate every 10 attempts or initially
                candidate = generateCandidateOptimized(bitLength, minVal, maxVal, gen, attempt, deadline);
                currentCandidate = candidate;
                hasCandidate = true;
                wheelIndex = 0;
            } else {
                // Use wheel increments to skip likely composites
                int increment = wheelIncrements[wheelIndex % wheelIncrements.size()];
                wheelIndex++;
                candidate = currentCandidate + BigInteger(increment * 2); // *2 because we only test odds
                
                // Wrap around if exceeded max
                if (candidate > maxVal) {
                    candidate = minVal + mod(candidate - minVal, maxVal - minVal + one);
                    // Ensure odd
                    if (!candidate.isOdd()) {
                        candidate = candidate + one;
                    }
                }
                currentCandidate = candidate;
            }
            
            candidateBatch.push_back(candidate);
        }
        
        // Launch parallel primality tests for the batch
        vector<future<bool>> futures;
        futures.reserve(candidateBatch.size());
        for (const auto& candidate : candidateBatch) {
            futures.push_back(async(launch::async, [candidate, millerRabinIterations]() {
                if (!quickTrialDivision(candidate, 100)) {
                    return false;
                }
                return isPrimeFast(candidate, millerRabinIterations);
            }));
        }
        
        // Collect results
        for (size_t i = 0; i < candidateBatch.size(); ++i) {
            checkDeadline();
            if (futures[i].get()) {
                return candidateBatch[i];
            }
        }
    }
    
    throw runtime_error("Failed to generate prime after maximum attempts");
}

// Parallel prime generation
BigInteger RSA::generatePrimeParallel(int bitLength,
                                      int threadId,
                                      std::chrono::steady_clock::time_point deadline) {
    if (std::chrono::steady_clock::now() >= deadline) {
        throw runtime_error("RSA key generation timed out");
    }

    // Use thread ID, time, and high-resolution clock to generate unique seed
    hash<thread::id> hasher;
    size_t threadHash = hasher(this_thread::get_id());
    auto now = chrono::high_resolution_clock::now();
    auto nanos = chrono::duration_cast<chrono::nanoseconds>(now.time_since_epoch()).count();
    unsigned int seed = static_cast<unsigned int>(
        threadId * 10000 + 
        (nanos % 1000000) + 
        (threadHash % 10000)
    );
    return generatePrimeWithSeed(bitLength, seed, deadline);
}

// Generate RSA key pair with parallel optimization
RSA::KeyPair RSA::generateKeyPair(int bitLength, std::chrono::milliseconds timeout) {
    if (bitLength < 64) {
        throw runtime_error("Bit length must be at least 64");
    }
    if (timeout <= std::chrono::milliseconds::zero()) {
        throw runtime_error("Timeout must be positive");
    }
    
    int primeLength = bitLength / 2;
    auto deadline = std::chrono::steady_clock::now() + timeout;
    
    // Use parallel generation for p and q
    // They can be generated independently, which approximately halves the generation time
    future<BigInteger> futureP = async(launch::async, &RSA::generatePrimeParallel, primeLength, 1, deadline);
    future<BigInteger> futureQ = async(launch::async, &RSA::generatePrimeParallel, primeLength, 2, deadline);
    
    // Wait for both primes to be generated
    BigInteger p = futureP.get();
    BigInteger q = futureQ.get();
    
    // Ensure p != q (extremely rare but handle it)
    // If equal, regenerate one of them in parallel
    if (p == q) {
        // Regenerate q with a different seed
        q = generatePrimeParallel(primeLength, 100, deadline);
        
        // If still equal (extremely unlikely), try a few more times
        int retryCount = 0;
        while (p == q && retryCount < 5) {
            future<BigInteger> futureQ2 = async(launch::async, &RSA::generatePrimeParallel, primeLength, 200 + retryCount, deadline);
            q = futureQ2.get();
            retryCount++;
        }
    }
    
    if (p == q) {
        throw runtime_error("Failed to generate distinct primes after multiple attempts");
    }
    
    // Calculate n = p * q
    BigInteger n = p * q;
    
    // Calculate phi(n) = (p-1) * (q-1)
    BigInteger phi = (p - BigInteger(1)) * (q - BigInteger(1));
    
    // Choose public exponent e (typically 65537)
    BigInteger e = BigInteger(65537);
    if (e >= phi || gcd(e, phi) != BigInteger(1)) {
        // Try smaller e
        e = BigInteger(3);
        while (e < phi && gcd(e, phi) != BigInteger(1)) {
            e = e + BigInteger(2);
        }
    }
    
    // Calculate private exponent d = e^(-1) mod phi(n)
    BigInteger d = modInverse(e, phi);
    
    KeyPair keys;
    keys.n = n;
    keys.e = e;
    keys.d = d;
    keys.p = p;
    keys.q = q;
    
    return keys;
}

// Convert BigInteger to string (hexadecimal for compactness)
string RSA::bigIntegerToString(const BigInteger& num) {
    BigInteger num_copy = num;
    return string(num_copy);
}

// Convert string to BigInteger
BigInteger RSA::stringToBigInteger(const string& str) {
    return BigInteger(str);
}

// Convert string to blocks
vector<BigInteger> RSA::stringToBlocks(const string& str, int blockSize) {
    vector<BigInteger> blocks;
    
    // Convert string to number: each byte becomes 2 hex digits
    string hexStr;
    for (char c : str) {
        unsigned char uc = static_cast<unsigned char>(c);
        char hex[3];
        snprintf(hex, sizeof(hex), "%02x", uc);
        hexStr += hex;
    }
    
    // Split into blocks
    for (size_t i = 0; i < hexStr.length(); i += blockSize * 2) {
        string blockHex = hexStr.substr(i, blockSize * 2);
        if (blockHex.empty()) continue;
        
        // Convert hex to decimal
        BigInteger block = BigInteger(0);
        BigInteger sixteen(16);
        for (char c : blockHex) {
            int digit = (c >= '0' && c <= '9') ? (c - '0') : (c - 'a' + 10);
            if (digit < 0 || digit > 15) digit = 0;
            BigInteger digitBig(digit);
            BigInteger mult = block * sixteen;
            block = mult + digitBig;
        }
        blocks.push_back(block);
    }
    
    return blocks;
}

// Convert blocks to string
string RSA::blocksToString(const vector<BigInteger>& blocks) {
    string result;
    
    for (const BigInteger& block : blocks) {
        // Convert to hex
        BigInteger temp = block;
        string hexStr;
        
        BigInteger zero = BigInteger(0);
        BigInteger sixteen(16);
        BigInteger temp_copy = temp;
        if (temp_copy == zero) {
            hexStr = "00";
        } else {
            while (temp > zero) {
                BigInteger remainder = mod(temp, sixteen);
                int digit = remainder.isZero() ? 0 : static_cast<int>(remainder.digits[0]);
                if (digit < 0 || digit > 15) digit = 0;
                
                char hexChar = (digit < 10) ? ('0' + digit) : ('a' + digit - 10);
                hexStr = hexChar + hexStr;
                temp = temp / sixteen;
            }
            
            // Ensure even length (each byte is 2 hex digits)
            if (hexStr.length() % 2 != 0) {
                hexStr = "0" + hexStr;
            }
        }
        
        // Convert hex to bytes
        for (size_t i = 0; i < hexStr.length(); i += 2) {
            if (i + 1 < hexStr.length()) {
                string byteHex = hexStr.substr(i, 2);
                try {
                    int byteVal = stoi(byteHex, nullptr, 16);
                    result += static_cast<char>(byteVal);
                } catch (...) {
                    // Skip invalid hex
                }
            }
        }
    }
    
    // Remove trailing null bytes
    while (!result.empty() && result.back() == '\0') {
        result.pop_back();
    }
    
    return result;
}

// Encrypt message
string RSA::encrypt(const string& message, const BigInteger& n, const BigInteger& e) {
    if (message.empty()) {
        return "";
    }
    
    // Calculate maximum block size: n must be greater than the block value
    // Each byte becomes 2 hex digits, so we need: blockSize * 2 <= log10(n) * log10(16)
    // Conservative: use about 1/4 of modulus digits
    BigInteger n_copy1 = n;
    int modulusBits = static_cast<int>(n_copy1.bitLength());
    int blockSize = (modulusBits / 8) - 1;
    if (blockSize < 1) blockSize = 1;
    if (blockSize > 100) blockSize = 100; // Limit block size
    
    // Convert message to blocks
    vector<BigInteger> blocks = stringToBlocks(message, blockSize);
    
    // Encrypt each block
    vector<string> encryptedBlocks;
    BigInteger one(1);
    BigInteger n_copy2 = n;
    for (const BigInteger& block : blocks) {
        // Ensure block is less than n
        BigInteger blockMod = mod(block, n);
        BigInteger n_minus_one = n_copy2 - one;
        BigInteger n_copy3 = n;
        if (blockMod >= n_copy3) {
            blockMod = n_minus_one;
        }
        
        BigInteger encrypted = modPow(blockMod, e, n);
        encryptedBlocks.push_back(bigIntegerToString(encrypted));
    }
    
    // Join blocks with delimiter
    string result;
    for (size_t i = 0; i < encryptedBlocks.size(); i++) {
        if (i > 0) result += ":";
        result += encryptedBlocks[i];
    }
    
    return result;
}

// Decrypt message
string RSA::decrypt(const string& ciphertext, const BigInteger& n, const BigInteger& d) {
    if (ciphertext.empty()) {
        return "";
    }
    
    // Split into blocks
    vector<BigInteger> blocks;
    stringstream ss(ciphertext);
    string token;
    
    while (getline(ss, token, ':')) {
        if (!token.empty()) {
            blocks.push_back(stringToBigInteger(token));
        }
    }
    
    // Decrypt each block
    vector<BigInteger> decryptedBlocks;
    for (const BigInteger& block : blocks) {
        BigInteger decrypted = modPow(block, d, n);
        decryptedBlocks.push_back(decrypted);
    }
    
    // Convert blocks to string
    return blocksToString(decryptedBlocks);
}

// Sign message
string RSA::sign(const string& message, const BigInteger& n, const BigInteger& d) {
    if (message.empty()) {
        return "";
    }
    
    // Create hash of message (simple: use message itself for small messages)
    // For production, use proper hash function like SHA-256
    string hash = message;
    
    // Calculate block size (same as encryption)
    BigInteger n_copy = n;
    int modulusBits = static_cast<int>(n_copy.bitLength());
    int blockSize = (modulusBits / 8) - 1;
    if (blockSize < 1) blockSize = 1;
    if (blockSize > 100) blockSize = 100;
    
    // Convert to blocks and sign
    vector<BigInteger> blocks = stringToBlocks(hash, blockSize);
    
    vector<string> signatureBlocks;
    BigInteger one(1);
    BigInteger n_copy4 = n;
    for (const BigInteger& block : blocks) {
        // Ensure block is less than n
        BigInteger blockMod = mod(block, n);
        BigInteger n_minus_one = n_copy4 - one;
        BigInteger n_copy5 = n;
        if (blockMod >= n_copy5) {
            blockMod = n_minus_one;
        }
        
        BigInteger signature = modPow(blockMod, d, n);
        signatureBlocks.push_back(bigIntegerToString(signature));
    }
    
    // Join signature blocks
    string result;
    for (size_t i = 0; i < signatureBlocks.size(); i++) {
        if (i > 0) result += ":";
        result += signatureBlocks[i];
    }
    
    return result;
}

// Verify signature
bool RSA::verify(const string& message, const string& signature, const BigInteger& n, const BigInteger& e) {
    if (message.empty() || signature.empty()) {
        return false;
    }
    
    // Create hash of message
    string hash = message;
    
    // Decrypt signature
    vector<BigInteger> signatureBlocks;
    stringstream ss(signature);
    string token;
    
    while (getline(ss, token, ':')) {
        if (!token.empty()) {
            try {
                signatureBlocks.push_back(stringToBigInteger(token));
            } catch (...) {
                return false;
            }
        }
    }
    
    if (signatureBlocks.empty()) {
        return false;
    }
    
    // Verify each block
    vector<BigInteger> verifiedBlocks;
    for (const BigInteger& sigBlock : signatureBlocks) {
        BigInteger verified = modPow(sigBlock, e, n);
        verifiedBlocks.push_back(verified);
    }
    
    // Convert to string
    string verifiedHash = blocksToString(verifiedBlocks);
    
    // Compare (simple comparison for demonstration)
    // In production, compare hash values properly
    // For now, compare the original message with verified hash
    return verifiedHash == hash;
}