[phyrrus9]

EDIT: updated the code:

Code:

#include <gmp.h> #include <stdlib.h> #include <time.h> #include <stdio.h> #define BITWIDTH 8 #define BITWIDTH_E (BITWIDTH) #define PROBABRUN 25 void print_status(mpz_t p, const char *s) { printf("[STATUS] %s=", s); mpz_out_str(stdout, 10, p); printf("\n"); fflush(stdout); } void totient(mpz_t ret, mpz_t p, mpz_t q) { mpz_t pt, qt; mpz_inits(pt, qt, NULL); mpz_sub_ui(qt, q, 1); mpz_sub_ui(pt, p, 1); mpz_mul(ret, pt, qt); mpz_clears(pt, qt, NULL); } char isPrime(mpz_t p) { mpz_t sqrtq, i, tmp; char ret = 1; int probab = mpz_probab_prime_p(p, PROBABRUN); if (probab == 2) return 1; else if (probab == 0) return 0; mpz_inits(sqrtq, i, tmp, NULL); mpz_sqrt(sqrtq, p); for (mpz_set_ui(i, 2); mpz_cmp(i, sqrtq) < 0 && ret == 1;mpz_add_ui(i, i, 1)) { mpz_mod(tmp, p, i); if (mpz_cmp_ui(tmp, 1) == 0) goto isPrimeDone; } isPrimeDone: mpz_clears(sqrtq, i, tmp, NULL); return ret; } void gen_pq(mpz_t r) { gmp_randstate_t rstate; unsigned long seed; gmp_randinit_default(rstate); seed = time(NULL); gmp_randseed_ui(rstate, seed); do { mpz_urandomb(r, rstate, BITWIDTH); } while (!isPrime(r)); gmp_randclear(rstate); } void gen_n(mpz_t n, mpz_t p, mpz_t q) { mpz_mul(n, p, q); //n = p*q } void gen_x(mpz_t x, mpz_t p, mpz_t q) { totient(x, p, q); } void gen_e(mpz_t e, mpz_t x) { gmp_randstate_t rstate; mpz_t i; unsigned long seed; mpz_init(i); gmp_randinit_default(rstate); seed = time(NULL); gmp_randseed_ui(rstate, seed); mpz_urandomb(e, rstate, BITWIDTH_E); mpz_nextprime(e, e); for (; mpz_cmp(e, x); mpz_nextprime(e, e)) { if (isPrime(e)) //this should be true anyways { mpz_mod(i, x, e); if (mpz_cmp_ui(i, 0) != 0) break; else if (mpz_cmp(e, x) > 0) mpz_urandomb(e, rstate, BITWIDTH_E); } } mpz_clear(i); } void gen_d(mpz_t d, mpz_t e, mpz_t x) { mpz_invert(d, e, x); } void *gen_binary(mpz_t r, unsigned long *size) { size_t words_alloc; void *ret = mpz_export(NULL, &words_alloc, 1, 1, 1, 0, r); *size = words_alloc; return ret; } void write_keyfile(char *fname, mpz_t r1, mpz_t r2) { void *r1v, *r2v; unsigned long r1s, r2s; FILE *f; r1v = gen_binary(r1, &r1s); r2v = gen_binary(r2, &r2s); printf("r1s=%lu\tr2s=%lu\n", r1s, r2s); r1s = htonl(r1s); r2s = htonl(r2s); f = fopen(fname, "wb"); fwrite(&r1s, sizeof(unsigned long), 1, f); fwrite(&r2s, sizeof(unsigned long), 1, f); fwrite(r1v, ntohl(r1s), 1, f); fwrite(r2v, ntohl(r2s), 1, f); fflush(f); fclose(f); free(r1v); free(r2v); } int main() { mpz_t p, q, x, n, d, e; mpz_inits(p, q, x, n, d, e, NULL); gen_pq(p); gen_pq(q); print_status(p, "P"); print_status(q, "Q"); gen_n(n, p, q); print_status(n, "N"); gen_x(x, p, q); print_status(x, "t(n)"); gen_e(e, x); print_status(e, "E"); gen_d(d, e, x); print_status(d, "D"); write_keyfile("rsa.pub", n, e); write_keyfile("rsa.pri", n, d); mpz_clears(p, q, x, n, d, e, NULL); }

