/****************************************************************************/
/* Cifrado de Hill con matrices 2x2                                         */
/*                                                                          */
/* Jaime Suarez <[email protected]> 2003                                  */
/* en http://www.matematicas.net                                            */
/****************************************************************************/

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long coef1(long,long);
long coef2(long,long);
long invmod(long a, long m);

int main()
{
	char *s,*t, op, ch, *pt;
	int a11,a12,a21,a22, idet,
	    m11,m12,m21,m22, x1,x2,y1,y2;

	s=(char *)malloc(200); t=(char *)malloc(200);
	printf("Cifrado de Hill 2x2.\n");

	/* Pedir datos y comprueba que la matriz es inversible */
	do {
		printf("Cifrar (c) o descifrar (d): ");
		scanf("%c",&op);
	} while (op!='c' && op!='d');

	printf("\nIntroduzca matriz de cifrado.\n");
	printf("a11 = "); scanf("%d",&a11);
	printf("a12 = "); scanf("%d",&a12);
	printf("a21 = "); scanf("%d",&a21);
	printf("a22 = "); scanf("%d",&a22);
	
	if ( (idet=invmod(a11*a22-a12*a21,26)) == 0) {
		printf("La matriz no es inversible.\n");
		return 1;
	}

	/* Pide el texto y suprime todos los caracteres no alfabéticos */
	/* si el número de caracteres no es par se añade una X         */
	getchar();
	printf("\nIntroduzca el texto que %s: ",
			(op=='c')?"cifrar":"descifrar");
	fgets(s,200,stdin);
	
	pt=t;
	while ( (ch=*s++) !=0) {
		if (isalpha(ch)) *pt++=toupper(ch);
	}
	*pt='\0';
	if (strlen(t)%2 != 0) strcat(t,"X");
	

	/* Se usa la matriz inicial o la inversa según cifre o descifre */
	if (op=='c') {
		m11=a11; m12=a12; m21=a21; m22=a22;
	}
	else {
		m11= a22*idet;
		m12=-a12*idet;
		m21=-a21*idet;
		m22= a11*idet;
	}
	
	/* Multiplicación de cada bloque por la matriz */
	pt=t;
	while (*pt) {
		x1= *pt++; x1 -= 'A';
		x2= *pt++; x2 -= 'A';
		y1= (x1*m11 + x2*m21) %26; while(y1<0) y1+=26;
		y2= (x1*m12 + x2*m22) %26; while(y2<0) y2+=26;
		putchar(y1+'A');
		putchar(y2+'A');
		putchar(' ');
	}
	printf("\n");

	return 0;
}		


/*---------------------------------------------------------------------
  Teorema de Bezout: si c=mcd(a,b) entonces existen enteros
  alfa y beta tales que c= alfa*a + beta*b
----------------------------------------------------------------------*/
long coef1(long a,long b)
{
    if (a%b==0) return (0);
    else return (coef2(b,a%b));
}
long coef2(long a, long b)
{
    if (a%b==0) return(1);
    else return (coef1(b,a%b)- a/b *coef2(b,a%b));
}

/*----------------------------------------------------------------------
  Calculo del inverso modulo un entero.
  Suponiendo que 1=mcd(m,n) entonces existen enteros a y b tales que
  1=m.a+n.b y por tanto a es un inverso de a mod n

  Devuelve el inverso de m modulo n o 0 si no es inversible.
----------------------------------------------------------------------*/
long invmod(long m,long n)
{
	long a,b;

    	a=coef1(m,n);
	b=coef2(m,n);
	if (m*a+n*b!=1) return 0;
	else return a;
}