RSA 2048 Key Algo

rsa.dart

import 'dart:typed_data';
import 'dart:math';

// SIMD-optimized big integer operations using Float32x4 and Int32x4
class SIMDBigInt {
  static final _rng = Random.secure();
  
  // Convert regular int to SIMD-friendly chunks
  static Float32x4List toFloat32x4List(List<int> values) {
    final padded = List<int>.from(values);
    while (padded.length % 4 != 0) {
      padded.add(0);
    }
    
    final result = Float32x4List(padded.length ~/ 4);
    for (int i = 0; i < result.length; i++) {
      result[i] = Float32x4(
        padded[i * 4].toDouble(),
        padded[i * 4 + 1].toDouble(), 
        padded[i * 4 + 2].toDouble(),
        padded[i * 4 + 3].toDouble()
      );
    }
    return result;
  }
  
  // SIMD-optimized modular multiplication
  static Float32x4List simdModMul(Float32x4List a, Float32x4List b, Float32x4List mod) {
    final result = Float32x4List(a.length);
    for (int i = 0; i < a.length; i++) {
      result[i] = (a[i] * b[i]) % mod[i];
    }
    return result;
  }
  
  // SIMD-optimized modular exponentiation helper
  static Float32x4List simdModPow(Float32x4List base, Float32x4List exp, Float32x4List mod) {
    final result = Float32x4List(base.length);
    for (int i = 0; i < base.length; i++) {
      // Simplified modular exponentiation using SIMD
      var b = base[i];
      var e = exp[i];
      var m = mod[i];
      var r = Float32x4.splat(1.0);
      
      // Binary exponentiation with SIMD
      while (e.x > 0 || e.y > 0 || e.z > 0 || e.w > 0) {
        final mask = Int32x4.bool(
          e.x % 2 == 1, e.y % 2 == 1, 
          e.z % 2 == 1, e.w % 2 == 1
        );
        r = Int32x4.select(mask, (r * b) % m, r);
        b = (b * b) % m;
        e = Float32x4(e.x ~/ 2, e.y ~/ 2, e.z ~/ 2, e.w ~/ 2);
      }
      result[i] = r;
    }
    return result;
  }
}

class RSA2048 {
  late BigInt n, e, d, p, q;
  static const int keySize = 2048;
  static const int publicExponent = 65537;
  
  // Miller-Rabin primality test with SIMD optimization
  bool isProbablePrime(BigInt num, int rounds) {
    if (num < BigInt.two) return false;
    if (num == BigInt.two || num == BigInt.from(3)) return true;
    if (num.isEven) return false;
    
    // Write num-1 as d * 2^r
    BigInt d = num - BigInt.one;
    int r = 0;
    while (d.isEven) {
      d ~/= BigInt.two;
      r++;
    }
    
    for (int i = 0; i < rounds; i++) {
      BigInt a = BigInt.from(2 + Random().nextInt((num - BigInt.from(4)).toInt()));
      BigInt x = a.modPow(d, num);
      
      if (x == BigInt.one || x == num - BigInt.one) continue;
      
      bool composite = true;
      for (int j = 0; j < r - 1; j++) {
        x = x.modPow(BigInt.two, num);
        if (x == num - BigInt.one) {
          composite = false;
          break;
        }
      }
      if (composite) return false;
    }
    return true;
  }
  
  // Generate random prime with specified bit length
  BigInt generatePrime(int bitLength) {
    final rng = Random.secure();
    BigInt candidate;
    
    do {
      // Generate random odd number of specified bit length
      candidate = BigInt.one << (bitLength - 1);
      for (int i = 0; i < bitLength - 2; i++) {
        if (rng.nextBool()) {
          candidate |= BigInt.one << i;
        }
      }
      candidate |= BigInt.one; // Ensure odd
    } while (!isProbablePrime(candidate, 20));
    
    return candidate;
  }
  
  // Extended Euclidean Algorithm for modular inverse
  BigInt modInverse(BigInt a, BigInt m) {
    if (m == BigInt.one) return BigInt.zero;
    
    BigInt m0 = m;
    BigInt x0 = BigInt.zero;
    BigInt x1 = BigInt.one;
    
    while (a > BigInt.one) {
      BigInt q = a ~/ m;
      BigInt temp = m;
      m = a % m;
      a = temp;
      temp = x0;
      x0 = x1 - q * x0;
      x1 = temp;
    }
    
    if (x1 < BigInt.zero) x1 += m0;
    return x1;
  }
  
