Основні типи шифрів. Поняття ключового потоку

Блокові симетричні шифри

Опис алгоритму знаходження квадратного кореня у простому полі

Очевидно,. Оскільки квадратичний лишок, то і ми можемо знизити показник у два рази:.

Після другого ділення показника на два в правій частині вийде. Ми можемо вибрати істинний варіант, обчислюючи ліву частину порівняння безпосередньо.

Якщо в правій частині виходить 1, то рухаємося далі. Зауважимо, що в правій частині може з’явитися не раніше чим на другому кроці, тобто при показнику і нижче. Припустимо, що в правій частині при зазначеному показнику вийшла:. Оскільки - квадратичний нелишок, то і, крім того, показник при більше показника при. Помножимо обидві частини порівняння на, одержимо.

З лівої частини порівняння легко витягнути квадратний корінь, тобто.

Як і раніше, просто з’ясувати, який з варіантів має місце насправді і, при необхідності, помножити порівняння на і т.д., поки показник при не виявиться рівним. Після останнього кроку, показник при буде відома і парним, як сума парних чисел. В результаті, виникає порівняння виду, звідки, помноживши обидві частини на, одержимо:.

Приклад. Розв’язати конгруенцію.

З'ясуємо, насамперед, чи є конгруенція розв'язним. Це дійсно так, оскільки.

Далі з'ясуємо, який з трьох випадків представлення має місце. Очевидно, має місце випадок. Записавши, одержимо,.

Знайдемо квадратичний нелишок за модулем. Можна вибрати, оскільки. Приступимо до знаходження кореня, враховуючи, що.

З теореми Ейлера, маємо. Розділимо показник на два. При цьому значення кореня дорівнює 1, тому що - квадратичний нелишок і.

Показник можна знову розділити на два. Отже,. Оскільки, те. Необхідно домогтися значення 1 у правій частині порівняння. Помножимо обидві частин на, одержимо. Як слід було очікувати, показник при трійці парний.

Нам залишився один крок, щоб знизити показник при вісімці до. Ділимо показники на два й обчислюємо значення лівої частини:,, тобто. Нам знову необхідно помножити обидві частини порівняння на, що дає. Показник при вісімці дорівнює. В останнє помноживши обидві частини порівняння на 8, одержимо, що дозволяє записати квадратний корінь з 8 у виді. Перевірка:.

Звернемо увагу на одну з відмінностей між шифром простої заміни і гаммирования: у шифрі простої заміни один і теж елемент відкритого тексту перейде у фіксований знак шифротекста в будь-якому такті шифрування, а в шифрі гаммирования це не так. Цей шифр перетворює елемент відкритого тексту в залежності від номера такта шифрування і значення гами (тобто ключа) на цьому такті.

Можна сказати, що згаданий ключ задає послідовність шифрперетворень, на відміну від шифру простої заміни, де всі шифрперетворення однакові. Зазначена відмінність приводить до понять основних типів шифрів: блокових і потокових шифрів відповідно.

Дата добавления: 2014-10-15