Bruteforce

[oskarvonephesos]

Hi!

This isn't really a bug in the code, but since I have been contributing some code to this repository, I thought it might be important to stress just how far this is from being secure. This really is purely for educational purposes!

I have attached a simple file that generates a key-pair and then times how long it takes to figure out the private key from the public key (actually it just factors the primes, but getting from the primes to the private exponent really is trivial). Running it on my laptop takes less than a ms.

Theoretically the primes.txt file could be modified to include larger primes, but the bottom line is: you won't be able to generate 1024-bit primes using C's built-in data types (that max out at 64 or 80 bits).

//save this as bruteforce.c and
//compile this using gcc rsa.c bruteforce.c -o bruteforce
#include <stdio.h>
#include "rsa.h"
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include <sys/time.h>

int main(){

      struct public_key_class* pub = (struct public_key_class *)malloc(sizeof(struct public_key_class));
      struct private_key_class* priv = (struct private_key_class*)malloc(sizeof(struct private_key_class));
      rsa_gen_keys(pub, priv, PRIME_SOURCE_FILE);
      struct timeval before, after, difference;
      uint64_t i = (uint64_t) sqrt((double)pub->modulus), j;
      uint64_t modulus = (uint64_t) pub->modulus;
      gettimeofday(&before, NULL);
      while (1){
            j = modulus/i;
            if (j * i == modulus){
                  break;
            }
            i--;
      }
      gettimeofday(&after, NULL);
      timersub(&after, &before, &difference);
      printf("Time elapsed: %ld.%06lds\n", (long int)difference.tv_sec, (long int)difference.tv_usec);
      printf("p: %llu q: %llu\n", j, i);
      printf("calculated modulus: %llx\n", j*i);
      printf("modulus was: %llx\n", pub->modulus);
      return 0;
}