Модульная арифметика
Я новичок в криптографии и модульной арифметике. Я уверен, что это глупый вопрос, но я ничего не могу с собой поделать.
Как рассчитать а из
pow (а, q) = 1 (мод п),
где известны п и q? Я не получаю часть «1 (mod п)», она равна 1, не так ли? Если да, то в чем суть "мода п"?
Это то же самое, что
pow (а, -q) (mod п) = 1?
Ответы 2
Совсем не глупо, поскольку это основа для шифрования с открытым ключом. Вы можете найти отличное обсуждение этого на http://home.scarlet.be/~ping1339/congr.htm#The-equation-a%3Csup%3Ex.
PKI работает, выбирая большие p и q и относительно простой. Один (скажем, p) становится вашим закрытым ключом, а другой (q) - вашим открытым ключом. Шифрование «взломано», если злоумышленник угадает p, учитывая aq (зашифрованное сообщение) и q (ваш открытый ключ).
Итак, чтобы ответить на ваш вопрос:
aq= 1 modp
Это означает, что aq - это число, которое оставляет остаток от 1 при делении на p. Нам не важна целая часть частного, поэтому мы можем написать:
aq/p=n+ 1/p
для любое целочисленное значение n. Если мы умножим обе части уравнения на p, мы получим:
aq=np+ 1
Решая для a, мы имеем:
a= (np+1)1/q
Последний шаг - найти значение n, которое генерирует исходное значение a. Я не знаю другого способа сделать это, кроме проб и ошибок, что равносильно попытке взломать шифрование методом «грубой силы».
Часть (mod p) относится не к правой части, а к знаку равенства: он говорит, что по модулю p, pow (a, q) и 1 равны. Например, «по модулю 10, 246126 и 7868726 равны» (и они оба равны 6 по модулю 10): два числа x и y равны по модулю p, если они имеют одинаковый остаток при делении на p, или, что то же самое, если p делит x-y.
Поскольку вы, кажется, исходите из точки зрения программирования, другой способ сказать, что это pow (a, q)% p = 1, где «%» - это оператор «остатка», реализованный на нескольких языках (при условии, что p> 1 ).
Вам следует прочитать статью в Википедии о Модульная арифметика или любую книгу по элементарной теории чисел (или даже книгу по криптографии, поскольку она, вероятно, вводит модульную арифметику).
Чтобы ответить на ваш другой вопрос: не существует общей формулы для поиска такого а (насколько мне известно) в целом. Предполагая, что p простое число, и используя Маленькая теорема Ферма для уменьшения q по модулю p-1, и предполагая, что q делит p-1 (или, иначе, такой а не существует), вы можете создать такое а, взяв первобытный корень из p и увеличив его до мощность (p-1) / q. [И в более общем плане, когда p не является простым, вы можете уменьшить q по модулю φ (p), а затем, предполагая, что он делит φ (p), и вы знаете первообразный корень (скажем, r) по модулю p, вы можете взять r в степень φ (p) / q, где φ - это функция totient - это происходит от Теорема Эйлера.]
Вау! Я рад, что вы здесь, чтобы ответить на подобные вопросы!