Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
е = НТтъ,
где г Е [0, q).
Однако этот факт не вызывает никаких трудностей. В то же время это чрезвычайно важно для доказательства стойкости. Попробуем разобраться в этой загадке.
1- (ffi! 92, ui, U2) Е D. Тогда, поскольку существует число г Е [0, q), удовлетворяющее условию щ — д\, и2 = д%, выполняется равенство
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
589
Эта имитация шифрования точно соответствует схеме шифрования Крамера-Шоупа с заданным открытым ключом. Это именно то, к чему мы стремились, заставляя атакующий алгоритм Л проявить всю свою силу.
2. (9lj92>MbM2) ^ D. В этом случае существуют целые числа т\,т2 G [0>чО> удовлетворяющие условию г\ ф r2(mod q), щ = д[г и«2 = 922- Поскольку число д\ ф 1 является порождающим элементом группы G, существуют числа loggi 52,logg] /г,1оёд1 (^) и logfll (^).
Чтобы упростить изложение, предположим, что атакующий алгоритм Л имеет неограниченную вычислительную мощность. Получив число е, содержащееся в зашифрованном оклике С*, атакующий алгоритм Л, имеющий неограниченную вычислительную мощность, должен решить систему, состоящую из двух линейных уравнений относительно неизвестных целых чисел (zj, z2).
(modg), (15.3.4)
(mod?). (15.3.5)
Поскольку (<7i>92,^i,U2) ? D, выполняются условия т\ ф r2(modq). Кроме того, заметим, что loggi д2 ф O(modg), так как д2 ф 1. Итак, матрицы систем (15.3.4), (15.3.5) имеют полный ранг, равный двум, поэтому обе системы имеют единственное решение (zj, Z2). Атакующий алгоритм Л не может определить, какой из этих вариантов является правильным. Следовательно, даже обладая неограниченными вычислительными возможностями, атакующий алгоритм Л не имеет ни малейшего представления, какое сообщение зашифровано в отклике С* — то или т\. Итак, в данном случае текст С* шифрует сообщение тъ в теоретико-информационном смысле по Шеннону. Следовательно, атакующий алгоритм Л не имеет никакого преимущества! Следует отметить, что сказанное выше относится лишь к атаке CPA. Иначе говоря, предполагается, что атакующий алгоритм Л является пассивным. Реальные взломщики так себя не ведут! Напомним, что атакуюший алгоритм Л прошел курс обучения криптоанализа после получения зашифрованного оклика. Например, если во втором варианте атакующий алгоритм Л, кроме систем (15.3.4) и (15.3.5), должен решить третью систему, возникающую в результате курса обучения криптоанализу в рамках атаки ССА2, схема Крамера-Шоупа перестанет быть стойкой в теоретико-информационном смысле по Шеннону.
В следующем разделе будет показано, как достигается точность имитации шифрования в ходе курса обучения криптоанализу во время атаки IND-CCA2.
590
Часть V. Методы формального доказательства стойкости
15.3.3.5 Имитация процедуры расшифровывания
Получив от атакующего алгоритма Л зашифрованный текст С = (ГД, U2, Е, V), Саймон сначала должен выполнить процедуру проверки целостности данных, описанную в алгоритме 15.3.2.1. Если проверка завершилась успешно, зашифрованный текст считается корректным. Тогда Саймон вычисляет значение
т = jj^, (15.3.6)
и возвращает его атакующему алгоритму Л как результат расшифровки. Если проверка завершается неудачей, зашифрованный текст считается некорректным, и Саймон должен вернуть отказ.
В свое время мы докажем теорему 15.1. утверждающую, что если зашифрованный текст С = (Ui,U2,E,V) является корректным, то (<д,92,^1,^2) € D с вероятностью 1 — ^. Следовательно, существует число R € \0,q), удовлетворяющее условию Ui = д^, U2 = д2. Итак,
U?U? = д^дХ* = = h*. (15.3.7)
Следовательно, имитация расшифровки, выполненная Саймоном при вычислении формулы (15.3.6), является корректной. Вероятность противоположного события равна ^. Этот факт устраняет сомнения, может ли Саймон правильно выполнить расшифровку, не имея закрытого компонента z = zx + z2 l°gfil <te(mod<7), сформулированные в разделе 15.3.3.3.
Способность правильно выполнять расшифровку корректных зашифрованных текстов позволяет Саймону обучать атакующий алгоритм Л в рамках атаки IND-ССА2.
Покажем теперь, что курсы обучения криптоанализу не компрометируют качество зашифрованного оклика, скрывающего число ть.
Для любого корректно зашифрованного текста, присланного атакующим алгоритмом Л, возвращенный результат расшифровки только подтверждает, что пара , целых чисел (21,22) в тексте (15.3.7) зависит от тройки (Ui,U2,hR) точно так | же, как пара компонентов открытого ключа (gi,g2, h) в третьем уравнении системы (15.3.2). Таким образом, атакующий алгоритм Л не может получить никакой дополнительной информации о числах z\ и z2. Следовательно, если атакующий алгоритм Л присылает корректно зашифрованный текст, то курс криптоанализа ему ни к чему.
Чтобы не утерять возможности, полученные в результате предыдущего кур- I са криптоанализа, атакующий алгоритм Л должен представить зашифрованный текст С = (ГЛ, U2, Е, V), для которого (<д, 52, Ui, U2) ? D. Если этот текст пройдет проверку, выполняемую Саймоном, атакующему алгоритму Л будет возвращен результат расшифровки, связанный с зашифрованным окликом отношением,
