Brute Force

[mystb]

Hi,

I need to find p,q and e values for RSA. Here is a simple & 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. 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 for loops (p,q,e) but no luck. I really need your help.

Thanks.

My code so far: #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;
}

[abhimanipal]

Then to encrypt you use the formula C[i] = pow(M[i],e)mod n. Why are you using a for loop for this ?
Similarly in the decrypt use the formula M[i] = pow(C[i],d). You dont need the for loop for that

[mystb]

t gives invalid operands to binary %. Error. It can be wait my priority is how can i create a nested loop and compare result to a word list.

My nested loop:

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

[abhimanipal]

Does this help ?

while(true)
{
    //Generate a permutation of the word
    // Compare it to the dictionary
    //if there is a match then break
    //else go for another iteration
}