ge fromfe writeup (RUS) (PDF)

ÐÅÇÞÌÅ

UNPUBLISHED

Ôóíêöèÿ ge_fromfe_frombytes_vartime
Øåí Íîåçåð (Shen Noether)∗
Èññëåäîâàòåëüñêàÿ ëàáîðàòîðèÿ Monero (Monero Research Lab)

Àííîòàöèÿ
Ìíîþ ðàññìàòðèâàåòñÿ ôóíêöèÿ ge_fromfe_frombytes_vartime, èñïîëüçóåìàÿ ñ ôóíêöèÿìè îáðàçîâ
êëþ÷åé Monero.

1

Âñòóïëåíèå

 ýòîé êîðîòêîé òåõíè÷åñêîé çàìåòêå ìíîþ ðàññìàòðèâàåòñÿ ôóíêöèÿ ge_fromfe_frombytes_vartime,
èñïîëüçóåìàÿ â îáðàçàõ êëþ÷åé Monero. Ñëåäóåò îòìåòèòü, ÷òî ýòîò êîä áûë óíàñëåäîâàí îò ðàçðàáîò÷èêîâ
îðèãèíàëüíîãî ïðîòîêîëà CryptoNote, êîòîðûå, áåçóñëîâíî, ÿâëÿþòñÿ ñïåöèàëèñòàìè â îáëàñòè êðèïòîãðàôèè,
íî ÷åé íåäîñòàòîê çàêëþ÷àåòñÿ â íåóìåíèè îáúÿñíÿòü è êîììåíòèðîâàòü ñâîþ ðàáîòó. Òàêæå õîòåëîñü
áû îòìåòèòü, ÷òî ïðîøëûì ëåòîì ìíîþ óæå áûëà çàìåíåíà áîëüøàÿ ÷àñòü êðèïòîãðàôè÷åñêîé áèáëèîòåêè
ed25519, èñïîëüçóåìîé Monero, íà âàðèàíò ref10, ïðåäëîæåííûé Áåðíøòåéíîì.
 íåäàâíî ïîÿâèâøèõñÿ èññëåäîâàòåëüñêèõ ðàáîòàõ (äîâîëüíî èçâåñòíûõ àâòîðîâ) ðàññìàòðèâàëàñü
âîçìîæíîñòü íàëîæåíèÿ ñëó÷àéíîé ñòðîêè íà òî÷êó íà ýëëèïòè÷åñêîé êðèâîé [ñì. [BCI+ 10, FFS+ 13]].
Èíòåðåñíî, ÷òî ôóíêöèÿ ¾õåøèðîâàíèÿ ïî òî÷êå¿, ge_fromfe_frombytes_vartime, èñïîëüçóåìàÿ ïðîòîêîëîì
CryptoNote [vS13], êàæåòñÿ, íå óïîìèíàëàñü íè â îäíîé èç ýòèõ ðàáîò, íî ïîòåíöèàëüíî ÿâëÿåòñÿ áîëåå
ýôôåêòèâíûì àëãîðèòìîì.

2

fe_frombytes

Î÷åâèäíî, ÷òî ýòà ÷àñòü ÿâëÿåòñÿ fe_frombytes èç ref10.

3

Íåèçâåñòíàÿ ÷àñòü

Ïðåäïîëîæèì, ÷òî ñíà÷àëà y ≡ 0, à sign ≡ sign.
Ñëåäîâàòåëüíî, ïîëó÷àåì:
2u2 + 1 − x ≡ 0
÷òî äà¼ò íàì x ≡ 2u2 + 1.
Òàêèì îáðàçîì,

2u2 + 1 ≡ rx2 (w2 − 2A2 u2 )
÷òî äà¼ò íàì


rx =

2u2 + 1
w2 − 2A2 u2

∗ shen.noether@gmx.com

1

 12
.

 ýòîì ñëó÷àå ìû ïðàâèëüíî âû÷èñëÿåì êâàäðàòíûé êîðåíü ñ ïåðâîé ïîïûòêè. Òåïåðü íàì íåîáõîäèìî
óáåäèòüñÿ â òîì, ÷òî y è x íàõîäÿòñÿ íà ýëëèïòè÷åñêîé êðèâîé.

xp = w2 − 2A2 u2 = 2u2 + 1


2

− 2A2 u2

.5

rxt = (w/xp )


xt = rxt2 w2 − 2A2 u2 →



w
w2 − 2A2 u2





w2 − 2A2 u2 → w

(åñëè rxt äåéñòâèòåëüíî ÿâëÿåòñÿ êâàäðàòíûì êîðíåì).

