Thread: RSA Decryption - Brute Force

1. RSA Decryption - Brute Force

Hi everyone,

I am working a project for RSA Algorithm. I need to encrypt/decrypt messages for certain p,q,e values. I have done that. (Even though it was hard). Now what i need help is about finding these p,q,e values. Here is a short description of RSA:

Your enter a word (actually it is a sentence but for now a word) then program will convert letters to numbers (like a=1 m=13 etc.) and group them. Use with all given values n=pq (n is the modulus). C=(m^e) (mod n ) where C is encrypted message m is numbers (converted from letters).
I can decrypt for known values of p,q,e as i said. But i can't find these values. Here are the steps:

1. Enter encrypted message.
2. Program will try all combinations of p,q,e.
3. For every combination it will check if decrypted message is in the wordlist.(There will be a wordlist containing 50 words)
4. If a word is found it will show p,q,e values. Else it will continue to try until p,q,e all equals to 100.
5. If still no result, program will stop.

I did 3 nested for loops (p,q,e) but no luck. I really need your help.

Thanks.

My code so far:

Code:
```#include<stdio.h>
#include<conio.h>

int main(void)
{
long int p,q,e,n,inv,s=0,d=1,C[100],M;
char m[100];
unsigned long int c;
int i,j,t;
printf("Enter the value of p and q: ");
scanf("%d%d",&p,&q);
n=p*q;
inv=(p-1)*(q-1);
printf("\nEnter the e value: ");
scanf("%d",&e);
do
{
s=(d*e)%inv;
d++;
}while(s!=1);
d=d-1;
printf("\nEnter the message to encrypt:");
scanf("%s",&m);
for(j=0;j<strlen(m);j++)
{
m[j]=tolower(m[j]);
t=m[j]-96;
c=1;
for(i=0;i<e;i++)
c=c*t%n;
c=c%n;
printf("%d ",c);
}
printf("\n\nEnter encrypted message to decrpyt :\n");
for(i=0;i<strlen(m);i++)
scanf("%d",&C[i]);
printf("\n\nDecrypted (original) message: ");
for(j=0;j<strlen(m);j++)
{
M=1;
for(i=0;i<d;i++)
M=M*C[j]%n;
M=M%n;
M=M+96;
printf("%c",M);
}
getch();
return 0;
}```

2. There's almost nothing here, in the decrypt portion:
Code:
```    printf("\n\nEnter encrypted message to decrpyt :\n");
for(i=0;i<strlen(m);i++)
scanf("%d",&C[i]);
printf("\n\nDecrypted (original) message: ");
for(j=0;j<strlen(m);j++)
{
M=1;
for(i=0;i<d;i++)
M=M*C[j]%n;
M=M%n;
M=M+96;
printf("%c",M);
}```
And I see only two nested for loops in it, not three. There's no mention of any range being tested for the values of your variables, there is no code to compare the resulting trial decrypt to any 50 word word list, etc.

Why don't you write out what you need to do, in plain English, step by step? Then put up the code to match that English description.

You can use other functions as well, to help simplify the logic. Another function to test the trail decrypt seems like a good way to go.

3. Yes this is my original one. It works if you enter p,q,e values and encrypted message. It succesfully decrypts it. I didn't send 3 nested loops because it wasn't working but it was:

Code:
```for (p=2;p<100;p++)
{
for (q=2;q<100;q++)
{
n=p*q;
inv=(p-1)*(q-1);
for (e=2;e<100;e++)
{
do
{
s=(d*e)%inv;
d++;
}while(s!=1);
d=d-1;
for(j=0;j<strlen(m);j++)
{
M=1;
for(i=0;i<d;i++)
M=M*C[j]%n;
M=M%n;
M=M+96;
printf("%c",M);
}
}
}
}```
The problem is it somehow doesn't work. Am i missing something? And how can i compare result to words from a text file?

Thanks

4. But you're not doing that problem, any more!

Use if((strcmp(string1, string2)) == 0), to see if your trial text, matches a word (which I would read into a 2D char array, and not read from a file every time a check is needed).

I'd also suggest using a binary search to try and find the word. That speeds everything up, but also means you need to sort the words so the binary search will work.

That's really simple to do, btw. What's not simple, is to get this logic down for the RSA brute force. I don't know enough about it to give you great advice, on that aspect of it.

I suggest you take a very simple word, say "ball", and encrypt it, then work thru the logic to brute force it, and see what logic is needed.

5. Thanks for your reply Adak. I am now getting the idea. I changed loops to this.

Code:
```for (p=2;p<100;p++)
{
for (q=2;q<100;q++)
{
n=p*q;
inv=(p-1)*(q-1);
for (e=2;e<100;e++)
{
do
{
s=(d*e)%inv;
d++;
}while(s!=1);
d=d-1;
for(j=0;j<strlen(m);j++)
{
M=1;
for(i=0;i<d;i++)
M=M*C[j]%n;
M=M%n;
M=M+96;
h[j]=M;
}
if((strcmp(h, words)) == 0) //words is the 2d array you mentioned.
printf("p is %d, q is %d, e is %d",p,q,e);
}
}
}```
But still it doesn't work. After i enter a number to decrypt it just hangs there, nothing happens. any idea why? And also could you help me about using 2d arrays? How should i store words to it and check? Also performance isn't important right now, since if don't get this working until tomorrow i'll have serious problems with professor.

6. Your brute force code makes no sense to me, because I don't know the RSA encryption algorithm, and can't make heads or tails out of your code.

When you brute force something, you work through the range of it's answer set, trying every value. I don't see that range being defined or used, in your code.

There is no way I can help you get this ready. I'd suggest you post your problem on the newsgroup that deals with encryption, and any forums that you can find that deal with encryption, and hope someone there is familiar with RSA, and willing to help.

While you're waiting, read a tutorial on opening a text file, if you have forgotten. I'm willing to help correct your code syntax, and your logic if I can, but I can't correct logic that I don't know, or correct syntax that you don't have.

Usually, words would be a 2D char array:

Code:
```/* holds 50 words, max word length of 49 letters. Set to empty, to start.
char words[50][40] = { { '\0' } };