20 января 2022

πŸ”‘ ΠŸΡ€ΠΎΡΡ‚ΠΎ ΠΎ слоТном: ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ простых чисСл Π² ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ

Kaggle expertβš›οΈ ΠŸΠΈΡˆΡƒ ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π» ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Ρ… ΠΈ Ρ‚Π΅Ρ…Π½ΠΈΠΊΠ°Ρ… Π² сфСрС Machine Learning.
ОбъясняСм, ΠΏΠΎΡ‡Π΅ΠΌΡƒ простыС числа Π²Π°ΠΆΠ½Ρ‹ Π² ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ. Для этого ΠΌΡ‹ рассмотрим ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΡƒΡŽ криптосистСму, Π° ΠΈΠΌΠ΅Π½Π½ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ RSA ΠΈ сосрСдоточимся Π½Π° Π΅Π³ΠΎ основных аспСктах.
πŸ”‘ ΠŸΡ€ΠΎΡΡ‚ΠΎ ΠΎ слоТном: ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ простых чисСл Π² ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ

Бвойства простых чисСл

КаТдоС число ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π°Π·Π»ΠΎΠΆΠΈΡ‚ΡŒ Π½Π° простыС ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΠΈ. Π’ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… случаях факторизация Ρ†Π΅Π»Ρ‹Ρ… чисСл прСдставляСт ΠΈΠ· сСбя слоТный процСсс. Π’ ΠΏΠ΅Ρ€Π²ΡƒΡŽ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ ΠΏΠΎΡ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎ для Π±ΠΎΠ»ΡŒΡˆΠΈΡ… чисСл Π·Π°Π΄Π°Ρ‡Π° Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ·Π°Ρ†ΠΈΠΈ являСтся Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ слоТной. ПодойдСм ΠΊ вопросу тСорСтичСски: для Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π°ΠΉΡ‚ΠΈ всС простыС Ρ„Π°ΠΊΡ‚ΠΎΡ€Ρ‹ (ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΠΈ) числа n, Π½ΡƒΠΆΠ½ΠΎ Ρ€Π°Π·Π΄Π΅Π»ΠΈΡ‚ΡŒ Π΄Π°Π½Π½ΠΎΠ΅ число Π½Π° всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΠΈ Π²ΠΏΠ»ΠΎΡ‚ΡŒ Π΄ΠΎ √n.

Π‘ Π΄Ρ€ΡƒΠ³ΠΎΠΉ стороны, Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π³ΠΎΡ€Π°Π·Π΄ΠΎ Π»Π΅Π³Ρ‡Π΅, ΠΊΠΎΠ³Π΄Π° простыС числа Π½Π°ΠΌ Π·Π°Ρ€Π°Π½Π΅Π΅ извСстны:

Π›Π΅Π³ΠΊΠΎ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ <code class="inline-code">x</code> ΠΈΠ· простых чисСл 1 ΠΈ 2. Но слоТно Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ простыС числа 1 ΠΈ 2 ΠΈΠ· <code class="inline-code">x</code>.
Π›Π΅Π³ΠΊΠΎ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ x ΠΈΠ· простых чисСл 1 ΠΈ 2. Но слоТно Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ простыС числа 1 ΠΈ 2 ΠΈΠ· x.

