Schnorr grupp

En Schnorr-grupp , föreslagen av Claus P. Schnorr , är en stor prime-order undergrupp av $\mathbb {Z} _{p}^{\times }$ , den multiplikativa gruppen av heltal modulo ${\ displaystyle p}$ för vissa primtal $p$ . För att generera en sådan grupp, generera $p$ , $q$ , $r$ så att

p=qr+1

med $p$ , $q$ primtal. Välj sedan valfri $h$ i intervallet $1<h<p$ tills du hittar en sådan som

h^{r}\not \equiv 1\;({\text{mod}}\;p)

.

Detta värde

g=h^{r}{\text{ mod }}p

är en generator av en undergrupp av $\mathbb {Z} _{p}^{\times }$ av ordningen $q$ .

Schnorr-grupper är användbara i diskreta loggbaserade kryptosystem inklusive Schnorr -signaturer och DSA . I sådana applikationer väljs typiskt ${\displaystyle p} för att vara tillräckligt stor för att motstå$ indexkalkyl och relaterade metoder för att lösa problemet med diskret logg (kanske 1024 till 3072 bitar), medan $q$ är tillräckligt stor för att motstå födelsedagsattacken på diskreta loggproblem, som fungerar i vilken grupp som helst (kanske 160 till 256 bitar). Eftersom Schnorr-gruppen är av högsta ordning, har den inga icke-triviala riktiga undergrupper, vilket motverkar instängningsattacker på grund av små undergrupper. Implementering av protokoll som använder Schnorr-grupper måste vid behov verifiera att heltal som tillhandahålls av andra parter faktiskt är medlemmar i Schnorr-gruppen; $x$ är medlem i gruppen om $0<x<p$ och $x^{q}\equiv 1\;({ \text{mod }}p)$ . Alla medlemmar i gruppen utom element $1$ är också en generator av gruppen.