View Full Version : ElGamal Signature
AdamA
November 23rd, 2002, 16:12
Hi,
if anybody would like to improve its Cryptoknowledge, should have a look at Gem Slider 2.5. They use ElGamal32, so you dont need a Cray at home to solve the DLP. It is a nice protection based on ElGamalSignature.
Happy cryptoreversing,
AdamA
Solomon
November 24th, 2002, 05:06
Hi
there is another one: Bubble Shooter v5.01.
though keygen is out. It's also Elgamal32 signature, using __int64 to implement it. It took me several hours to bruteforce it.
strafer
November 24th, 2002, 14:47
Quote:
Originally posted by Solomon
Hi
there is another one: Bubble Shooter v5.01.
though keygen is out. It's also Elgamal32 signature, using __int64 to implement it. It took me several hours to bruteforce it. 
hi Solomon, did you mean that you take hours to solve the DLP?
Solomon
November 25th, 2002, 03:39
yeah, maybe 2~3 hours. It may be optimized to shorten the bruteforcing 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 bruteforcing.
Quote:
Originally posted by strafer
hi Solomon, did you mean that you take hours to solve the DLP?

Solomon
November 25th, 2002, 04:19
Ooops, moment ago I found that both the above 2 progs are from the same company
strafer
November 25th, 2002, 10:22
...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 bruteforced 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!
AdamA
November 25th, 2002, 12:18
Hi,
you can use the pollardrho implementation from miracllib(index.cpp). It took me about 1sec to solve to DLP with pollardrho.
AdamA
Solomon
November 25th, 2002, 12:31
Will read it. Thx
Quote:
Originally posted by AdamA
Hi,
you can use the pollardrho implementation from miracllib(index.cpp). It took me about 1sec to solve to DLP with pollardrho.
AdamA 
which is the best?
Quote:
Some efficient algorithms for the discrete logarithm problem have been reported. They include the Pollard's rho algorithm of logarithms [Pol74], the PohligHellman algorithm [PH78] and the indexcalculus methods [HR83]. The indexcalculus algorithm is the most efficient method known for computing discrete logarithms. It is a subexponential time algorithm for some groups [MvOV99] but not elliptic curves 
AdamA
November 25th, 2002, 14:26
Of course the indexcalculus is the best, but I have never seen a working implementation of it, so far
I always use the Index.cpp(pollardrho) 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
strafer
November 25th, 2002, 15:18
thx!
and i also use the same version of index.c to do that. hehe.
Solomon
November 27th, 2002, 09:46
for Gem Slider v2.5
__int64 p = 0x797A8D77;
__int64 g = 0xA6258277;
__int64 y = 0x0AFBBF83;
__int64 x = 0x2F0917AC;
We have to factorize (p1) before using index.c in MIRACL.
strafer
November 27th, 2002, 10:43
after the factorization, we should use the result to get the order
of the generator which we should use in the dlp sovling.
watj
December 28th, 2002, 04:14
Quote:
Originally posted by Solomon
yeah, maybe 2~3 hours. It may be optimized to shorten the bruteforcing 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 bruteforcing. 
HI Solomon!
Can you tell me How can bruteforcing? tools?
Thanks!
mike
December 28th, 2002, 05:21
You don't need any "tools" except a programming language that implements 64bit integers. Just run through all 4 billion or so possibilities for x and check to see that g^x mod p = y. Use the squareandmultiply method of exponentiation and you'll never need more than 64 bits.
Solomon
December 28th, 2002, 08:52
yeah I did as what mike said.
The index calculus algo will take much less time.
Quote:
Originally posted by watj
Can you tell me How can bruteforcing? tools?

