crackme 8 by WiteG
------------------

Serial ma dlugosc 170 bajtow.. znaczenie poszczegolnych czesci
w ponizszej tabelce...


offset | dlugosc | znaczenie
-------+---------+------------------------------------------------------------
1      | 64      | (M)^e mod N1
-------+---------+------------------------------------------------------------
65     | 1       | przerywnik '-'
-------+---------+------------------------------------------------------------
66     | 64      | (X)^2 mod N2
-------+---------+------------------------------------------------------------
130    | 1       | przerywnik '-'
-------+---------+------------------------------------------------------------
131    | 40      | sygnaturka ElGamala, pod hashem z pierwszych 130 bajtow :)
-------+---------+------------------------------------------------------------

najpierw pierwsze dwie czesci sn sa 'szyfrowane' przy uzyciu mnozenia modulo 2^32

mov eax, X  <-- co bedziemy mnozyc
mul CONST   <-- jakas stala
add eax, edx
adc eax, 0

zeby to odwrocic, nalezy znalezc odwrotnosc CONST, przy uzyciu rozszerzonego algorytmu
euklidesa (dla N=FFFFFFFF)

musza zachodzic nastepujace rownosci:

M^e mod N1 == X             
X^2 mod N2 < hash_z_name            
X^2 mod N2 > (hash_z_name - 25)

W pierwszej linijce, szyfrowanie RSA-225, w dwoch nastepnych cos co sie zowie
funkcja Rabina, trudnosc polega na niemoznosci wyliczenia X, gdy N jest odpowiednio
duze (N to iloczyn dwoch duzych liczb pierwszych). 

Co ciekawe, modulus w RSA jest produktem CZTERECH liczb pierwszych.. 
Klucz prywantny liczymy w sposob analogiczny co w przypadku 2 liczb..

d=e^-1 mod (p-1)*(q-1)*(r-1)*(s-1)

p,q,r,s to oczywiscie czynniki pierwsze N

Jesli chodzi o funkcje Rabina -- WiteG dal przedzial {hash-1,hash-24}, bo nie z kazdej
liczby da sie wyciagnac pierwiastek kwadratowy modulo N.

Liczenie pierwiastkow kwadratowych modulo N, gdzie N jest produktem dwoch liczb pierwszych:

WEJSCIE: liczba N, jej czynniki pierwsze p i q, oraz a nalezace do N.
WYJSCIE: 4 pierwiastki kwadratowe modulo N.
1. Znajdz 2 pierwiastki kwadratowe r i -r, a modulo p
2. Znajdz 2 pierwiastki kwadratowe s i -s, a modulo q
3. Uzyj rozszerzonego algo. euklidesa, aby znalezc takie dwie liczby c i d, ze cp + dq = 1.
4. Policz x=(rdq + scp) mod n i y=(rdq - scp) mod n.
5. Zwroc ( -+ x mod n, -+ y mod n).
                                            -- Handbook  of Applied Cryptography
                                            
liczenie pierwiastkow modulo liczba pierwsza, zalatwi za nas sqroot w miracl.

Ostatnie 32 bajty to sygnatura ElGamal'a pod hashem z pierwszych 64 bajtow.

PODPISY ELGAMALA

Czynnosci wstepne:
WiteG wybiera liczbe pierwsza p, oraz generator g z Z*(p). Nastepeni WiteG wybiera
losowo liczbe x < p-1, oblicza y=g^x mod p oraz ujawnia g,p,y jako klucz publiczny.

Podpisywanie:
Cracker wykonuja nastepujace czynnosci w trakcie podpisywania wiadomosci M:

1. Cracker oblicza liczbe k wzglednie pierwsza z p-1
2. Cracker oblicza a = g^k mod p
3. Poniewaz k i p-1 sa wzglednie pierwsze, istnieje t takie, ze k*t = 1 mod p-1. Cracker
wyznacza t za pomoca rozszerzonego algorytmu Euklidesa. Nastepnie oblicza

b = t*(M-xa) mod p-1    (jesli M<xa to M-(ax-p-1))

Tym samym zachodzi M = kb + xa mod p-1
4. Cracker przedstawia (a,b) jako podpis dla M

Weryfikacja podpisu:
Zauwazmy, ze y^a * y^b = g^ax * g^kb = g^M mod p
Crackme sprawdza, czy y^a * a^b = g^M mod p
                                               -- Kryptografia Kutylowski, Strothmann
                  
W naszym przypadku:

p = F31CB7BBDF75FA650113
y = A3536157D7E74721637C
g = 5
x = F1CB7BBDF75FA6501101  (16 min 59 sec.)

Dyskretny logarytm - x, zostal znalezniony przy uzyciu implementacji algotymu RHO Pollarda,
napisanego przez tE! (dzieki smola). 

ps
niezla implementacja bigow, WiteG ;)

to tyle,
ged_//aaocg