RSA

The RSA algorithm has an public key which is generated by the multiplication of two prime numbers (p * q). These two prime numbers are the numbers you need to calculate the private key too. The private key is used to decrypt (M = C^d mod N) and the public key to crypt data (C = M^e mod N). The algorithms are often used to share the key with which the data will crypt and decrypt in an symmetric algorithm like the AES and DES. For example this is used to share the keys of the AES algortimus by an ssh connection.

More information: Wikipedia Article on RSA

The security of the RSA depends on the prime numbers p and q. I wrote a demo program that can find out p and q if it knows the public key N and N is not to big. The program is not perfect. It would run faster if it used a text file where a lot of prime numbers were stored. But maybe the code can help others too, and if anyone has an any code improvement proposals, please post it in the RSA forum post.

Code


#include 
#include 
#include 
#include 
#include 

using namespace std;

//Globale Vars
unsigned int usage();
int arraycounter=1;
int prims[9999999];


bool checkprim(int zahl)
{
 
  for(int u=0; u   {
   if(zahl % prims[u] == 0)
    return false;
  }
  prims[arraycounter]=zahl;
  arraycounter++;
  //If array is full
  if(arraycounter==99999999)
   {
     cout << "Fehler: Array ist voll. Programm wurde beendet ";
     exit(1);                      
   }
  //If for has not exit this function return true
  return true;

}

// Check if that digits cab be divided
bool check_divisible(int denom, int count)
 {
      
    int solution_division=0;
    if (denom < count)
    {
    
     exit(1);            
    }
    if(denom % count == 0)
     {
      
        solution_division = (denom / count) ;
        for (int counter=0; counter <= arraycounter; counter++)
         {      
            
            if (prims[counter] == solution_division) return true;
          }
          printf("n Digitl %d is not a prime", solution_division);       
     } 
    else 
    {
       printf("n Digit %d can not be divided by  %d ", denom, count);
      return false;
    } 
     
 } 

int main (int argv,char* argc[])
 {
    unsigned int digit;
    bool return_value;
  
    if (argv < 2)
      digit = usage();   
    else
     digit=atoi(argc[1]);
     
    int cached_digit=digit;
    digit=(digit/2)+1;
    
    prims[0]=2;
    
    for(int i=3; i<=digit; i++)
     checkprim(i);
     
     
     digit=cached_digit;
    for(int i=0; i<=arraycounter; i++)
     {
           return_value=check_divisible(prims[i], digit);    
         if (return_value == true)
          {
            int solution=(digit/prims[i]);
            printf("n n p: %d n q: %d n N=p*q= %d", solution,prims[i], digit);
            break;
          }
          
     }
    
     
     
         
    system("pause");     
    return 1;     
         
  }
  
  
  
  
unsigned int usage()
 {
           
  int input;
  cout <<"Usage [name] [Public Key N]n n: Please enter the Public key N (p *q) ";
  cin >> input;             
  return input;
 }