SimoneUrsula

#include <stdlib.h>
#include <stdio.h>
#include <time.h> // biblioteca necessária para função time
#include <math.h> // sqrt
main()
{
	/*
	Criptografar os dados: Gerar a Chave Pública
	                       necessário calcular o N e o e
	Cálculo do N
	N = p * q: O cálculo do N envolve gerar os número p e q
	p = tem que ser um número grande primo gerado de forma aleatória
    q = tem que ser um número grande primo gerado de forma aleatória e <> p

    Cálculo do e
    e = calcular seu inverso modular
        teste de primalidade (precisa ser primo e usar método)

    Com os valores de N e e se pode calcular a chave pública
    KeyPublic =
	*/
	/* definção das variáveis utilizadas */
	long long int p;
	long long int q;
	long long int n;
    int e;
    int d;
    int Key;
	long long int qEuler;

	/*
	utilizado para ser o ponto de partida da função rand() --> semente
    */
    srand(time(NULL));

	/* Cálculo do N = p * q
	gerar o número p
	p = tem que ser um número grande primo gerado de forma aleatória
	chama a função criada newNumber() para gerar p
	*/
	p = newNumber();
	printf("número p = %d", p);
	getwchar();

	/* gerar o número q
	q = tem que ser um número grande primo gerado de forma aleatória
	chama a função criada newNumber() para gerar q
	q<>p: q tem que ser diferente de p
	      função criada newNumber() não gera dois número iguais
	*/
	q = p;
	while (p == q) q = newNumber();
	/*
	imprime valor q
	*/
	printf("número q = %d", q);
	getwchar();

	/*
	Calculo do número N
	N = p * q
	*/
	n = p * q;
	/*imprime n */
	printf("número n = %d ", n);
	getwchar();

	/*
	Cálculo do número e
	gerar um número pequeno primo, impar e relativamente primo $\o(N)$
	Para gerar o número será utilizado a função newNumber(), essa função trabalha com número grande
	Para verificar se o número é relativamente primo $\o(N)$, utilizar o algoritmo estendido de Euclides
	Para Algoritmo estendido de euclides será utilizado a função modEuclides() criada
	primo relativo: utilizado quociente euler: (p-1)*(q-1)
    */

	qEuler = (p - 1) * (q - 1);
	/*imprime qEuler */
    e = keyE(qEuler, n);
    /*imprime e*/
    printf("número e = %d ", e);
	getwchar();


	/* KeyPublic - temos n, e -
	podemos aplicar a fórmula c = m ^ e mod n
	m é o valor numérico da letra
	para criptografar é aplicar a fórmula a cada letra
	*/
	/* Término da Criptografia dos dados*/

	/*
	Descriptografar dos dados: Gerar a Chave Privada
	                          necessário o N e o d, só calcular o d, o N é o mesmo da Chave Pública
	N: é o mesmo da Chave Pública

    Cálculo do d
    d = calcular seu inverso modular, através do algoritmo estendido de Euclides
        teste de primalidade (precisa ser primo e usar método)
	*/

    /*Tem-se o e e o qEuler.
	Para o RSA o X deve ser 1, pois d*e mod qq = 1
	(peguei pronto o euclides_ext
    apenas renomeei aqui mdcEuclidesEstendido
    */
    d = keyD(e, qEuler);
   	/*imprime d */
	printf("número d = %d \n", d);
	getwchar();

	/* KeyPrivate - temos n, d -
	podemos aplicar a fórmula c = m ^ e mod n
	*/
	/* Término da Descriptografia dos dados */

	/*
	Com os valores de n, e, d
	Ter um menu com opções de criptografar, descriptografar e para quebra da chave

	opção Criptografar: poder escolher arquivo a ser criptogrado
	Aplicar a chave pública, n e e ...
	mostrar a mensagem criptograda

	opção Quebra de chave:
	mostrar quanto tempo leva para quebrar e depois o arquivo

	opção Descriptografar: descriptografa, temos n e d
	mostra a mensagem descriptografada
	*/

	/*
	Teste de Força Bruta
	*/
	printf("fatorar n = %d \n", n);
	forcaBruta(n);

	return EXIT_SUCCESS;
}

