rsa.cpp

用C++实现rsa算法

// rsa.cpp : Defines the entry point for the console application.
//

// rsa.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

// RSA.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include <iostream>
#include "math.h"
using namespace std;
int getD(long Fn,long e)
{
    int  i, j, x, y,b,a,c;
    long xx, yy;
    x=0,y=1,xx=1,yy=1;
	c=Fn;
    while(e)
    {
        i=Fn / e;   //i is maximum multiple 
        j=Fn % e;   //j is remainder 
        Fn=e;
        e=j;
        j=y;
        y*=i;
        if(xx == yy)
        {
            if(x > y)
            {
                y=x - y;
            }
            else
            {
                y-=x;
                yy=0;
            }
        }
        else
        {
            y+=x;
            xx=1 - xx;
            yy=1 - yy;
        }        x=j;
    }    
	if(xx == 0)
    {
        x=Fn - x-1;
    }   

	if(x<0)
	{
	printf("private is negative number is %d\n",x);
	return 0;
	}
    return(x);
}

int gcb(int a,int b){
    int r;
    while(b!=0)
	{
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int prime(int a)                   //check whether p and q is prime or not.
{
	int i,p;
	for(i=2;i<a;i++)
    {

			p=a%i;
			while(p==0)
			{
			    printf("this is not a prime,please enter a new prime\n");
				return 0;
			}
	
	}
    return 1;
}


int main()
{   
	long long Fn,e,n,cyphertext,plaintext;
    long p,q,mm,nn,k=1,d=0,hh,y=0,pp=0;
    long test=0;
	int sum=1;
	int z=1;
	int kk=1;
	FILE *fp1;
	fp1=fopen("outfile.txt","w");
	while(d<=0)
	{    if(y==1) 
             { 
               goto loop; 
             } 
			 if(y==2)
			 {
				 goto secondloop;
			 }

          


	loop:test=0;
		while(test==0)
		{
			printf("please input p\n");
			scanf("%d",&p);
			test=prime(p);
		}
		test=0;
		while(test==0)
		{
			printf("please input q\n");
			scanf("%d",&q);
			test=prime(q);
		}
	
	

secondloop:printf("please input public key\n");
		scanf("%d",&e);
		mm=e;
		Fn=(p-1)*(q-1);
		n=p*q;
		if(mm>=Fn)
		{
		printf("you must enter public key ie less than Fn\n");
		printf("if you want to change Fn,please enter 1,if you want to change e, you can enter 2\n");
		scanf("%d",&y);
		}
		else
		{
		
		hh=gcb(Fn,e);
		if(hh!=1)                                           //check relation of between Fn and e 
		{
			printf("error,because e is not relatively prime to Fn\n");
		    	printf("if you want to change Fn,please enter 1,if you want to change e, you can enter 2\n");
		scanf("%d",&y);
		}
		else
		{
			
			d=getD(Fn,e);//get private key
			if(d<=0)
			{
				printf("private key is negative number,so can not calculate\n");
				printf("if you want to change Fn,please enter 1,if you want to change e, you can enter 2\n");
		scanf("%d",&y);
			}
		}	
		}
		
	
	
	}
    fprintf(fp1,"p is %d\n",p);
	fprintf(fp1,"q is %d\n",q);
	fprintf(fp1,"public key is %d\n",e);
	fprintf(fp1,"private key is %d\n",d);
	printf("private key is %d\n",d);
thirdloop:	printf("please input plaintext,only one number\n");
	scanf("%d",&plaintext);
	mm=plaintext;
    if(mm>=n)
	{
	printf("according to my algorithm,plaintext are not either equal or greater than P times Q\n");
	printf("if plaintext are either equal or greater than P times Q,result will be faulty\n");
	printf("please enter new plaintext\n");
	goto thirdloop;
	}
	if(mm<=0)
	{ printf("plaintext is greater than 0,please enter new plaintext\n");
	  goto thirdloop;
	}
	fprintf(fp1,"plaintext is %d\n",plaintext);
    nn=e;
	k=plaintext;
	z=1;
	for(int i=0;i<nn;i++)                //get cyphertext
	{
		z=z*k;
		z=z%n;
	}
	kk=1;
	for(int i=0;i<d;i++)           // calculate plaintext
    {   
		kk=kk*z;
		kk=kk%n;
		
	}
	fprintf(fp1,"cyphertext is %d\n",z);
	fprintf(fp1,"after calculating,get plaintext is %d\n",kk);
	system("pause");
}