Autor Tema: RSA Probita ;)  (Leído 367 veces)

Phicar

  • :P
  • Administrador
  • Mensajes: 283
  • (1+sqrt(5))/2
    • MSN Messenger - diego_villahacker@hotmail.com
    • Ver Perfil
    • Phicar's Blog
    • Email
RSA Probita ;)
« : marzo 07, 2010, 10:15:39 pm »
Jejejeje Hola!!!, a que no me extragnaban(no seas huevon, es tu blog, solo te extragna a ti)...Bueno como que no sabian pa donde iba con las factorizaciones? no jodas...

RSA es un algoritmo que usa la complejidad del algoritmo de factorizacion de numeros compuestos en sus factores primos..:P...es ademas un cifrado de llave publica y privada, o sea el arrogante se cifra de una forma y de otra se (des)cifra ACOJONANTE! jajajja...

El algoritmo es mas o menos asi..

se tienen dos primos potencialmente grandes llamados p y q, la multiplicacion de ellos se llamara n (n=pq), se usara ademas la cantidad de coprimos de n y menores a si mismo o sea la Totient Euler Function definida en este blog hace la re puta mierda (phi(n)) aca como sabemos cuales son los dos factores de n tonces pa que lo descomponemos...

phi(x) = x * [(p-1)/p] siendo p todos los factores primos que descomponen a x, veamos lo siguiente, si x = pq ->

phi(x)= x*[(p-1)(q-1)]/pq -> phi(x)=(p-1)(q-1)

llamaremos ademas e a un numero que sea coprimo al valor de phi(n) o sea GcD(e,phi(n)) == 1...y e mayor que 1

Ademas tomaremos un numero d que al ser multiplicado con e y dividido por phi(n) su residuo sea 1 ((ed)%phi(n)==1)

ademas sacaremos un numero N2 que sera de la forma  2^N2-1<=n<=2^N2, si la gente es pila sabra que va a ser la longitud que necesitaremos pa los binarios ;) y con la cual tambien sacamos lo hexadecimal ;)

Bueno ahora si, la clave publica sera (n,e) y la privada sera d ;)

El cifrado es asi, ;)

C = (P^e)%n
 donde C es el la parte cifrada y P es la parte no cifrada :P

P = (C^d)%n


Bueno hijos los dejo con el Codigo, si no lo entienden me vale culo hasta hice validaciones y perdonen las chambonadas, ;)


