ajutor algoritm rsa

[wildchild]

Am de facut asta si n-am timp.Nu e nimic complex nici complicat.Puteti sa il scrieti in orice limbaj de programare mai putin java si javascript.Merci anticipat.

1. Sa se aleaga sau sa se genereze 2 numere prime.
2. Folosind cele 2 numere prime si algoritmul RSA, sa se genereze o cheie publica si una secreta (perechile e, n si d,n).
3. Sa se cripteze folosind cheia publica unu sau mai multe caractere.
4. Sa se decripteze mesajul criptat folosind cheia secreta.

Ah da,se poate face un singur program care sa le faca pe toate sau mai multe.

Ca si compensatie, ofer o invitatie pe filelist.

Edited May 16, 2011 by wildchild

[SlicK]

RSA pe 16 biti, daca vrei mai mult trebuie sa folosesti clase de numere mari.

#include <windows.h>
#include <stdio.h>
#include <math.h>
#include <time.h>

bool IsPrime(int nr)
{
	for(int i=2;i<nr-1;i++)
	{
		if(nr%i==0)
		{
			return(false);
		}
	}
	return(true);
}

int RandPrime(int min, int max)
{
	int nr=rand()%(max-min+1)+min;
	while(!IsPrime(nr))
	{
		nr++;
	}
	return(nr);
}

int GCD(int nr1, int nr2)
{
	do
	{
		int tmp=nr1%nr2;
		nr1=nr2;
		nr2=tmp;
	} while(nr2!=0);
	return(nr1);
}

int MultInv(int a,int m)
{
	a=a%m;
	for(int i=1;i<m;i++)
	{
		if(a*i%m==1)
		{
			return(i);
		}
	}
	return(0);
}