Π’ ΠΈΠ΄Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… условиях Ρƒ нас ΠΈΠΌΠ΅ΡŽΡ‚ΡΡ Π΄Π²Π° Π±ΠΎΠ»ΡŒΡˆΠΈΡ… числа, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡΠ²Π»ΡΡŽΡ‚ΡΡ простыми. Π—Π°Ρ‚Π΅ΠΌ ΠΌΡ‹ вычисляСм ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ этих Π΄Π²ΡƒΡ… чисСл, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Ρ‚ΡŒ сообщСниС. ПозТС, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Ρ‚ΡŒ Π΅Π³ΠΎ, Π½Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΠΎΠ΄Π½ΠΎ ΠΈΠ· Π΄Π°Π½Π½Ρ‹Ρ… простых чисСл, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ Π½Π΅Ρ‚ простого способа Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ «Число 1Β» ΠΈ «Число 2Β» ΠΈΡΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΏΠΎ x. ΠŸΠ΅Ρ€Π΅Π΄ Ρ‚Π΅ΠΌ ΠΊΠ°ΠΊ ΡƒΠ³Π»ΡƒΠ±ΠΈΡ‚ΡŒΡΡ Π² Π΄Π΅Ρ‚Π°Π»ΠΈ использования Π΄Π°Π½Π½Ρ‹Ρ… чисСл, Π΄Π°Π²Π°ΠΉΡ‚Π΅ рассмотрим Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ криптографичСскиС систСмы.

ΠšΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΡ‡Π΅ΡΠΊΠΈΠ΅ систСмы

Π’ ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ сущСствуСт Π΄Π²Π° основных ΠΌΠ΅Ρ‚ΠΎΠ΄Π° ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ сообщСний: симмСтричноС ΠΈ асиммСтричноС.

Π’ случаС симмСтричного ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ ΠΎΠ±Π΅ стороны ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ ΠΎΠ΄ΠΈΠ½ ΠΈ Ρ‚ΠΎΡ‚ ΠΆΠ΅ ΠΊΠ»ΡŽΡ‡ для ΡˆΠΈΡ„Ρ€ΠΎΠ²ΠΊΠΈ ΠΈ Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΠΎΠ²ΠΊΠΈ сообщСния. Π­Ρ‚ΠΎ Π½Π°Π΄Π΅ΠΆΠ½ΠΎ Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° ΠΊΠ»ΡŽΡ‡ Π΅ΡΡ‚ΡŒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρƒ Π΄Π²ΡƒΡ… Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊ: отправитСля ΠΈ получатСля. ΠšΡ€ΠΎΠΌΠ΅ Ρ‚ΠΎΠ³ΠΎ, ΠΈΠΌ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠ° Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ бСзопасно ΠΏΠΎΠ΄Π΅Π»ΠΈΡ‚ΡŒΡΡ ΠΊΠ»ΡŽΡ‡ΠΎΠΌ Π΄Ρ€ΡƒΠ³ с Π΄Ρ€ΡƒΠ³ΠΎΠΌ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, ΠΏΡ€ΠΈ Π»ΠΈΡ‡Π½ΠΎΠΉ встрСчС.

Π’ΠΎ Π΅ΡΡ‚ΡŒ, Π½Π° ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ рСализация Π΄Π°Π½Π½ΠΎΠ³ΠΎ случая Π·Π°Ρ‚Ρ€ΡƒΠ΄Π½Π΅Π½Π°. Π’Π΅Π΄ΡŒ, Ссли ΠΌΡ‹ Ρ…ΠΎΡ‚ΠΈΠΌ Π½Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ ΠΊΠΎΠΌΡƒ-Ρ‚ΠΎ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½Π½ΠΎΠ΅ письмо, Π² наши ΠΏΠ»Π°Π½Ρ‹ Π½Π΅ Π²Ρ…ΠΎΠ΄ΠΈΡ‚ личная встрСча с Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊΠΎΠΌ для ΠΎΠ±ΠΌΠ΅Π½Π° сСкрСтными ΠΊΠ»ΡŽΡ‡Π°ΠΌΠΈ.

ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΏΡ€ΠΈ асиммСтричном ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠΈ Ρƒ нас Π΅ΡΡ‚ΡŒ Π΄Π²Π° Ρ€Π°Π·Π½Ρ‹Ρ… ΠΊΠ»ΡŽΡ‡Π°: ΠΎΠ΄ΠΈΠ½ для ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ, Π΄Ρ€ΡƒΠ³ΠΎΠΉ для Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΠΎΠ²ΠΊΠΈ. Один ΠΊΠ»ΡŽΡ‡ ΠΏΡ€Π΅Π΄Π½Π°Π·Π½Π°Ρ‡Π΅Π½ для Π°Π²Ρ‚ΠΎΡ€Π° сообщСния. ПослС Π΅Π³ΠΎ написания ΠΎΠ½ ΠΌΠΎΠΆΠ΅Ρ‚ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Ρ‚ΡŒ Π΅Π³ΠΎ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΎΠ³ΠΎ ΠΊΠ»ΡŽΡ‡Π° получатСля. Π­Ρ‚ΠΎΡ‚ ΠΊΠ»ΡŽΡ‡, ΠΊΠ°ΠΊ слСдуСт ΠΈΠ· названия, являСтся ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΌ ΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π½Π°ΠΉΠ΄Π΅Π½ Π² Π±Π°Π·Π΅ Π΄Π°Π½Π½Ρ‹Ρ… ΠΊΠ»ΡŽΡ‡Π΅ΠΉ. Π’Π°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½ ΠΏΡ€Π΅Π΄Π½Π°Π·Π½Π°Ρ‡Π΅Π½ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ для ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ, Π΅Π³ΠΎ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΎΡΡ‚ΡŒ Π½Π΅ причиняСт Π²Ρ€Π΅Π΄Π°.

