ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1236. Decoding Task

Can anyone explain me the meaning of the problem in Russian???
Please, send to snipious@mail.ru!!!
Re: Can anyone explain me the meaning of the problem in Russian???
I think the problem is easy, but I cannot understand it!!!
Re: Can anyone explain me the meaning of the problem in Russian???
Posted by Slam [Tartu U] 9 Jan 2007 08:24
В ближайшем будущем любое исследование и публикация о криптографии будет вне закона повсюду в мире национальных организаций безопасности. Причина для этого ясна и широко принята всеми правительствами  - если литература по криптографии будет публичной как раньше, то все (даже преступники и террористы) смогут  легко использовать ее для скрытия их злонамеренных планов против национальной и международных сил безопасности.

Следовательно, публичные алгоритмы по криптографии и системы перестанут существовать и все кому нужна мощная защита для их секретов вынуждены будут изобретать собственные алгоритмы.

Корпорация ACM имеет множество участников которые стремятся изучить его торговые секреты (-хз, бред какой-то, но вроде так )).
Более того, работа для защиты их секретов осложнена тем фактом, что они вынуждениы использовать межконтинентальные линии связи которые легко подслушать, в отличии от внутренних линий АСМ которые хорошо защищены. Поэтому, АСМ
изобрела Межконтинентальный Криптографический Защитный Код (ICPC) , которым они очень гордятся, и который считается неуязвимым - никто даже не пытался взломать его еще, но это может изменится.

Группа хакеров была нанята соперничающей компанией, которая не раскрывает свое имя им, чтобы взломать код ICPC. Первым делом, они подкупили одного из программистов который написал программиное обеспечение для ICPC и изучал как ICPC работает. Оказалось, что ICPC использует очень большой ключ который есть последовательность битов сгенерированных каким-то сложным и случайным физическим процессом.

Этот ключ менятся каждую неделю и используется для зашифровки всех сообщений которые посылаются через межконтинентальные линии связи в течении этой недели. Этот программист также гордо сказал им, что ICPC это самый быстрый код в мире, потому что (благодаря очень высокой сложности генерации кода) они просто выполняют побитовое исключающее ИЛИ (XOR) между битами сообщения и ключа. То есть, i-тый бит зашифрованного сообщения Ei = Ki XOR Ci, где Ki это i-тый бит ключа и Ci это i-тый бит исходного сообщения.

Изуча принцип работы ICPC, они начали искать путь получать ключ каждую неделю, который есть единственная вещь которая недостает им для прослушивания всех межконтинентальных коммуникаций корпорации АСМ. (прослушивание межконтинентальных линий  тогда становится легкой задачей)
Попытка подкупить охрану ключа провалилась, поскольку охранников (которые имели одну из самых высокооплачиваемых профессий на тот момент) было очень дорого подкупить!

В поисках альтернативных решений , они натолкнулись на  клерка, который отправлял недельные газеты различным работникам и депортаментам. К счастью, эти газеты были посланы сразу после изменения ключа и сообщения обычно достаточно длинные для получения существенных частей ключа путем изучения оригинальных газеит и их зашифрованного кода.

Однакно, они не могли найти кого-то, кто бы раскрыл содержание газеты на неделю, потому что все рабочие были ограничены Соглашением о неразгланеии (NDA) и штраф за разглашение  любого сообщения это смерть.

Кроме того они смогли убедить этого клерка (за небольшую плату) сделать на вид невинную вещь : пока отсылаются копии газеты в корпорацию, ему нужно вставить несколько дополнительных пробелов в начало некоторых сообщений, но послать также другие копии в их оригинальном виде.

Теперь задача получения ключа становится простой и это для тебя, ты создашь программу для этого. Программе даны два ICPC сообщения, где длина первого - N битов, длина второго N + 1 битов , и второе является зашифровкой такого же сообщения как первое, но  с одним дополнительным пробелом (который представлен битом с кодом 32) в начале. Программа должна найти первые N+1 битов ключа который используется для зашифровки сообщений.


Фух блин запарило, целый роман написали)
Re: Can anyone explain me the meaning of the problem in Russian???
Спасибо огромное!!!
Re: Can anyone explain me the meaning of the problem in Russian???
Posted by Arthur 19 Mar 2007 14:40
thank you very much! :)))