Código: (java) [Seleccionar]
import java.util.*;
import java.math.BigInteger;
public class RSAProb{
public static String error = "Usage: java RSAProb [option] [data] [(plain/cipher) text]\nOptions:  -c to cipher\n          -d to (des)cipher\nData: \nfor cipher, p and q as primes\nfor (des)cipher d n\nphicar@yashira.org->redinfocol.org";
public static void main(String args[]){
System.out.println(ToHex(new BigInteger(args[1]),8));
if(args[0].equalsIgnoreCase("-c")){
try{
BigInteger p = new BigInteger(args[1]);
BigInteger q = new BigInteger(args[2]);
if(!p.isProbablePrime(100) || !q.isProbablePrime(100))
return;
BigInteger n = p.multiply(q);
BigInteger Tn = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
BigInteger e=new BigInteger("2");
//BUSCAMOS E COMO K | GCD(K,TOT(n))==1
while(GcD(e,Tn).compareTo(BigInteger.ONE)!=0) e=e.add(BigInteger.ONE);
BigInteger d = Tn.subtract(BigInteger.ONE);
//BUSCAMOS D COMO K | 1<K<TOT(n) ^ (D*E)%TOT(n)==1
while(((e.multiply(d)).mod(Tn)).compareTo(BigInteger.ONE)!=0)
d=d.subtract(BigInteger.ONE);
int n2 = 1;
for(;!((((new BigInteger("2").pow(n2-1)).subtract(BigInteger.ONE)).compareTo(n)<=0)&&((new BigInteger("2").pow(n2)).compareTo(n)>0));n2++);
System.out.println("n="+n+",Tn(n)="+Tn+",e="+e+",d="+d+",n2="+n2);
String plain = args[3];
String tmp ="";
//PASAMOS A BINARIO EL PLAIN
for(int x = 0;x<args[3].length();x++)
tmp+=ToBin((int)plain.charAt(x),7);
//HACEMOS PADDING POR LA DERECHA MIENTRAS SEA N2-1
while(tmp.length()%(n2-1)!=0)tmp+="0";
//System.out.println(tmp);
//HACEMOS EL MAXIMO DE CARACTERES BASE-16
/*int u = 0;
while(())u++;
no se si hacer con hexadecimal o con binario, hexadecimal esta muy jodido no se porque
*/
String tmp2 = "";
//GENERAMOS LOS NUMEROS y por ende el final en HEXADECIMAl, uso de longitud en hexadecimal n2 que es longitud en bytes/4 ya que 2^4=16
for(int y=0;(y+(n2-1))<=tmp.length();y+=(n2-1)){
tmp2+=ToHex(new BigInteger(String.valueOf(ToDec(tmp.substring(y,y+(n2-1)),2))).modPow(e,n),(n2/4)+4);
//System.out.println(ToDec(tmp.substring(y,y+(n2-1)),2)+"-->"+(new BigInteger(String.valueOf(ToDec(tmp.substring(y,y+(n2-1)),2))).pow(Integer.parseInt(e.toString()))).mod(n)+"-->"+ToHex((new BigInteger(String.valueOf(ToDec(tmp.substring(y,y+(n2-1)),2))).pow(Integer.parseInt(e.toString()))).mod(n),(n2/4)+4));
}
System.out.println(tmp2);
}catch(Exception Phicar){
System.err.println("Hptaaaaaaa Error, la cagaste en algo o la cague yo, lo importante es que me postees en que fue xDDD\n"+Phicar+"\n recuerda usar bien el programa de la siguiente manera:\n"+error);
}
}else if(args[0].equalsIgnoreCase("-d")){
try{
BigInteger d = new BigInteger(args[1]);
BigInteger n = new BigInteger(args[2]);
int n2 = 1;
for(;!((((new BigInteger("2").pow(n2-1)).subtract(BigInteger.ONE)).compareTo(n)<=0)&&((new BigInteger("2").pow(n2)).compareTo(n)>0));n2++);
System.out.println("n2="+n2);
String tmp = "";
//de hex a los numeros ;)
for(int x = 0;(x+((n2/4)+4))<=args[3].length();x+=(n2/4)+4){
tmp+=new BigInteger(String.valueOf(ToDec(args[3].substring(x,x+((n2/4)+4)),16))).modPow(d,n)+",";
//System.out.println(args[3].substring(x,x+((n2/4)+4))+"-->"+ToDec(args[3].substring(x,x+((n2/4)+4)),16)+"-->"+((new BigInteger(String.valueOf(ToDec(args[3].substring(x,x+((n2/4)+4)),16))).pow(Integer.parseInt(d.toString()))).mod(n)));
}
tmp = tmp.substring(0,tmp.length()-1);
//separo numeros, no encontre mejor metodo, espero sepan obviar mis chambonadas de novato ;) jejejeje
StringTokenizer token = new StringTokenizer(tmp,",");
String tmp2="";
while(token.hasMoreTokens())
tmp2+=ToBin(Integer.parseInt(token.nextToken()),n2-1);
//System.out.println(tmp2);
String res = "";
for(int x = 0;(x+7)<tmp2.length();x+=7)
res+=(char)ToDec(tmp2.substring(x,x+7),2);
System.out.println(res);
}catch(Exception phicar){
System.err.println("Hptaaaaaaa Error, la cagaste en algo o la cague yo, lo importante es que me postees en que fue xDDD\n"+phicar+"\n recuerda usar bien el programa de la siguiente manera:\n"+error);
}
}else{
System.err.println(";) Ups..\n"+error);
}
}
public static String ToHex(BigInteger a,int b){
String charset = "0123456789abcdef",tmp="";
do{
tmp = charset.charAt(Integer.parseInt(String.valueOf(a.mod(new BigInteger("16")))))+tmp;
}while((a=a.divide(new BigInteger("16"))).compareTo(new BigInteger("0"))>0);
while(tmp.length()<b)tmp ="0"+tmp;
return tmp;
}
public static int ToDec(String a,int b){
String charset = "0123456789abcdef";
int tmp = 0;
for(int n = a.length()-1,c=0;n>-1;n--,c++)
tmp+=charset.indexOf(a.charAt(n))*Math.pow(b,c);
return tmp;
}
public static String ToBin(int a,int b){
String tmp = "";
do{
tmp = (a%2)+tmp;
}while((a>>=1)>0);
while(tmp.length()<b)tmp = "0"+tmp;
return tmp;
}
public static BigInteger GcD(BigInteger a,BigInteger b){
if(b.compareTo(new BigInteger("0"))==0)
return a;
return GcD(b,a.mod(b));
}
}
:)

my.opera.com/phicar