Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Так как в квадратичных многочленах три неизвестных коэффициента , a, b и M, для создания трех уравнений можно использовать любые три цели. Одной или двух теней не хватит, а четырех или пяти теней будет много . Например, пусть M равно 11. Чтобы создать пороговую схему (3, 5), в которой любые трое из пяти человек могут восстановить M, сначала получим квадратичное уравнение (7 и 8 - случайно выбранные числа chosen ran- domly): F(x) = (7x 2 + 5x + 11) mod 13 Пятью тенями являются: k 1 = F(1) = 7 + 8 + 11? 0 (mod 13) k 2 = F(2) = 28 + 16 + 11? 3 (mod 13) k 3 = F(3) = 63 + 24 + 11? 7 (mod 13) k 4 = F(4) = 112 + 32 + 11? 12 (mod 13) k 5 = F(5) = 175 + 40 + 11? 5 (mod 13) Чтобы восстановить M по трем теням, например, k 2 , k 3 и k 5 , решается система линейных уравнений: a*2 2 + b*2 + M = 3 (mod 13) a*3 2 + b*3 + M = 7 (mod 13) a*5 2 + b*5 + M = 5 (mod 13) Решением будут a = 7, b = 8 и M = 11. Итак, M получено. Эту схему разделения можно легко реализовать для больших чисел . Если вы хотите разбить сообщение на 30 равных частей так, чтобы восстановить сообщение можно было, объединив любые шесть из них , выдайте каждому из 30 человек значения многочлена пятой степени . F(x) = ax 5 + bx 4 + cx 3 + dx 2 + ex + M (mod p) Шесть человек могут шесть неизвестных (включая M), но пятерым не удастся узнать ничего об M. Наиболее впечатляющим моментом совместного использования секрета является то, что, если коэффицие н- ты выбраны случайным образом, пять человек даже при помощи бесконечных вычислительных мощностей не смогут узнать ничего, кроме длины сообщения (которая и так им известна) . Это также безопасно, как одноразо- вый блокнот, попытка выполнить исчерпывающий поиск (то есть, перебор всех возможных шестых теней) по- кажет, что любое возможное сообщение останется секретным . Это справедливо для всех представленных в этой книге схем разделения секрета. Векторная схема Джордж Блэкли (George Blakley) изобрел схему, использующую понятие точек в пространстве [182]. Сооб- щение определяется как точка в m-мерном пространстве. Каждая тень - это уравнение (m-1)-мерной гиперпло- скости, содержащей эту точку. Например, если для восстановления сообщения нужны три тени, то оно является точкой в трехмерном пр о- странстве. Каждая тень представляет собой иную плоскость . Зная одну тень, можно утверждать, что точка нах о- дится где-то на плоскости. Зная две тени - что она находится где-то на линии пересечения двух плоскостей . Зная три тени, можно точно определить, что точка находится на пересечении трех плоскостей . Asmuth-Bloom В этой схеме используются простые числа [65]. Для (m, n)-пороговой схемы выбирается большое простое число p, большее M. Затем выбираются числа, меньшие p - d 1 , d 2 , . . . d n , для которых: 1. Значения d i упорядочены по возрастанию, d i < d i+1 2. Каждое d i взаимно просто с любым другим d i 3. d 1 *d 2 * . . .*d m > p*d n-m+2 *d n-m+3 *. . .*d n Чтобы распределить тени, сначала выбирается случайное число r и вычисляется M' = M + rp Тенями, k i , являются k i = M' mod d i Объединив любые m теней, можно восстановить M, используя китайскую теорему об остатках , но это невоз- можно с помощью любых m-1 теней. Подробности приведены в [65]. Karnin-Greene-Hellman В этой схеме используется матричное умножение [818]. Выбирается n+1 m-мерных векторов, V 0 , V 1 , . . . V n , так, что ранг любой матрицы размером m*m, образованной из этих векторов, равен m. Вектор U - это вектор размерности m+1. M - это матричное произведение U·V 0 . Тенями являются произведения U·V i , где i меняется от 1 до n. Любые m теней можно использовать для решения системы линейных уравнений размерности m*m, неиз- вестными являются коэффициенты U. U·V 0 можно вычислить по U. Используя любые m-1 теней, решить систе- му уравнений и, таким образом, восстановить секрет невозможно . Более сложные пороговые схемы В предыдущих примерах показаны только простейшие пороговые схемы : секрет делится на n теней так, что- бы, объединив любые m из них, можно было раскрыть секрет. На базе этих алгоритмов можно создать намного более сложные схемы. В следующих примерах будет использоваться алгоритм Шамира, хотя будут работать и все остальные. Чтобы создать схему, в которой один из участников важнее других, ему выдается больше теней . Если для восстановления секрета нужно пять теней, и у кого-то есть три тени, а у всех остальных - по одной , этот человек вместе с любыми двумя другими может восстановить секрет . Без его участия для восстановления секрета потр е- буется пять человек. По несколько теней могут получить два человека и более . Каждому человеку может быть выдано отличное число теней. Независимо от того, сколько теней было роздано, для восстановления секрета потребуется любые m из них. Ни один человек, ни целая группа не смогут восстановить секрет, обладая только m-1 тенями. Для других схем представим сценарий с двумя враждебными делегациями . Можно распределить секрет так, чтобы для его восстановления потребовалось двое из 7 участников делегации A и трое из 12 участников делега- ции B. Создается многочлен степени 3, который является произведением линейного и квадратного выражений . Каждому участнику делегации A выдается тень, которая является значением линейного выражения, а участн и- кам делегации B выдаются значения квадратичного выражения . Для восстановления линейного выражения достаточны любые две тени участников делегации A, но незави- симо от того, сколько других теней есть у делегации , ее участники не смогут ничего узнать о секрете . Аналогич- но для делегации B: ее участники могут сложить три тени, восстанавливая квадратное выражение, но другую информацию, необходимую для восстановления секрета в целом, они получить не смогут . Только перемножив свои выражения, участники двух делегаций смогут восстановить секрет . В общем случае, может быть реализована любая мыслимая схема разделения секрета . Потребуется только написать систему уравнений, соответствующих конкретной системе. Вот несколько прекрасных статей на тему обобщенных схем разделения секрета [1462, 1463, 1464]. Разделение секрета с мошенниками Этот алгоритм изменяет стандартную пороговую схему (m, n) для обнаружения мошенников [1529]. Я пока- жу его использование на базе схемы Лагранжа , но алгоритм работает и с другими схемами . Выбирается простое число p, большее n и большее (s - 1)(m - 1)/e + m где s - это самый большой возможный секрет, а e - вероятность успеха мошенничества. e можно сделать на- столько малым, насколько это необходимо, это просто усложнит вычисления . Постройте тени как раньше, но вместо использования 1, 2, 3, . . . , n для x i , выберите случайным образом числа из диапазона от 1 до p-1. Теперь, если Мэллори при восстановлении секрета заменит свою часть подделкой , его тень с высокой веро- ятностью окажется невозможной. Невозможный секрет, конечно же, окажется подделанным секретом . Матема- тика этой схемы приведена в [1529]. К сожалению, хотя мошенничество Мэллори и будет открыто, ему удастся узнать секрет (при условии, что все остальные нужные тени правильны). От этого защищает другой протокол, описанный в [1529, 975]. Основ- ной идеей является использование набора из k секретов, так чтобы никто из участников заранее не знал, какой из них правильный. Каждый секрет, за исключением настоящего, больше предыдущего. Участники объединяют свои тени, получая один секрет за другим, пока они не получат наименьшее значение секрета . Этот секрет и будет правильным. В этой схеме мошенники легко выявляются еще до получения конечного секрета . Существует определенные сложности, если участники предъявляют свои тени по очереди, подробности можно найти в литературе . В сле- дующих работах также рассматриваются обнаружение и предотвращение мошенничества в пороговых схемах [355, 114, 270]. 23.3 Подсознательный канал Ong-Schnorr-Shamir Этот подсознательный канал (см. раздел 4.2), разработанный Густавусом Симмонсом (Gustavus Simmons) [1458, 1459, 1460], использует схему идентификации Ong-Schnorr-Shamir (см. раздел 20.5). Как и в оригиналь- ной схеме отправитель (Алиса) выбирает общедоступный модуль n и закрытый ключ k так, чтобы n и k были взаимно простыми числами. В отличии от оригинальной схемы k используется совместно Алисой и Бобом, по- лучателем в подсознательном канале. Открытый ключ вычисляется следующим образом : h = -k 2 mod n Если Алисе нужно отправить подсознательное сообщение M в безобидном сообщении M', она сначала про- веряет, что пары M' и n, а также M и n являются взаимно простыми числами. Алиса вычисляет S 1 = 1/2*((M'/M + M)) mod n S 2 = 1/2*((M'/M - M)) mod n Пара чисел S 1 и S 2 представляет собой подпись в традиционной схеме Ong-Schnortr-Shamir и одновременно является носителем подсознательного сообщения . Тюремщик Уолтер (помните такого?) может проверить подлинность сообщения, как это принято в Ong- Schnorr-Shamir, но Боб может сделать еще кое-что. Он может проверить подлинность сообщения (Всегда воз- можно, что Уолтер попытается ему подсунуть поддельное сообщение ). Он проверяет, что S 1 2 - S 2 2 ? M' (mod n) Если подлинность сообщения доказана, получатель может извлечь и подсознательное сообщение, используя следующую формулу: M=M'/(S 1 + S 2 k -1 ) mod n Это работает, но не забывайте, что сама схема Ong-Schnorr-Shamir была взломана. ElGamal Другой предложенный Симмонсом подсознательный канал [1459], описанный в [1407, 1473], основан на схеме подписи ElGamal см. раздел 19.6). Генерация ключа выполняется также, как и в основной схеме подписи ElGamal. Сначала выбирается простое число p и два случайных числа, g и r, меньшие p. Затем вычисляется K = g r mod p Открытым ключом служат K, g и p. Закрытым ключом является r. Помимо Алисы r известно и Бобу, это число используется не только для подписи безобидного сообщения, но и в качестве ключа для отправки и чт е- ния подсознательного сообщения. Чтобы послать подсознательное сообщение M в безобидном сообщении, M', M и p должны быть попарно взаимно простыми, кроме того, взаимно простыми должны быть M и p-1. Алиса вычисляет X = g M mod p и решает следующее уравнение для Y (с помощью расширенного алгоритма Эвклида ): M' = rX+ MY mod (p-1) Как и в базовой схеме ElGamal, подписью является пара чисел: X и Y. Уолтер может проверить подпись El- Gamal. Он убеждается, что K X X Y ? g M' (mod p) Боб может восстановить подсознательное сообщение. Сначала он убеждается, что (g r ) X X Y ? g M' (mod p) Если это так, он считает сообщение подлинным (не подделанным Уолтером) . Затем для восстановления M он вычисляет M = (Y -1 (M' - rX)) mod (p - 1) Например, пусть p = 11, а g = 2. Закрытый ключ r выбирается равным 8. Это означает, что открытым клю- чом, который Уолтер может использовать для проверки подписи, будет g r mod p = 2 8 mod 11 = 3. Чтобы отправить подсознательное сообщение M = 9, используя безобидное сообщение M' = 5, Алиса прове- ряет, что 9 и 11, а также 5 и 11 попарно взаимно просты . Она также убеждается, что взаимно просты 9 и 11-1=10. Это так, поэтому она вычисляет X = g M' (mod p) = 2 9 mod 11 = 6 Затем она решает следующее уравнение для Y: 5 = 8 6 + 9 Y mod 10 Y= 3, поэтому подписью служит пара чисел 6 и 3 ( X и Y). Боб убеждается, что (g r ) X X Y ? g M' (mod p) (2 8 ) 6 6 3 ? 2 5 (mod 11) Это так (выполните арифметические действия самостоятельно, если вы мне не верите ), поэтому он может раскрыть подсознательное сообщение, вычисляя M = (Y -1 (M' - rX)) mod (p - 1)= 3 -1 (5 - 8*6) mod 10 = 7(7) mod 10 = 49 mod 10 = 9 ESIGN Подсознательный канал можно добавить и к ESIGN [1460] (см. раздел 20.6). В ESIGN секретный ключ явля- ется парой больших простых чисел p и q, а открытым ключом служит n = p 2 q. Использовании подсознательного канала закрытым ключом являются три простых числа p, q и r, а открытым ключом - n, такое что n = p 2 qr Переменная r - это дополнительные данные, нужные Бобу для прочтения подсознательного сообщения . Чтобы подписать обычное сообщение, Алиса сначала выбирает случайное число x, меньшее pqr, и вычисляет: w, наименьшее целое, которое больше или равно (H(m) - x k mod n)/pq s = x + ((w/kx k-1 mod p) pq H(m) - это хэш-значение сообщения, а k - параметр безопасности. Подписью является значение s. Для проверки подписи Боб вычисляет s k mod n. Кроме этого, он вычисляет a, наименьшее целое, которое больше или равно удвоенному числу битов n, деленному на 3. Если H(m) меньше или равна s k mod n, и если s k mod n меньше H(m)+2 a , то подпись считается правильной. Для отправки подсознательного сообщения M с помощью безобидного сообщения M' Алиса вычисляет s, ис- пользуя M вместо of H(m). Это означает, что сообщение должно быть меньше, чем p 2 qr. Затем она выбирает случайное число u и вычисляет x' = M' + ur Затем это значение x' используется в качестве "случайного числа" x при подписи M'. Соответствующее зна- чение s посылается в качестве подписи. Уолтер может проверить, что s (второе s) является правильной подписью M' Точно также проверить подлин- ность сообщения может и Боб. Но, так как ему известно и r, он может вычислить s = x' + ypqr = M + ur + ypqr ? M (mod r) Эта реализация подсознательного канала намного лучше двух предыдущих . В вариантах Ong-Schnorr- Shamir и ElGamal у Боба должен быть закрытый ключ Алисы. Боб сможет не только читать подсознательные сообщения Алисы, но и выдавать себя за Алису, подписывая обычные документы . Алиса ничего с этим не смо- жет поделать, устанавливая такой подсознательный канал, ей придется довериться Бобу . Схема ESICN страдает от этой проблемы. Закрытым ключом Алисы служит набор трех простых чисел: p, q и r. Секретным ключом Боба является только r. Он знает n = p 2 qr, но, чтобы раскрыть p и q, ему понадобится разложить на множители это число. Если простые числа достаточно велики, Бобу будет так же трудно выдать себя за Алису, как и Уолтеру или кому-нибудь еще . DSA Подсознательный канал существует и в DSA (см. раздел 20.1) [1468, 1469, 1473]. На самом деле их даже может быть несколько. Простейший подсознательный канал включает выбор k. Предполагается, что это будет 160-битовое число. Однако, если Алиса выбирает конкретное k, то Боб, зная закрытый ключ Алисы, сможет раскрыть это k. Алиса посылать Бобу 160-битовое подсознательное сообщение в каждой подписи DSA, а все остальные будут только проверять подпись Алисы . Дополнительное усложнение: Так как k должно быть слу- чайным, Алиса и Боб должны использовать общий одноразовый блокнот и шифровать подсознательное соо б- щение с помощью этого блокнота, генерируя k. В DSA есть подсознательные каналы, не требующие передавать Бобу закрытый ключ Алисы . Они также подразумевают выбор конкретных значений k, но не могут передавать по 160 битов информации. Следующая схема, представленная в [1468, 1469], позволяет Алисе и Бобу обмениваться в каждой подписи одним битом подсознательной информации. (1) Алиса и Боб выбирают случайное простое число P (отличающееся от параметра p в схеме подписи). Это секретный ключ для подсознательного канала . (2) Алиса подписывает безобидное сообщение M. Если она хочет отправить Бобу подсознательный бит 1 , она убеждается, что параметр r подписи является квадратичным остатком по модулю P. Если она хочет отпра- вить ему 0, она проверяет, что параметр r подписи не является квадратичным остатком по модулю P. Она добивается этого, подписывая сообщение с помощью случайных значений k, пока она не получит подпись с нужным ей свойством для r. Так как числа, являющиеся квадратичными остатками и не являющиеся ими, равновероятны, то это не должно быть слишком сложно. (3) Алиса посылает Бобу подписанное сообщение. (4) Боб проверяет подпись, убеждаясь в подлинности сообщения . Затем он проверяет, является ли r квадра- тичным остатком по модулю P и восстанавливает подсознательный бит. Передача таким образом нескольких битов подразумевает подбор такого r, которое является или не является квадратичным остатком по нескольким модулям . Подробности приведены в [1468, 1469]. Эта схема может быть легко расширена для передачи нескольких подсознательных битов на подпись . Если Алиса и Боб выбирают два случайных числа P и Q, то Алиса может посылать два бита, выбирая случайное k так, чтобы r являлось или не являлось квадратичным остатком mod P, а также являлось или не являлось квадра- тичным остатком mod Q. Случайное значение k с вероятностью 25 процентов позволит получить r с нужными свойствами. Вот как Мэллори, нечестный реализатор DSA, может создать алгоритм, извлекающий по 10 битов закрытого ключа Алисы из каждой ее подписи. (1) Мэллори строит свою реализацию DSA базе устойчивой к взлому СБИС, чтобы никто не смог проверить, как она работает. Он создает 14 подсознательных каналов в своей реализации DSA. То есть, он выбирает 14 случайных простых чисел и использует микросхему, которая выбирает значение k так, чтобы r являлось или не являлось квадратичным остатком по модулю каждого из этих 14 простых чисел , в зависимости от подсознательного сообщения. (2) Мэллори выдает микросхемы Алисе, Бобу и остальным желающим. (3) Алиса обычным образом подписывает сообщение , используя свой закрытый 160-битовый ключ x. (4) Микросхема случайным образом выбирает 10-битовый блок x: первые 10 битов, вторые 10 битов, и т.д. Так как существует 16 возможных 10-битовых блоков , то номер блока выражается 4-битовым числом . Этот 4-битовый идентификатор и 10 битов ключа и будут 14-битовым подсознательным сообщением . (5) Микросхема перебирает случайные значения k, пока не удастся найти то, которое обладает правильными квадратичными остатками, нужными для передачи подсознательного . Вероятность случайного k обладать правильной формой равна 1/16384. Если микросхема может проверить 10000 значений k в секунду, нуж- ное значение будет найдено меньше, чем за пару секунд. Эти вычисления не зависят от сообщения и могут быть вычислены заранее, до того, как Алиса захочет подписать сообщение. |