1761708 - mp_xgcd produces incorrect Bezout coefficients

Status: RESOLVED WONTFIX

(NSS :: Libraries, defect, P5)

Description

[Guido Vranken]

Attachment: nss-mp_xgcd-bezout.c

Steps to reproduce:

The attached reproducer produces X = 125, Y = -1.

Actual results:

Produce X = -124, Y = 1.

Expected results:

GCD(4, 498) is 2.

The attached reproducer produces X = 125, Y = -1.
This is correct in the sense that it satisfies the equation XA + YB == GCD(A,B).

However, the X, Y returned from an extended GCD algorithm must satisfy:

X <= (B / (2 * GCD(A,B)))
Y <= (A / (2 * GCD(A,B)))

Source: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Description

The correct output is:

X = -124
Y = 1

Comment 1

[John Schanck [:jschanck]]

Thanks for raising this, Guido. I see why it would be useful in some situations to assume that mp_xgcd produces the minimal Bezout pair, but most applications do not need this. The comment at the top of mp_xgcd says that it implements Stein's algorithm as in "algorithm 14.61 in Handbook of Applied Cryptogrpahy". As far as I can tell it does this correctly.

I'm curious, do you have an application that needs the minimal Bezout pair? I think it would be strange for an "xgcd" function to output a very large Bezout pair, but the two smallest solutions seem equally good to me.

Comment 2

[Guido Vranken]

I don't use this function myself, so I'm not bothered by its behavior. I found this issue with my fuzzer and wanted to notify you about it. Feel free to close this report as N/A.