PDA

Pogledaj cijelu verziju : problem sa decrypt



kicho
20-11-2010, 18:59
imam problem sa decryptanjem - decrypt 256 bytes decryptano RSA-algorithm (http://en.wikipedia.org/wiki/RSA)

nesto o RSA:
Prvo morate odabrati dva velika prosta broja i pomnožiti te brojeve da biste dobili veliki broj (n =) (u našem slučaju rezultira broj 256 Bytes dug (~ = 616 decimalnih znamenki)). Sada možete izračunati funkciju eulers totient (= Phi) na tom velikom broju. Za rezultat od dvaju prostih brojeva ovu funkciju vraća (p - 1) * (q - 1) i stoga je vrlo lako izračunati. Nakon što imate Phi (n) morate naći E i D (private i public key) za zadovoljiti sljedeće jednadžbe: (e * d) mod fi (n) = 1 gdje je mod znači modulo i e nema zajednički djelitelj s fi (n). Sada možemo koristiti E i D na sljedeći način:
encrypt = (data ^ e) mod n;
data = (encrypt ^ d) mod n;

U oba slučaja ^ ne znači XOR nego exponentation.

Sto je sada naš problem? Znamo "n" i znamo "d". Mi neznamo "e", neznamo "p" i "q". Ako znamo Phi (n), lako možemo izračunati e od (e * d) mod fi (n) = 1 koristeći extended euclidic algoritam izračunavanja ali Phi (n) za takvi veliki n ne znajući p i q će trajati zauvjek (koristeci > 10 ^ 313 iterations gdje se svaki iteration ponovno koristi mnoge dodatke / podjele ...).

moze li mi netko pomoci?