I'll leave alone the OpenPGP spec, and consider the problem of identifying among $k$ public keys $(n_i,e_i)$ the RSA public key $(n_j,e_j)$ used to encrypt $m$ messages per RSA with proper encryption padding. The only way is by examining the $m$ cryptograms $c_\ell$, which essentially are indistinguishable from uniformly random in $[0,n_j)$.
The analysis can use two facts:
- If $n_i\le\max c_\ell$ , that rules out $i=j$.
- $x=\frac1m\sum c_\ell$, which the attacker should compute, has Bates distribution close to normal for large $m$, with mean $(n_j-1)/2$, standard deviation $(n_j-1)/\sqrt{12m}$.
In practice, the most likely $j$ is $i$ with $n_i/2$ closest to $x$ among the $n_i$ surviving test 1. It should be computed $t_i=\lvert n_i/2-x\rvert\sqrt{12m}/n_i$ for the values of $i$ with $n_i/2$ the closest to $x$: the larger $t_i$, the least likely $i$ is, with $t_i<1$, $t_i<2$, $t_i<3$ per the 68-95-99.7% rule.
To pursue the analysis, we need an idea of the distribution of the $n_i$.
- By making the say 256 high-order bits of the $n_i$ equal at generation time (fixed to some haphazard constant), which is easy and does not harm RSA security or interoperability, we could make identification hopeless.
- For a generation with the prime factors $p_i$ and $q_i$ of $n_i$ independent and roughly uniform in $[2^{(b-1)/2},2^{b/2}]$ as customary, I think an attacker would need $m$ in the order of $k^2$, but it's getting too late for me to make a justification or a better evaluation.