Π‘ Π΄Ρ€ΡƒΠ³ΠΎΠΉ стороны, сущСствуСт Π·Π°ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π²ΠΈΠ΄Π΅Π½ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊΡƒ – ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚Π΅Π»ΡŽ сообщСний. Он ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π΅Π³ΠΎ для Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΠΎΠ²ΠΊΠΈ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Ρ… сообщСний:

ΠŸΡƒΠ±Π»ΠΈΡ‡Π½Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡ β†’ Автор сообщСния β†’ Π—Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½Π½ΠΎΠ΅ сообщСниС β†’ ΠŸΠΎΠ»ΡƒΡ‡Π°Ρ‚Π΅Π»ΡŒ β†’ ΠŸΡ€ΠΈΠ²Π°Ρ‚Π½Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡
ΠŸΡƒΠ±Π»ΠΈΡ‡Π½Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡ β†’ Автор сообщСния β†’ Π—Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½Π½ΠΎΠ΅ сообщСниС β†’ ΠŸΠΎΠ»ΡƒΡ‡Π°Ρ‚Π΅Π»ΡŒ β†’ ΠŸΡ€ΠΈΠ²Π°Ρ‚Π½Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ простыС числа для ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ

Π’Π΅ΠΏΠ΅Ρ€ΡŒ, ΠΊΠΎΠ³Π΄Π° Ρƒ нас имССтся Ρ‡Π΅Ρ‚ΠΊΠΎΠ΅ прСдставлСниС ΠΎ Π΄Π²ΡƒΡ… Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… систСмах ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ, Π΄Π°Π²Π°ΠΉΡ‚Π΅ рассмотрим, ΠΊΠ°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΌΡ‹ создадим ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΉ ΠΈ Π·Π°ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡ Π² случаС асиммСтричного ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ.

Для Π½Π°Ρ‡Π°Π»Π° слСдуСт ΠΎΡ‚ΠΌΠ΅Ρ‚ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΌΡ‹ Π½Π΅ ΠΌΠΎΠΆΠ΅ΠΌ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Ρ‚ΡŒ тСкст Π½Π°ΠΏΡ€ΡΠΌΡƒΡŽ, Π° Π΄ΠΎΠ»ΠΆΠ½Ρ‹ сначала ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚ΡŒ Π΅Π³ΠΎ Π² число. Π­Ρ‚ΠΎΡ‚ процСсс называСтся подстановкой ΠΈ происходит с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ списка, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ символу присваиваСтся число.