its obvious it isn't going to calculate D. Looks like E is being computed/validated incorrectly.

Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime.
e is released as the public key exponent.
e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 216 + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.

maybe @0xDEAD10CC or @Reiko or another C programmer can take a look at this?

[0xDEAD10CC]

Firstly, <stdio.h> should be included first. gmp checks for having FILE, and so order does matter. Also, what is htonl? Seems like you're failing to include <winsock2.h>? I changed your includes to this when I first compiled it:

Code:

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <gmp.h> #include <winsock2.h>

Otherwise the macro which resolves to __gmpz_out_str (mpz_out_str) was being implicitly defined.

Also, what is this?

Code:

#define BITWIDTH 8 #define BITWIDTH_E (BITWIDTH)

Why not just have BITWIDTH defined?

Another thing:

Code:

char isPrime(mpz_t p)

You're using C99 obviously, which comes with a <stdbool.h> header for the bool type. However, with that said, the only thing you do with the value to be returned is:

1. Set it to 1

Code:

char ret = 1;

2. Check it against 1

Code:

&& ret == 1

3. And return it

Code:

return ret;

This doesn't make sense.

Furthermore:

Code:

for (mpz_set_ui(i, 2); mpz_cmp(i, sqrtq) < 0 && ret == 1;mpz_add_ui(i, i, 1)) { mpz_mod(tmp, p, i); if (mpz_cmp_ui(tmp, 1) == 0) goto isPrimeDone; } isPrimeDone:

That's the only goto statement for this label... Did you REALLY need a label to make use of a goto here? C still has the break; statement too. :S

There's lots to be fixed as it stands before looking at the actual algorithm and calculations involved.

[phyrrus9]

Firstly, <stdio.h> should be included first. gmp checks for having FILE, and so order does matter. Also, what is htonl? Seems like you're failing to include <winsock2.h>? I changed your includes to this when I first compiled it:

Code:

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <gmp.h> #include <winsock2.h>

Otherwise the macro which resolves to __gmpz_out_str (mpz_out_str) was being implicitly defined.

Also, what is this?

Code:

#define BITWIDTH 8 #define BITWIDTH_E (BITWIDTH)

Why not just have BITWIDTH defined?

Another thing:

Code:

char isPrime(mpz_t p)

You're using C99 obviously, which comes with a <stdbool.h> header for the bool type. However, with that said, the only thing you do with the value to be returned is:

1. Set it to 1

Code:

char ret = 1;

2. Check it against 1

Code:

&& ret == 1

3. And return it

Code:

return ret;

This doesn't make sense.

Furthermore:

Code:

for (mpz_set_ui(i, 2); mpz_cmp(i, sqrtq) < 0 && ret == 1;mpz_add_ui(i, i, 1)) { mpz_mod(tmp, p, i); if (mpz_cmp_ui(tmp, 1) == 0) goto isPrimeDone; } isPrimeDone:

That's the only goto statement for this label... Did you REALLY need a label to make use of a goto here? C still has the break; statement too. :S

There's lots to be fixed as it stands before looking at the actual algorithm and calculations involved.

winsock? who the fuck uses windows. htonl is just so that the endian of the types are the same.

as for that goto, yeah, it should be a break. there was other code there.

Now that you've made your rant on how I program, do you have any ACTUAL help to give or are you just being a troll?