/*
Função newNumber para gerar número de forma aleatória e primo
A função gera um número aleatório através da função rand() do c, ponto de partida é calculado pela função srand() do c, usei hora
Entrada: não tem
Saida:   número grande primo gerado aleatoriamente
*/
newNumber()
{
	/* definação das variaveis utilizadas
	/* vaiável n: tipo de dados inteiro grande
	              gera o número inteiro grande aleatoriamente
	              a função isPrimi(n) verifica se o número gerado é primo
    */
    long long int number;
    int isPrimi;
    isPrimi= 0;   /* varíavel começa com zero, só será 1 quando o número gerado for primo
	/*
	executa o loop while da linha 78 - 90 até o número inteiro grande gerado aleatoriamente ser primo
	*/
    while (isPrimi == 0 )
    {
    	/* função rand() gera um número aleatório
    	parte do ponto de partida calculado pela função srand
    	sendo o calculo baseado na hora, em segundo ... desde 1970 até a data atual
    	*/
     	number  = rand();
     	/*
		verifica se o número gerado aleatoriamente é primo
        ser primo não significa que passou pelo teste da primalidade,
		mas para o teste a premissa é ser primo
        */
     	isPrimi = Primi(number);
     }

     return number;  /* retorna o número gerado */
}

/*
Função isPrimi()? verifica se o número é primo
Para um nro ser primo precisa ser divisível por ele mesmo e por 1
?? Verificar se tem algo mais, Cormen fala algo que isso é um pseudoprimo(), precisa utilizar Fermat ou outro método além desse
para o Teste de Prmalidade ??
Entrada: nro a ser verificado se é primo[
Saída:   1 se for primo e 0 se não for primo
*/
int Primi(long long int number)
{
    int i = 0;
    int nroVezes = 0;
	/*
	se o nrovezes = 2 é porque o nro é primo sqrt(number)
	se o nrovezes = 2 não precisa continuar a divisão porque o nro não é primo - performance
	*/
	for(i = 1; (i < number) && (nroVezes < 3); i++)
		if (number % i == 0) nroVezes += 1;

	/* sai do loop */
	if (nroVezes = 2)
	    return 1;
   	else return 0;


}

/*
Função KeyE: calcula o e
Enrada: recebe o qeuler -> já calculado
Saida:  devolve o cálculo do e
*/
keyE(long long int qEuler, long long int n)
{
	/*
	Definição das variáveis
	*/
	int key  = 0;
	int ok   = 0;
	int mdcE = 0;

	/*
	chave pública tem que ser um pequeno gerado aleatoriamente, chama função criada newNumber()
	número precisa ser primo, a propria rotina newNumber() já faz este teste
	número precisa ser impar, o while abaixo será executado enquando o número gerado não for impar
	no while é pego o resto da divisão -: no c usa %, se ele for = 0 é par
	a parada do while é quando o número for impar
	*/
	while (ok != 1) { /* Impar e MDC( e, qeuler ) == 1 */
       key = newNumber();
       /* ser impar */
       if ((key % 2 != 0) && (key > 1) && key < (n-1))
	   {

	   	/*
	   	mdc - para ver se primo relativo
		o e ter que ser um um primo relativo
		para isso calculamos o mdc entre o número e o quociente de euler recebido por parâmentro
	  	Chamar a função criada modEuclides() passando o e e qeuler
    	O número e deve ser calculado de maneira que o MDC (máximo divisor comum)
    	entre e e qeuler seja 1, dessa forma, e seja relativamente primo de qeuler.
    	MDC( e, qeuler ) == 1 e o número gerado tem que estar entre 1 e n-1
		*/


		mdcE = mdc(qEuler,key );
		//printf("número mdcE %d \n", mdcE);
		//getwchar();

		if (mdcE == 1) ok = 1;
	   }
	}
	return key;
}

/*
Função KeyE: calcula o d
Enrada: recebe o qeuler  e o e-> já calculados
Saida:  devolve o cálculo do d
*/
keyD(int e, long long int qEuler)
{
	/*
	Definição das variáveis
	*/
	int mdcD = 0;
	mdcD = mdcEuclidesEstendido(e, qEuler, 1);
	/*
	chamando a função que calcula o d
	Retorna o nro da expressao Ã§Ã£o que calcula o d. Ela retorna um nÃºmero que case na
    expressÃ£o: d*e mod qq = X

    Fazer o teste para ver se está ok
    */
    //printf("número e = %d \n", e);
   // printf("número qEuler = %d \n", qEuler);
	//printf("número mdcD = %d \n", mdcD);
	//getwchar();


    return mdcD;

}


