Skip to content

Instantly share code, notes, and snippets.

@HeySreelal

HeySreelal/rsa.dart

Last active February 19, 2024 15:29
Show Gist options
  • Save HeySreelal/618cacc30bbea7ea865b76be5a839247 to your computer and use it in GitHub Desktop.
Save HeySreelal/618cacc30bbea7ea865b76be5a839247 to your computer and use it in GitHub Desktop.
Download ZIP
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!
Raw
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;
}
@HeySreelal
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment