20170531, 08:01  #1 
May 2017
2^{2} Posts 
ElGamal crypto without prime
I have an ElGamal complied code that I can generate Public / Private keys and it accepts any value for the Prime and doesn't require a safe prime let alone a prime. It doesn't seem to generate the public key as per standard DLP. I believe the Generator is some mathematical calculation rather than the value passed am I wondering how best to figure out what calculation it's doing.
Assuming the standard ElGamal formula. y = g^x mod p; P: 100000000000003 G: 3 X: 181797159892737 Y: 1092431056012 Or running it again with a different X and the calculated Y P: 100000000000003 G: 3 X: 270172190021377 Y: 69135963644161 And with a different Prime: P: 100000000000008 G: 3 X: 50024232260613 Y: 32213936827398 How exactly would I go about figuring out what calcuation was used to Calculate Y? 
20170602, 10:30  #2 
Dec 2012
The Netherlands
5×353 Posts 
If you do use a prime number as P (and keep X less than P1) does it then produce the values you would expect?

20170602, 11:31  #3 
May 2017
4_{16} Posts 
That's my issue. I'm trying to generate the same Y values as this code is compiled on an EOL hardware platform. We are trying to decommission so want to be able to make the same calculations on something from this century.

20170602, 15:46  #4 
Aug 2006
5,987 Posts 
You say you have compiled code, can you disassemble and show the assembly code?

20170602, 18:27  #5 
May 2017
2^{2} Posts 
I've tried that too and I think the code was obsficated so it just comes out with garbage.
The joys of legacy systems with code you don't know where it came from. Also tried qemu to run the mips code but that just segfaulted as soon as I tried. So this seems to be my only option where I can generate as many Y values as I like I just don't know how they did it and what analysis I can do to figure it out. 
20170602, 18:41  #6  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:


20170602, 18:51  #7  
Aug 2006
5,987 Posts 
Quote:
Start by picking a prime value for p and some sequential values for x, say p = 16430021897689, g = 3, and x = 1000, 1001, 1002, 1003, 1004. What y values do you get? 

20170609, 20:44  #8 
May 2017
2^{2} Posts 
I've figured out where I was going wrong, it seems to results of the program was in hex byte reverse order. So once I reversed the hex string and converted into decimal then the DLP all worked out correctly.
Is factoring a 1505 bit DLP even possible with todays hardware? I don't think so unless I am lucky with a bad prime. Which doesn't seem to be the case. P: 468029702894433684338977303489534318417334367616607345543428776126464095000376621884290399754349745808879895270205541241072767207906464162314251755662526537024983389334838417600652186137585063995837264260996040968751336532611024193585582432745901609312180603810227726057154397764800133098748154730519485960151201386481431426283203247901683214337996406628246576573348018861619324567706734548997441151472664889303271158880469542104984598537661774830924507 G:7 Y: 14265530197277129914611611081229157985580706498666050251757745961393168417849610318372227677724471864859331775848364354652281942908912445232767774531830229042695142820224197553367009182953517334904824838299102263930197296974179256699919574684740716620837956336179969252960220344073531676359129097141585691582997547280585453857061341488124837116386308403621521499125941884705193361200677875306461595012659586777143840214401542579608771607921444251733550 
20170609, 21:24  #9  
"Forget I exist"
Jul 2009
Dartmouth NS
8418_{10} Posts 
Quote:


20170610, 03:26  #10 
Aug 2006
5,987 Posts 
Not with publicly known algorithms, and AFAIK it's not believed to be privately possible either.
The biggest discrete log that's been done in a prime field is 1024bit but that was a trapdoor prime with a SNFS form. The biggest generalform discrete log in a prime field was 768 bits and that took almost 5000 coreyears between 2015 and 2016. 1505 bits is ~63 orders of magnitude harder by the asymptotic formula, so not within striking distance. There's been a lot of progress recently in discrete logs where the modulus is a prime power (= small characteristic) but none that I know of where the modulus is prime. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Crypto News  Nick  Tales From the Crypt(o)  52  20201217 21:16 
Fujitsu cracks 278digit crypto  firejuggler  Science & Technology  8  20120620 20:03 
SHA1 Crypto Hash weakened  plandon  Lounge  0  20090616 13:55 
Crypto 2007  R.D. Silverman  Lounge  2  20070808 20:24 
crypto game  MrHappy  Lounge  0  20050119 16:27 