Категорія «Криптографія та теорія ігор» охоплює дві сфери, що мають на диво багато спільної математичної ДНК. Обидві базуються на асиметрії інформації, стратегічних рівновагах та межах раціонального прийняття рішень. Обидві також є прекрасними темами для візуалізації — ви можете буквально спостерігати, як RSA шифрує повідомлення, або дивитись, як стратегії «зуб за зуб» домінують у турнірі з дилеми в'язня в реальному часі.
8 нових симуляцій
У фокусі: дилема в'язня
Дилема в'язня — найбільш вивчена гра в усій теорії ігор саме тому, що вона моделює універсальне протиріччя: те, що індивідуально раціонально, призводить до колективно гіршого результату. Два підозрювані, кожен обираючи співпрацювати чи зрадити, стикаються з такою матрицею виплат:
| Гравець Б: співпраця | Гравець Б: зрада | |
|---|---|---|
| Гравець А: співпраця | (3, 3) | (0, 5) |
| Гравець А: зрада | (5, 0) | (1, 1) ← Неш |
Рівновага Неша — результат, за якого жоден гравець не може покращити своє становище, одноосібно змінюючи стратегію, — взаємна зрада (1,1), хоча взаємна співпраця (3,3) краща для обох. Однак в ітеративній версії співпраця може розвинутися. Знамениті комп'ютерні турніри Аксельрода показали, що «зуб за зуб» — спочатку співпрацювати, а потім дзеркально повторювати останній хід суперника — була найрезультативнішою стратегією серед сотень учасників.
У фокусі: шифрування RSA у браузері
Наша симуляція RSA використовує невеликі (32-бітні) прості числа, щоб кожен крок можна було перевірити, але показує той самий алгоритм, що захищає HTTPS. Симуляція:
- Генерує два випадкових простих числа p, q, використовуючи перевірку простоти Міллера-Рабіна
- Обчислює n = p·q і функцію Ейлера φ(n) = (p-1)(q-1)
- Обирає відкритий показник e = 65537 (стандартний вибір)
- Обчислює приватний показник d = e⁻¹ mod φ(n) через розширений алгоритм Евкліда
- Шифрує: C = M^e mod n — анімовано як повторювані кроки піднесення до квадрата
- Розшифровує: M = C^d mod n — та сама анімація у зворотному напрямку
(M^e)^d ≡ M^(ed) ≡ M^(1 + kφ(n)) ≡ M · (M^φ(n))^k ≡ M · 1^k ≡ M
(mod n)
Припущення безпеки: факторизація n = p·q обчислювально складна
для великих p, q.
Злам 2048-бітного RSA найкращими відомими алгоритмами: ~10^19
операцій.
Що пов'язує криптографію і теорію ігор? Обидві дисципліни вивчають стратегічну поведінку в умовах асиметрії інформації. Докази з нульовим розголошенням — це буквально теоретико-ігрові протоколи. Дизайн механізмів — як структурувати аукціони та контракти для досягнення бажаних результатів — використовує той самий аналіз рівноваги, що й докази безпеки криптографічних протоколів.