y = 2u2 + 1 − xt





 12
1

u2 w
w 2
= − 2A (A + 2) 2
rx = −u 2A (A + 2)
xp
w − 2A2 u2
z = −2Au2 = − (w − 1) A = (1 − w) A
(ñëåäóåò îòìåòèòü, ÷òî −z = 2Au2 , zA = −2A2 u2

ry = z − w
2

Y 2 = (z − w)

rz = z + w
2

Z 2 = (z + w)

u2 w
rx−f inal = (z + w) 2A (A + 2) 2
w + zA


2Au2 w
2
2
X = Z (A + 2) 2
w + zA
−zw
= Z 2 (A + 2) 2
w + Az


d=−

 12

A−2
A+2

ïðîâåðÿåì, äåéñòâèòåëüíî ëè

−X 2 Z 2 + Y 2 Z 2 = Z 2


2

+ dX 2 Y 2

èëè, äðóãèìè ñëîâàìè, ÷òî

Z 4 (A + 2)

zw
zw
2
2
+ Z 2 (z − w) = Z 4 + (A − 2) Z 2 2
(z − w)
w2 + Az
w + Az

ñîêðàùàåì Z 2 :
2

(z + w) (A + 2)

w2

zw
zw
2 ?
2
2
+ (z − w) = (z + w) + (A − 2) 2
(z − w)
+ Az
w + Az
2

Ïîñëå ýòîãî óìíîæàåì íà w2 + Az



2
2
(z + w) (A + 2) zw + (z − w) w2 + Az


?
2
2
= (z + w) w2 + Az + (A − 2) (zw) (z − w)
Ïîñëå âêëþ÷åíèÿ z = (1 − w) A ïðè ïîìîùè êîìïüþòåðíîé àëãåáðàè÷åñêîé ñèñòåìû, òàêîé êàê Maxima,
ïðîâåðÿåì ðàâåíñòâî äâóõ ñòîðîí.
Òåïåðü ó íàñ èìååòñÿ íåñêîëüêî îïåðàòîðîâ ¾åñëè¿ äëÿ ðàçëè÷íûõ ñëó÷àåâ.  ïåðâîì ñëó÷àå
ïðîâåðÿåòñÿ, áûë ëè â ðåçóëüòàòå âû÷èñëåíèé äåéñòâèòåëüíî ïîëó÷åí îòðèöàòåëüíûé êâàäðàòíûé
êîðåíü. Åñëè ýòî íå òàê, ïðîâåðÿåòñÿ, íå áûë ëè âû÷èñëåí êâàäðàòíûé êîðåíü äëÿ îòðèöàòåëüíîãî
íà÷àëüíîãî çíà÷åíèÿ. Íàêîíåö, îòìåòèâ, ÷òî p = 22 55 − 19 ≡ 1 mod 4, òàê ÷òî −1 ÿâëÿåòñÿ íåâû÷åòîì,
è åñëè âçÿòü ïðîèçâåäåíèå íåâû÷åòîâ, òî ïîëó÷èòñÿ âû÷åò, ìû óìíîæàåì íàøó ïîïûòêó íà −1.

Ññûëêè
[BCI+ 10] Eric Brier, Jean-S
ebastien Coron, Thomas Icart, David Madore, Hugues Randriam, and
Mehdi Tibouchi. Ecient indierentiable hashing into ordinary elliptic curves (Ýôôåêòèâíîå
íåäèôôåðåíöèðóåìîå õåøèðîâàíèå íà îáû÷íûõ ýëëèïòè÷åñêèõ êðèâûõ). In Advances in
CryptologyCRYPTO 2010 (Îïóáëèêîâàíî â ¾Ïðîãðåññ â êðèïòîëîãèè¿), pages 237254.
Springer, 2010.
[FFS+ 13] Reza R Farashahi, Pierre-Alain Fouque, Igor Shparlinski, Mehdi Tibouchi, and J Voloch. Indierentiable deterministic hashing to elliptic and hyperelliptic curves (Íåäèôôåðåíöèðóåìîå
äåòåðìèíèðîâàííîå õåøèðîâàíèå íà ýëëèïòè÷åñêèõ è ãèïåðýëëèïòè÷åñêèõ êðèâûõ). Mathematics of Computation (Âû÷èñëèòåëüíàÿ ìàòåìàòèêà), 82(281):491512, 2013.
[vS13]

Nicolas van Saberhagen (Íèêîëàñ Âàí Ñàáåðõàãåí). Cryptonote v 2. 0. Ññûëêà: https: //
cryptonote. org/ whitepaper. pdf , 2013.

3