Злам XOR із повторюваним ключом

Це офіційний початок, зараз!

Цей виклик концептуально не дуже складний, але він передбачє фактичне кодування схильне до помилок. Інші виклики у цьому наборі тут для того щоб ви набрали швидкості. Оцей потрібен для того щоб кваліфікувати вас. Ящо ви зможете зробити його, ви мабуть впораєтесь до набору 6.

Ось туточки файл. Він переведений у base64 після шифрування із XOR із повторюваним ключом.

Розшифруйте його.

Ось як:

  1. Нехай KEYSIZE буде вгадана довжина(be the guessed length) ключа; спробуй значення від 2 до (скажемо) 40.
  2. Напиши функцію для розрахунку відстань редагування/відстань Хемінга між двома рядками. Відстань Хемінга це лише кількість відмінних біт. Відстань між: 
    this is a test

    та

    wokka wokka!!!

    дорівнює 37. Будьте впевнені що ваш код згоден перед тим як продовжувати.

  3. Для кожного KEYSIZE, взяти першу KEYSIZE кількість байтів, і другу KEYSIZE кількість байтів, і знайти відстань редагування між ними. Нормалізуйте результат розділівши на KEYSIZE.
  4. KEYSIZE із наймешною нормалізованою відстанню редакгування найімовірніше ключ. Ви можете продолжити продовжити мабуть із найменшими 2-3 значеннями KEYSIZE. Або брати 4 блока KEYSIZE змість 2 та усреднити відстань.
  5. Зараз ви мабуть знаете KEYSIZE: розбийте шифр на блоки довжиною KEYSIZE.
  6. Зараз транспонуйте блоки: сробите блок із першого байта кожного блоку, і блок із другим байтом кожного блоку і так далі.
  7. Вірішіть кожен блок наче він односимволний XOR. У вас вже є код для цього.
  8. Для кожного блока, однобайтний XOR ключ який зробить найкращ вигладаючу гістограму це ключовий байт повторюемого ключа для XOR для цього блоку. Поєднайте їх і у вас буде ключ.

Цей код буд дивовижно корисним пізніш. Злам повторюємого ключа XOR (“Vigenere”) статистично академічне завдання, штука із “Crypto 101”. Але більше людей “знають як” зламати його, ніж насправді зламували його, і аналогічні техніки ломають щось набагато важливіше.

Ні. це не помилка.

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