Skip to content

Instantly share code, notes, and snippets.

@Oshawk Oshawk/rsa.dart
Last active Oct 24, 2018

Embed
What would you like to do?
A simple RSA implementation in Dart!
import 'dart:math';
BigInt randomBigInt(Random rng, int bitLength) {
BigInt bigInt = BigInt.zero;
for (int i = 0; i < bitLength; i++) {
if (rng.nextBool()) {
bigInt = (bigInt << 1) + BigInt.one;
} else {
bigInt = bigInt << 1;
}
}
return bigInt;
}
bool isPrime(Random rng, BigInt w, int iterations) {
if (w.isEven) {
return false;
}
int a = 0;
BigInt m = w - BigInt.one;
while (m.isEven) {
m = m >> 1;
a += 1;
}
for (var i = 0; i < iterations; i++) {
BigInt b = BigInt.zero;
while ((b <= BigInt.one) || (b >= (w - BigInt.one))) {
b = randomBigInt(rng, w.bitLength);
}
BigInt z = b.modPow(m, w);
if ((z != 1) && (z != (w - BigInt.one))) {
bool broken = false;
for (int j = 0; j < (a - 1); j++) {
z = z.modPow(BigInt.two, w);
if (z == BigInt.one) {
return false;
} else if (z == (w - BigInt.one)) {
broken = true;
break;
}
}
if (!broken) {
return false;
}
}
}
return true;
}
List<BigInt> genPQ(Random rng, int nLen, BigInt e) {
BigInt p = BigInt.zero;
while ((!isPrime(rng, p, 5)) || ((p - BigInt.one).gcd(e) != BigInt.one)) {
p = BigInt.zero;
while (p < (((BigInt.two.pow((nLen ~/ 2) - 1))
~/ BigInt.from(70)) * BigInt.from(99))) {
p = randomBigInt(rng, nLen ~/ 2);
if (p.isEven) {
p = p + BigInt.one;
}
}
}
BigInt q = BigInt.zero;
while ((!isPrime(rng, q, 5)) || ((q - BigInt.one).gcd(e) != BigInt.one)) {
q = BigInt.zero;
while (((p - q).abs() <= BigInt.two.pow((nLen ~/ 2) - 100)) ||
(q < (((BigInt.two.pow((nLen ~/ 2) - 1)) ~/
BigInt.from(70)) * BigInt.from(99)))) {
q = randomBigInt(rng, nLen ~/ 2);
if (q.isEven) {
q = q + BigInt.one;
}
}
}
return <BigInt>[p, q];
}
void main() {
Random rng = new Random.secure();
BigInt e = BigInt.from(pow(2, 16) + 1);
print('e -> $e');
List<BigInt> pq = genPQ(rng, 2048, e);
BigInt p = pq[0];
BigInt q = pq[1];
print('p -> $p');
print('q -> $q');
BigInt n = p * q;
print('n -> $n');
BigInt k = BigInt.one;
while (((k * ((p - BigInt.one) * (q - BigInt.one))) + BigInt.one)
.remainder(e) != BigInt.zero) {
k = k + BigInt.one;
}
BigInt d = ((k * ((p - BigInt.one) * (q - BigInt.one))) + BigInt.one) ~/ e;
print('d -> $d');
print('');
print('Test with message 42:');
BigInt ct = BigInt.from(42).modPow(e, n);
print('c -> $ct');
BigInt mt = ct.modPow(d, n);
print('m -> $mt');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.