í. é. áÎÏÈÉÎ, î. ð. ÷ÁÒÎÏ×ÓËÉÊ, ÷. í. óÉÄÅÌØÎÉËÏ×, ÷. ÷. ñÝÅÎËÏ "ëòéðôïçòáæéñ ÷ âáîëï÷óëïí äåìå"

çÅÏ×ÉËÉÐÅÄÉÑ
wiki.web.ru

ðÏÉÓË

çÌÁ×ÎÁÑ ÓÔÒÁÎÉÃÁ

ëÏÎÆÅÒÅÎÃÉÉ: ëÁÌÅÎÄÁÒØ / íÁÔÅÒÉÁÌÙ

ëÁÔÁÌÏÇ ÓÓÙÌÏË

óÌÏ×ÁÒØ

æÏÒÕÍÙ

÷ ÐÏÍÏÝØ ÓÔÕÄÅÎÔÕ

ðÏÓÌÅÄÎÉÅ ÐÏÓÔÕÐÌÅÎÉÑ

çÅÏÌÏÇÉÑ | ëÕÒÓÙ ÌÅËÃÉÊ

ïÂÓÕÄÉÔØ × ÆÏÒÕÍÅ

äÏÂÁ×ÉÔØ ÎÏ×ÏÅ ÓÏÏÂÝÅÎÉÅ

÷ÐÅÒÅÄ: 6.2.2.2 óÔÏÊËÏÓÔØ ÐÒÏÔÉ× ÍÎÏÇÏËÁÎÁÌØÎÏÇÏ ÐÏÄÓÌÕÛÉ×ÁÎÉÑ ÷×ÅÒÈ: 6.2.2 ðÒÏÔÏËÏÌÙ ÄÌÑ ËÏÎÆÅÒÅÎÃ-Ó×ÑÚÉ îÁÚÁÄ: 6.2.2 ðÒÏÔÏËÏÌÙ ÄÌÑ ËÏÎÆÅÒÅÎÃ-Ó×ÑÚÉ óÏÄÅÒÖÁÎÉÅ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ

6.2.2.1 ðÒÏÔÏËÏÌ éÎÇÅÍÁÒÓÓÏÎÁ -- ôÁÎÇÁ -- ÷ÏÎÇÁ

íÙ ÐÒÉ×ÅÄÅÍ ÐÒÏÔÏËÏÌ ÄÌÑ ËÏÎÆÅÒÅÎÃ-Ó×ÑÚÉ, Ñ×ÌÑÀÝÉÊÓÑ ÏÂÏÂÝÅÎÉÅÍ ÐÒÏÔÏËÏÌÁ äÉÆÆÉ -- èÅÌÌÍÁÎÁ É ÐÒÅÄÌÏÖÅÎÎÙÊ × ÒÁÂÏÔÅ éÎÇÅÍÁÒÓÓÏÎÁ, ôÁÎÇÁ É ÷ÏÎÇÁ [ITW]. ÷×ÅÄÅÍ ÏÂÏÚÎÁÞÅÎÉÑ. ðÕÓÔØ -- ÞÉÓÌÏ ÁÂÏÎÅÎÔÏ×, ÖÅÌÁÀÝÉÈ ×ÙÒÁÂÏÔÁÔØ ÏÂÝÉÊ ÓÅËÒÅÔÎÙÊ ËÌÀÞ. ïÂÏÚÎÁÞÉÍ ÜÔÉÈ ÁÂÏÎÅÎÔÏ× ÜÌÅÍÅÎÔÁÍÉ ËÏÌØÃÁ $\mathbb{Z}_m$ , ÓÌÏÖÅÎÉÅ É ×ÙÞÉÔÁÎÉÅ × ËÏÔÏÒÏÍ ÂÕÄÅÔ ÏÂÏÚÎÁÞÁÔØÓÑ ÞÅÒÅÚ $\oplus$ É $\ominus$ . ðÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ×ÓÅÍ ÁÂÏÎÅÎÔÁÍ ÉÚ×ÅÓÔÎÙ ÂÏÌØÛÏÅ ÐÒÏÓÔÏÅ ÞÉÓÌÏ É ÐÏÒÏÖÄÁÀÝÉÊ ÇÒÕÐÐÙ $\mathbb{Z}_p*$ .

