Logarithm problem - Revision history

Rational Point: /* Difficulty of problem and security of cryptosystems */

2025-02-10T06:29:42Z

Difficulty of problem and security of cryptosystems

← Older revision		Revision as of 06:29, 10 February 2025
Line 11:		Line 11:
	Many elliptic curve cryptosystems would immediately be broken by a polynomial-time solution to this problem. The existence of [[Schoof’s point-counting algorithm]] would appear to cast doubt on the difficulty of the discrete logarithm problem over elliptic curves and the security of cryptosystems that depend on it.		Many elliptic curve cryptosystems would immediately be broken by a polynomial-time solution to this problem. The existence of [[Schoof’s point-counting algorithm]] would appear to cast doubt on the difficulty of the discrete logarithm problem over elliptic curves and the security of cryptosystems that depend on it.

	The U.S. government does not have very much interest at all in the research and development or cryptanalysis of elliptic curve cryptography that depend on the discrete logarithm problem. However, certain European and European axis-aligned governments, including Canada, Japan, Chile and Brazil, do.		The U.S. government does not have very much interest at all in the research and development or cryptanalysis of elliptic curve cryptography that depend on the discrete logarithm problem. However, certain European and European axis-aligned governments, including Canada, Japan, Chile and Brazil, do, and information is redacted from published sources in those countries as well as Germany, Switzerland, and probably New Zealand as well.

			The NSA probably (in effect, if not through an official quid pro quo) gave up most of its theoretical cryptanalysis and cryptology on elliptic curves as a bargaining chip in exchange for cementing NSA’s access to raw surveillance intelligence throughout the “Western” world, as most of the countries of the Trilateral Commission and Bilderberg Meetings humored dumb Americans who couldn’t crack their crypto.

			And for as much as the NSA used to prize secrecy and loyalty, there has been a falling away at the agency toward a general homeland security labor union beat cop mentality of establishing [https://www.dhs.gov/fusion-centers “fusion centers” for domestic surveillance], [https://ttp.dhs.gov/ hustling travelers at airports with random searches], and similar low-intelligence and mostly ineffectual security theater.

			Alan Turing built “the Bombe” that cracked the codes of Germany’s Enigma cipher machine, and again, as much as NSA would value secrecy and loyalty, there are certain things about those top secret government places, which when we don’t hear the noise and the chatter of them abroad, we know simply are not happening. «Fait accompli» and they have the intelligence already by some preprogrammed or automated process, or else they simply don’t care and it’s someone else’s job to find it out for them.

Rational Point: /* Difficulty of problem and security of cryptosystems */

2025-02-10T02:41:04Z

Difficulty of problem and security of cryptosystems

← Older revision		Revision as of 02:41, 10 February 2025
Line 9:		Line 9:
	== Difficulty of problem and security of cryptosystems==		== Difficulty of problem and security of cryptosystems==

	Many elliptic curve cryptosystems would be ~~immediately~~ broken by a polynomial-time solution ~~were found~~ to this problem. The existence of [[Schoof’s point-counting algorithm]] would appear to cast doubt on the difficulty of the discrete logarithm problem over elliptic curves and the security of cryptosystems that depend on it.		Many elliptic curve cryptosystems would immediately be broken by a polynomial-time solution to this problem. The existence of [[Schoof’s point-counting algorithm]] would appear to cast doubt on the difficulty of the discrete logarithm problem over elliptic curves and the security of cryptosystems that depend on it.

	The U.S. government does not have very much interest at all in the research and development or cryptanalysis of elliptic curve cryptography that depend on the discrete logarithm problem. However, certain European and European axis-aligned governments, including Canada, Japan, Chile and Brazil, do.		The U.S. government does not have very much interest at all in the research and development or cryptanalysis of elliptic curve cryptography that depend on the discrete logarithm problem. However, certain European and European axis-aligned governments, including Canada, Japan, Chile and Brazil, do.

Rational Point: cryptanalysis

2025-02-10T02:40:10Z

cryptanalysis

← Older revision		Revision as of 02:40, 10 February 2025
Line 1:		Line 1:
	The difficulty, or assumed difficulty, of the elliptic curve discrete '''logarithm problem''' is essentially the basis for the claimed security of all elliptic curve public key cryptographic schemes such as [[Ed25519]].		The difficulty, or assumed difficulty, of the elliptic curve discrete '''logarithm problem''' is essentially the basis for the claimed security of all elliptic curve public key cryptographic schemes such as [[Ed25519]].

	Given two points ''P'' and ''Q'' on an elliptic curve over a [[finite field]], the objective is to find the number of times ''P'' should be composed with itself using the [[point group operation]] <math>\oplus</math> to yield ''Q''.		Given two points ''P'' and ''Q'' on an elliptic curve over a [[finite field]], the objective is to find the minimum number of times ''P'' should be composed with itself using the [[point group operation]] <math>\oplus</math> to yield ''Q''. The discrete logarithm is called the '''index''' of ''Q'' with respect to ''P'', and

	:<math>P\oplus P\oplus \cdots \oplus P =Q</math>		:<math>\operatorname{ind}_P(Q)=\min_{n\in\mathbb N}\left\{\underbrace{P\oplus P\oplus \cdots \oplus P}_{n\times} =Q\right\}</math>.

	The [[baby-step giant-step algorithm]] <ref>https://mvpworkshop.co/baby-step-giant-step-algorithm/</ref><ref>https://asecuritysite.com/principles/baby</ref> and [[Pollard’s rho algorithm]] <ref>https://www.geeksforgeeks.org/pollards-rho-algorithm-prime-factorization/</ref> are two of the most well known methods of solving small examples of this problem.		The [[baby-step giant-step algorithm]] <ref>https://mvpworkshop.co/baby-step-giant-step-algorithm/</ref><ref>https://asecuritysite.com/principles/baby</ref> and [[Pollard’s rho algorithm]] <ref>https://www.geeksforgeeks.org/pollards-rho-algorithm-prime-factorization/</ref> are two of the most well known methods of solving small examples of this problem.

			== Difficulty of problem and security of cryptosystems==

			Many elliptic curve cryptosystems would be immediately broken by a polynomial-time solution were found to this problem. The existence of [[Schoof’s point-counting algorithm]] would appear to cast doubt on the difficulty of the discrete logarithm problem over elliptic curves and the security of cryptosystems that depend on it.

			The U.S. government does not have very much interest at all in the research and development or cryptanalysis of elliptic curve cryptography that depend on the discrete logarithm problem. However, certain European and European axis-aligned governments, including Canada, Japan, Chile and Brazil, do.

Rational Point: baby step giant step etc.

2024-12-23T19:35:16Z

baby step giant step etc.

New page

The difficulty, or assumed difficulty, of the elliptic curve discrete '''logarithm problem''' is essentially the basis for the claimed security of all elliptic curve public key cryptographic schemes such as [[Ed25519]].

Given two points ''P'' and ''Q'' on an elliptic curve over a [[finite field]], the objective is to find the number of times ''P'' should be composed with itself using the [[point group operation]] <math>\oplus</math> to yield ''Q''.

:<math>P\oplus P\oplus \cdots \oplus P =Q</math>

The [[baby-step giant-step algorithm]] <ref>https://mvpworkshop.co/baby-step-giant-step-algorithm/</ref><ref>https://asecuritysite.com/principles/baby</ref> and [[Pollard’s rho algorithm]] <ref>https://www.geeksforgeeks.org/pollards-rho-algorithm-prime-factorization/</ref> are two of the most well known methods of solving small examples of this problem.