int modpow(int b, int e, int m)
{
    int ret=1;
    while(e>0)
	{
        if((e&1)==1)
		{
           ret=(ret*%m;
		}
        e=e>>1;
        b=(b*%m;
	}
    return(ret);
}

void GenKeys(int& n,int& e,int& d)
{

	int p=RandPrime(0x43,0x7F);
	int q=RandPrime(0x43,0x7F);
	if(p==q)
	{
		return(GenKeys(n,e,d));
	}
	n=p*q;
	e=3;

	int phi=(p-1)*(q-1);
	if(GCD(e,phi)!=1)
	{
		return(GenKeys(n,e,d));
	}
	d=MultInv(e,phi);
	if(d==0)
	{
		return(GenKeys(n,e,d));
	}
}

void Encrypt(int n,int e,char* src,int srclen,unsigned char* dst,int& dstlen)
{
	for(int i=0;i<srclen;i++)
	{
		int c=modpow(src[i],e,n);
		dst[i*2]  =(c>>8)&0xFF;
		dst[i*2+1]=c&0xFF;
	}
	dstlen=srclen*2;
}

void Decrypt(int n,int e,unsigned char* src,int srclen,unsigned char* dst,int& dstlen)
{
	for(int i=0;i<srclen;i+=2)
	{
		int x=(src[i]<<8)|src[i+1];
		dst[i/2]=(unsigned char)modpow(x,e,n);
	}
	dstlen=srclen/2;
}

int main()
{
	srand((int)time(0));

	int n,e,d;
	GenKeys(n,e,d);

	printf("n=%X\n",n);
	printf("e=%X\n",e);
	printf("d=%X\n",d);

	char plain[]="Hello RSA";
	printf("%s\n",plain);

	unsigned char encr[256]="";
	int elen;
	Encrypt(n,e,plain,strlen(plain),encr,elen);
	for(int i=0;i<elen;i++)
	{
		printf("%c",(UCHAR)encr[i]);
	}
	printf("\n");


	unsigned char decr[256]="";
	int dlen;
	Decrypt(n,d,encr,elen,decr,dlen);
	for(int i=0;i<dlen;i++)
	{
		printf("%c",decr[i]);
	}
	printf("\n");

	getchar();
	return(0);
}

Poti sa pastrezi invitatia

[hammerfall]

L-am portat pe Linux. L-am si testat, dar unele caractere sunt putin cam... neinteligibile. Nu stiu daca asa ar trebui sa fie sau e vreo problema... Sunt incepator in C++ asa ca puteti sa-mi corectati codul ca nu ma supar.

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <cstdlib>
#include <string.h>
#include <iostream>
using namespace std;

bool IsPrime(int nr)
{
	for(int i=2;i<nr-1;i++)
	{
		if(nr%i==0)
		{
			return false;
		}
	}
	return true;
}

int RandPrime(int min, int max)
{
	int nr=rand()%(max-min+1)+min;
	while(!IsPrime(nr))
	{
		nr++;
	}
	return nr;
}

int GCD(int nr1, int nr2)
{
	do
	{
		int tmp=nr1%nr2;
		nr1=nr2;
		nr2=tmp;
	} while(nr2!=0);
	return nr1;
}

int MultInv(int a,int m)
{
	a=a%m;
	for(int i=1;i<m;i++)
	{
		if(a*i%m==1)
		{
			return i;
		}
	}
	return 0;
}

int modpow(int b, int e, int m)
{
    int ret=1;
    while(e>0)
	{
        if((e&1)==1)
		{
           ret=(ret*%m;
		}
        e=e>>1;
        b=(b*%m;
	}
    return ret;
}

void GenKeys(int& n,int& e,int& d)
{

	int p=RandPrime(0x43,0x7F);
	int q=RandPrime(0x43,0x7F);
	if(p==q)
	{
		return GenKeys(n,e,d);
	}
	n=p*q;
	e=3;

	int phi=(p-1)*(q-1);
	if(GCD(e,phi)!=1)
	{
		return GenKeys(n,e,d);
	}
	d=MultInv(e,phi);
	if(d==0)
	{
		return GenKeys(n,e,d);
	}
}

void Encrypt(int n,int e,char* src,int srclen,unsigned char* dst,int& dstlen)
{
	for(int i=0;i<srclen;i++)
	{
		int c=modpow(src[i],e,n);
		dst[i*2]  =(c>>8)&0xFF;
		dst[i*2+1]=c&0xFF;
	}
	dstlen=srclen*2;
}

void Decrypt(int n,int e,unsigned char* src,int srclen,unsigned char* dst,int& dstlen)
{
	for(int i=0;i<srclen;i+=2)
	{
		int x=(src[i]<<8)|src[i+1];
		dst[i/2]=(unsigned char)modpow(x,e,n);
	}
	dstlen=srclen/2;
}

int main()
{
	srand((int)time(0));

	int n,e,d;
	GenKeys(n,e,d);

	cout << "n=" << n << endl;
	cout << "e=" << e << endl;
	cout << "d=" << d << endl;

	char plain[]="Ported to Linux";
	cout << plain << endl;

	unsigned char encr[256]="";
	int elen;
	Encrypt(n,e,plain,strlen(plain),encr,elen);
	for(int i=0;i<elen;i++)
	{
		cout << (char unsigned) encr[i];
	}
	cout << endl;


	unsigned char decr[256]="";
	int dlen;
	Decrypt(n,d,encr,elen,decr,dlen);
	for(int i=0;i<dlen;i++)
	{
		cout << decr[i];
	}
	cout << endl;

	return 0;
}

[wildchild]

multumesc mult pentru ajutor.as vrea totusi sa va intreb in ce program le-ati facut, eu am probleme cu anumite compilatoare si imi dau unele erori chiar si cu programele scrise corect.hammerfall,daca doresti invitatia pe fl, lasa-mi pe privat o adresa de mail

[nedo]

Primul este scris in c, pentru windows, al 2-lea este scris in c++ pe linux.

[hammerfall]

Mersi nedo, mi-ai luat-o inainte cu explicatiile.

Nu, multumesc wildchild, n-am nevoie. Incerc si eu sa ma joc cu C++ cat mai mult sa invat. :">

Si sper ca-i va fi de folos cuiva.

[wildchild]

nedo, nu ma interesa limbajul de programare ci compilatorul anume.eu folosesc visual studio si imi face figuri la unele coduri scrise corect

[hammerfall]

La codul care ti l-am "tradus" eu in C++, varianta de Linux, am folosit g++. Nu cred ca este disponbil si pentru windows, dar cred ca merita specificat pentru cine vrea sa-l incerce pe linux.

[nedo]

scuze,wildchild, nu am citit bine intrebarea ta. ... Pe langa visual studio pentru c/c++ iti recomand code blocks, mult mai usor, mult mai prietenos si mult mai intuitiv.

[wildchild]

no problem dude.thanks for help you guys!apropo,MultInv ce face?i just don't get it

[SlicK]

MultInv vine de la "multiplicative inverse" si e necesar pentru ca d=e-1 mod phi sau alfel spus d e "multiplicative inverse" pentru e mod phi.

Primul cod trebuie sa compileze fara probleme in Visual Studio 2008.

Unele caractere sunt neinteligibile pentru ca sunt intre 0x00 si 0xFF adica in afara ASCII-ului printabil.

Edited May 16, 2011 by SlicK

[wildchild]

multumesc mult Slick pentru tot!