mersenneforum.org > Math ElGamal crypto without prime
 Register FAQ Search Today's Posts Mark Forums Read

 2017-05-31, 08:01 #1 ElChapo   May 2017 22 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?
 2017-06-02, 10:30 #2 Nick     Dec 2012 The Netherlands 5×353 Posts 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?
 2017-06-02, 11:31 #3 ElChapo   May 2017 22 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.
 2017-06-02, 15:46 #4 CRGreathouse     Aug 2006 598710 Posts You say you have compiled code, can you disassemble and show the assembly code?
 2017-06-02, 18:27 #5 ElChapo   May 2017 1002 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.
2017-06-02, 18:41   #6
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 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.

2017-06-02, 18:51   #7
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 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?

 2017-06-09, 20:44 #8 ElChapo   May 2017 22 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
2017-06-09, 21:24   #9
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

Quote:
 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. Code: 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.

2017-06-10, 03:26   #10
CRGreathouse

Aug 2006

176316 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Tales From the Crypt(o) 52 2020-12-17 21:16 firejuggler Science & Technology 8 2012-06-20 20:03 plandon Lounge 0 2009-06-16 13:55 R.D. Silverman Lounge 2 2007-08-08 20:24 MrHappy Lounge 0 2005-01-19 16:27

All times are UTC. The time now is 03:53.

Tue Dec 6 03:53:52 UTC 2022 up 110 days, 1:22, 0 users, load averages: 0.65, 0.84, 0.84