The discrete logarithm problem

I had an encounter with a problem when trying to solve for the discrete logarithm problem. I'm trying to figure this out;

``````a = b^x mod n
``````

where a = Public Key, b = Generator point, x = Private Key and n = Modular Integer.

I came across the problem in the Public key section. The public key has two different variants. The Compressed public key and the Uncompressed public key.

When i wanted to solve for the discrete logarithm problem this problem came across which brings up my question;

When finding x using the discrete logarithm problem, which is required or better; using the uncompressed public key or using the compressed public key?

π︎ 4
π°︎ r/crypto
π¬︎
π€︎ u/Kent305
π︎ Feb 01 2021
π¨︎ report
Understanding difference between normal logarithm and discrete logarithm.

The wikipedia page on discrete logarithms is unclear to me. In the second sentence it says, " Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm log(b,a) is an integer k such that b^k = a ". However, what is meant by "group" in this context and how is this definition different from your typical garden variety logarithm?

π︎ 3
π¬︎
π€︎ u/A_Cinnamon_Babka
π︎ Dec 10 2020
π¨︎ report
Computation of a 30750-Bit Binary Field Discrete Logarithm eprint.iacr.org/2020/965
π︎ 23
π°︎ r/crypto
π¬︎
π€︎ u/beefhash
π︎ Aug 15 2020
π¨︎ report
Using extended euclid algorithm to solve discrete logarithm problem

I've been tasked with showing how the discreet logarithm problem mis 'easy' on a group of integers modulo 'a' prime 'n' under addition, ie:

Find an x such that x . g == h (mod n)

Not so much as looking for an answer so as to just help understanding this shit because my brains about to fucking explode and I can't go get proper support because my uni is closed. My textbook states it's "easy to solve the additive discreet logarithm problem bla bla using extended gcd" but provides nothing furhter on this. It's legit a full stop.

How does one apply this?
I know the extended gcd(a,b), rather than giving just [gcd(a,b)], gives values [x, y, gcd(a,b)] such that x.a + y.b = gcd(a,b)

How does this help me?
Thanks <3

π︎ 8
π°︎ r/crypto
π¬︎
π€︎ u/RagingSerenity
π︎ May 23 2020
π¨︎ report
Calculate the discrete logarithm

