Hi,

if anybody would like to improve its Crypto-knowledge, should have a look at Gem Slider 2.5. They use ElGamal-32, so you dont need a Cray at home to solve the DLP. It is a nice protection based on ElGamal-Signature.

Happy crypto-reversing,
AdamA

Hi


there is another one: Bubble Shooter v5.01.
though keygen is out. It's also Elgamal-32 signature, using __int64 to implement it. It took me several hours to brute-force it.

hi Solomon, did you mean that you take hours to solve the DLP?

yeah, maybe 2~3 hours. It may be optimized to shorten the brute-forcing time.
Here is the result:
public key = (y, g, p), where y = g ^ x (mod p).
y = 0x260992DA
g = 0xFD3242AC
p = 0x797A8D77
I got x = 0x2B83B537 after brute-forcing.

Ooops, moment ago I found that both the above 2 progs are from the same company

...yea,i did not believe what you have said above for such a long
time to solve the 32bit dlp for the first time i saw this thread. then i do it myself using the p, y, g you provide, i gota reasonably long period to work the 'x' out from that. it's really weird, i just
thought. for the reason why some other case in which the key length is mush longer than this one can be brute-forced in a short
times? it do not like the IFP which is just base on the key length,
the longer the key is the harder to solve the problem.
pardon for my poor knowledge, and any suggestion/hints from you are appreciate!

Hi,

you can use the pollard-rho implementation from miracl-lib(index.cpp). It took me about 1sec to solve to DLP with pollard-rho.

AdamA

Will read it. Thx



which is the best?

Of course the index-calculus is the best, but I have never seen a working implementation of it, so far
I always use the Index.cpp(pollard-rho) from miracl.
But you will get some problems with Index.cpp, solving DLPs with good and big(>160bit) parameters. I got these problems with Dictation Buddy(highcriteria.com).

AdamA

thx!
and i also use the same version of index.c to do that. hehe.

for Gem Slider v2.5

__int64 p = 0x797A8D77;
__int64 g = 0xA6258277;
__int64 y = 0x0AFBBF83;
__int64 x = 0x2F0917AC;

We have to factorize (p-1) before using index.c in MIRACL.

after the factorization, we should use the result to get the order
of the generator which we should use in the dlp sovling.

HI Solomon!
Can you tell me How can brute-forcing? tools?
Thanks!

You don't need any "tools" except a programming language that implements 64-bit integers. Just run through all 4 billion or so possibilities for x and check to see that g^x mod p = y. Use the square-and-multiply method of exponentiation and you'll never need more than 64 bits.

yeah I did as what mike said.
The index calculus algo will take much less time.

Can you give me source code or similar function program? I want to get the resultĄŁ

If you're only interested in the result, it's already been posted. If you want to learn something, go get the MIRACL library like he said, read the docs, and code something yourself.

I'm willing to make a trade, just for teaching purposes: you go factor p-1, post the factors, and I'll walk you through Pohlig Hellman, which is really pretty fast, too, for this size.

*Newbie to cryptography alert*
I want to be walked through Pohlig Hellman too!
And there, I factored (797A8D77 - 1):
The 5 prime factors are: deleted by mike.

I will delete the primes from this post as soon as Mike sees it, so watj can factor it for himself

I'll post more when watj responds or it becomes obvious that he's not coming back. In the meantime, see

http://www-math.cudenver.edu/~wcherowi/courses/m5410/phexam.html

Discrete logarithm calculator

http://www.alpertron.com.ar/DILOG.HTM

Yes, Dario's got a lot of good stuff on his site; there's an ECM-based java applet for doing factoring, too.

