Information Technology and Security, Vol. 6, Iss. 2 (11)
ΠΠΎΡΡΡΠΉΠ½Π΅ ΠΏΠΎΡΠΈΠ»Π°Π½Π½Ρ Π·ΡΠ±ΡΠ°Π½Π½Ρ
ΠΠ΅ΡΠ΅Π³Π»ΡΠ½ΡΡΠΈ
ΠΠ΅ΡΠ΅Π³Π»ΡΠ΄ Information Technology and Security, Vol. 6, Iss. 2 (11) Π·Π° ΠΠ²ΡΠΎΡ "ΠΠ°ΠΊΡΠΈΠΌΠ΅Π½ΠΊΠΎ, ΠΠ²Π³Π΅Π½ ΠΠ°ΡΠΈΠ»ΡΠΎΠ²ΠΈΡ"
ΠΠ°ΡΠ°Π· ΠΏΠΎΠΊΠ°Π·ΡΡΠΌΠΎ 1 - 1 Π· 1
Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡΠ² Π½Π° ΡΡΠΎΡΡΠ½ΡΡ
ΠΠ°Π»Π°ΡΡΡΠ²Π°Π½Π½Ρ ΡΠΎΡΡΡΠ²Π°Π½Π½Ρ
ΠΠΎΠΊΡΠΌΠ΅Π½Ρ ΠΡΠ΄ΠΊΡΠΈΡΠΈΠΉ Π΄ΠΎΡΡΡΠΏ ΠΠΎΠ΄ΠΈΡΡΠΊΠΎΠ²Π°Π½ΠΈΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠ°ΠΊΡΠΎΡΠΈΠ·Π°ΡΡΡ Π²Π΅Π»ΠΈΠΊΠΈΡ ΡΠΈΡΠ΅Π» ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π€Π΅ΡΠΌΠ° Π· Π²ΠΈΠΊΠΎΡΠΈΡΡΠ°Π½Π½ΡΠΌ Π±Π°Π·ΠΎΠ²ΠΎΡ ΠΎΡΠ½ΠΎΠ²ΠΈ ΠΌΠΎΠ΄ΡΠ»Ρ(Institute of Special Communication and Information Protection of National Technical University of Ukraine βIgor Sikorsky Kyiv Polytechnic Instituteβ, 2018) ΠΠΈΠ½ΠΈΡΡΠΊ, Π‘ΡΠ΅ΠΏΠ°Π½ ΠΠΌΠΈΡΡΠΎΠ²ΠΈΡ; ΠΠ°ΠΊΡΠΈΠΌΠ΅Π½ΠΊΠΎ, ΠΠ²Π³Π΅Π½ ΠΠ°ΡΠΈΠ»ΡΠΎΠ²ΠΈΡΠΠ΅ΡΠΎΠ΄ ΡΠ°ΠΊΡΠΎΡΠΈΠ·Π°ΡΡΡ Π€Π΅ΡΠΌΠ° Π²Π²Π°ΠΆΠ°ΡΡΡΡΡ ΠΊΡΠ°ΡΠΈΠΌ ΠΏΡΠΈ ΡΠ°ΠΊΡΠΎΡΠΈΠ·Π°ΡΡΡ ΡΠΈΡΠ΅Π» Π²ΠΈΠ΄Ρ N = p β’ q Ρ Π²ΠΈΠΏΠ°Π΄ΠΊΠ°Ρ ΠΊΠΎΠ»ΠΈ ΠΌΠ½ΠΎΠΆΠ½ΠΈΠΊΠΈ p Ρ q Π±Π»ΠΈΠ·ΡΠΊΡ Π·Π° Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌ. ΠΠ±ΡΠΈΡΠ»ΡΠ²Π°Π»ΡΠ½Π° ΡΠΊΠ»Π°Π΄Π½ΡΡΡΡ Π±Π°Π·ΠΎΠ²ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ°ΠΊΡΠΎΡΠΈΠ·Π°ΡΡΡ Π€Π΅ΡΠΌΠ° Π²ΠΈΠ·Π½Π°ΡΠ°ΡΡΡΡΡ ΠΊΡΠ»ΡΠΊΡΡΡΡ ΠΏΡΠΎΠ±Π½ΠΈΡ Π·Π½Π°ΡΠ΅Π½Ρ Π₯ ΠΏΡΠΈ Π²ΠΈΡΡΡΠ΅Π½Π½Ρ ΡΡΠ²Π½ΡΠ½Π½Ρ YΒ² = XΒ² β N, Π° ΡΠ°ΠΊΠΎΠΆ ΡΠΊΠ»Π°Π΄Π½ΡΡΡΡ Π²ΠΈΠΊΠΎΠ½Π°Π½Π½Ρ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ½ΠΈΡ ΠΎΠΏΠ΅ΡΠ°ΡΡΠΉ Π· Π²Π΅Π»ΠΈΠΊΠΈΠΌΠΈ ΡΠΈΡΠ»Π°ΠΌΠΈ: Π·Π²Π΅Π΄Π΅Π½Π½Ρ Π² ΠΊΠ²Π°Π΄ΡΠ°Ρ, ΡΠΊΠ»Π°Π΄Π°Π½Π½Ρ, ΠΎΠ±ΡΠΈΡΠ»Π΅Π½Π½Ρ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠ³ΠΎ ΠΊΠΎΡΠ΅Π½Ρ. ΠΠ½ΠΈΠΆΠ΅Π½Π½Ρ ΠΎΠ±ΡΠΈΡΠ»ΡΠ²Π°Π»ΡΠ½ΠΎΡ ΡΠΊΠ»Π°Π΄Π½ΠΎΡΡΡ Π·Π°Π·Π½Π°ΡΠ΅Π½ΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄Ρ Π·Π°Π±Π΅Π·ΠΏΠ΅ΡΡΡΡΡΡΡ Π·Π° ΡΠ°Ρ ΡΠ½ΠΎΠΊ Π²ΠΈΠΊΠΎΡΠΈΡΡΠ°Π½Π½Ρ Π±Π΅Π·Π»ΡΡΡ ΠΎΡΠ½ΠΎΠ² ΠΌΠΎΠ΄ΡΠ»ΡΠ² Π² ΡΡΠ²Π½ΡΠ½Π½Ρ YΒ²modb = (XΒ²-N)modb, ΡΠΎ Π² ΡΠ²ΠΎΡ ΡΠ΅ΡΠ³Ρ Π΄ΠΎΠ·Π²ΠΎΠ»ΡΡ Π·Π½Π΅Ρ ΡΡΠ²Π°ΡΠΈ ΡΠΊΠ»Π°Π΄Π½ΡΡΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΡΠΉ ΠΎΠ±ΡΠΈΡΠ»Π΅Π½Π½Ρ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠ³ΠΎ ΠΊΠΎΡΠ΅Π½Ρ. ΠΠ»Ρ Π·ΠΌΠ΅Π½ΡΠ΅Π½Π½Ρ ΡΠΈΡΠ»Π° ΠΏΡΠΎΠ±Π½ΠΈΡ Π·Π½Π°ΡΠ΅Π½Ρ Π₯ ΡΠΎΠ·Π³Π»ΡΠ΄Π°Π»Π°ΡΡ ΠΌΠΎΠΆΠ»ΠΈΠ²ΡΡΡΡ Π²ΠΈΠΊΠΎΡΠΈΡΡΠ°Π½Π½Ρ Π±Π°Π·ΠΎΠ²ΠΎΡ (ΠΏΠ΅ΡΠ²ΠΈΠ½Π½ΠΎΡ) ΠΎΡΠ½ΠΎΠ²ΠΈ ΠΌΠΎΠ΄ΡΠ»Ρ bb. ΠΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΈΠΉ Π²ΠΈΠ±ΡΡ Π±Π°Π·ΠΎΠ²ΠΎΡ ΠΎΡΠ½ΠΎΠ²ΠΈ ΠΌΠΎΠ΄ΡΠ»Ρ bb Π΄ΠΎΠ·Π²ΠΎΠ»ΡΡ Π·ΠΌΠ΅Π½ΡΠΈΡΠΈ ΡΠΈΡΠ»ΠΎ ΠΏΡΠΎΠ±Π½ΠΈΡ Π₯ Π½Π° Π²Π΅Π»ΠΈΡΠΈΠ½Ρ, Π±Π»ΠΈΠ·ΡΠΊΡ Π·Π° Π·Π½Π°ΡΠ΅Π½Π½ΡΠΌ Π΄ΠΎ Π²Π΅Π»ΠΈΡΠΈΠ½ΠΈ ΠΊΠΎΠ΅ΡΡΡΡΡΠ½ΡΠ° ΠΏΡΠΈΡΠΊΠΎΡΠ΅Π½Π½Ρ z(N, bb) = bb/bb*, Π΄Π΅ bb* β ΡΠΈΡΠ»ΠΎ Π΅Π»Π΅ΠΌΠ΅Π½ΡΡΠ² ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ ΠΊΠΎΡΠ΅Π½ΡΠ² ΡΡΠ²Π½ΡΠ½Π½Ρ (Ymodb)Β²modb = ((Xmodb)Β²modb - Nmodb)modb. ΠΠΎΠΊΠ°Π·Π°Π½ΠΎ, ΡΠΎ Π² Π·Π°Π³Π°Π»ΡΠ½ΠΎΠΌΡ Π²ΠΈΠΏΠ°Π΄ΠΊΡ Π±Π°Π·ΠΎΠ²Π° ΠΎΡΠ½ΠΎΠ²Π° ΠΌΠΎΠ΄ΡΠ»Ρ bb Ρ Π΄ΠΎΠ±ΡΡΠΊΠΎΠΌ ΡΡΡΠΏΠ΅Π½ΡΠ² ΠΏΡΠΎΡΡΠΈΡ ΡΠΈΡΠ΅Π» Ρ, ΠΊΠΎΠ΅ΡΡΡΡΡΠ½Ρ ΠΏΡΠΈΡΠΊΠΎΡΠ΅Π½Π½Ρ Π΄Π»Ρ ΡΠΊΠΎΠ³ΠΎ z(N, bb) Ρ ΡΡΠ½ΠΊΡΡΡΡ Nmodp Ρ ΠΏΠΎΠΊΠ°Π·Π½ΠΈΠΊΡΠ² ΡΡΡΠΏΠ΅Π½ΡΠ² Ρ. ΠΠΈΠ·Π½Π°ΡΠ΅Π½ΠΎ ΡΡΡΠΏΡΠ½Ρ Π²ΠΏΠ»ΠΈΠ²Ρ Π·Π½Π°ΡΠ΅Π½Π½Ρ Π·Π°Π»ΠΈΡΠΊΡΠ² Nmodp (Π² ΡΠ°Π·Ρ Ρ=2 Π²ΠΈΠΊΠΎΡΠΈΡΡΠΎΠ²ΡΡΡΡΡΡ Π·Π°Π»ΠΈΡΠΊΠΈ Nmod8) Ρ ΠΏΠΎΠΊΠ°Π·Π½ΠΈΠΊΡΠ² ΡΡΡΠΏΠ΅Π½ΡΠ² ΠΏΡΠΎΡΡΠΈΡ Ρ Π½Π° Π²Π΅Π»ΠΈΡΠΈΠ½Ρ ΠΊΠΎΠ΅ΡΡΡΡΡΠ½ΡΠ° ΠΏΡΠΈΡΠΊΠΎΡΠ΅Π½Π½Ρ z(N, bb)). ΠΠ°ΠΏΡΠΎΠΏΠΎΠ½ΠΎΠ²Π°Π½ΠΎ ΠΏΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΡ Π·Π°Π΄Π°ΡΡ ΠΏΠΎΡΡΠΊΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½Π½Ρ Π±Π°Π·ΠΎΠ²ΠΎΡ ΠΎΡΠ½ΠΎΠ²ΠΈ ΠΌΠΎΠ΄ΡΠ»Ρ bb ΠΏΡΠΈ ΠΎΠ±ΠΌΠ΅ΠΆΠ΅Π½Π½ΡΡ Π½Π° ΠΎΠ±ΡΡΠ³ ΠΏΠ°ΠΌ'ΡΡΡ ΠΠΠ Ρ ΡΠΏΠΎΡΡΠ± ΡΡ Π²ΠΈΡΡΡΠ΅Π½Π½Ρ. ΠΠ°Π²Π΅Π΄Π΅Π½ΠΎ ΠΎΡΡΠ½ΠΊΡ Π΅ΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΡ Π·Π°ΠΏΡΠΎΠΏΠΎΠ½ΠΎΠ²Π°Π½ΠΎΠ³ΠΎ ΠΌΠΎΠ΄ΠΈΡΡΠΊΠΎΠ²Π°Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ°ΠΊΡΠΎΡΠΈΠ·Π°ΡΡΡ Π€Π΅ΡΠΌΠ°. ΠΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½ΠΎ, ΡΠΎ Π·Π°ΠΏΡΠΎΠΏΠΎΠ½ΠΎΠ²Π°Π½ΠΈΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π΄Π»Ρ ΡΠΈΡΠ΅Π» 2ΒΉβ°Β²β΄ Π·Π°Π±Π΅Π·ΠΏΠ΅ΡΡΡ Π·Π½ΠΈΠΆΠ΅Π½Π½Ρ ΠΎΠ±ΡΠΈΡΠ»ΡΠ²Π°Π»ΡΠ½ΠΎΡ ΡΠΊΠ»Π°Π΄Π½ΠΎΡΡΡ Π² ΠΏΠΎΡΡΠ²Π½ΡΠ½Π½Ρ Π· Π±Π°Π·ΠΎΠ²ΠΈΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠΌ Π² ΡΠ΅ΡΠ΅Π΄Π½ΡΠΎΠΌΡ Π² 10β· ΡΠ°Π·ΡΠ². ΠΠΈΠΊΠΎΡΠΈΡΡΠ°Π½Π½Ρ Π·Π°ΠΏΡΠΎΠΏΠΎΠ½ΠΎΠ²Π°Π½ΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄Ρ Π΄ΠΎΠ·Π²ΠΎΠ»ΠΈΡΡ ΠΏΡΠΎΠ΅ΠΊΡΡΠ²Π°ΡΠΈ Π±ΡΠ»ΡΡ Π΅ΡΠ΅ΠΊΡΠΈΠ²Π½Ρ, Π· ΡΠΎΡΠΊΠΈ Π·ΠΎΡΡ ΡΠ²ΠΈΠ΄ΠΊΠΎΠ΄ΡΡ, Π°ΠΏΠ°ΡΠ°ΡΠ½ΠΎ-ΠΏΡΠΎΠ³ΡΠ°ΠΌΠ½Ρ Π·Π°ΡΠΎΠ±ΠΈ ΠΏΡΠΎΠ²Π΅Π΄Π΅Π½Π½Ρ ΠΊΡΠΈΠΏΡΠΎΠ°Π½Π°Π»ΡΠ·Ρ Π°ΡΠΈΠΌΠ΅ΡΡΠΈΡΠ½ΠΈΡ ΠΊΡΠΈΠΏΡΠΎΠ³ΡΠ°ΡΡΡΠ½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡΠ² ΡΠ°, ΡΠΊ Π½Π°ΡΠ»ΡΠ΄ΠΎΠΊ, ΠΏΡΠ΄Π²ΠΈΡΠΈΡΠΈ ΡΠΊΡΡΡΡ ΠΎΡΡΠ½ΠΊΠΈ ΠΊΡΠΈΠΏΡΠΎΡΡΡΠΉΠΊΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ RSA.