Π—Π°Ρ‚Π΅ΠΌ ΠΌΡ‹ соСдиняСм ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ число, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡΠΎΠ·Π΄Π°Ρ‚ΡŒ Π΄Ρ€ΡƒΠ³ΠΎΠ΅ (Π½Π°Π·ΠΎΠ²Π΅ΠΌ Π΅Π³ΠΎ m), ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ ΠΌΡ‹ ΠΏΠΎΡ‚ΠΎΠΌ Π·Π°ΡˆΠΈΡ„Ρ€ΡƒΠ΅ΠΌ. Π‘Π°ΠΌΡ‹ΠΌ простым ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ списка являСтся присвоСниС ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π±ΡƒΠΊΠ²Π΅ Π΅Π΅ ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ Π² Π°Π»Ρ„Π°Π²ΠΈΡ‚Π΅, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, A – 1, Π‘ – 2 ΠΈ Ρ‚. Π΄. НСсмотря Π½Π° Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ Π΄Π°Π½Π½Ρ‹ΠΉ список позволяСт ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΊΡ€Π°ΠΉΠ½Π΅ простыС слова, Π΅Π³ΠΎ достаточно для понимания Ρ‚Π΅ΠΎΡ€ΠΈΠΈ, Π»Π΅ΠΆΠ°Ρ‰Π΅ΠΉ Π² основС RSA.

Π‘ΠΎΠ·Π΄Π°Π΅ΠΌ ΠΊΠ»ΡŽΡ‡

Как Π±Ρ‹Π»ΠΎ Ρ€Π°Π½Π΅Π΅ сказано, Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ большоС число Π»Π΅Π³ΠΊΠΎ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ ΠΏΡ€ΠΈ условии, Ρ‡Ρ‚ΠΎ простыС числа ΡƒΠΆΠ΅ извСстны. Π‘ Π΄Ρ€ΡƒΠ³ΠΎΠΉ стороны, ΠΎΡ‡Π΅Π½ΡŒ Ρ‚Ρ€ΡƒΠ΄Π½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΠΈ (Ρ„Π°ΠΊΡ‚ΠΎΡ€Ρ‹) извСстного Π½Π°ΠΌ большого числа. Π§Ρ‚ΠΎΠ±Ρ‹ ΡΠΎΠ·Π΄Π°Ρ‚ΡŒ Π΄Π²Π° ΠΊΠ»ΡŽΡ‡Π° – Π·Π°ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΉ ΠΈ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΉ, – ΠΌΡ‹ осущСствляСм ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ процСсс:

  1. Π’Ρ‹Π±Π΅Ρ€ΠΈΡ‚Π΅ Π΄Π²Π° случайных, стохастичСски нСзависимых ΠΈ простых числа, p ΠΈ q.
  2. ВычислитС ΠΈΡ… ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅: N = p * q
  3. Π”Π°Π»Π΅Π΅ вычислитС Ο†-Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ: Ο†(N) = (p – 1) * (q – 1)
  4. Π’Ρ‹Π±Π΅Ρ€ΠΈΡ‚Π΅ простоС Π½Π°Ρ‚ΡƒΡ€Π°Π»ΡŒΠ½ΠΎΠ΅ число e, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ мСньшС значСния Ο†(N) ΠΈ являСтся ΠΊΡ€Π°Ρ‚Π½Ρ‹ΠΌ ΠΏΠΎ ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡŽ ΠΊ Π½Π΅ΠΌΡƒ.
  5. ВычислитС ΠΌΡƒΠ»ΡŒΡ‚ΠΈΠΏΠ»ΠΈΠΊΠ°Ρ‚ΠΈΠ²Π½ΡƒΡŽ ΠΎΠ±Ρ€Π°Ρ‚Π½ΡƒΡŽ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Ρƒ k ΠΎΡ‚ e ΠΏΠΎ ΠΌΠΎΠ΄ΡƒΠ»ΡŽ Ο†(N), Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ: e * k + d * Ο†(N) = 1

