Högre restproblem

Inom kryptografi bygger de flesta kryptosystem med publik nyckel på problem som tros vara svårlösta. Problemet med högre resthalt (även kallat problemet med n:te rester ) är ett sådant problem. Detta problem är lättare att lösa än heltalsfaktorisering , så antagandet att detta problem är svårt att lösa är starkare än antagandet att heltalsfaktorisering är svårt.

Matematisk bakgrund

Om n är ett heltal så bildar heltalen modulo n en ring . Om n = pq där p och q är primtal , så säger den kinesiska restsatsen oss att

$\mathbb {Z} /n\mathbb {Z} \simeq \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z}$

Gruppen av enheter i valfri ring bildar en grupp , och gruppen av enheter i $\mathbb {Z} /n\mathbb {Z}$ betecknas traditionellt $(\mathbb {Z} /n\mathbb {Z} )^{*}$ .

Från isomorfismen ovan har vi

$(\mathbb {Z} /n\mathbb {Z} )^{*}\simeq (\mathbb { Z} /p\mathbb {Z} )^{*}\times (\mathbb {Z} /q\mathbb {Z} )^{*}$

som en isomorfism av grupper . Eftersom p och q antogs vara primtal, grupperna $(\mathbb {Z} /p\mathbb {Z} )^{*}$ och ${ \displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$ är cykliska av order p -1 respektive q -1. Om d är en divisor av p -1, så bildar mängden d :te potenser i $(\mathbb {Z} /p\mathbb {Z} )^{*}$ en undergrupp av index d . Om gcd( d , q -1) = 1, så är varje element i ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}} en d:$ te potens , så uppsättningen d :te potenser i $(\mathbb {Z} /n\mathbb {Z} )^{*}$ är också en undergrupp av index d . I allmänhet, om gcd( d , q -1) = g , så finns det ( q -1)/( g ) d :te potenser i $(\mathbb {Z} /q\ mathbb {Z} )^{*}$ , så uppsättningen d :te potenser i $(\mathbb {Z} /n\mathbb {Z} )^{*}$ har index dg . Detta ses oftast när d =2, och vi betraktar undergruppen av kvadratiska rester , det är välkänt att exakt en fjärdedel av elementen i $(\mathbb {Z} /n \mathbb {Z} )^{*}$ är kvadratiska rester (när n är produkten av exakt två primtal, som det är här).

Det viktiga är att för varje divisor d av p -1 (eller q -1) bildar mängden d :te potenser en undergrupp av $(\mathbb {Z} /n\mathbb {Z} )^{*}.$

Problemformulering

Givet ett heltal n = pq där p och q är okända, ett heltal d så att d delar p -1, och ett heltal x < n , är det omöjligt att bestämma om x är en d: te potensen (motsvarande d: te resten) modulo n .

Observera att om p och q är kända är det lätt att avgöra om x är en d: te restmodulo n eftersom x kommer att vara en d: te restmodulo p om och endast om

$x^{(p-1)/d}\equiv 1{\pmod {p}}$

När d =2 kallas detta det kvadratiska residuositetsproblemet .

Ansökningar

Den semantiska säkerheten för Benalohs kryptosystem och Naccache-Stern kryptosystem vilar på svårigheten i detta problem.