eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Задача розшифровки

Задача розшифровки

Ліміт часу 1 секунда
Ліміт використання пам'яті 32 MiB

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

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

Група хакерів була найнятя компанією конкурентом, яка не розкриває своєї назви, щоб викрасти ІККЗ. У якості першого кроку, вони підкупили одного із програмістів, який розробляє програмне забезпечення для ICPC і взнали, як ІККЗ працює. Виявляється, ІККЗ використовує дуже довгий ключ, який являє собою послідовність байтів, породжуваних деякими складними і випадковими фізичними процесами. Цей ключ змінюється раз на тиждень і буде використовуватись для шифрування усіх повідомлень, які відправляються по міжконтинентальним лініям зв'язку протягом тижня. Цей програміст також з гордістю повідомив їм, що ІККЗ є найшвидшим кодом у світі, так як (мається на увазі складна система генерації коду), вони просто виконують побітове виключне АБО (XOR) як операцію між байтами повідомлення і ключа. Тобто, i-ий байт зашифрованого повідомлення E_i = K_i XOR C_i, де K_i - байт ключа а C_i - байт початкового повідомлення відкритим текстом.

Взнавши, як ІККЗ працює, вони почали шукати спосіб надійного отримання ключа кожен тиждень, це єдина річ, якої все ще не вситачає для прослуховування усіх міжконтинентальних зв'язків ACM корпорації (перехоплення повідомлень на міжконтинентальних лініях дійсно виявилось складною задачею). Спроба підкупу працівників служби охорони, які охороняють і поширюють ключ не вдалась, так як співробітники служби безпеки (які мають із-за специфіки своєї професії одну із самих високих зарплат того часу) виявились занадто дорогими для підкупу.

Під час пошуку альтернативних рішень, вони наштовхнулись на клерка, який розсилає щотижневі бюлетені для різних співробітників та відділів. На щастя, ці бюлетені було відправлено лише після зміни ключа а повідомлення йдуть, як правило, достатньо довго, щоб був час відновити достатньо частин ключа для вивчення оригінальних інформаційних бюлетенів у їх закодованій формі. Проте, вони не могли тайно знайти людину, яка буде розкривити зміст бюлетеня на щотижневій основі, тому що всі спіробітники були пов'язані Угодою про Нерозголошення Інформації (УНІ) і покарання за розголошення довільних корпоративних повідомлень у відповілності з цим УНІ - це смерть.

Тим не менше, вони були у змозі переконати цього клерка (за невелику винагороду), щоб зробити, здавалось би, невинні речі. Тобто, при відправці копії бюлетеня усій корпорації, йому було доручено, щоб вставляти додадковий символ пропуску на початку деяких повідомлень, але відправляти інші копії у їх початковому виді. Тепер задача відновити ключ є простою для вас, і вам потрібно написати для цього програму. Програма отримує два ІККЗ повідомлення, у яких перше повідомлення з N байт, а друге з N+1 байта, і є результатом кодування того ж повідомлення відкритим текстом, що і перше, але з одним додатковим проруском (подається байтом з десятковим значением 32) на початку. Програма повинна знайти перші N+1 байт ключа, який було використано для кодування повідомлень.

Вхідні дані

Вхідні дані складаються з двох рядків. Перший рядок складається з 2N символів і являє собою закодоване повідомлення з N байт. Другий рядок складається з 2N+2 символів і являє собою закодоване повідомлення з N+1 байту. Тут 1N10000. Кожне повідомлення записано у одному рядку в шістнадцятковій формі байт за байтом без пропусків. Кожен байт повідомлення подано ​​двома символами '0'-'9', 'А'-'F', які подають шістнадцяткове значення відповідного байту.

Вхідіні дані продовжуються до кінця файлі.

Вихідні дані

Вивести у вихідний файл однин рядок, який являє собою N+1 байт відновленого кюча у шістнадцятковому форматф так само, як і у вхідному файлі.

Приклад

Вхідні дані #1
05262C5269143F314C2A69651A264B
610728413B63072C52222169720B425E
Вихідні дані #1
41434D2049435043204E454552432732
Автор Олена Крючкова
Джерело 2002-2003 ACM Northeastern European Regional Programming Contest