Post by @hipsterelectron@circumstances.run

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

https://weakdh.org/ really cute shit

View

15 Replies

3 Boosts

This comment is unavailable — it may have been deleted or is not visible to you.

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

(like people say you can pull log q bits there are papers on it but i don't just trust anything i read because it says diffie-hellman on it)

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

but i cannot tell you how my jaw dropped to learn elliptic curves and lattices are quite literally the two components of the techniques used against discrete log in diffie-hellman. very literally

this is the one i found most useful to understand it (this is not the quadratic/number field sieve method, btw, that just runs to factor your q - 1 afaict):

A.K. Lenstra, H.W. Lenstra, Jr., L. Lovasz: Factoring Polynomials with Rational Coefficients

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

there's a book by lenstra on the number field sieve with a surprise visit by daniel jackoff bernstein in the credits but i haven't read it because i don't really care that much and as far as i'm aware you can in fact just delegate to the hardness of discrete log and feel satisfied that you are not going to die horribly. ECC does not give you that

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

i have spent the past two days reading number theory (evil) and group theory (hero) and i've learned some vaguely interesting tidbits but largely the whole thing about numbers is that they have behavior that can surprise you when you go into the positive integers and away from the realm of complexity theory bounds for fixed n

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

imho it's obvious that RSA was based upon the number-theoretical problem that had been known as Computationally Complex since antiquity i.e. prime factorization, which doesn't scale exponentially in a fixed bit width and essentially encodes a reliance upon whoever can buy the most hardcore machinery to compute the biggest primes. just like world war 2, forever

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

you should be able to determine a level of security you expect to resist attacks against and diffie-hellman (as far as i can tell) gives us that. the fact that it's also demonstrably capable of overriding information-theoretic and probabilistic arguments is incredibly deep and well worth your time to look into and think about.

i don't know if that 1974 john dillon phd thesis over difference sets in a prime power is going to solve complexity theory for us but group theory is so meaningful because it can allow us to confirm we don't have backdoors

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

i obviously hate wikipedia and i hate this wikipedia page for it https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm obviously it fails to mention the q = 2p + 1 criterion (which is quite literally derived from euclid's first proof of the infinitude of primes, and demonstrates a deep meaning to the act of machine arithmetic), but it's good when you publish definitive discussions of attacks against your system and the current mitigations against it

Pohlig–Hellman algorithm - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

it's deeply funny that the q = 2^m - 1 criterion was not one well known to science because number theorists were more obsessed with being bigger they named 2^m + 1 and even 2^(2^m) + 1 but this construction for discrete log eluded them. i think that's funny

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

actually finding this paper is hell it's not available by DOI anywhere but luckily it was not erased from time and space altogether https://link.springer.com/chapter/10.1007/978-1-4757-0602-4_1

while hellman is being more blase than i would be about the term "subexponential" i understand he is playing it safe and not overstating the security level and i love him for this. there is also a very in-depth discussion of the chinese remainder theorem method

SpringerLink

Fast Computation of Discrete Logarithms in GF (q)

The Merkte-Adleman algorithm computes discrete logarithms in GF (q),the finite field with q elements, in subexponential time, when q is a prime number p. This paper shows that similar asymptotic behavior can be obtained for the logarithm problem when q = p...

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

and btw yes i feel very icky calling it the "chinese remainder theorem" especially because we have an actual name for it it's called sunzi's theorem. i'm gonna say that from now on

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

ok the dillon 1974 thesis on difference sets is actually just a remarkably well-written thesis but this 1982 paper from hellman and reyneri actually does the fucking probabilistic analysis of polynomials better than any other paper i've seen. diving into the citations now

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

also just incredibly fucking funny that the MITRE corporation (the one that does CVEs and sucks at it) is the same one computing logarithms in a field of size 2127, in hardware, in 1982, when the 1978 paper literally says not to do that. two explanations, the first one is that they were chasing massive key sizes at all costs without regard to security

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

omfg the exp{(1 + δ) * sqrt(k * l * ln(2m)} is literally the bound demonstrated BY hellman lmao

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

oh yeah i forgot about this paper https://www.cs.ru.nl/E.Verheul/papers/Joc2004/joc2004.pdf it basically makes the argument that you can get smaller keys and faster execution by using the XTR approach of stuffing a cyclotomic polynomial into your diffie-hellman without translating to an elliptic curve (because that's basically all ECC is doing)

View (PDF)

d.rift

@d_rift@beige.party 2 hr. ago

@hipsterelectron 🤨 (ok, adds that to the pile...)