eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

В ближайшем будущем какие-либо исследования и публикации о криптографии будут признаны во всем мире вне закона по соображениям национальной безопасности. Рассуждения эти ясны и широко признанны всеми правительствами - если криптография станет достоянием общественности, как в старые времена, то все (даже преступники и террористы) смогут легко использовать её, чтобы скрыть свои вредоносные планы от национальных и международных сил безопасности. Следовательно, публикация криптографических алгоритмов и систем, перестанет существовать, и все, кто нуждается в сильной защите своих секретов, будут вынуждены изобретать собственные алгоритмы. ACM Корпорация имеет множество конкурентов, которые хотят узнать её тайны. Кроме того, работа по защите своих секретов осложняется тем, что они вынуждены использовать межконтинентальные линии связи, которые легко подслушать, в отличие от внутренних линий ACM корпорации, которые хорошо охраняются. Таким образом, ACM корпорация придумала Интерконтинентальный Код Криптографической Защиты (ИККЗ), которым они очень гордятся, и который считается очень крепким - никто даже попытался сломать его, но это скоро изменится. Группа хакеров была нанята конкурирующей компанией, которая не раскрывает свое название, чтобы украсть ИККЗ. В качестве первого шага, они подкупили одного из программистов, который разрабатывает программное обеспечение для ICPC и узнали, как ИККЗ работает. Оказывается, ИККЗ использует очень длинный ключ, который представляет собой последовательность байтов, порождаемых некоторыми сложными и случайными физическими процессами. Этот ключ меняется раз в неделю и будет использоваться для шифрования всех сообщений, которые отправляются по межконтинентальным линиям связи в течение недели. Это программист также с гордостью сказал им, что ИККЗ является самым быстрым кодом в мире, так как (имея в виду сложную систему генерации кода), они просто выполняют побитовое исключающее ИЛИ (XOR) как операцию между байтами сообщения и ключа. То есть, \textbf{i}-ый байт зашифрованного сообщения \textbf{E_i = K_i XOR C_i}, где \textbf{K_i} - байт ключа и \textbf{C_i} - байт исходного сообщения открытым текстом. \includegraphics{https://static.e-olymp.com/content/07/0713d21c5a916db679f68fc7acede748fcfffe0e.jpg} Узнав, как ИККЗ работает, они начали искать способ надежного получения ключа каждую неделю, это единственная вещь, которой всё еще не хватает для прослушивания всех межконтинентальных связей ACM корпорации (перехват сообщений на межконтинентальных линиях действительно оказалось непростой задачей). Попытка подкупа сотрудников службы охраны, которые охраняют и распространяют ключ не удалась, так как сотрудники службы безопасности (имеющие по долгу своей профессии одну из самых высоких зарплат того времени) оказались слишком дорогими для взятки. Во время поиска альтернативных решений, они наткнулись на клерка, который посылает еженедельные бюллетени для различных сотрудников и отделов. К счастью, эти бюллетени были отправлены только после смены ключа и сообщения идут, как правило, достаточно долго, чтобы было время восстановить достаточно частей ключа для изучении оригинальных информационных бюллетеней в их закодированной форме. Однако, они не могли тайно найти человека, который будет раскрывать содержание бюллетеня на еженедельной основе, потому что все сотрудники были связаны Соглашением о Неразглашении Информации (СНИ) и наказание за разглашение любых корпоративных сообщений в соответствии с этим СНИ - это смерть. Тем не менее, они были в состоянии убедить этого клерка (за небольшое вознаграждение), чтобы сделать, казалось бы, невинные вещи. То есть, при отправке копии бюллетеня всей корпорации, ему было поручено, чтобы вставлять дополнительный символ пробела в начале некоторых сообщений, но отправлять другие копии в их первоначальном виде. Теперь задача восстановить ключ является простой для вас, и вам нужно написать для этого программу. Программа получает два ИККЗ сообщения, в которых первое сообщение из \textbf{N} байт, а второе из \textbf{N+1} байта, и является результатом кодирования того сообщения открытым текстом, что и первое, но с одним дополнительным пробелом (представляется байтом с десятичным значением \textbf{ 32}) в начале. Программа должна найти первые \textbf{N+1} байт ключа, который был использован для кодирования сообщений. \InputFile Входные данные состоят из двух строк. Первая строка состоит из \textbf{2N} символов и представляет собой закодированное сообщение из \textbf{N} байт. Вторая строка состоит из \textbf{2N+2} символов и представляет собой закодированное сообщение из \textbf{N+1} байта. Здесь \textbf{1} ≤ \textbf{N} ≤ \textbf{10000}. Каждое сообщение записывается в одну строку в шестнадцатеричной форме байт за байтом без пробелов. Каждый байт сообщения представлен ​​двумя символами '\textbf{0}'- '\textbf{9}', '\textbf{А}'-'\textbf{F}', которые представляют шестнадцатеричное значение соответствующего байта. Ввод продолжается до конца файла. \OutputFile Вывести в выходной файл одну строку, которая представляет собой \textbf{N+1} байт восстановленного ключа в шестнадцатеричном формате так же, как и в исходном файле.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 32 MiB
Giriş verilənləri #1
05262C5269143F314C2A69651A264B
610728413B63072C52222169720B425E
Çıxış verilənləri #1
41434D2049435043204E454552432732
Müəllif Елена Крючкова
Mənbə 2002-2003 ACM Northeastern European Regional Programming Contest