RSA

Ola' a tutti, 
sto cercando di implementare in c++ una classe che simuli l'rsa. Dopo le iniziali difficolta' nel riorganizzare il materiale disponibile, cercare quello mancante sul web e sui libri di mate sono riuscito ad implementare partendo da 0 tutte le funzioni che mi servivano (tranne gcd(), l'ho preso dal tutorial sull'rsa di sorrow, complimenti :-) Dopo estenuanti e sempre piu' confuse ricerche anche il mai_bene_spiegato modinv() :-] Le funzioni matematiche esterne alla classe sono:

//isprime e' molto rudimentale e la uso solo per la creazione delle chiavi
vlong isprime(vlong x);
//una ricerca da d=2 fino a che ( e ^ d mod ( p - 1 ) * ( q - 1 ) ) == 0;
vlong modinv(vlong x, vlong n);
//non molto efficente neanche questo algoritmo, viene eseguito a = (a * a) MOD n per b volte
vlong esp(vlong a, vlong b, vlong, n);

int isprime(vlong n)
{
  if (n>0) if (n<=3) return 1;
  if ((n % 2) == 0) return 0;

  vlong i=3;
  vlong fine=vlong(sqrt(float(n)));

  while (i<=fine)
  {
     if (((n % i) == 0) && i<n) return 0;
     i+=2;
  }

  return 1;
}


vlong modinv(vlong e, vlong n)
{
vlong d=1;
while ( ((e*d-1) % n) != 0) ++d;
return d;
}

vlong esp(vlong a, vlong b, vlong n)
{
if (b<0 || a<0) exit (-1);
if (b==0) return 1;
if (b==1) return (a);
while (b>1)
{
   a*=a;
   a%=n;
   --b;
}
return a;
}

Premettendo che vlong - per ora - e' il normale tipo long:
In fase di creazione delle chiavi non ho grossi problemi, almeno per quel che riguarda la correttezza. Il problema e' in fase di cifratura:

vlong rsa::cifra(vlong pmsg)
{
//cifrato=pmsg^e MODULO n;
return esp(pmsg,e,n);
}

vlong rsa::decifra(vlong cmsg)
{
//messaggio=cmsg^d MODULO n;
return esp(cmsg,d,n);
}


(p-1)*(q-1) 616
n = 667
p = 23
q = 29
e = 593
d = 241
/*
le chiavi sono state generate con successo:
-  p e q sono primi

-  e<(p-1)*(q-1) e primo con essi

-  e^d MOD n=0, quindi d e' l'inverso di e (per sicurezza ho provato l'inverso tramite al funzione inverse_mod(e,n) con derive...
*/

 msg --> 5
//msg e' il messaggio da cifrare
cmsg --> 257
//l'inghippo e' qua sopra... 5^593 MOD 667 fa 428 e non 257!! 

naturalmente 428^241 MOD 667 fa 5...

Quindi... riuscite a trovare il problema negli algoritmi che ho usato?
Penso si tratti di esp().

Sperando di non aver usurpato troppi cicli macchina al vostro cervello, banda al vostro modem e tempo alla vostra vita, saluto tutta la mailing-list

Byz, Demo

--
TiscaliNet, libero accesso ad Internet.
http://www.tiscalinet.it


________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List