N ΠΈ e Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ ΡΠ²Π»ΡΡŽΡ‚ΡΡ нашими ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΌΠΈ ΠΊΠ»ΡŽΡ‡Π°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π±ΡƒΠ΄ΡƒΡ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ для ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ сообщСния. Наш ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡ для Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΠΎΠ²ΠΊΠΈ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ сообщСния, k, являСтся Π·Π°ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΌ ΠΊΠ»ΡŽΡ‡ΠΎΠΌ. Для Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅Π³ΠΎ понимания процСсса, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ стоит Π·Π° названиями ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Π΄Π°Π²Π°ΠΉΡ‚Π΅ рассмотрим процСсс ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ ΠΈ Π΄Π΅ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ.

Π¨ΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈ Π΄Π΅ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ сообщСния

Π’Π΅ΠΏΠ΅Ρ€ΡŒ ΠΌΡ‹ Π·Π°ΡˆΠΈΡ„Ρ€ΡƒΠ΅ΠΌ нашС сообщСниС m с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΎΠ³ΠΎ ΠΊΠ»ΡŽΡ‡Π°:

s≅memodN

И Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΡƒΠ΅ΠΌ Π΅Π³ΠΎ:

m≅skmodN

Из Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ Π²Ρ‹ΡˆΠ΅ слСдуСт, Ρ‡Ρ‚ΠΎ ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΈΠ½Π²Π΅Ρ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ нашС ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ссли Π½Π°ΠΌ извСстна ΠΌΡƒΠ»ΡŒΡ‚ΠΈΠΏΠ»ΠΈΠΊΠ°Ρ‚ΠΈΠ²Π½Π°Ρ обратная k ΠΎΡ‚ e ΠΏΠΎ ΠΌΠΎΠ΄ΡƒΠ»ΡŽ Ο†(N). Π­Ρ‚ΠΈ Π΄Π°Π½Π½Ρ‹Π΅ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ, Ссли Ρƒ нас Π΅ΡΡ‚ΡŒ:

  1. ΠŸΡ€ΠΈΠ²Π°Ρ‚Π½Ρ‹ΠΉ (Π·Π°ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΉ) ΠΊΠ»ΡŽΡ‡
  2. ΠŸΡ€ΠΎΡΡ‚Ρ‹Π΅ ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΠΈ N

ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ простыС ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΠΈ большого N физичСски нСвыполнимая Π·Π°Π΄Π°Ρ‡Π°, Π±Π΅Π· Π·Π°ΠΊΡ€Ρ‹Ρ‚ΠΎΠ³ΠΎ ΠΊΠ»ΡŽΡ‡Π° Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Ρ‚ΡŒ сообщСниС Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ. Π­Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ систСму ΠΈΡΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ бСзопасной.

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠΈΠΉ ΠΏΡ€ΠΈΠΌΠ΅Ρ€

  • Π‘ΠΎΠ·Π΄Π°Π΅ΠΌ ΠΊΠ»ΡŽΡ‡.

ΠŸΡƒΡΡ‚ΡŒ Π±ΡƒΠΊΠ²Π°, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΌΡ‹ Ρ…ΠΎΡ‚ΠΈΠΌ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Ρ‚ΡŒ – O. ΠŸΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΡƒΠ΅ΠΌ Π΅Π΅ Π² число m=15, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ это пятнадцатая Π±ΡƒΠΊΠ²Π° латинского Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°. Π’Π΅ΠΏΠ΅Ρ€ΡŒ ΠΌΡ‹ Π²Ρ‹Π±ΠΈΡ€Π°Π΅ΠΌ случайныС простыС числа. Π§Ρ‚ΠΎΠ±Ρ‹ ΡƒΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡Ρƒ, Π²Ρ‹Π±Π΅Ρ€Π΅ΠΌ простыС числа p = 13 ΠΈ q = 17.

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, функция: Ο†(N) = (p – 1) * (q – 1) = 192

ΠœΡ‹ Ρ‚Π°ΠΊΠΆΠ΅ Π²Ρ‹Π±ΠΈΡ€Π°Π΅ΠΌ число e, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ ΠΊΡ€Π°Ρ‚Π½ΠΎ Ο†(N). ΠŸΡƒΡΡ‚ΡŒ это Π±ΡƒΠ΄Π΅Ρ‚ 29.