As far as bool vs char, they are the same thing, I prefer to use char (some compilers I use don't have the support for bool, its easier to use one type).

[0xDEAD10CC]

You've marked me as a troll before for providing valid feedback. Btw, no... bool and char are not the same thing:

Code:

#define bool _Bool #define true 1 #define false 0

Using GCC, it's clearly an integer here since numeric literals are by default int. int (32-bit integer) is optimized for the x86 processor. Windows BOOL type does the same thing for this reason. If they don't support bool, then they don't have support for C99, and are probably outdated. You can define your own true and false as similar to above, but this is ALSO the same reason why int is used in ANSI C for booleans (1 and 0).

As for any 'actual' help as you request it. I never seen what your question was or what exactly you were having issues with. You just threw the code out there and asked that others take a look at it.

I did exactly that.

edit: If not winsock, then where are you getting that function from? (ntohl). I don't see <arpa/inet.h> or <winsock2.h> in there.

[phyrrus9]

You've marked me as a troll before for providing valid feedback. Btw, no... bool and char are not the same thing:

Code:

#define bool _Bool #define true 1 #define false 0

Using GCC, it's clearly an integer here since numeric literals are by default int. int (32-bit integer) is optimized for the x86 processor. Windows BOOL type does the same thing for this reason. If they don't support bool, then they don't have support for C99, and are probably outdated. You can define your own true and false as similar to above, but this is ALSO the same reason why int is used in ANSI C for booleans (1 and 0).

As for any 'actual' help as you request it. I never seen what your question was or what exactly you were having issues with. You just threw the code out there and asked that others take a look at it.

I did exactly that.

edit: If not winsock, then where are you getting that function from? (ntohl). I don't see <arpa/inet.h> or <winsock2.h> in there.

The problem is that E and D are not getting generated correctly (ive since fixed one issue, those are the two left).

http://linux.die.net/man/3/htonl

[0xDEAD10CC]

Why are you seeding these random number generators every single time? Do you know how they work? :S You only have to seed it once, meaning you should be keeping a single instance of it instead of generating a seed for a new generator each and every time. Other than that, I tested the values once, and I don't get what you mean about d and e not being calculated correctly.

(d * e) % z == 1 holds true.

Code:

303 * 151 = 45753 / 344 = 133.00290697674419 133 * 344 = 45752 45753 - 45752 = 1

Here's an RSA implementation written using the GMP library too: http://www.opensource.apple.com/source/H.../rsa-gmp.c

[phyrrus9]

Why are you seeding these random number generators every single time? Do you know how they work? :S You only have to seed it once, meaning you should be keeping a single instance of it instead of generating a seed for a new generator each and every time. Other than that, I tested the values once, and I don't get what you mean about d and e not being calculated correctly.

(d * e) % z == 1 holds true.

Code:

303 * 151 = 45753 / 344 = 133.00290697674419 133 * 344 = 45752 45753 - 45752 = 1

Here's an RSA implementation written using the GMP library too: http://www.opensource.apple.com/source/H.../rsa-gmp.c

Just, ignore the shitty programming that has no effect on the output. re-seeding doesn't effect it. If there is an issue in E or D generation, please alert me. That is the only issue I have. I also like to write everything myself without outside code so that I can tune my skills.

[0xDEAD10CC]

Re-seeding with time(NULL) in this case DOES affect it, you'll get all of the same results if you seed with the same value, and in this case, if the time hasn't incremented before you re-seed (a full second hasn't elapsed before you re-seed with the same time value), the result will be the exact same. In fact, I was getting both the same values for P and Q.

Same reason why you typically only call srand() one time; you need to do some more research on random number generators.

Need help with RSA system (C bug likely)

This could hardly be a bug with C and most definitely a bug with your code if it doesn't work the way you want it to...

[phyrrus9]

Re-seeding with time(NULL) in this case DOES affect it, you'll get all of the same results if you seed with the same value, and in this case, if the time hasn't incremented before you re-seed (a full second hasn't elapsed before you re-seed with the same time value), the result will be the exact same. In fact, I was getting both the same values for P and Q.

Same reason why you typically only call srand() one time; you need to do some more research on random number generators.


This could hardly be a bug with C and most definitely a bug with your code if it doesn't work the way you want it to...

By C bug I mean user issue with how the code was written (aka, i dun fucked the code up). MUCH more likely. "Problem exists between leopard and chair" (if you don't get the joke)

---

@DEAD10CC I switched it so that the random state was only seeded once, and it seems that it is working normally now. Will do some intensive testing on it, but looks like it has been solved.

Thanks!