/*
Função para calcuar o inverso modular
Entrada: 2 parametros
Saida:   r: máximo divisor comum
*/
mdc(long long int a, long long int b )
{
	/*
	Definição das variáveis
	*/
	long long int r;
	//r = a%b;
	r = mod(a, b);
    a = b;
	b = r;

	/*
	Se o r não for zero, vai entrar no loço de repetição
	laço de repetição até o r for diferente de zero - condição de parada
	*/
	while (r != 0) {
	  // r = a%b;
	   r = mod(a, b);
	   a = b;
	   b = r;
	 }
//	printf("número r = %d\n ", r);
//	printf("número a = %d \n", a);
	return a; /* maior divisor comum */
}


/*
TITULO: Algoritmo de euclides extendido (calcula o D RSA)
DATA: 13/Agosto/2009
*/


/* AritmÃ©tica modular Ã© tambÃ©m considerada como o "algoritmo do relÃ³gio".

Ao extrair o modulo 12, como resposta possÃvel pode-se ter nÃºmeros de
0 a 11. Nunca negativo, pois a ideia Ã© de um relÃ³gio com 12 posiÃ§Ãµes, sendo
a primeira o zero e a Ãºltima o 11.

PorÃ©m o operador de mÃ³dulo do C (operador %) computa apenas o resto da divisÃ£o
e gera nÃºmeros negativos. Em C:

-2 mod 12 = -2 (nÃ£o estÃ¡ entre 0 e 11)
2 mod -12 = 2  (nÃ£o estÃ¡ entre -11 e 0)

O C dizer que -2 mod 12 Ã© -2 significa dizer que ele estÃ¡ a -2 de distÃ¢ncia do
final do relÃ³gio, ou seja, estÃ¡ em 10 (o inÃcio e tambÃ©m o final do relÃ³gio Ã© o zero).

Dizer que 2 mod -12 significa um relÃ³gio ao contrÃ¡rio (0, -1, -2, -3, .. -11, andando
no sentido anti-horÃ¡rio) e que o valor 2 estÃ¡ a 2 posiÃ§Ãµes de distÃ¢ncia do 0, ou seja,
estÃ¡ em -10.

Nesta artimÃ©tica modular o resultado da operaÃ§Ã£o PRECISA SER do mesmo sinal
do divisor.

Observou-se que o operador de mÃ³dulo do python (%) nÃ£o tem este comportamento,
calculando o mÃ³dulo nÃ£o negativo. A biblioteca bn.h do openssl possui ambos,
tanto a funÃ§Ã£o BN_mod que simplesmente retorna o resto da divisÃ£o (comportamento
igual ao %) como a funÃ§Ã£o BN_nnmod que calcula o mÃ³dulo nÃ£o negativo.

Nesta versÃ£o em C resolveu-se fazer uma pequena correÃ§Ã£o na resposta dada pelo
operador de mÃ³dulo, pois o algoritmo de euclides precisa do mÃ³dulo positivo.
*/
mod(long long int a, long long int b)
{
    long long int r = a % b;

    /* Uma correÃ§Ã£ Ã© necessÃ¡ria se r e b nÃ£o forem do mesmo sinal */

    /* se r for negativo e b positivo, precisa corrigir */
    if ((r < 0) && (b > 0)) return (b + r);

    /* Se ra for positivo e b negativo, nova correcao */
    if ((r > 0) && (b < 0)) return (b + r);

    return (r);
}


/*
Entrada: 3 parametros
Saida:   r: máximo divisor comum
*/
mdcEuclidesEstendido(long long int a, long long int b, long long int c)
{
    long long int r;
    r = mod(b, a);

    if (r == 0){
	    return (mod((c / a), (b / a)));	// retorna mod((c/a) , (b/a))
   	}

    return ((mdcEuclidesEstendido(r, a, -c) * b + c) / (mod(a, b)));
}

/*
Teste de Força Bruta
Ataques Matemáticos
Três são os ataques matemáticos:
* Fatorar n em dois números primos. Isto possibilita calcular Primo relativo n = (p-1)(q-1),
                                    e com isso determinar o valor de d = e-1 (mod f n)
*Determinar Primo relativo n diretamente, sem determinar p e q,
									permitindo novamente determinar o valor de d = e-1
                                   (mod Primo relativo n)
* Determinar d sem descobrir Primo relativo n.
*/
forcaBruta(long long int n)
{
long long int fat;

	printf("\nFatorial calculado: %d", fat);
	getchar();
	for(fat = 1; n > 1; n = n - 1){
		fat = fat * n;
 	//	printf("\nFatorial calculado: %d", fat);
 	//	getchar();
 	}
	return 0;
}