Курс теорії чисел та криптографії Параметр b (більше
Параметр b (складніші криптосистеми зазвичай використовують кілька параметрів) називається ключем або, точніше, ключем шифрування.
Приклад 2. Так, припустимо, що перехоплено повідомлення «FQOCUDEM», яке, як відомо, зашифровано з використанням перетворення зсуву на літерах 26-літерного алфавіту, як у прикладі вище. Нам лишається знайти Ь. Зробити це можна за допомогою частотного аналізу. Він працює в такий спосіб. Припустимо, що ми перехоплено довгий відрізок шифртексту, скажімо, кілька сотень букв. Ми знаємо, що «Е» — найпоширеніша літера англійської мови. Тому розумно припустити, що літера, що найбільш часто зустрічається в шифртексті, є результатом шифрування літери «Е». Нехай найчастіше в шифртексті зустрічається буква «U». Це означає, що зрушення перетворює «Е»= 4 в «U»= 20, тобто. 20 = 4 + b (mod 26), тому b = 16. Щоб дешифрувати повідомлення, залишається відняти 16 (за модулем 26) з числових еквівалентів «FQOCUDEM»:
«FQOCUDEM» = 5 1614 2 20 3 412
к* 15 0 2412413 1422 = "PAYMENOW".
Якщо шифрування зрушенням застосовується до букв 26-літерного алфавіту, то немає необхідності мати довгий відрізок шифртексту, що дозволяє знайти літеру, що найбільш часто зустрічається. Зрештою, для b є всього 26 можливостей, і можна просто спробувати їх усі. Швидше за все, лише одному з значень буде відповідати осмислене повідомлення, таке b і є ключ шифрування.
Отже, цей тип криптосистем дуже простий, щоб бути добрим. Розкрити його дуже легко. Його можна вдосконалити, використовуючи ширший клас перетворень Z/NZ, званих афінними відображеннями: С = aP+b (mod N), де а і 6 фіксовані цілі числа (разом вони утворюютьключ шифрування). Якщо,
§ 1. ДЕЯКІ ПРОСТІ КРИПТОСИСТЕМИ
наприклад, знову маючи справу з 26-літерним алфавітом, ми хочемо зашифрувати повідомлення PAYMENOW, використовуючи афінне відображення з ключем шифрування а = 7 і Ь = 12, то отримаємо
15 0 24 12 4 13 14 22 h-> 13 12 24 18 14 25 6 10 = "NMYSOZGK".
Щоб розшифрувати повідомлення, зашифроване застосуванням афінного відображення С = аР + b (mod TV), потрібно просто виразити P через С: P = а!С + b' (mod N), де а' = а 1 є зворотним ка по модулю TV число, a b '-а lb. Зауважимо, що це можливо лише за НОД (a, N)=I. В іншому випадку не можна виразити P через С: якщо НОД (a, N) > 1, то, як неважко переконатися, одній літері шифртексту відповідає кілька літер відкритого тексту, тому не можна однозначно відновити відкритий текст по шифрованому. За визначенням таке перетворення перестав бути шифруючим, оскільки останнє має бути взаємно однозначним, тобто. відкритий текст має визначатися шифртекстом однозначно. Отже, афінна криптосистема над TV-літерним алфавітом з параметрами а Є (Z/TVZ)* та Ь Є Z/TVZ задається правилами
С = АР + b (mod TV), P = а С + Ь1 (mod N),
де a = a 1B (Z/7VZ)*, b' = -а ХЬ.
Як окремий випадок афінної криптосистеми при а = 1 отримуємо перетворення зсуву. В іншому випадку при 6 = 0 отримуємо P = аС (mod N), С = a P (mod TV). Таке перетворення називається лінійним. Воно відображає суму у сумі, тобто. якщо Р при шифруванні переходить в С, a P2 - в C2, то P1 + P2 переходить в C1 + C2 (складання, звичайно, проводиться по модулю TV).
Нехай тепер нам відомо, що перехоплене повідомлення зашифроване застосуванням афінного відображення букв TV-літерного алфавіту. Ми хочемо визначити ключ а,Ь, щоб прочитати це повідомлення.Для цього потрібно знати, як зашифровуються якісь дві літери.
Приклад 3. Як і раніше використовуємо 26-літерний алфавіт. Припустимо, що в шифртексті найчастіше зустрічається літера «К», а друга за літерою - «D». Розумно припустити, що ними зашифровані дві літери англійської мови «Е» і «Т», що найчастіше зустрічаються. Замінюючи літери їх числовими еквівалентами і підставляючи останні формулу дешифрування, отримуємо:
10а' + b' = 4 (mod 26), За + Ъ' = 19 (mod 26).
ГЛ. ІІІ. КРИПТОГРАФІЯ
Ми маємо два порівняння з двома невідомими а та b'. Найкоротший спосіб рішення - відняти одне порівняння з іншого, щоб виключити Ь'. Отримуємо Ia = 11 (mod 26) та а = 7-111 = 9 (mod 26). Нарешті, знаходимо b , підставивши це значення а одне з порівнянь: b' = 4 —10а' = 18 (mod 26). Отже, повідомлення можна дешифрувати застосуванням формули P = 9С + 18 (mod 26).
З лінійної алгебри відомо, що рівнянь дозволяють визначити невідомих тільки тоді, коли ці рівняння незалежні (тобто коли визначник системи відмінний від нуля). Наприклад, у разі двох рівнянь із двома невідомими це означає, що прямолінійні графіки рівнянь перетинаються в одній точці (не паралельні). У нашому випадку при спробі провести криптоаналіз афінної системи на базі інформації про дві найбільш часто зустрічаються літери шифртексту може виявитися, що два порівняння не можуть бути однозначно дозволені щодо а і b.
Приклад 4. Нехай є відрізок шифртексту, отриманого застосуванням афінного перетворення 28-літерного алфавіту, що містить літери A-Z, пропуск і знак ?, причому літери мають чисельні еквіваленти 0-25, пропуск = 26, ? = 27. Нехай частотний аналіз показав, що найчастіше у шифртексті зустрічаються «В» та «?» (У зазначеному порядку).Оскільки найчастішими літерами в англійському письмовому тексті в такому 28-літерному алфавіті є пробіл і "Е" (у зазначеному порядку), ми припускаємо, що пробіл при шифруванні переходить у "В", а "Е" - в "?". Це призводить до двох порівнянь a - b' = 26 (mod 28), 27а' + b' = 4 (mod 28). Віднімаючи одне з іншого, отримуємо 2а' = 22 (mod 28), що еквівалентно порівнянню а = 11 (mod 14). Це означає, що а = 11 або 25 (mod 28), а тоді b'
15 або 1 (mod 28) відповідно. Обидва допустимі афінні перетворення HC + 15 і 25С -f- 1 дають пробіл і «Е» як літери відкритого тексту, що відповідають «В» і «?» відповідно. Тепер можна випробувати обидві можливості та визначити, який варіант дає осмислене повідомлення. А можна продовжити частотний аналіз. Нехай «I» — третя за частотою народження шифртексту. Використовуючи той факт, що «Т» — третя за частотою літера англійської мови (з наших 28 літер), отримуємо третє порівняння 8а' + b' = 19 (mod 28). Ця додаткова інформація достатня для того, щоб вибрати із двох афінних відображень правильне: ПС + 15. Попередня 34 35 36 37 38 39 .. 125 >> Наступна