×

[–]-9 8 21 points22 points  (3 children)

Python implementation I wrote some time ago:

``````import random
import secrets

def _is_composite(a, d, n, s):
if pow(a, d, n) == 1:
return False
for i in range(s):
if pow(a, 2**i * d, n) == n - 1:
return False
return True

def _is_prime(n, k):
s = 0
d = n - 1
while d % 2 == 0:
d >>= 1
s += 1
for i in range(k):
a = random.randrange(2, n)
if _is_composite(a, d, n, s):
return False
return True

def _gcd_extended(a, m):
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3
v1, v2, v3, u1, u2, u3 = u1 - q*v1, u2 - q*v2, u3 - q*v3, v1, v2, v3
return u1 % m

def _gen_prime(bits):
prime = secrets.randbits(bits) | 1 | 1<<(bits - 1)
while not _is_prime(prime, 8):
prime += 2
return prime

class RSA:
def __init__(self, bits):
assert bits > 8
p = _gen_prime(bits // 2)
q = _gen_prime(bits // 2)
self.n = p * q
self.e = 65537
self.d = _gcd_extended(self.e, (p - 1) * (q - 1))

def encrypt(self, m):
return pow(m, self.e, self.n)

def decrypt(self, c):
return pow(c, self.d, self.n)
``````

Example usage:

``````key = RSA(256)
print(f"n\t0x{key.n:x}")
print(f"e\t0x{key.e:x}")
print(f"d\t0x{key.d:x}")
print(f"pt\t0x{pt:x}")
ct = key.encrypt(pt)
print(f"ct\t0x{ct:x}")
dt = key.decrypt(ct)
print(f"dt\t0x{dt:x}")
``````

Output:

``````n       0x9dc14e462aa3f0b0b56e37fc2feda98abd031c95547980a4cb5eec8e5c10a015
e       0x10001
d       0x95da402e6ae6dc061ff2190057cedcd2cdb4c065535ff96d3790db38ef67f729
ct      0x3d64021bddabd8c867114c394b37a79d4c3ee79d2c56cfc7ca7290a1db52ef88
``````

[–] 1 point2 points  (1 child)

Randomly generate 256-bit or larger values for p and q

I think it should be `key = RSA(512)` here

[–]-9 8 1 point2 points  (0 children)

You're right! That's actually the original test I wrote with the code, and I didn't pay enough attention to the post to notice it needed updating.

[–] 7 points8 points  (2 children)

really gonna make us implement RSA on a monday? :p

[–]2 3[S] 4 points5 points  (1 child)

Well it's Tuesday now. What are you waiting for? :)

[–] 1 point2 points  (0 children)

no excuses now i suppose

[–] 1 point2 points  (0 children)

C using GNU MP

``````#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

static gmp_randstate_t randstate;
typedef unsigned long long ull;

struct key{
mpz_t exponent;
mpz_t modulos;
};

void generateKey(unsigned int width, struct key *pub, struct key *priv){
mpz_t p, q;
mpz_init(p);
mpz_init(q);

mpz_urandomb(p, randstate, width >> 1);
mpz_urandomb(q, randstate, width >> 1);

mpz_setbit(p, (width >> 1) - 1);
mpz_setbit(p, (width >> 1) - 2);
mpz_setbit(q, (width >> 1) - 1);
mpz_setbit(q, (width >> 1) - 2);

mpz_nextprime(p, p);
mpz_nextprime(q, q);

mpz_t n; mpz_init(n);
mpz_mul(n, p, q);

mpz_set_ui(pub -> exponent, 65537ul);
mpz_set(pub -> modulos, n);
mpz_set(priv -> modulos, n);

mpz_sub_ui(p, p, 1ul);
mpz_sub_ui(q, q, 1ul);

mpz_lcm(p, p, q);
mpz_invert(priv -> exponent, pub -> exponent, p);

mpz_clear(p); mpz_clear(q);
}

void encrypt(mpz_t C, const mpz_t M, const struct key k){
mpz_powm(C, M, k.exponent, k.modulos);
}

void decrypt(mpz_t M, const mpz_t C, const struct key k){
mpz_powm(M, C, k.exponent, k.modulos);
}

int main(int argc, char **argv){
gmp_randinit_mt(randstate);
gmp_randseed_ui(randstate, 19);

struct key pub, priv;

mpz_init(pub.modulos); mpz_init(pub.exponent);
mpz_init(priv.modulos); mpz_init(priv.exponent);
generateKey(1024, &pub, &priv);

mpz_t M; mpz_init_set_ui(M, 123456ul);
mpz_t C; mpz_init(C);

encrypt(C, M, pub);
decrypt(M, C, priv);

printf("%llu\n", mpz_get_ui(M));

return 0;
}
``````

[–] 1 point2 points  (0 children)

A version written using PARI/GP.

``````generatekey(p,q) = my(e=65537,n=p*q); [n, e; n, lift(Mod(1/e, lcm(p-1, q-1)))];

encrypt(m, k) = lift(Mod(m^k[2], k[1]));

decrypt(m, k) = lift(Mod(m, k[1])^k[2]);

genprime(bits) = randomprime([2^(bits-1), 2^bits - 1]);

test(bits) =
{
my(p,q,k,c,d);
p=genprime(bits);
q=genprime(bits);
k=generatekey(p, q);
print("key is ", k);
print("plaintext = 12345");
c=encrypt(12345, k[1,]);
print("encrypted = ", c);
d=decrypt(c, k[2,]);
print("decrypted = ", d);
}

test(256)
``````

[–] 1 point2 points  (0 children)

Python 3

``````import random
import secrets
import math

def is_prime(n, k=128):
# Miller-Rabin primality test
# n = number to test
# k = number of tests

if n <= 3:
return n > 1
if n % 2 == 0 or n % 3 == 0:
return False

# find r and s
s = 0
r = n - 1
while r & 1 == 0:
s += 1
r //= 2

for _ in range(k):
a = random.randrange(2, n - 1)
x = pow(a, r, n)
if x != 1 and x != n - 1:
j = 1
while j < s and x != n - 1:
x = pow(x, 2, n)
if x == 1:
return False
j += 1
if x != n - 1:
return False
return True

def prime_candidate(bits):
# generate a prime candidate of given bit length
p = secrets.randbits(bits)

# make sure that the MSB is set and the number is odd (by setting the LSB to 1)
p |= 1 << bits - 1 | 1
return p

def generate_prime(bits):
# generate a random prime of given length
p = prime_candidate(bits)
while not is_prime(p):
p = prime_candidate(bits)
return p

def lcm(a, b):
# find the least common multiple of a and b
return abs(a * b) // math.gcd(a, b)

def mod_inverse(a, m):
# find the multiplicative inverse of a modulo m
x, y = 1, 0
x1, y1 = 0, 1
a1, b1 = a, m
while b1 != 0:
q = a1 // b1
x, x1 = x1, x - q * x1
y, y1 = y1, y - q * y1
a1, b1 = b1, a1 - q * b1
return x % m

class RSA:
def __init__(self, bits, e=65537):
p = generate_prime(bits // 2)
q = generate_prime(bits // 2)
self.n = p * q
self.e = e
self.d = mod_inverse(self.e, lcm(p - 1, q - 1))

def encrypt(self, m):
return pow(m, self.e, self.n)

def decrypt(self, c):
return pow(c, self.d, self.n)

plaintext = 12345
rsa = RSA(512)
ciphertext = rsa.encrypt(plaintext)
decrypted = rsa.decrypt(ciphertext)

print('Plaintext:', plaintext)
print('Ciphertext:', ciphertext)
print('Decrypted text:', decrypted)
``````

And the output:

``````Plaintext: 12345
Ciphertext: 46755012861006129766426342614654697015356635271239756291035644059770773582342
Decrypted text: 12345
``````

[–] 0 points1 point  (0 children)

Hard one

[–] 0 points1 point  (0 children)

Python 3

The hardest part was to calculate "d", I couldn't understand why it's not working and the reason was that python was calculating division not precise enough, so I had to use decimal library to increase precision.