Un protocole de signature électronique

Je ne comprends pas le principe. Comment est-ce que Bob peut vérifier quelque chose sans calculer $Q$ ni $n$ ?

Dans un autre esprit, la taille de $Q$ augmente de façon exponentielle, ce qui borne $n$ assez fort – par exemple, sur Sage, c'est-à-dire sur Singular, le degré maximal d'un polynôme est $65536=2^{16}$ par défaut (encore plus petit que prévu). Il faut 1,7 s à Sage pour calculer la 15^e itération de $x^2+1$ sur $\mathbf{F}_{25}$ (mais Sage n'est pas très fort à ça).

De plus, le degré de $P$ permet de retrouver $d^n$, où $d$ est le degré de $Q$. Vu la remarque précédente, cela permet de trouver $d$ avec peu d'indétermination (le pire qui puisse arriver, c'est de remplacer $d^n$ par $(d^e)^{n'}$ avec $n=en'$). Connaître le degré de $Q$, sans doute assez petit, pourrait permettre une attaque par force brute.

Si Oscar intercepte $P$, il lui suffit ensuite de réenvoyer $P$ pour se faire passer pour Alice ??