mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-05-31, 08:01   #1
ElChapo
 
May 2017

22 Posts
Default 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?
ElChapo is offline   Reply With Quote
Old 2017-06-02, 10:30   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5×353 Posts
Default

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?
Nick is offline   Reply With Quote
Old 2017-06-02, 11:31   #3
ElChapo
 
May 2017

22 Posts
Default

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.
ElChapo is offline   Reply With Quote
Old 2017-06-02, 15:46   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

598710 Posts
Default

You say you have compiled code, can you disassemble and show the assembly code?
CRGreathouse is offline   Reply With Quote
Old 2017-06-02, 18:27   #5
ElChapo
 
May 2017

1002 Posts
Default

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.
ElChapo is offline   Reply With Quote
Old 2017-06-02, 18:41   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by ElChapo View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-06-02, 18:51   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by ElChapo View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2017-06-09, 20:44   #8
ElChapo
 
May 2017

22 Posts
Default

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
ElChapo is offline   Reply With Quote
Old 2017-06-09, 21:24   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts
Default

Quote:
Originally Posted by ElChapo View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-06-10, 03:26   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176316 Posts
Default

Quote:
Originally Posted by ElChapo View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Crypto News Nick Tales From the Crypt(o) 52 2020-12-17 21:16
Fujitsu cracks 278-digit crypto firejuggler Science & Technology 8 2012-06-20 20:03
SHA-1 Crypto Hash weakened plandon Lounge 0 2009-06-16 13:55
Crypto 2007 R.D. Silverman Lounge 2 2007-08-08 20:24
crypto game 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