загрузка...
загрузка...
На головну

Модульна арифметика

  1. арифметика
  2. арифметика
  3. арифметика
  4. арифметика відрахувань
  5. Арифметика рядів Фібоначчі
  6. Увага! Модульна формула пишеться зліва направо.
  7. Увага! Модульна формула пишеться зліва направо.

У криптографії та криптоанализе часто буває необхідно скласти дві послідовності чисел або ж відняти одну з іншої. Таке додавання і віднімання проводиться, як правило, не за допомогою звичайних арифметичних дій, а за допомогою операцій, які називаються модульної арифметикою. В модульної арифметики додавання, віднімання виконується щодо деякого фіксованого числа, яке називається модуль. Типовими значеннями модулів, які використовуються в криптографії, є 2, 10 і 26. Який би модуль ми не взяли, все зустрічаються числа замінюються на залишки від ділення цих чисел. Якщо в залишку виходить негативне число, то до нього додають значення модуля, щоб залишок став невід'ємним. Наприклад, якщо використовується модуль 26, то єдино можливі числа лежать в діапазоні від 0 до 25. Так, якщо додати 17 до 19, то результат дорівнює 10, оскільки 17 + 19 = 36, а 36 при розподілі на 26 дає залишок 10. Щоб вказати, що використовується модуль 26, прийнята форма запису:

17 + 19 = 10 (mod26).

Якщо відняти 19 з 17, то результат (-2) виходить негативним, тому до нього додається 26, і в підсумку виходить 24.

При додаванні по модулю 26 двох числових послідовностей сформульовані правила складання застосовуються в кожній парі чисел окремо, без «перенесення» на наступну пару. Аналогічно, при відніманні по модулю 26 одній числової послідовності з іншого правила віднімання застосовуються до кожної пари чисел окремо, без «запозичення» з наступної пари.

приклад 1.1

Скласти по модулю 26 послідовності 15 11 23 06 11 і 17 04 14 19 23

Рішення

11 23 06 11

17 04 14 19 23

32 15 37 25 34

06 15 11 25 08

і в результаті 06 15 11 25 08

Якщо модуль дорівнює 10, то використовуються числа від 0 до 9; при модулі 2 - тільки 0 і 1

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

0 0 1 1 0 0 1 1

+ 0 1 0 1 - 0 1 0 1

0 1 1 2 0 -1 1 0

0 1 1 0 0 1 1 0 (mod 2) в обох випадках.

Модульне додавання і віднімання букв

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

Додати TODAY до NEVER по модулю 26

Відняти TODAY з NEVER по модулю 26

Рішення

TODAY = 19 14 03 00 24

NEVER = 13 04 21 04 17

Сума = 32 18 24 04 41 06 18 24 04 15 = GSYEP

TODAY = 19 14 03 00 24

NEVER = 13 04 21 04 17

Різниця = 06 10 -18 -04 07 06 10 08 22 07 = GKIWH




короткі підсумки | Машинна мова. | Історія мов програмування. | Основи машинної математики. | Базові алгоритмічні структури | Лекція 8 Деякі аспекти безпеки зв'язку | Шифр Юлія Цезаря | Основні визначення | Коди і шифри | Оцінка стійкості системи шифрування |

загрузка...
© um.co.ua - учбові матеріали та реферати