I want to calculate the discrete logarithm with Haskell. Brute force (since I'm working with cyclic groups). I have a, (a^x) and n for log_a(a^x) mod n and want to figure out what x is. So I start at m=1 and go to m=p-1. I will calculate a^m and if it is equal to (a^x) I will return the x value. If not, I want it to break.

Here is what I tried:

``````secret :: Int -&gt; Int -&gt; (Int, Int) -&gt; Maybe Int
``````

secret g, h, (:,p) | mod g1 p == h = 1 secret g, h, (x,p) | mod gx p == h = x | secret g h (x+1,p)

Problem: it doesn't break after a while. And I don't know how good the code is. I am very inexperienced in Haskell.

π︎ 2
π¬︎
π︎ Apr 14 2020
π¨︎ report
Undetected Inflation vis a vis Discrete Logarithm Problem youtube.com/watch?v=jWAhDβ¦
π︎ 38
π°︎ r/Monero
π¬︎
π€︎ u/mrthrowawaymrmr
π︎ Jan 31 2019
π¨︎ report
The Discrete Logarithm Problem and Diffe-Hellman nashpotato.github.io/2019β¦
π︎ 17
π°︎ r/crypto
π¬︎
π︎ Aug 20 2019
π¨︎ report
Factorization of RSA-240, from RSA's challenge list, and the computation of a discrete logarithm of the same size (795 bits) lists.gforge.inria.fr/pipβ¦
π︎ 3
π°︎ r/cryptography
π¬︎
π€︎ u/bobmancoast
π︎ Dec 02 2019
π¨︎ report
Discrete Logarithm for RSA

So I've been looking around for an alternative way of cracking RSA (with the aim of arguing why the usual way of factoring N is faster than this rather than actually breaking RSA) by solving the equation of c^d = m (mod N) where c, m and N are known and you want to solve for d. I know that this is not the usual discrete log problem, which has to do with multipicative groups of prime order etc. because N is composite and m isnt necessarily coprime to N. Does anyone know of any sources which state how this problem is solved by current algorithms or why it can't be solved in the general case?

π︎ 4
π°︎ r/crypto
π¬︎
π€︎ u/xMatimos
π︎ Jul 22 2019
π¨︎ report
Discrete Logarithm key vs group

Hi All,

My apologies in advance if this isn't the correct place to ask these questions, and if they seem a bit basic.

Can someone please tell me the difference between a discrete logarithm KEY and GROUP (Such as listed here: https://www.keylength.com/en/8/)

Thank you.

π︎ 2
π°︎ r/cryptography
π¬︎
π€︎ u/CDNZTE
π︎ Sep 23 2019
π¨︎ report
RSA uses the prime factorization problem, but since it relies on modular exponentiation, does it use the discrete logarithm problem as well?
π︎ 20
π°︎ r/crypto
π¬︎
π€︎ u/BrainDeity
π︎ Jan 21 2019
π¨︎ report
Question about ECC and discrete logarithm

I've recently been reading about ECC and of course they always mention that the strength of ECC is derived from the difficulty of solving the discrete logarithm problem.

While I fully trust that conclusion, I'm still confused as to why it's so hard to calculate.

Let me first start off by explaining my thought process.

So we start off picking a standard curve of the form "y^2 = x^3 + x + 1" and picking a generator point on the curve (call it P). We take our private key "d" (a random integer) and then "jump around" the curve that many times, arriving at the final point Q. (I say "jump around" to bypass the complicated math stuff...that piece I understand)

Now, Q is now our public key, and it can be defined as Q = dP.

Where I get confused is that "d" is supposed to be difficult to find...but can't we just do the exact same steps and keep a counter to get the value of "d"?

In other words can't an attacker just start at point P and do the exact same steps and maintain a counter to arrive at Q?

I'm sure I'm mistaken somewhere, but I can't wrap my head around why an attacker can't calculate "d" themselves when someone can do effectively the same steps in a feasible way.

Any explanation is appreciated.

Thanks.

π︎ 11
π°︎ r/crypto
π¬︎
π€︎ u/phelarok
π︎ Aug 25 2017
π¨︎ report
New algorithm for the discrete logarithm problem on elliptic curves eprint.iacr.org/2015/310.β¦
π︎ 40
π°︎ r/crypto
π¬︎
π€︎ u/npouillard
π︎ Apr 07 2015
π¨︎ report
New algorithm shakes up cryptography: Researchers have solved one aspect of the discrete logarithm problem. This is considered to be one of the 'holy grails' of algorithmic number theory, on which the security of many cryptographic systems used today is based. [x-post /r/science] reddit.com/r/science/commβ¦
π︎ 51
π°︎ r/Bitcoin
π¬︎
π€︎ u/DrunkRaven
π︎ May 17 2014
π¨︎ report
Week 24 discussion: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

In this paper, Peter Shor proved that factoring takes polynomial time on a quantum computer. This was an important result because the best classical algorithm for factoring takes sub-exponential time. This paper motivated more people to perform research on quantum computers.

Discuss!

π︎ 4
π°︎ r/QuantumComputing
π¬︎
π€︎ u/vtomole
π︎ Dec 05 2017
π¨︎ report
A kilobit hidden SNFS discrete logarithm computation, How one could put undetectable βtrapdoorsβ in millions of crypto keys [PDF] eprint.iacr.org/2016/961.β¦
π︎ 60
π°︎ r/netsec
π¬︎
π€︎ u/Extremite
π︎ Oct 11 2016
π¨︎ report
The Proof is in the Pudding: Proofs of Work for Solving Discrete Logarithms

Cryptology ePrint Archive: Report 2018/939

Date: 2018-10-05

Author(s): Marcella Hastings, Nadia Heninger, Eric Wustrow

Abstract

We propose a proof of work protocol that computes the discrete logarithm of an element in a cyclic group. Individual provers generating proofs of work perform a distributed version of the Pollard rho algorithm. Such a protocol could capture the computational power expended to construct proof-of-work-based blockchains for a more useful purpose, as well as incentivize advances in hardware, software, or algorithms for an important cryptographic problem. We describe our proposed construction and elaborate on challenges and potential trade-offs that arise in designing a practical proof of work.

References

1. SpaceMint: A cryptocurrency based on proofs of space. In: FCβ18. Springer (2018)

2. Back, A.: Hashcash-a denial of service counter-measure (2002)

3. Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: CRYPTO 2018. Springer International Publishing (2018)

4. Barbulescu, R., Gaudry, P., Joux, A., ThomΒ΄e, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: EUROCRYPTβ14 (2014)

5. Barker, E., Chen, L., Roginsky, A., Vassilev, A., Davis, R.: SP 800-56A Revision 3. Recommendation for pair-wise key establishment schemes using discrete logarithm cryptography. National Institute of Standards & Technology (2018)

6. Biryukov, A., Pustogarov, I.: Proof-of-work as anonymous micropayment: Rewarding a Tor relay. In: FCβ15. Springer (2015)

7. Bitansky, N., Canetti, R., Chiesa, A., Goldwasser, S., Lin, H., Rubinstein, A., Tromer, E.: The hunting of the SNARK. Journal of Cryptology 30(4) (2017)

8. Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422β426 (Jul 1970). https://doi.org/10.1145/362686.362692

9. Boneh, D., Bonneau, J., BΒ¨unz, B., Fisch, B.: Verifiable delay functions. In: Annual International Cryptology Conference. pp. 757β788. Springer (2018)

10. Bos, J.W., Kaihara, M.E., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction. International Journal of Applied Cryptography 2(3) (2012)

11. Buterin, V.: Uncle rate and transact

... keep reading on reddit β‘

π︎ 2
π°︎ r/myrXiv
π¬︎
π€︎ u/dj-gutz
π︎ Jan 07 2019
π¨︎ report
New algorithm shakes up cryptography: researchers have solved one aspect of the discrete logarithm problem, which is considered to be one of the 'holy grails' of algorithmic number theory sciencedaily.com/releasesβ¦
π︎ 326
π°︎ r/tech
π¬︎
π€︎ u/nastratin
π︎ May 16 2014
π¨︎ report
Decisional Diffe-Hellman (DDH) assumption, Discrete Logarithm Problem (DLP) assumption

This fascinates me. It seems most cryptography systems are build on one or both of these assumptions.

π︎ 6
π°︎ r/tari
π¬︎
π€︎ u/hansie_
π︎ Oct 10 2018
π¨︎ report
[.pdf] New algorithm shakes up cryptography: Researchers have solved one aspect of the discrete logarithm problem. This is considered to be one of the 'holy grails' of algorithmic number theory, on which the security of many cryptographic systems used today is based. www2.cnrs.fr/sites/en/ficβ¦
π︎ 96
π°︎ r/science
π¬︎
π€︎ u/Libertatea
π︎ May 16 2014
π¨︎ report
New algorithm for the discrete logarithm problem on elliptic curves (PDF) eprint.iacr.org/2015/310.β¦
π︎ 67
π°︎ r/programming
π¬︎
π€︎ u/numinit
π︎ Apr 07 2015
π¨︎ report
Quasi-polynomial time algorithm for discrete logarithm. Are there any concerns for public-key crypto? truthiscool.com/faster-diβ¦
π︎ 40
π°︎ r/compsci
π¬︎
π€︎ u/DevFRus
π︎ Jun 21 2013
π¨︎ report
New algorithm for the discrete logarithm problem on elliptic curves eprint.iacr.org/2015/310.β¦
π︎ 13
π°︎ r/Bitcoin
π¬︎
π€︎ u/npouillard
π︎ Apr 07 2015
π¨︎ report
Coin flipping with discrete logarithms medium.com/unraveling-theβ¦
π︎ 6
π°︎ r/perl6
π¬︎
π€︎ u/liztormato
π︎ Mar 12 2018
π¨︎ report
Discrete logarithm implementation?

Anyone have seen one :(?

π︎ 3
π°︎ r/FPGA
π¬︎
π€︎ u/yarecube
π︎ Mar 03 2016
π¨︎ report
A kilobit hidden SNFS discrete logarithm computation eprint.iacr.org/2016/961
π︎ 9
π°︎ r/crypto
π¬︎
π€︎ u/asanso
π︎ Oct 07 2016
π¨︎ report
Quasi-polynomial time algorithm for discrete logarithm. Are there any concerns for public key crypto? [x-post r/compsci] truthiscool.com/faster-diβ¦
π︎ 19
π°︎ r/crypto
π¬︎
π€︎ u/DevFRus
π︎ Jun 22 2013
π¨︎ report
A discrete logarithm encryption protocol using supersingular curves, deemed as one of the candidates for the Internet's future security systems, was decrypted by EPFL researchers in two hours. phys.org/news/2014-05-unaβ¦
π︎ 69
π°︎ r/hacking
π¬︎
π€︎ u/spsheridan
π︎ May 20 2014
π¨︎ report
Question about the Elliptic Curve Discrete Logarithm problem

When calculating a public key point, you add base point G to itself d times, where d is our private key. My question is this: if the base point G is public information, what stops our attacker from adding G to itself using a counter for iterations and making checks against each new point? They would essentially be calculating their public key in the same fashion.

If the answer is computational complexity, how can our curve holder calculate a public key using the same logic?

π︎ 3
π°︎ r/crypto
π¬︎
π€︎ u/retardsrunfunny
π︎ Aug 01 2012
π¨︎ report
A discrete logarithm encryption protocol using supersingular curves, deemed as one of the candidates for the Internet's future security systems, was decrypted by EPFL researchers in two hours. phys.org/news/2014-05-unaβ¦
π︎ 26
π°︎ r/technology
π¬︎
π€︎ u/spsheridan
π︎ May 20 2014
π¨︎ report
A discrete logarithm encryption protocol using supersingular curves, deemed as one of the candidates for the Internet's future security systems, was decrypted by EPFL researchers in two hours. phys.org/news/2014-05-unaβ¦
π︎ 20
π°︎ r/TechNewsToday
π¬︎
π€︎ u/spsheridan
π︎ May 20 2014
π¨︎ report
Progress in solving discrete logarithm problem link.springer.com/chapterβ¦
π︎ 13
π°︎ r/crypto
π¬︎
π€︎ u/jshou
π︎ May 19 2014
π¨︎ report
A discrete logarithm encryption protocol using supersingular curves, deemed as one of the candidates for the Internet's future security systems, was decrypted by EPFL researchers in two hours. phys.org/news/2014-05-unaβ¦
π︎ 6
π¬︎
π€︎ u/spsheridan
π︎ May 20 2014
π¨︎ report
The Discrete logarithm Problem

I had an encounter with a problem when trying to solve for the discrete logarithm problem. I'm trying to figure this out;

``````a = b^x mod n
``````

where a = Public Key, b = Generator point, x = Private Key and n = Modular Integer.

I came across the problem in the Public key section. The public key has two different variants. The Compressed public key and the Uncompressed public key.

When i wanted to solve for the discrete logarithm problem this problem came across which brings up my question;

When finding x using the discrete logarithm problem, which is required or better; using the uncompressed public key or using the compressed public key?

π︎ 14
π°︎ r/cryptography
π¬︎
π€︎ u/Kent305
π︎ Feb 01 2021
π¨︎ report
Link between discrete logarithm problem and hash functions.

Was just wondering what the major link was between the discrete logarithm problem and hash functions? Is the DLP limited to provably secure hash functions or does it have a link to common algorithms such as SHA?

π︎ 7
π°︎ r/crypto
π¬︎
π€︎ u/vntech
π︎ Aug 13 2017
π¨︎ report