Я разовью тему "козы и капусты", изложив здесь суть другой столь же мощной (а на самом деле даже более мощной) идеи.
Задача почти та же: у всех на глазах договориться об общем для нас ключе для шифра. Так, чтобы никто не узнал этот ключ, кроме меня и тебя.
[Spoiler (click to open)]
Делаем так.
Прежде всего, мы у всех на глазах договариваемся о некотором числе A, которое ляжет в основу нашего шифрования. Пусть это число будет всем известным, нам это не помешает.
Далее.
Я придумываю секретную функцию F. И высылаю тебе у всех на глазах только результат действия этой функции F(A), оставляя саму функцию в секрете.
Ты придумываешь секретную функцию G. И высылаешь мне у всех на глазах только результат действия этой функции G(A), оставляя саму функцию в секрете.
После этого я применяю свою секретную функцию к высланному тобой результату, а ты применяешь свою функцию к моему результату.
У тебя получается G(F(A)), а у меня F(G(A)).
А что, если подобрать наши функции таким образом, чтобы G(F(A)) всегда совпадало с F(G(A))?
Тогда мы имели бы замечательный результат: мы оба знаем некоторое число G(F(A))=F(G(A)), а кроме нас двоих это число неизвестно никому! Этим можно воспользоваться для шифрования.
Но сначала убедимся, что такие функции существуют. Для этого достаточно привести один реальный пример.
Например, мы можем просто возводить в степень наше число A. И пусть это не будет секретом. Для нас вполне достаточно , если секретом останется то, в какую именно степень мы его возводим!
Итак.
Я беру произвольное секретное число F, вычисляю AF и высылаю результат тебе. Число F секретное, но AF секретом теперь не является.
Ты берешь произвольное секретное число G, вычисляешь AG и высылаешь мне. Число G секретное, но AG тоже секретом не является.
Далее мы делаем вот что. Я возвожу полученное от тебя число в свою секретную степень, а ты возводишь полученное от меня число в свою секретную степень.
Но! барабанная дробь (AF)G=(AG)F !!!
Следовательно, мы оба получили одно и то же число.
Моё секретное число осталось известным только мне. Твоё - только тебе.
Однако число (AF)G=(AG)F теперь известно нам обоим! Но кроме нас неизвестно никому. И потому может работать как общий ключ для шифра, неизвестный никому кроме нас.
А секретные числа F и G, которые были использованы нами для произведения этих расчетов, мы теперь можем и даже должны ликвидировать, стереть из памяти компьютера. Они больше не нужны и даже опасны, так как зная их, можно легко вскрыть наш шифр.
Это фокус-покус именуется (wiki/ru) Протокол_Диффи-Хеллмана и он используется, когда мы обмениваемся информацией с сайтами, в адрес которых добавлена буквочка s (https://...) - например, в приведенном выше адресе Википедии.
Такова суть метода.
А чтобы до конца понять эту суть, осталось разрешить лишь одно недоумение.
Если всем известно наше число A и всем известно AF, то что может помешать вычислить моё F при помощи банального логарифма? Ничто не помешает!
И потому наши функции должны быть чуть-чуть хитрее устроены.
Давайте при возведении в степень брать не весь результат вычисления, а только остаток от деления этого результата на некоторые число B. Это число B тоже не является секретом. Однако при отбрасывании всего кроме остатка теряется информация, необходимая для вычисления логарифма!
Ну, например.[Если угодно, вот конкретный пример такого возведения в степень]
Вот как ведут себя числа при возведении в степень и делением с отбрасыванием всего кроме остатка. Например, будем возводить в степень число А=11 и делить на В=17, чтобы узнать остаток:
110 = 1
111 = 11
112 = 121 = 7*17 + 2
113 = 1331 = 78*17 + 5
114 = 14641 = 861*17 + 4
115 = 161054 = 9473*17 + 10
Ну, надеюсь, суть дела ясна. Использую общепринятую краткую запись и воспользуюсь он-лайн-сервисом, специально предназначенным для таких расчетов:
110 (%17) = 1
111 (%17) = 11
112 (%17) = 2
113 (%17) = 5
114 (%17) = 4
115 (%17) = 10
116 (%17) = 8
117 (%17) = 3
118 (%17) = 16
119 (%17) = 6
1110 (%17) = 15
1111 (%17) = 12
1112 (%17) = 13
1113 (%17) = 7
1114 (%17) = 9
1115 (%17) = 14
1116 (%17) = 1
1117 (%17) = 11
1118 (%17) = 2
1119 (%17) = 5
1120 (%17) = 4
1121 (%17) = 10
1122 (%17) = 8
1123 (%17) = 3
1124 (%17) = 16
1125 (%17) = 6
1126 (%17) = 15
1127 (%17) = 12
1128 (%17) = 13
1129 (%17) = 7
1130 (%17) = 9
1131 (%17) = 14
1132 (%17) = 1
1133 (%17) = 11
1134 (%17) = 2
1135 (%17) = 5
1136 (%17) = 4
1137 (%17) = 10
1138 (%17) = 8
и так далее.
Заметим, что
1116 (%17) = 110 (%17) = 1
И начиная с этого места всё идет по кругу, так что 1117 (%17) = 111 (%17) = 11 и так далее
Это не случайность, а действие малой теоремы Ферма, которая утверждает, что для если число N простое, то у любого числа A его N-я степень обязательно дает при делении на N остаток А: АN(%N)=A
(Возможно, кто-то из моих читателей помнит, как я использовал эту теорему для доказательства потрясающего факта, что если n нечетно, то (n5 - n) делится на 240 без остатка.)
При таком способе возведения в степень результат ведет себя хаотично, прыгает туда-сюда с перебором всех вариантов ответа от 0 до B-1. Кроме факта повтора заметить какую-либо закономерность в его скачках невозможно.
И потому узнать наши секретные F и G криптоаналитик сможет только путем тупого перебора всех вариантов. Число вариантов равно B. А значит, если мы будем использовать для вычислений по-настоящему большое B, то этот перебор потребует астрономического времени (миллиардов лет). А если когда-нибудь компьютеры станут настолько быстродействующими, что эти миллиарды превратятся в годы или десятилетия, мы просто-напросто слегка увеличим размеры нашего B - и снова будут те же миллиарды. Нам это нетрудно!
Именно B задает масштаб нашей работы; ведь когда при всех расчетах мы берем только остаток от деления на B, то какие бы большие числа мы ни брали, результат расчета не может быть больше чем B. Нам совсем нетрудно один раз возвести полученное нами число в секретную степень и поделить результат на B для вычисления остатка. А несчастному криптоаналитику придется проделать то же самое B раз!
Ну, а теперь осталось лишь объяснить, при чем тут квантовая телепортация.
В чём суть, в чём фишка идеи Диффи и Хеллмана?
Они очень мудро переформулировали задачу.
Все люди всю жизнь думали: каким образом можно передать собеседнику секретный ключ, чтобы он не попал в чужие руки?
А Диффи и Хеллмана осенило: а зачем его передавать, если его можно просто-напросто получить в результате совместной работы?! Если ключ устроен так, что он рождается лишь в процессе работы, то и обладать этим ключом будут лишь те, кто в этой работе участвовал. Случайные свидетели обмена информацией, необходимого для этой работы, останутся в неведении о её результатах.
Совершенно так же работает и пресловутая "квантовая телепортация", которую успели раструбить как "преодоление светового барьера". Якобы благодаря квантовой запутанности можно передать информацию со скоростью, превышающей скорость света. На самом же деле там так же точно, как и в методе Диффи-Хелмана, по сути дела не передается никакой информации. Эта информация рождается в момент квантовых измерений независимо в двух разных местах в два разных момента времени. Просто рождается там и там не что попало, а одно и то же - благодаря этой самой "запутанности".
Никакой сверхсветовой скорости люди не изобрели (и лично я думаю, никогда не изобретут).
Но зато придумали отличный способ заморочить всем голову. В чем и заключается прелесть криптографии :)
Ужасно интересный комментарий от Ивана Кипрея:
Вечная проблема всех шифровальных систем: качество генератора случайных чисел. Квантовая телепортация по сути — хорошее приближение к идеальному генератору. Но эта проблема решена в 60-е, с помощью оцифровки квантового шума диода Шоттки. Военные пользуются. Гражданским же не положено. Именно поэтому извели сотовый протокол CDMA, конверсионный из военных технологий - он использовал такие генераторы и сетевой трафик у него не ломался ни половинными ключами ни брутфорсом. GSM, LTE — ломаются.
Мой ответ:
Большое спасибо! очень интересный комментарий. Я мысленно изобрел такой генератор ещё когда учился на физфаке, но это не моя область знания, так что я до сего дня даже не знал, что они существуют в реальности! Да, квантовые флуктуации - это идеальный генератор случайности. И что ещё интереснее - это прямое выражение воли Бога. Потому что они зависят только от Него. Это контакт нашего компьютера с Богом. А запрет CDMA - это прямое богоборчество :)
Иван, если бы мог, поставил бы десять лайков к этому комменту. Имело смысл писать всю заметку только ради одного этого комментария в ответ.
May 7 2018, 08:05:31 UTC 1 year ago
Если и его передавать тоже ?
May 7 2018, 10:43:30 UTC 1 year ago
Я так и написал. Цитирую:
"Прежде всего, мы у всех на глазах договариваемся о некотором числе A, которое ляжет в основу нашего шифрования. Пусть это число будет всем известным, нам это не помешает."