watj
December 28th, 2002, 09:32
Quote:
Originally posted by Solomon
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ĄŁ
mike
December 29th, 2002, 21:05
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 p1, post the factors, and I'll walk you through Pohlig Hellman, which is really pretty fast, too, for this size.
Noxerus
January 5th, 2003, 00:56
Quote:
Originally posted by mike
you go factor p1, 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
mike
January 5th, 2003, 22:19
I'll post more when watj responds or it becomes obvious that he's not coming back. In the meantime, see
http://wwwmath.cudenver.edu/~wcherowi/courses/m5410/phexam.html
watj
January 6th, 2003, 02:46
Quote:
Originally posted by mike
I'll post more when watj responds or it becomes obvious that he's not coming back. In the meantime, see
http://wwwmath.cudenver.edu/~wcherowi/courses/m5410/phexam.html 
Discrete logarithm calculator
http://www.alpertron.com.ar/DILOG.HTM
mike
January 6th, 2003, 04:01
Yes, Dario's got a lot of good stuff on his site; there's an ECMbased java applet for doing factoring, too.
Watj, are you interested in a walkthrough of PohligHellman, or did you find what you were looking for? (Yes, Noxerus, I'll still cover it for you if you want.)
Noxerus
January 8th, 2003, 17:51
Me, I'm still interested
mike
January 9th, 2003, 05:44
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
p1 = 18 = 2*3^2
so we'd have to do more work on the 3's.
Here we have p = 0x797A8D77 = 2038074743
p1 = 2038074742 = 2 x 11 x 67 x 211 x 6553
Fermat's little theorem says that a^(p1) mod p =1 for all 0<a<p. That's where the (p1) comes from.
So x2 = a^((p1)/2) is going to be a square root of 1 mod p, either 1 or 1. x2^2 = 1 mod p.
And x11 = a^((p1)/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 p1.
We want a = y = 0x260992DA = 638161626.
Calculate y^((p1)/2) mod p = 638161626 ^ 1019037371 mod p = 1. We know that g^0 = 1, so x mod 2 = 0.
Calculate y^((p1)/11) mod p = 638161626 ^ 185279522 mod p = 530667471. This one isn't immediately obvious what it is, so we calculate powers of g^((p1)/11):
4247929516^( 0 (p1)/11) = 1
4247929516^( 1 (p1)/11) = 530667471 Here it is!
4247929516^( 2 (p1)/11) = 1476055738
4247929516^( 3 (p1)/11) = 1577372493
4247929516^( 4 (p1)/11) = 1556672107
4247929516^( 5 (p1)/11) = 1164698744
4247929516^( 6 (p1)/11) = 157526512
4247929516^( 7 (p1)/11) = 332468944
4247929516^( 8 (p1)/11) = 1273244622
4247929516^( 9 (p1)/11) = 620334131
4247929516^( 10 (p1)/11) = 1501332952
So x mod 11 = 1.
Calculate y^((p1)/67) mod p = 638161626 ^ 30419026 mod p = 837055778.
Calculate powers of g^((p1)/67):
4247929516^( 0 (p1)/67) = 1
4247929516^( 1 (p1)/67) = 969279158
4247929516^( 2 (p1)/67) = 627462209
4247929516^( 3 (p1)/67) = 1923309045
4247929516^( 4 (p1)/67) = 1491205505
4247929516^( 5 (p1)/67) = 1616231650
4247929516^( 6 (p1)/67) = 1430903068
4247929516^( 7 (p1)/67) = 858152029
4247929516^( 8 (p1)/67) = 700138780
4247929516^( 9 (p1)/67) = 450173072
4247929516^( 10 (p1)/67) = 1145195681
4247929516^( 11 (p1)/67) = 265253246
4247929516^( 12 (p1)/67) = 1590062376
4247929516^( 13 (p1)/67) = 1610058652
4247929516^( 14 (p1)/67) = 538804611
4247929516^( 15 (p1)/67) = 222570830
4247929516^( 16 (p1)/67) = 77171383
4247929516^( 17 (p1)/67) = 995947742
4247929516^( 18 (p1)/67) = 1843915853
4247929516^( 19 (p1)/67) = 1434514064
4247929516^( 20 (p1)/67) = 817579263
4247929516^( 21 (p1)/67) = 1887925213
4247929516^( 22 (p1)/67) = 15849998
4247929516^( 23 (p1)/67) = 84615908
4247929516^( 24 (p1)/67) = 1949393505
4247929516^( 25 (p1)/67) = 652376957
4247929516^( 26 (p1)/67) = 525399415
4247929516^( 27 (p1)/67) = 1801408622
4247929516^( 28 (p1)/67) = 893704256
4247929516^( 29 (p1)/67) = 647363056
4247929516^( 30 (p1)/67) = 1533497277
4247929516^( 31 (p1)/67) = 1719778403
4247929516^( 32 (p1)/67) = 832957763
4247929516^( 33 (p1)/67) = 554248528
4247929516^( 34 (p1)/67) = 1718318301
4247929516^( 35 (p1)/67) = 1649641819
4247929516^( 36 (p1)/67) = 1162586056
4247929516^( 37 (p1)/67) = 838130037
4247929516^( 38 (p1)/67) = 1442672583
4247929516^( 39 (p1)/67) = 385980540
4247929516^( 40 (p1)/67) = 1473057032
4247929516^( 41 (p1)/67) = 1958149338
4247929516^( 42 (p1)/67) = 187216864
4247929516^( 43 (p1)/67) = 317573875
4247929516^( 44 (p1)/67) = 1191478852
4247929516^( 45 (p1)/67) = 773712805
4247929516^( 46 (p1)/67) = 1563067286
4247929516^( 47 (p1)/67) = 1255085586
4247929516^( 48 (p1)/67) = 162828941
4247929516^( 49 (p1)/67) = 542963462
4247929516^( 50 (p1)/67) = 164666018
4247929516^( 51 (p1)/67) = 1582717187
4247929516^( 52 (p1)/67) = 205968428
4247929516^( 53 (p1)/67) = 876471562
4247929516^( 54 (p1)/67) = 1756421293
4247929516^( 55 (p1)/67) = 172990721
4247929516^( 56 (p1)/67) = 601398531
4247929516^( 57 (p1)/67) = 1990839337
4247929516^( 58 (p1)/67) = 861384721
4247929516^( 59 (p1)/67) = 732439570
4247929516^( 60 (p1)/67) = 663613693
4247929516^( 61 (p1)/67) = 1965313413
4247929516^( 62 (p1)/67) = 1133873381
4247929516^( 63 (p1)/67) = 837055778 Here it is!!
4247929516^( 64 (p1)/67) = 1046026847
4247929516^( 65 (p1)/67) = 2034779028
4247929516^( 66 (p1)/67) = 301596515
So x mod 67 = 63.
We do the same thing for 211 and find
y^( (p1)/211 ) = g^( 124 (p1)/211 )
so x mod 211 = 124.
We do the same thing for 6553 and find
y^( (p1)/6553 ) = g^( 1824 (p1)/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.
Powered by vBulletin® Version 4.2.2 Copyright © 2020 vBulletin Solutions, Inc. All rights reserved.