Thread: RSA Decryption - Need Help!

Hiya,
I was here yesterday requestiong help with Integers because I wasnt able to calculate large numbers to Decrypt RSA message.

I was advised to get the GMP library which I did but some how I am still not making progress after spending all day at it today as well. Whenever I debug/run the program I get an error saying the program has stopped. My best guess is that I am running out of buffer but that should be the case since I am using GMP Library.

I have tried it with 3 digit numbers as well but still no use.

I would appreciate any kind of guidance.

Code:

#include <stdio.h>
#include <gmp.h>
//c = 14608026857865359,
//n = 2639496137
//d = 160772669
//m = (c ^ d) % n
//e = 197
//p = 21383
//q = 123439
//Origiional Text = hello
  
 int main(void)
 {
     mpz_t d,n,c,m; // c = Encrypted Text(cipher), n = Secret Key, d = Publick Key, m = decrypted cipher.
    /* init ints */
     mpz_init(d);
     mpz_init(n);
     mpz_init(c);
     mpz_init(m);

     printf("Please Enter The Public Key: ");
     scanf("%d", d);
     printf("\nPlease Enter The Private Key: ");
     scanf("%d", n);
     printf("\nPlease Enter The Encrypted Message: ");
     scanf("%d", c);

     /* m = (c^d) % n ... RSA decryption */
     mpz_powm(m,c,d,n);
     printf("Your Decrypted Message Is: %d", m);
 return 0;
 }

Thanks for your help in advance.

Never used GNU's Bignum library, but my first guess would be that scanf and printf %ds probably don't work with the massive ints defined in the bignum library.

That aside...one of the more obvious mistakes on all of your scanfs:

Code:

scanf("%d", d);

should be

Code:

scanf("%d", &d);

Originally Posted by Epy

Never used GNU's Bignum library, but my first guess would be that scanf and printf %ds probably don't work with the massive ints defined in the bignum library.

That aside...one of the more obvious mistakes on all of your scanfs:

Code:

scanf("%d", d);

should be

Code:

scanf("%d", &d);

Thanks for pointing that out, I hvae installed the openssl library as well see if I can get soemthing out of that, still no use. I am meeting a friend tomorrow who is far better than me I'll ask him, see if he has a solution.

thanks

You can use gmp's own printf-like functions to print an mp*_t. For mpz_t, you can do something like:

Code:

gmp_printf("Your decripted message is: %Zd\n", m);

Otherwise, you can do it by hand, first checking if it fits into a regular integer with mpz_fits_ulong_p, and using mpz_get_ui if it does, or by exporting it as a string if doesn't with mpz_get_str.

I hope that is not the entire code. For your consideration your function mpz_powm(m,c,d,n); is only sending cdn and missing m. also mpz_init(d); and mpz_int[d]; are two different things.

It looks like the problem (as stated before) is the scanf and printf:

Code:

#include <stdio.h>
#include <gmp.h>
//c = 14608026857865359,
//n = 2639496137
//d = 160772669
//m = (c ^ d) % n
//e = 197
//p = 21383
//q = 123439
//Origiional Text = hello
  
 int main(void)
 {
     mpz_t d,n,c,m; // c = Encrypted Text(cipher), n = Secret Key, d = Publick Key, m = decrypted cipher.
    /* init ints */
     mpz_init(d);
     mpz_init(n);
     mpz_init(c);
     mpz_init(m);

     printf("Please Enter The Public Key: ");
     scanf("%d", d);
     printf("\nPlease Enter The Private Key: ");
     scanf("%d", n);
     printf("\nPlease Enter The Encrypted Message: ");
     scanf("%d", c);

     /* m = (c^d) % n ... RSA decryption */
     mpz_powm(m,c,d,n);
     printf("Your Decrypted Message Is: %d", m);
 return 0;
 }

Gave output:

Please Enter The Public Key: 160772669

Please Enter The Private Key: 2639496137

Please Enter The Encrypted Message: 14608026857865359
Your Decrypted Message Is: 250150506


I basicly changed scanf,printf to gmp_scanf,gmp_printf, %d to %Zd, no pointers to gmp_scanf (see Formatted Input Strings - GNU MP 4.3.0)

By the way, bmp is really optimized for this kind of stuff. I know that haskell isn't really fast and furious but it can also handle large number out of the box. I have been running the same calculation for minutes without an answer:
Hugs> (14608026857865359^160772669) `mod` 2639496137

but the c program finishes before two seconds. I think haskell is trying to compute 14608026857865359^160772669 which probably finishes after the sun eats the earth! Might be a better way to compute this.