  We give polynomial time attacks on the McEliece public key cryptosystem based
either on algebraic geometry (AG) codes or on small codimensional subcodes of
AG codes. These attacks consist in the blind reconstruction either of an Error
Correcting Pair (ECP), or an Error Correcting Array (ECA) from the single data
of an arbitrary generator matrix of a code. An ECP provides a decoding
algorithm that corrects up to $\frac{d^*-1-g}{2}$ errors, where $d^*$ denotes
the designed distance and $g$ denotes the genus of the corresponding curve,
while with an ECA the decoding algorithm corrects up to $\frac{d^*-1}{2}$
errors. Roughly speaking, for a public code of length $n$ over $\mathbb F_q$,
these attacks run in $O(n^4\log (n))$ operations in $\mathbb F_q$ for the
reconstruction of an ECP and $O(n^5)$ operations for the reconstruction of an
ECA. A probabilistic shortcut allows to reduce the complexities respectively to
$O(n^{3+\varepsilon} \log (n))$ and $O(n^{4+\varepsilon})$. Compared to the
previous known attack due to Faure and Minder, our attack is efficient on codes
from curves of arbitrary genus. Furthermore, we investigate how far these
methods apply to subcodes of AG codes.
