Сформулируйте теорему Эйлера.
При n и НОД(a,n)=1 имеем аφ(n)≡1(modn). Теперь легко вычислить, что для простого n, и при условии, что а не делиться на n, справедлива формула: аn-1≡1(modn)
Для вычисления обратных значений алгоритм Евклида быстрее, чем обобщение Эйлера, особенно для чисел длиной порядка 500 бит.
Опишите способ получения таблицы простых чисел на основе решета Эратосфена.
Один из первых алгоритмов для поиска простых чисел принадлежит древнегреческому математику Эратосфену. Алгоритм состоит в том, что выписываются подряд все натуральные числа и вычеркивается каждое второе число, большее двух, потом каждое третье, большее трех, потом каждое пятое, большее пяти (каждое четвертое уже было вычеркнуто, когда вычеркивалось каждое второе), и так далее. Алгоритм “решета Эратосфена” иногда используется в программах для оценки быстродействия компьютеров—компьютер тем быстрее, чем больше простых чисел он сможет найти за заданное время. Таким образом, для каждого числа n его проверка на простоту может быть организована как “просев” через “решето Эратосфена”, т. е. делением n на все простые числа, не большие pn. Если одно из делений будет успешным, т. е. с нулевым остатком, то n — непростое. Если же все деления будут неуспешны, то n — простое.
Опишите упрощенную модель шифрования битовой строки.
Идея упрощенной модели состоит в применении к открытому тексту обратимой операции для получения шифротекста. На основе обратимой операции побитового сложения по модулю 2 открытого текста с случайным потоком битов. Получатель восстанавливает текст с помощью обратной операции, складывая шифротекст с тем же самым случайным потоком. Такую модель можно реализовать на практике, поскольку для ее реализации применяется простейшая компьютерная операция «исключающее или» (XOR).
Шифруя каждое новое сообщение своим ключом, длина которого совпадает с длиной открытого текста, мы получим абсолютно стойкую симметричную криптосистему (одноразовый шифр блокнот). Однако, несмотря на совершенство этого алгоритма, он редко применяется на практике, поскольку порождает проблему распределения ключей, поэтому разрабатываются симметричные криптосистемы, в которых длинное сообщение шифруется коротким ключом, причем этот ключ можно использовать несколько раз. Разумеется, такие системы не являются стойкими, но распределение ключей оказывается решаемой задачей.
Приведите схему и опишите принцип работы поточного шифра.
Шифротекст
011011011
Открытый
текст
110010101
+
Генератор
ключевого потока
Поток
ключей
101001110
Секретный
ключ
Случайный поток битов теперь генерируется по короткому секретному ключу с помощью открытого алгоритма, называемого генератором ключевого потока, при этом биты шифротекста получаются оп правилу сi = mi + ki, где mi – биты открытого текста, а ki – это соответствующие биты ключевого потока. Поскольку процесс шифрования – это сложение по модулю 2, то расшифровывание является по существу той же самой операцией: mi = ci + ki
Поточные шифры просты и удобны для реализации. Позволяют быстро шифровать большие объемы данных, поэтому они подходят для передачи аудио- и видеосигналов в реальном режиме времени. В процессе шифрования не происходит накопления ошибки. Если отдельный бит шифротекста исказился в процессе передачи, то в расшифрованном открытом тексте только 1 бит окажется неверным. Однако повторное использование того же ключа дает тот же ключевой поток. Это влечет за собой зависимость между соответствующими сообщениями. Предположим, что сообщение m1 и m2 были зашифрованы одним и тем же ключом, тогда противник, перехватив шифротексты, легко найдет сумму по модулю 2 открытых текстов: с1 + с2 = (m1 + h) + (m2 + h) = m1 + m2, где + есть сложение по модулю 2.
Следовательно, необходимо менять ключи либо с каждым новым сообщением, либо с очередным сеансом связи. Обычно алгоритмы с открытым ключом применяются для передачи ключа, закрепленного за отдельным сообщением или за целым сеансом связи. И только после этого шифруются фактические данные с помощью блочного или поточного шифра.
Чтобы придать необходимую стойкость шифру, генератор ключевого потока производит строку бит с определенными свойствами. Ключевой поток должен содержать как минимум:
• Иметь большой период;
• Иметь псевдослучайные свойства, т.к. генератор должен производить последовательность, которая кажется случайной и должна выдержать статические тесты на случайность;
• Иметь линейную сложность.
Но и этого не хватает, поскольку восстановление значительной части этой последовательности должно быть неосуществимым в вычислительном отношении.