Здравствуйте,
SEL> Отвечаю письмом, что бы не загромождать и без того забитый форум.
Уважаемый Эксперктик, к сожалению, я не нашёл Вашего E-mail. Поэтому, увы, загромождаю своими поясненими форум.
SEL> Легко видеть, что x0 просто не существует.
SEL>
SEL> 1. Элементы a^x mod p образуют мультипликативную
SEL> подгруппу порядка q по построению алгоритма ЭЦП (выбор
SEL> параметров p, q, a);
SEL>
SEL> 2. q- простое число, 2^254 < q < 2^256,
SEL> следовательно, q - нечётно;
SEL>
SEL> 3. Следовательно, если в подгруппу входит элемент y, то
SEL> элемент -y в подгруппу не входит;
SEL>
SEL> 4. Следовательно, уравнение p - y == a^x0 mod p, корней не имеет.
Ну, давайте от сохи. Лучше, конечно, какой учебник почитать, а то один "неуч" другого "неуча" учит :) Ну да ничего, для красной армии сойдёт.
1.1 Берём параметры ЭЦП, согласно Эль-Гамалю (ГОСТ-у, DSA). Почему они выбраны так, а не иначе будет ясно по ходу дела;
1.2 Множество Z = { z | 0 <= z < p }. Является коммутативной (абелевой) группой относительно операции сложения по модулю p. Так же, оно является коммутативной группой относительно операции умножения по модулю p. Эти операции обладают свойством ассоциативности. Это хозяйство называют полем и обозначают GF(p);
1.3 GF(p) содержит 0 по сложению, он обладает свойством
z + 0 == z mod p;
1.4 Каждый элемент GF(p) имеет обратный по сложению, он обозначается как -z и обладает свойством
z + (-z) == 0 mod p
Примечание: (-z) = p - z, для z != 0 и (-z) = z, для z = 0;
Примечание: т.к. p - нечётное простое, (-z) != z, для z != 0;
1.5 GF(p) содержит 1 по умножению, он обладает свойством
z*1 == z mod p;
1.6 Легко видеть, что в GF(p) (-1) обладает обычным свойством
z*(-1) == (-z) mod p;
1.7 Т.к. p - простое, то согласно малой теореме Ферма, z^(p-1) == 1 mod p для z != 0 и, следовательно, все не нулевые элементы GF(p) имеют обратные, они обозначаются (z^-1) и обладают свойством
z*(z^-1) == 1 mod p
Примечание: (z^-1) == z^(p-2) mod p;
1.8 Т.к. q является делителем p-1, то мы можем выбрать такое a, что
a^q == 1 mod p
Примечание: a == d^(p - 1)/q mod p;
1.9 По a построим множество Y = { y | y == a^x mod p }. Это множество является мультипликативной подгруппой GF(p) по наведённой операции умножения, т.е. для любых y1 и y2 принадлежащих Y, y1*y2 принадлежит Y (по наведённой операции сложения она группой не является). Эта подгруппа так же является циклической подгруппой Y = { a, a^2, ..., a^x, ..., a^q-1, 1 }. Так же заметим, что если y принадлежит Y, то (y^-1) принадлежит Y (очевидно, что 0 не принадлежит Y);
1.10 Легко видеть, что т.к. q - простое, то множество Y содержит ровно q различных элементов;
2. q - простое число, 2^254 < q < 2^256, следовательно, q - нечётно;
3.1 Предположим, что для какого либо y из Y, (-y) принадлежит Y;
3.2 Тогда (-1) == (-y)*(y^-1) mod p тоже принадлежит Y;
3.3 Тогда для любого y принадлежащего Y, (-y) == (-1)*y mod p тоже принадлежит Y;
3.4 Тогда Y содержит чётное количество элементов, что противоречит пп. 2 и 1.10.
3.5 Следовательно, если в подгруппу входит элемент y, то элемент (-y) в подгруппу не входит;
4. Следовательно, уравнение p - y == a^x0 mod p, корней не имеет.
Уф. Ну вроде бы демонстрационную версию закончил.
--
LSE, Сергей Леонтьев, Крипто-Про, http://www.CryptoPro.ru
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