ΠžΡΡ‚Π°Π»ΠΎΡΡŒ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎΠ΅ k ΠΎΡ‚ e. Π‘ ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π•Π²ΠΊΠ»ΠΈΠ΄Π° ΠΌΡ‹ ΡƒΠ·Π½Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ ΠΎΠ½ΠΎ Ρ€Π°Π²Π½ΠΎ 53.

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Ρƒ нас Π΅ΡΡ‚ΡŒ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡ N = p * q = 221 ΠΈ Π·Π°ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΉ ΠΊΠ»ΡŽΡ‡ k = 53.

  • Π¨ΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈ Π΄Π΅ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ сообщСния.

Π”Π°Π»Π΅Π΅ ΠΌΡ‹ Π·Π°ΡˆΠΈΡ„Ρ€ΡƒΠ΅ΠΌ нашС число:

15β‰…s29mod221

Π­Ρ‚ΠΎ Π΄Π°Π΅Ρ‚ s = 19. Π’Π΅ΠΏΠ΅Ρ€ΡŒ Ρƒ нас Π΅ΡΡ‚ΡŒ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½Π½ΠΎΠ΅ сообщСниС, ΠΈ ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ бСзопасно ΠΏΠ΅Ρ€Π΅Π΄Π°Ρ‚ΡŒ Π΅Π³ΠΎ ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚Π΅Π»ΡŽ. Никто Π½Π΅ ΡƒΠ·Π½Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ ΠΎΠ½ΠΎ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ Π±ΡƒΠΊΠ²Ρƒ O.

Π’Π΅ΠΏΠ΅Ρ€ΡŒ Π½Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ нашС ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎΠ΅ k, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Ρ€Π°Π²Π½ΠΎ 53:

15β‰…1953mod221

ПослС этого ΠΌΡ‹ снова смотрим Π½Π° Π°Π»Ρ„Π°Π²ΠΈΡ‚ ΠΈ Π²ΠΈΠ΄ΠΈΠΌ, Ρ‡Ρ‚ΠΎ Π΅Π³ΠΎ пятнадцатая Π±ΡƒΠΊΠ²Π° – это O. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΌΡ‹ ΡƒΡΠΏΠ΅ΡˆΠ½ΠΎ Π·Π°ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π»ΠΈ ΠΈ Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π»ΠΈ нашС сообщСниС.

***

Из Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Π° Π²Ρ‹ ΡƒΠ·Π½Π°Π»ΠΈ ΠΎΠ± Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ΅ RSA (Rivest, Shamir ΠΈ Aldeman – создатСли Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°) ΠΈ ΠΎ Ρ‚ΠΎΠΌ, ΠΊΠ°ΠΊ ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎ Π΅Π³ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ для ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ Π΄Π°Π½Π½Ρ‹Ρ….

ΠœΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π΄Ρ€ΡƒΠ³ΠΈΠ΅, Π±ΠΎΠ»Π΅Π΅ ΠΎΠ±ΡŠΠ΅ΠΌΠ½Ρ‹Π΅ числа. Π˜Ρ… Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ разлоТСния Π½Π° простыС ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΠΈ ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ‚ созданию бСзопасной ΠΈ асиммСтричной криптографичСской систСмы.

ΠœΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹ ΠΏΠΎ Ρ‚Π΅ΠΌΠ΅

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊΠΈ

ΠœΠ•Π ΠžΠŸΠ Π˜Π―Π’Π˜Π―

ΠšΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΈ

Π’ΠΠšΠΠΠ‘Π˜Π˜

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ вакансию
ML- ΠΈΠ½ΠΆΠ΅Π½Π΅Ρ€
Москва, ΠΏΠΎ ΠΈΡ‚ΠΎΠ³Π°ΠΌ собСсСдования

Π›Π£Π§Π¨Π˜Π• БВАВЬИ ПО Π’Π•ΠœΠ•