andrewkiluk / rsa-library Goto Github PK

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;
}

Hi, I'm looking for a leight weight rsa library and this surely is one.

But can it handle keys with 2048 bits? The key classes only handles long long modulus?

struct public_key_class{
  long long modulus;
  long long exponent;
};

I'm trying to find out the values to use with this command:

openssl rsa -pubin -inform PEM -text -noout < ../qep/scripts/usb_flash/public.pem 
Public-Key: (2048 bit)
Modulus:
    00:d5:f5:ae:6f:8c:3d:34:f6:da:05:91:d0:50:ad:
...some lines rmoved...
    dc:99
Exponent: 65537 (0x10001)

Hello,
I don't know it it was just me, but when I tried to use this code in C++, it kept crashing in the rsa_modExp function. After hours of debugging, I found this line of code:
long long *encrypted = malloc(sizeof(long long)*message_size);
This seemed suspicious to me, so I decided to change it to:

long long *encrypted; 
encrypted = (long long*)malloc(sizeof(long long)*message_size);

(this kind of code appeared multiple times, I changed it everywhere)
and suddenly, the code started working.

EDIT: Unfortunately, after further testing, it keeps crashing completely randomly.

Edit:
As shipof123 says, there is problem with rsa_modExp function, which is exiting when:
(b < 0 || e < 0 || m <= 0)

Everything compiles fine, but sometimes output of test.c is only showing half of prints:
primes are 74077 and 71537 Private Key: Modulus: 5299246349 Exponent: 3525860801 Public Key: Modulus: 5299246349 Exponent: 257 Original: 49 50 51 97 98 99

instead of:

primes are 25463 and 24793 Private Key: Modulus: 631304159 Exponent: 363523649 Public Key: Modulus: 631304159 Exponent: 257 Original: 49 50 51 97 98 99 Encrypted: 436385454 7093305 328497852 488616667 550174409 97597229 Decrypted: 49 50 51 97 98 99

Any solution?

Thank you for this awesome library. I'm afraid I can't use it on my opensource project yet unless I know the its license. Do you plan to update it and add license file?

Regards
-- sora

Hi, this lib is very 'clean' !

1. is openssl compatible ?

I'm interested in utilising your library for a small project of mine, but being new to GitHub, I have no idea how to install/implement your library so that if run your test.c, it includes rsa.h and compiles properly on all - VS 2019, Apple Clang, and GCC ....

Guide me !

I can't quite work it out from the source code, thanks!

in rsa_modExp in rsa.c, it seems there is a check for integer overflow (checking for negative numbers) that leads to an exit. It would be great to at least print out a warning when that happens. Would you consider reworking this function and integrating a bignums library instead of using long longs? If you want me to try that and see if it prevents the intermittent overflow crashes, let me know.