Pourquoi c'est sûr : soundness et zero-knowledge

Un bon protocole d'identification doit satisfaire deux exigences opposées : ne rien révéler du secret, et pourtant prouver de façon convaincante qu'on le détient. Schnorr réussit les deux.

Zero-knowledge : l'aléa masque tout

Reprenons la réponse s = r + c*x. La clé x y est bien présente, mais elle est additionnée à r, un nombre tiré au hasard à chaque exécution. Comme r est uniforme et secret, la somme r + c*x est elle aussi uniformément distribuée : elle ne laisse rien filtrer sur x.

Concrètement, un observateur qui enregistrerait mille exécutions verrait mille triplets (t, c, s) d'apparence parfaitement aléatoire. On dit que le protocole est zero-knowledge : Valérie (ou un espion) repart convaincue, mais sans un bit d'information exploitable sur x. L'aléa r joue le rôle d'un masque jetable renouvelé à chaque preuve.

Soundness : on ne triche pas au hasard

La solidité (soundness) est la propriété inverse : un menteur qui ne connaît pas x ne doit pas pouvoir convaincre Valérie. La preuve repose sur une idée magnifique, l'extraction.

Supposons qu'un tricheur sache répondre correctement à deux défis différents c1 et c2 pour le même engagement t. Il produit donc deux réponses valides :

s1 = r + c1*x
s2 = r + c2*x

Soustrayons la seconde de la première :

s1 - s2 = (r + c1*x) - (r + c2*x) = (c1 - c2)*x

Le r disparaît ! On isole alors la clé :

x = (s1 - s2) / (c1 - c2)

   même t, deux défis
   ------------------
   t fixé
     |-- c1 --> s1 = r + c1*x
     |-- c2 --> s2 = r + c2*x
                        |
        x = (s1 - s2) / (c1 - c2)

Autrement dit : savoir répondre à deux défis, c'est connaître x. Un tricheur qui ne connaît pas x ne peut donc répondre qu'à un seul défi au mieux (celui qu'il a anticipé). Face à un défi tiré au hasard parmi un grand nombre de possibilités, sa probabilité de succès est négligeable.

Le piège mortel : réutiliser l'aléa

Cette même arithmétique se retourne contre le prouveur s'il est négligent. Si Pierre réutilise le même r (donc le même t) pour répondre à deux défis distincts, il fournit lui-même les deux équations ci-dessus. N'importe qui, en observant (s1, c1) et (s2, c2), calcule :

x = (s1 - s2) / (c1 - c2)

et récupère la clé privée. La règle d'or est donc : r doit être frais, aléatoire et secret à chaque exécution.

Ce n'est pas une menace théorique. La même faille a compromis des clés bien réelles : le nonce réutilisé dans ECDSA a permis d'extraire les clés de signature de la console PlayStation 3 en 2010, et de portefeuilles Bitcoin dont le générateur d'aléa était défaillant.

En résumé

L'aléa r masque la clé (zero-knowledge) et rend la triche impossible (soundness) : deux réponses valides pour un même t révèlent x par x = (s1 - s2) / (c1 - c2). Cette extraction prouve la sûreté, mais impose une discipline absolue — ne jamais réutiliser r, sous peine de divulguer soi-même son secret.