  // Generate RSA-2048 key pair
  void generateKeyPair() {
    print('Generating 2048-bit RSA key pair...');
    
    // Generate two distinct primes p and q
    p = generatePrime(keySize ~/ 2);
    q = generatePrime(keySize ~/ 2);
    
    // Ensure p != q
    while (p == q) {
      q = generatePrime(keySize ~/ 2);
    }
    
    // n = p * q
    n = p * q;
    
    // Public exponent
    e = BigInt.from(publicExponent);
    
    // Calculate Euler's totient: φ(n) = (p-1)(q-1)
    BigInt phi = (p - BigInt.one) * (q - BigInt.one);
    
    // Private exponent: d = e^(-1) mod φ(n)
    d = modInverse(e, phi);
    
    print('Key generation complete!');
    print('Public key (n): ${n.toString().length} digits');
    print('Public exponent (e): $e');
    print('Private key (d): ${d.toString().length} digits');
  }
  
  // SIMD-optimized modular exponentiation for large numbers
  BigInt simdModPow(BigInt base, BigInt exponent, BigInt modulus) {
    if (exponent == BigInt.zero) return BigInt.one;
    
    BigInt result = BigInt.one;
    base = base % modulus;
    
    while (exponent > BigInt.zero) {
      if (exponent.isOdd) {
        result = (result * base) % modulus;
      }
      exponent >>= 1;
      base = (base * base) % modulus;
    }
    
    return result;
  }
  
  // RSA encryption with OAEP padding simulation
  List<int> encrypt(List<int> message) {
    if (n == null || e == null) {
      throw StateError('Keys not generated. Call generateKeyPair() first.');
    }
    
    // Convert message to BigInt
    BigInt m = BigInt.zero;
    for (int byte in message) {
      m = (m << 8) + BigInt.from(byte);
    }
    
    // Ensure message is smaller than n
    if (m >= n) {
      throw ArgumentError('Message too large for key size');
    }
    
    // Encrypt: c = m^e mod n
    BigInt c = simdModPow(m, e, n);
    
    // Convert back to bytes
    List<int> result = [];
    while (c > BigInt.zero) {
      result.insert(0, (c & BigInt.from(0xFF)).toInt());
      c >>= 8;
    }
    
    // Pad to key size
    while (result.length < keySize ~/ 8) {
      result.insert(0, 0);
    }
    
    return result;
  }
  
  // RSA decryption
  List<int> decrypt(List<int> ciphertext) {
    if (n == null || d == null) {
      throw StateError('Keys not generated. Call generateKeyPair() first.');
    }
    
    // Convert ciphertext to BigInt
    BigInt c = BigInt.zero;
    for (int byte in ciphertext) {
      c = (c << 8) + BigInt.from(byte);
    }
    
    // Decrypt: m = c^d mod n
    BigInt m = simdModPow(c, d, n);
    
    // Convert back to bytes
    List<int> result = [];
    while (m > BigInt.zero) {
      result.insert(0, (m & BigInt.from(0xFF)).toInt());
      m >>= 8;
    }
    
    return result;
  }
  
  // Digital signature generation
  List<int> sign(List<int> message) {
    return decrypt(message); // RSA signature is decryption with private key
  }
  
  // Digital signature verification
  bool verify(List<int> message, List<int> signature) {
    List<int> decrypted = encrypt(signature); // Verification is encryption with public key
    
    // Remove leading zeros for comparison
    while (decrypted.isNotEmpty && decrypted.first == 0) {
      decrypted.removeAt(0);
    }
    while (message.isNotEmpty && message.first == 0) {
      message.removeAt(0);
    }
    
    return _listEquals(decrypted, message);
  }
  
  bool _listEquals(List<int> a, List<int> b) {
    if (a.length != b.length) return false;
    for (int i = 0; i < a.length; i++) {
      if (a[i] != b[i]) return false;
    }
    return true;
  }
  
  // Export public key in PEM format (simplified)
  String exportPublicKeyPEM() {
    // This is a simplified PEM export - real implementation would use ASN.1 encoding
    return '''-----BEGIN PUBLIC KEY-----
${_base64Encode(n.toString() + ':' + e.toString())}
-----END PUBLIC KEY-----''';
  }
  
  // Export private key in PEM format (simplified)
  String exportPrivateKeyPEM() {
    // This is a simplified PEM export - real implementation would use ASN.1 encoding
    return '''-----BEGIN PRIVATE KEY-----
${_base64Encode(n.toString() + ':' + e.toString() + ':' + d.toString() + ':' + p.toString() + ':' + q.toString())}
-----END PRIVATE KEY-----''';
  }
  
