4
$\begingroup$

I understand it when we have to solve Discrete Logarithm Problem $a^x\equiv b\pmod p$, where $a$ and $b$ are given integers and we have to find secret integer $x$ that makes the equation true for some given modulus $p$.

I do not understand it when $a$ and $b$ are polynomials and we are working not only modulo integer but also modulo another polynomial.

  1. Can you give me an explicit working example of DSA applied to this context?
  2. What attacks against it are known?

EDIT: In the original standard, finite field has characteristic 2. By "medium" fields I mean field GF(p^n) where prime $p$ is bigger. Instead of $p=2$ it is around $10^{10}$ and $n=17$ or so.

EDIT 2: My own example: $$a=4 x^6+10 x^5+11 x^4+3 x^3+x^2+15 x+7$$ $$b=12 x^6+4 x^5+8 x^4+4 x^3+9 x^2+6 x+7$$ $$m_1=x^7-2$$ $$m_2=17$$

Find $e$ that $$a^e\equiv b\pmod{m_1}\pmod{m_2}$$

I am not sure whether my example is relevant, there are some criteria on choosing polynomial $m_1$ and prime $m_2$. I chose them arbitrary. But I can say $e=103$ is a solution since I brute-forced it.

$\endgroup$
  • $\begingroup$ The context is arithmetic in $\mathrm{GF}(p^n)$ for stated $p$ and $n$, the DLP in this, and a variant of DSA in this. Note: in the original DSA, the field is $\mathrm{GF}(p)$ for large $p$, not $\mathrm{GF}(2^n)$. If you start from a variant of DSA in $\mathrm{GF}(2^n)$, it could help to describe it (in particular the equivalent of $q$ in standard DSA is unclear to me). Update: your "own example" in $\mathrm{GF}(p^n)$ with $p=m_2=17$ and $n=7$, right? $\endgroup$ – fgrieu Mar 1 at 21:58
  • $\begingroup$ Yes, that is right. $\endgroup$ – azerbajdzan Mar 1 at 22:06
  • $\begingroup$ Do you have a reference for your "original standard" constructing a DSA in $\mathrm{GF}(2^n)$, which is not standard DSA? Hint: the criteria for $m_1$ is that it irreducible modulo $p=m_2$. Otherwise we get a ring, not a field as in the question's title. Per the question's choices of $m_1=x^2-2$ and $m_2=17=p$, can $(x+8)$ have an inverse? Notice that$$(x+8)(x^6+9x^5+13x^4+15x^3+16x^2+8x+4)\\\quad\equiv x^7-2\pmod{17}$$ $\endgroup$ – fgrieu Mar 2 at 9:34
  • $\begingroup$ I do not think your equation holds. Left side is $x^7+15$ and right is $x^2+15$. Or am I missing something? I read several papers on internet I hope I can find the one with the "original standard". But I can confirm $x^7-2$ is not irreducibile modulo $p=17$. So $p=m_2=29$ would be a better choice with $m_1=x^7-2$. $\endgroup$ – azerbajdzan Mar 2 at 10:17
  • 1
    $\begingroup$ Yes with modulo $p=29$, the polynomial $x^7-2$ is irreducible. Pollard's rho can solve the DLP for your toys instances, but not the general case in $\mathrm{GF}(p^n)$ with $p^n$ like 565-bit, as you aim at. Other methods can. There's a tour with recent results, in Razvan Barbulescu and Cécile Pierrot's The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields. Algorithm of choice could be their [JLSV06]. $\endgroup$ – fgrieu Mar 2 at 10:53
4
$\begingroup$

The question deals with the finite field $\mathrm{GF}(p^n)$. It wants to study/attack a variant of DSA in (the multiplicative subgroup of) that field, rather than $\mathrm{GF}(p)$. Whatever that DSA variant is, it can be attacked by solving the Discrete Logarithm Problem in $\mathrm{GF}(p^n)$.

The multiplicative subgroup of $\mathrm{GF}(p^n)$ has order $p^n-1$, and the order of any element divides that. If the order of $a$ has no large prime factor, then the Pohlig-Hellman method allows reduction to easier subproblems, that a general DLP algorithm like Baby-Step Giant Step or Pollard's rho can solve. DSA blocks such attacks by working in a multiplicative subgroup of large prime order $q$ (e.g. at least 256-bit). That also keeps signature size to the minimum (twice the bitsize of $q$).

The parameters envisioned are $p\approx10^{10}$ and $n=17$, thus $p^n$ about 565-bit, making such subgroup plausible. If we want $p$ just below $2^{32}$ and $x^{17}-2$ irreducible modulo $p$ (which simplifies computations), we can use the 32-bit $p=\mathtt{ffe083f1}_\text{h}$, with $p^{17}-1$ having as highest prime factor the 262-bit $q=\mathtt{2a92bc16243adf3264304adf2adc292c32e64b569a5abfbd7be71d7a1816e3d8c1}_\text{h}$. To obtain an element of order $q$, we can select almost any arbitrary polynomial $u$; find the order $r$ of $u$ (we divide $p^{17}-1$ by primes in its factorization while raising $u$ to that power yields $1$); and use $g=u^{r/q}$ as the generator of a subgroup of order $q$.

Building a DSA analog from that and SHA-512 is easy. The only difficulty is when the original makes an exponentiation modulo $p$ followed by a reduction modulo $q$. Among many, one option to parallel this is to make the exponentiation modulo $x^{17}-2\pmod p$, then evaluate that polynomial in $\Bbb Z$ at the point $x=2^{32}$ (that is concatenate the coefficients expressed as 32-bit integers), then reduce modulo $q$.

That will make a working DSA, secure against all the aforementioned algorithms thanks to the large $q$. But that's nevertheless insecure, for other DLP methods are applicable to the case at hand. There's a summary of recent results in Razvan Barbulescu and Cécile Pierrot's The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields, in LMS Journal of Computation and Mathematics, 2014.

Tentatively: the algorithm of choice to attack that DSA analog could be Antoine Joux, Reynald Lercier, Nigel P. Smart, and Frederik Vercautere's The number field sieve in the medium prime case, in proceedings of Crypto 2006.


The musing with a small example at the end of the question attempts to work in $\mathrm{GF}(17^7)$, but uses a polynomial $m_1=x^7-2$ that is not irreducible modulo $p=17=m_2$, since$$(x+8)(x^6+9x^5+13x^4+15x^3+16x^2+8x+4)\\\quad\equiv x^7-2\pmod{17}$$

It follows that $(x+8)$ is not invertible, and we get a ring rather than a field.

If we change to $p=29$ that makes $x^7-2$ irreducible. I assume this in the following.

The multiplicative subgroup of $\mathrm{GF}(p^n)$ has order $p^n-1$, here $29^7-1$. This factors as $2^2\cdot7^2\cdot88009573$. The order of $a$ is bound to be a divisor of that. By computing $a^{(29^7-1)/2}=-1\ne1$, $a^{(29^7-1)/7}=-5\ne1$, and $a^{(29^7-1)/88009573}\ne1$, we get that $a$ is a generator of the full multiplicative group. $b\ne0$, therefore $a^e=b$ has a solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.