When your teacher gives you assignment to work out RSA algorithm, you code it to automate it and copy-paste to submit! 🤖 Damn man, I love Dart!

rsa.dart

import 'dart:math' as math;
import 'dart:io';

void main() {
  stdout.write("❓ Enter p: ");
  final p = int.parse(stdin.readLineSync()!);
  stdout.write("❓ Enter q: ");
  final q = int.parse(stdin.readLineSync()!);

  final n = p * q;

  final phi = (p - 1) * (q - 1);
  final es = findPossibleEs(phi, limit: 10);
  stdout.write("Choose e from ${es}: ");
  final e = int.parse(stdin.readLineSync()!);
  if (!es.contains(e)) {
    print("❌ Invalid selection. Please run again.");
    exit(-1);
  }
  print("ℹ️ Perfect! E is set to $e\n\n");

  final d = findD(e, phi);

  print("Phi is: $phi");
  print("e is: $e");
  print("d is: $d");

  print("\n🔑 Public Key: (e, n) = ($e, $n)");
  print("🔑 Private Key: (d, n) = ($d, $n)");

  stdout.write("\n\nℹ️ Enter message to encrypt: ");
  final m = int.parse(stdin.readLineSync()!);

  // Encrypt the message
  final c = modPow(m, e, n);

  // Decrypt the message
  final dm = modPow(c, d, n);

  print("\nMessage to Encrypt: $m");
  print("Cipher: $c");
  print("Decrypted: $dm");
}

/// Checks if a number is prime
bool isPrime(int n) {
  if (n <= 1) {
    return false;
  }
  for (int i = 2; i <= math.sqrt(n); i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

/// Finds all possible values of e
///
/// Optionally, you can set a limit to the number of possible values
List<int> findPossibleEs(
  int phi, {
  int? limit,
}) {
  List<int> list = [];
  for (int i = 2; i < phi; i++) {
    if (gcd(i, phi) == 1 && isPrime(i)) {
      list.add(i);
      if (limit != null && list.length >= limit) {
        break;
      }
    }
  }
  return list;
}

/// Finds the value of d for given e and phi
int findD(int e, int phi) {
  return modInverse(e, phi);
}

/// Returns the greatest common divisor of two numbers
int gcd(int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

/// Returns the result of a number raised to the power of another number
int modPow(int base, int exponent, int modulus) {
  if (modulus == 1) return 0;
  int result = 1;
  base = base % modulus;
  while (exponent > 0) {
    if (exponent % 2 == 1) {
      result = (result * base) % modulus;
    }
    exponent = exponent >> 1;
    base = (base * base) % modulus;
  }
  return result;
}

/// Returns the modular multiplicative inverse of a number
int modInverse(int a, int m) {
  int m0 = m;
  int y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    // q is quotient
    int q = a ~/ m;
    int t = m;

    // m is remainder now, process same as Euclid's algo
    m = a % m;
    a = t;
    t = y;

    // Update y and x
    y = x - q * y;
    x = t;
  }

  // Make x positive
  if (x < 0) x += m0;

  return x;
}

So, that's it. Here's an example output.

❓ Enter p: 181
❓ Enter q: 191
Choose e from [11, 13, 17, 23, 29, 31, 37, 41, 43]: 43
ℹ️ Perfect! E is set to 43


Phi is: 34200
e is: 43
d is: 15907

🔑 Public Key: (e, n) = (43, 34571)
🔑 Private Key: (d, n) = (15907, 34571)


ℹ️ Enter message to encrypt: 101

Message to Encrypt: 101
Cipher: 14622
Decrypted: 101