ðÒÏÔÏËÏÌ ÓÏÓÔÏÉÔ ÉÚ ÛÁÇÏ×. ëÁÖÄÙÊ ÛÁÇ (ÓËÁÖÅÍ, -Ê) ÓÏÓÔÏÉÔ × ÔÏÍ, ÞÔÏ ËÁÖÄÙÊ ÁÂÏÎÅÎÔ ×ÙÞÉÓÌÑÅÔ ÓÏÏÂÝÅÎÉÅ $M_{ir}$ É, ÅÓÌÉ $r\ne m$ , ÐÏÓÙÌÁÅÔ ÅÇÏ ÁÂÏÎÅÎÔÕ $i\oplus1$ . äÅÊÓÔ×ÉÑ ÁÂÏÎÅÎÔÁ ÎÁ -Í ÛÁÇÅ × ÜÔÏÍ ÐÒÏÔÏËÏÌÅ ÉÍÅÀÔ ÓÌÅÄÕÀÝÉÊ ×ÉÄ: I. åÓÌÉ , ÔÏ ×ÙÂÒÁÔØ $x_i\in_{\mbox{\tiny\rm R}}\{1,2,\ldots,p-1\}$ , ×ÙÞÉÓÌÉÔØ $M_{i1}^{(1)}=g^{x_i}\bmod p$ É ÐÅÒÅÓÌÁÔØ ÅÇÏ ÁÂÏÎÅÎÔÕ $i\oplus1$ .

II. åÓÌÉ $r\geqslant 2$ , ÔÏ ×ÙÞÉÓÌÉÔØ $M_{ir}=M_{i\ominus1,r-1}^{x_i}\bmod p$ , ÉÓÐÏÌØÚÕÑ ÓÏÏÂÝÅÎÉÅ $M_{i\ominus1,r-1}$ , ÐÏÌÕÞÅÎÎÏÅ ÏÔ ÁÂÏÎÅÎÔÁ $i\ominus1$ ÎÁ -Í ÛÁÇÅ. åÓÌÉ $r\ne m$ , ÔÏ ÐÅÒÅÓÌÁÔØ ÓÏÏÂÝÅÎÉÅ $M_{ir}$ ÁÂÏÎÅÎÔÕ $i\oplus1$ . åÓÌÉ ÖÅ , ÔÏ ÐÏÌÏÖÉÔØ $k_i=M_{ir}=M_{im}$ × ËÁÞÅÓÔ×Å ÏÂÝÅÇÏ ÓÅËÒÅÔÎÏÇÏ ËÌÀÞÁ. ïÞÅ×ÉÄÎÏ, ÞÔÏ × ÜÔÏÍ ÐÒÏÔÏËÏÌÅ $M_{ir}=g^{x_{i\ominus(r\ominus1)}\ldots x_{i\ominus1}x_i}\bmod p$ , É ÏÂÝÉÊ ÓÅËÒÅÔÎÙÊ ËÌÀÞ ËÁÖÄÏÇÏ ÁÂÏÎÅÎÔÁ ÒÁ×ÅÎ $g^{x_0x_1\ldots x_{m-1}}\bmod p$ .

íÉÈÁÉÌ áÎÏÈÉÎ

ðÒÏÅËÔ ÏÓÕÝÅÓÔ×ÌÑÅÔÓÑ ÐÒÉ ÐÏÄÄÅÒÖËÅ:
çÅÏÌÏÇÉÞÅÓËÏÇÏ ÆÁËÕÌØÔÅÔÁ íçõ,
òææé