ВОПРОС 4 RSA АЛГОРИТМСтр 1 из 5Следующая ⇒
Обратные элементы в кольцах вычетов Если же n _ простое, то согласно последнему свойству сравнения можно сокращать на любое ненулевое число. Более того, в кольце вычетов по простому модулю можно выполнять деление на любое ненулевое число и, как следствие, можно решать уравнения вида ax ≡ b (mod n). Решением такого уравнения явлется число x = ba−1, где a−1 _ обратный элемент к a в кольце вычетов по модулю n, то есть такое число, что aa−1 ≡ 1 (mod n). Если n _ простое, то для любого ненулевого числа существует обратный элемент, и, следовательно, можно делить на любое ненулевое число. Для нахождения обратного элемента к a в кольце вычетов по модулю n используем расширенный алгоритм Евклида для чисел a и n. Он найдет такие числа x и y, что ax + ny = 1, а, значит, ax ≡ 1 (mod n). Подумайте, для каких чисел a существует обратный элемент в кольце вычетов по модулю n, если n _ составное. Шаг 1. Пусть d = (a, b, n) (наибольший общий делитель трех чисел). Тогда сократим a, b, n на d (свойство 4). Шаг 2. Если a необратим в кольце вычетов по модулю n, то решений нет. Иначе x = ba−1 (mod n) _ решение. Китайская теорема об остатках В решении систем линейных сравнений помогает китайская теорема об остатках.Простейшая система сравнений имеет вид x ≡ a (mod m), x ≡ b (mod n), где (m, n) = 1. Тогда существует целое число c, такое, что эта система верна тогда, и только тогда, когда x ≡ c (mod mn). Доказательство. Поскольку m и n _ взаимно простые, то существуют числа r = n−1 (mod m) и s = m−1 (mod n). Положим c = arn + bsm. Тогда если x ≡ c (mod mn), то x ≡ c = arn + bsm ≡ arn ≡ ann−1 ≡ a (mod m) x ≡ c = arn + bsm ≡ bsm ≡ bmm−1 ≡ b (mod n) Докажем утверждение в другую сторону. Предположим, что x ≡ a (mod m), x ≡ b (mod n). Выше было доказано, что c ≡ a (mod m) и c ≡ b (mod n). Поэтому, x ≡ c (mod m), то есть x−c делится на m. Ана- логично, x−c делится на n, откуда x−c делится на mn, следовательно, x ≡ c (mod mn). Подумайте сами, как быть с системой из трёх и более неравенств и как быть, если m и n не взаимно просты.
Вопрос 2 идея алгоритма состоит в том, чтобы возвести a в произвольную степень, применяя элементарные операции возведения в квадрат и умножения. В качестве фазового пространства X этой задачи рассмотрим множество троек X = {(b,k,p)}. Здесь b выступает в роли текущего основания степени, k - в роли текущего показателя степени, p - это уже вычисленная часть степени. Ключевым моментом всегда является формулировка инварианта цикла: Вопрос 3 Определение группы Пусть задано множество элементов G g1, g2, ... , gn , обладающих следующими свойствами: 1. Определен закон умножения элементов gi gj = gk, причем если gi, gj G, то gi gj = gk G, 2. Выполняется закон ассоциативности gi (gj gk) = (gi gj) gk. 3. Существует единичный элемент e, egi = gi, i = 1, 2, ... , n. 4. Существует обратный элемент g i-1, g i-1gi = e, i = 1, 2, ... , n. Тогда на множестве G задана группа элементов g1, g2, ... , gn
ВОПРОС 4 RSA АЛГОРИТМ Выберем группу порядка , который держится в секрете. Но при этом в группе возможны вычисления. Пусть — обратимое целое число по модулю , . Зашифруем элемент группы по правилу , а расшифруем по другому правилу . При этом предполагается, что исходный текст можно разбить на части, которым можно взаимно однозначно сопоставить элементы группы . Пример. Пусть группа — мультипликативная группа вычетов по модулю , где и — различные простые числа, которые держатся в секрете. Порядок группы равен . В настоящее время считается, что задача разложения целого числа на простые множители настолько сложна, что это обеспечивает достаточную стойкость системы шифрования. Замечание 1. Свойство быть квадратичным вычетом сохраняется при зашифровке. Замечание 2. Неизвестно, является ли задача расшифровки в RSA алгоритме задачей, эквивалентной задаче факторизации целых чисел. Замечание 3. Сравнение верно для любого класса вычетов по модулю , а не только для вычетов взаимно простых с . Действительно, пусть . Тогда . Число кратно и значит , следовательно, и так как и — различные простые числа, то . Аналогично . Из мультипликативности классов вычетов следует, что сравнение верно для любого , так как любой необратимый элемент группы кратен или [ 5 ]. Пример (алгоритм RSA) . Пусть — простые числа, .Процесс шифрования выглядит так: : , т.е. , а процесс расшифровки так : ,те . Замечание. Допустим удалось получить тексты такие, что . Тогда, если и — законные подписи для текстов и , то —законная подпись для текста . ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|