Watj, are you interested in a walk-through of Pohlig-Hellman, or did you find what you were looking for? (Yes, Noxerus, I'll still cover it for you if you want.)

Me, I'm still interested

In this case, all the primes are raised to the first power, so we've got it somewhat easier. If the prime were, say, 19, then

p-1 = 18 = 2*3^2

so we'd have to do more work on the 3's.




Here we have p = 0x797A8D77 = 2038074743
p-1 = 2038074742 = 2 x 11 x 67 x 211 x 6553

Fermat's little theorem says that a^(p-1) mod p =1 for all 0<a<p. That's where the (p-1) comes from.

So x2 = a^((p-1)/2) is going to be a square root of 1 mod p, either 1 or -1. x2^2 = 1 mod p.

And x11 = a^((p-1)/11) is going to be an eleventh root of 1 mod p, either 1 or one of the ten other roots. x11^11 = 1 mod p.

And so forth for each of the prime factors of p-1.





We want a = y = 0x260992DA = 638161626.

Calculate y^((p-1)/2) mod p = 638161626 ^ 1019037371 mod p = 1. We know that g^0 = 1, so x mod 2 = 0.




Calculate y^((p-1)/11) mod p = 638161626 ^ 185279522 mod p = 530667471. This one isn't immediately obvious what it is, so we calculate powers of g^((p-1)/11):

4247929516^( 0 (p-1)/11) = 1

4247929516^( 1 (p-1)/11) = 530667471 Here it is!

4247929516^( 2 (p-1)/11) = 1476055738
4247929516^( 3 (p-1)/11) = 1577372493
4247929516^( 4 (p-1)/11) = 1556672107
4247929516^( 5 (p-1)/11) = 1164698744
4247929516^( 6 (p-1)/11) = 157526512
4247929516^( 7 (p-1)/11) = 332468944
4247929516^( 8 (p-1)/11) = 1273244622
4247929516^( 9 (p-1)/11) = 620334131
4247929516^( 10 (p-1)/11) = 1501332952

So x mod 11 = 1.





Calculate y^((p-1)/67) mod p = 638161626 ^ 30419026 mod p = 837055778.

Calculate powers of g^((p-1)/67):
4247929516^( 0 (p-1)/67) = 1
4247929516^( 1 (p-1)/67) = 969279158
4247929516^( 2 (p-1)/67) = 627462209
4247929516^( 3 (p-1)/67) = 1923309045
4247929516^( 4 (p-1)/67) = 1491205505
4247929516^( 5 (p-1)/67) = 1616231650
4247929516^( 6 (p-1)/67) = 1430903068
4247929516^( 7 (p-1)/67) = 858152029
4247929516^( 8 (p-1)/67) = 700138780
4247929516^( 9 (p-1)/67) = 450173072
4247929516^( 10 (p-1)/67) = 1145195681
4247929516^( 11 (p-1)/67) = 265253246
4247929516^( 12 (p-1)/67) = 1590062376
4247929516^( 13 (p-1)/67) = 1610058652
4247929516^( 14 (p-1)/67) = 538804611
4247929516^( 15 (p-1)/67) = 222570830
4247929516^( 16 (p-1)/67) = 77171383
4247929516^( 17 (p-1)/67) = 995947742
4247929516^( 18 (p-1)/67) = 1843915853
4247929516^( 19 (p-1)/67) = 1434514064
4247929516^( 20 (p-1)/67) = 817579263
4247929516^( 21 (p-1)/67) = 1887925213
4247929516^( 22 (p-1)/67) = 15849998
4247929516^( 23 (p-1)/67) = 84615908
4247929516^( 24 (p-1)/67) = 1949393505
4247929516^( 25 (p-1)/67) = 652376957
4247929516^( 26 (p-1)/67) = 525399415
4247929516^( 27 (p-1)/67) = 1801408622
4247929516^( 28 (p-1)/67) = 893704256
4247929516^( 29 (p-1)/67) = 647363056
4247929516^( 30 (p-1)/67) = 1533497277
4247929516^( 31 (p-1)/67) = 1719778403
4247929516^( 32 (p-1)/67) = 832957763
4247929516^( 33 (p-1)/67) = 554248528
4247929516^( 34 (p-1)/67) = 1718318301
4247929516^( 35 (p-1)/67) = 1649641819
4247929516^( 36 (p-1)/67) = 1162586056
4247929516^( 37 (p-1)/67) = 838130037
4247929516^( 38 (p-1)/67) = 1442672583
4247929516^( 39 (p-1)/67) = 385980540
4247929516^( 40 (p-1)/67) = 1473057032
4247929516^( 41 (p-1)/67) = 1958149338
4247929516^( 42 (p-1)/67) = 187216864
4247929516^( 43 (p-1)/67) = 317573875
4247929516^( 44 (p-1)/67) = 1191478852
4247929516^( 45 (p-1)/67) = 773712805
4247929516^( 46 (p-1)/67) = 1563067286
4247929516^( 47 (p-1)/67) = 1255085586
4247929516^( 48 (p-1)/67) = 162828941
4247929516^( 49 (p-1)/67) = 542963462
4247929516^( 50 (p-1)/67) = 164666018
4247929516^( 51 (p-1)/67) = 1582717187
4247929516^( 52 (p-1)/67) = 205968428
4247929516^( 53 (p-1)/67) = 876471562
4247929516^( 54 (p-1)/67) = 1756421293
4247929516^( 55 (p-1)/67) = 172990721
4247929516^( 56 (p-1)/67) = 601398531
4247929516^( 57 (p-1)/67) = 1990839337
4247929516^( 58 (p-1)/67) = 861384721
4247929516^( 59 (p-1)/67) = 732439570
4247929516^( 60 (p-1)/67) = 663613693
4247929516^( 61 (p-1)/67) = 1965313413
4247929516^( 62 (p-1)/67) = 1133873381

4247929516^( 63 (p-1)/67) = 837055778 Here it is!!

4247929516^( 64 (p-1)/67) = 1046026847
4247929516^( 65 (p-1)/67) = 2034779028
4247929516^( 66 (p-1)/67) = 301596515

So x mod 67 = 63.





We do the same thing for 211 and find

y^( (p-1)/211 ) = g^( 124 (p-1)/211 )

so x mod 211 = 124.





We do the same thing for 6553 and find

y^( (p-1)/6553 ) = g^( 1824 (p-1)/6553 )

so x mod 6553 = 1824.

Now we know what x is modulo all these different primes, we have to reassemble them using the Chinese Remainder Theorem. That I leave to you as homework. Post it below.