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 = pow(M,e)mod n. Why are you using a for loop for this ?
Similarly in the decrypt use the formula M = pow(C,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
}