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?

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?

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

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 -> Int -> (Int, Int) -> 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.

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?

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.

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.

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.

Link to paper: https://arxiv.org/pdf/quant-ph/9508027.pdf

Discuss!

Cryptology ePrint Archive: Report 2018/939

Date: 2018-10-05

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

Link to Paper

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

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

Anyone have seen one :(?

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?

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?

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?