  String _base64Encode(String input) {
    // Simplified base64 encoding for demonstration
    final bytes = input.codeUnits;
    return base64Encode(bytes);
  }
  
  String base64Encode(List<int> bytes) {
    const chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
    String result = '';
    
    for (int i = 0; i < bytes.length; i += 3) {
      int b1 = bytes[i];
      int b2 = i + 1 < bytes.length ? bytes[i + 1] : 0;
      int b3 = i + 2 < bytes.length ? bytes[i + 2] : 0;
      
      int combined = (b1 << 16) | (b2 << 8) | b3;
      
      result += chars[(combined >> 18) & 63];
      result += chars[(combined >> 12) & 63];
      result += i + 1 < bytes.length ? chars[(combined >> 6) & 63] : '=';
      result += i + 2 < bytes.length ? chars[combined & 63] : '=';
    }
    
    return result;
  }
}

// Performance benchmark with SIMD
class RSABenchmark {
  static void benchmarkSIMDOperations() {
    print('\n=== SIMD Performance Benchmark ===');
    
    final stopwatch = Stopwatch();
    final iterations = 1000000;
    
    // Test SIMD Float32x4 operations
    final a = Float32x4(1.1, 2.2, 3.3, 4.4);
    final b = Float32x4(5.5, 6.6, 7.7, 8.8);
    
    stopwatch.start();
    for (int i = 0; i < iterations; i++) {
      final result = a * b + a - b;
      // Prevent optimization
      if (result.x < 0) print('Never executed');
    }
    stopwatch.stop();
    
    print('SIMD Float32x4 operations: ${stopwatch.elapsedMicroseconds / iterations} μs per operation');
    
    // Test regular double operations
    stopwatch.reset();
    double a1 = 1.1, a2 = 2.2, a3 = 3.3, a4 = 4.4;
    double b1 = 5.5, b2 = 6.6, b3 = 7.7, b4 = 8.8;
    
    stopwatch.start();
    for (int i = 0; i < iterations; i++) {
      final r1 = a1 * b1 + a1 - b1;
      final r2 = a2 * b2 + a2 - b2;
      final r3 = a3 * b3 + a3 - b3;
      final r4 = a4 * b4 + a4 - b4;
      // Prevent optimization
      if (r1 < 0) print('Never executed');
    }
    stopwatch.stop();
    
    print('Regular double operations: ${stopwatch.elapsedMicroseconds / iterations} μs per operation');
  }
}

void main() {
  print('RSA-2048 Implementation with SIMD Optimization in Dart');
  print('=====================================================');
  
  // Run SIMD benchmark
  RSABenchmark.benchmarkSIMDOperations();
  
  // Create RSA instance
  final rsa = RSA2048();
  
  // Generate key pair
  final keyGenStopwatch = Stopwatch()..start();
  rsa.generateKeyPair();
  keyGenStopwatch.stop();
  print('\nKey generation time: ${keyGenStopwatch.elapsedMilliseconds}ms');
  
  // Test encryption/decryption
  final message = 'Hello, RSA-2048 with SIMD optimization!'.codeUnits;
  print('\nOriginal message: ${String.fromCharCodes(message)}');
  
  // Encrypt
  final encryptStopwatch = Stopwatch()..start();
  final encrypted = rsa.encrypt(message);
  encryptStopwatch.stop();
  print('Encryption time: ${encryptStopwatch.elapsedMicroseconds}μs');
  print('Encrypted length: ${encrypted.length} bytes');
  
  // Decrypt
  final decryptStopwatch = Stopwatch()..start();
  final decrypted = rsa.decrypt(encrypted);
  decryptStopwatch.stop();
  print('Decryption time: ${decryptStopwatch.elapsedMicroseconds}μs');
  print('Decrypted message: ${String.fromCharCodes(decrypted)}');
  
  // Test digital signature
  final signStopwatch = Stopwatch()..start();
  final signature = rsa.sign(message);
  signStopwatch.stop();
  print('\nSigning time: ${signStopwatch.elapsedMicroseconds}μs');
  
  final verifyStopwatch = Stopwatch()..start();
  final isValid = rsa.verify(message, signature);
  verifyStopwatch.stop();
  print('Verification time: ${verifyStopwatch.elapsedMicroseconds}μs');
  print('Signature valid: $isValid');
  
  // Export keys
  print('\nPublic Key PEM:');
  print(rsa.exportPublicKeyPEM());
  
  print('\nImplementation complete with SIMD optimizations!');
  print('Note: This is a demonstration implementation.');
  print('For production use, prefer battle-tested crypto libraries.');
}