Блокчейн/Уровень I · Деньги/1.2 Путь шифропанков/Урок 1
Криптография с открытым ключом: Диффи-Хеллман и RSA
Общий секрет без личной встречи и подпись, доказывающая право владения
МатериалыКалькулятор или электронная таблица с поддержкой модульной арифметикиСтатья Диффи и Хеллмана (1976)
Любопытство
- Как двум незнакомцам договориться о секретном ключе, если их слушают все остальные?
- Почему перемножить два больших простых числа — тривиальная задача, а восстановить эти числа по их произведению практически невозможно?
- Что значит владеть чем-то, если владение определяется способностью подписывать?
Исследование
- До 1976 года для защищённой связи требовался общий секрет, переданный по доверенному каналу. Если перехватчик получал этот ключ, весь последующий трафик оказывался скомпрометирован. Уитфилд Диффи и Мартин Хеллман предложили решение в статье «New Directions in Cryptography» (IEEE Transactions on Information Theory, ноябрь 1976 года). Две стороны могли получить общий секрет по открытому каналу с помощью модульного возведения в степень. Эта математика односторонняя: в прямом направлении вычисление выполняется легко, а обратить его без закрытых входных данных вычислительно неосуществимо.
- Ральф Меркл придумал похожие головоломки в 1974–1975 годах и опубликовал их в 1978 году. Одна сторона публиковала множество небольших зашифрованных головоломок; другая решала одну из них, выбранную наугад, и использовала её содержимое как ключ. Преимущество было лишь квадратичным: при n головоломках две стороны выполняли около n единиц работы, а перехватчик — около n². У схемы Диффи — Хеллмана этот разрыв растёт с размером ключа, а если для каждого сеанса используются новые пары ключей, последующая утечка долгосрочных ключей не раскрывает прошлый трафик.
- Рон Ривест, Ади Шамир и Леонард Адлеман из MIT разработали RSA в 1977 году. Мартин Гарднер описал эту систему в своей колонке в Scientific American в августе 1977 года, ещё до выхода официальной статьи в Communications of the ACM (февраль 1978 года). RSA опирается на сложность разложения произведения двух больших простых чисел на множители. Он сделал возможными цифровые подписи: закрытый ключ подписывает данные, а соответствующий открытый ключ проверяет подпись, не раскрывая секрета подписавшего.
- Джеймс Эллис из GCHQ придумал «несекретное шифрование» примерно в 1969 году и описал его в 1970 году; Клиффорд Кокс в 1973 году вывел систему, эквивалентную RSA; Малкольм Уильямсон в 1974 году вывел аналог схемы Диффи — Хеллмана. Эти открытия оставались засекреченными до 1997 года. Параллельное развитие показывает, что математические основы сложились уже к началу 1970-х годов, но практическое применение началось лишь после открытой публикации работ академических исследователей. Засекреченная работа не создаёт публичной инфраструктуры.
- Ривест, Шамир и Адлеман получили премию Тьюринга в 2002 году; Диффи и Хеллман — в 2015 году. Для биткоина это важно: право собственности больше не привязано к физическому хранению или банковским записям — оно определяется способностью создать действительную подпись закрытым ключом. Биткоин использует криптографию на эллиптической кривой secp256k1, а не RSA, но базовая структура сохраняется. Пользователь доказывает контроль над средствами, подписывая транзакции; сеть проверяет подписи с помощью открытых ключей, ни разу не видя закрытых.
- Разберите схему Диффи — Хеллмана на небольших числах. Публично договоритесь о простом числе p = 23 и основании g = 5. Алиса выбирает секрет a = 6 и отправляет 5^6 mod 23 = 8. Боб выбирает b = 15 и отправляет 5^15 mod 23 = 19. Алиса вычисляет 19^6 mod 23 = 2; Боб вычисляет 8^15 mod 23 = 2. Теперь у обоих есть секрет 2, хотя по открытому каналу передавались только 23, 5, 8 и 19. В реальных системах используются числа длиной в сотни цифр, и восстановить a или b по открытым значениям практически невозможно.
Ключевые факты
- Диффи и Хеллман опубликовали свой протокол обмена ключами в ноябре 1976 года.
- RSA был разработан в MIT в 1977 году и опубликован в Communications of the ACM в феврале 1978 года.
- В GCHQ Джеймс Эллис, Клиффорд Кокс и Малкольм Уильямсон разработали методы криптографии с открытым ключом примерно в 1970–1974 годах, независимо от более поздних американских работ.
- Работы GCHQ в области криптографии с открытым ключом были рассекречены в 1997 году.
- Безопасность RSA основана на сложности факторизации произведения двух больших простых чисел.
- Владение биткоинами определяется способностью поставить подпись закрытым ключом.
Упражнение девять, шесть, три, один
9СобратьПеречислите 9 криптографических примитивов или протоколов периода с 1970 по 2008 год. Укажите их создателя, год создания и основное математическое свойство.
6СгруппироватьРазделите эти 9 пунктов на 6 категорий: обмен ключами, цифровые подписи, хеширование, симметричное шифрование, аутентификация и прочее.
3Выделить главноеСведите 6 групп к 3 причинам, по которым асимметричная криптография сделала возможными децентрализованные системы.
1КристаллизоватьНапишите одно предложение о том, что доказывает закрытый ключ и почему это меняет природу владения.
Проверка фактов
Даты, цифры и утверждения были проверены по приведенным ниже опубликованным источникам.
- W. Diffie & M. Hellman, 'New Directions in Cryptography', IEEE Transactions on Information Theory (Nov 1976)
- R. Rivest, A. Shamir & L. Adleman, 'A Method for Obtaining Digital Signatures and Public-Key Cryptosystems', Communications of the ACM (Feb 1978)
- S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (1999)
- S. Levy, Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age (2001)