ElGamal crypto without prime

[ElChapo]

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?

[Nick]

If you do use a prime number as P (and keep X less than P-1) does it then produce the values you would expect?

[ElChapo]

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.

[CRGreathouse]

You say you have compiled code, can you disassemble and show the assembly code?

[ElChapo]

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.

[science_man_88]

Originally Posted by ElChapo

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.

are you sure it's garbage ? do you know the assembly language for the machine it was originally done with ? if not how can we say it's garbage ? looking up elgamel got me to cryptosystem using discrete logs if so you would need to solve the discrete log problem at last check unless I'm mixing things up.

[CRGreathouse]

Originally Posted by ElChapo

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.

OK.

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?

[ElChapo]

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

[science_man_88]

Originally Posted by ElChapo

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

there fixed that for you so you don't have to scroll off the screen to see it all.

[CRGreathouse]

Originally Posted by ElChapo

Is factoring a 1505 bit DLP even possible with todays hardware?

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 1024-bit but that was a trapdoor prime with a SNFS form. The biggest general-form discrete log in a prime field was 768 bits and that took almost 5000 core-years 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.