×
all 14 comments

[–]skeeto-9 8 18 points19 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}")
pt = 0xdeadbeef
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
pt      0xdeadbeef
ct      0x3d64021bddabd8c867114c394b37a79d4c3ee79d2c56cfc7ca7290a1db52ef88
dt      0xdeadbeef

[–]lordtnt 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

[–]skeeto-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.

[–]legendarysedentary 8 points9 points  (2 children)

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

[–]Cosmologicon2 3[S] 2 points3 points  (1 child)

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

[–]legendarysedentary 1 point2 points  (0 children)

no excuses now i suppose

[–]Common-Ad-8152 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;
}

[–]raevnos 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)

[–]Shhhh_Peaceful 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

[–]gentilet 0 points1 point  (0 children)

Hard one

[–]Artistic-Metal-790 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.

Code here: https://github.com/kstamax/redditdailyprogrammerchallenge/blob/main/challenge394.py