 Gcoco Jii - 3 years ago 251
C Question

# How to make RSA that works with bigger p and q value?

My project was to implement RSA using the skeleton which is written in C given by the lecturer himself. I'm not that familiar with C but was able to do it. But the problem is it only works when it is in the condition of:

p<200 and q<200
When the value exceeds that, it fails. I want to make p and q bigger than that numbers. Is there something wrong with my code that causes it only to works or successful when it is only p and q is less than 200.

``````//unsigned int
uint p, q, e, d, n;
``````

Function for modular exponentiation when encrypt/decrypt:

``````uint ModPow(uint base, uint exp, uint n) {
uint h;
uint r;
int bin;
int i;

r=base;
i=0;

while(exp > 0)
{
if(exp%2 == 0)
{
bin[i] = 0;
}else{
bin[i] = 1;
}
exp = exp/2;
i++;
}
i--;
while(i>0)
{
r = (r*r)%n;
if(bin[--i]==1)
{
r = (r*base)%n;
}
}
printf("r:%d n:%d\n", r,n );
return r;
}
``````

Function to check GCD(a,b):

``````uint GCD(uint a, uint b) {
uint prev_a;

while(b != 0) {
printf("GCD(%u, %u)\n", a, b);
prev_a = a;
a = b;
while(prev_a >= b) prev_a -= b;
b = prev_a;
}
printf("GCD(%u, %u)\n\n", a, b);
return a;
}
``````

Using Extended Euclidean Algorithm to find d

``````uint ModInv(uint a, uint m) {
int m0 = m, t, q;
int x0 = 0, x1 = 1;

if(m==1)
return 0;

while(a>1)
{
q = a/m;
t = m;
m = a%m, a=t;
t=x0;
x0=x1-q*x0;
x1=t;
}
if(x1<0)
x1+=m0;
return x1;
}
``````

generate key, this one I use p=23, and q=17

``````void miniRSAKeygen(uint *p, uint *q, uint *e, uint *d, uint *n) {
*p =23;
*q = 17;
*n = (*p)*(*q);
*e = 2;
unsigned long long phi = (*p-1)*(*q-1);
printf("Phi %llu\n",phi);
while(*e<phi)
{
if(GCD(phi,*e)==1)
break;
else
*e = *e + 1;
}
*d = ModInv(*e,phi);
}
``````

Encrypt/Decrypt

``````uint miniRSA(uint data, uint key, uint n) {
unsigned long long result;
result = ModPow(data,key,n);
printf("%llu\n", result );
return result;
}
``````

This is the main function:

``````int main(int argc, char* argv[]) {
uint plain_data, encrpyted_data, decrpyted_data;
uint seed = time(NULL);
plain_data = 201;

// create random number with seed
seed = time(NULL);
InitWELLRNG512a(&seed);

// create RSA key
miniRSAKeygen(&p, &q, &e, &d, &n);
printf("0. Key generation is Success!\n ");
printf("p : %u\n q : %u\n e : %u\n d : %u\n N : %u\n\n", p, q, e, d, n);

// test RSA encryption
encrpyted_data = miniRSA(plain_data, e, n);
printf("1. plain text : %u\n", plain_data);
printf("2. encrypted plain text : %u\n\n", encrpyted_data);

// test RSA decryption
decrpyted_data = miniRSA(encrpyted_data, d, n);
printf("3. cipher text : %u\n", encrpyted_data);
printf("4. Decrypted plain text : %u\n\n", decrpyted_data);

// print result
printf("RSA Decryption: %s\n", (decrpyted_data == plain_data) ? "SUCCESS!" : "FAILURE!");

return 0;
}
``````

What seems to be the problem here? Thanks in advance.
The failure here is that when the encrypted value does not return to the value of plaintext when decrypted.

This is the example of the result:

failed one

success one James K Polk

On your system `uint` is a 32-bit unsigned type. If p and q are greater than 255 (28-1) then n = p*q is greater than or equal to 216. That means that the intermediate calculation `r*r` may end up greater than 232 - 1 in the line `r = (r*r)%n;`. Unsigned integer overflow is silent and only the low-order 32-bits (for a 32-bit unsigned type) will be retained, which loses information and will result in an incorrect answer. A similar problem occurs in the line `r = (r*base)%n;`.

The solution is firstly to not take arithmetic for granted. That's part of your maturation as a programmer. Secondly, you can use a wider type for the intermediate results to solve the problem. For example, you can make a simple mod_mul function:

``````#include  <stdint.h>

uint mod_mul(uint a, uint b, uint n) {
uint64_t result = ((uint64_t) a) * ((uint64_t) b) % ((uint64_t) n);
return (uint) result;
}
``````

This works because the intermediate arithmetic is carried out with 64-bit arithmetic, and since we know the result is less than 232 the final (uint) cast result in no loss of information.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download