Password Authentication challenge
Password is an n-vector <math>\hat{x}</math> over GF(2)
Repeated until Computer is convinced that Human knowns password <math>\hat{x}</math> .
Eve eavesdrops on communication, learns m pairs: <MATH> \begin{array}{c} a_1,b_1 \\ \vdots \\ a_m,b_m \end{array} </MATH> such that <math>b_i</math> is the right response to challenge <math>a_i</math> (ie <math>a · \hat{x}</math> ).
Then Eve can calculate right response to any challenge in <math>Span \{a1, \dots , a_m\}</math>
Suppose <math>a = \alpha_1 a_1 + \dots + \alpha_m a_m</math> Then right response is <math>\beta_1 . b_1 + \dots + \beta_m . b_m</math>
Fact: Probably rank [a1, . . . , am] is not much less than m.
Once m > n, probably <math>Span \{a_1, \dots , a_m\}</math> is all of <math>GF(2)^n</math> .
So Eve can respond to any challenge
Also: The password <math>\hat{x}</math> is a solution to: <MATH> \underbrace{ \begin{bmatrix} \begin{array}{r} a_1 \\ \hline\\ \vdots\\ \hline a_2 \end{array} \end{bmatrix} }_{A} \begin{bmatrix} x \end{bmatrix} = \underbrace{ \begin{bmatrix} \begin{array}{r} b_1 \\ \hline\\ \vdots\\ \hline b_m \end{array} \end{bmatrix} }_{b} </MATH>
Solution set of Ax = b is <math>\hat{x}+ \textrm{Null A}</math> Once rank A reaches n, columns of A are linearly independent so Null A is trivial, so the only solution is the password <math>\hat{x}</math> , so we can compute the password using solver.
The way to make the scheme more secure is to introduce mistakes.
Gaussian elimination (of any other method) does not find the solution when some of the right-hand side values are wrong.