Hello everyone.
Soon, On the night after the Halloween, there will be a Codeforces gym contest, named Crypto cup 1.0.
Like its name, it's a cryptography contest and for all problems, you are given some sample encryptions encrypted using a certain algorithm and you have to write a program to decrypt the given messages.
There will be 18 problems and you have 6:30 hours to solve them. I hope it will be interesting.
Problems are prepared by me (PrinceOfPersia) and tested by Damon also thanks HosseinYousefi for editing problem statements.
For practicing cryptography, we recommend SecutiryOverRide's cryptography challenges.
Also, this round needs a little Algorithm and CS knowledge.Don't forget to pay attention to problem's titles, they might be helpful ;)
Currently, problems are being prepared, so you're unable to see the contest in gym contest list yet.
Problems are in decreasing order of difficulty.
UPD: Duration has been increased by half an hour, now it's 6:30 .
UPD2: Please note that contest will be held on November 1st, because it had overlap with Shahid Beheshti University ACM.
UPD3: Now it's in the Gym contests list.
UPD4: Registration is open.
UPD5: Contest is over.
I hope you enjoyed the problems.
Congratulation to the winners who solved all the problems :
Be aware, our standard rounds are coming... ;)
Cool, crypto CTF at CF =)
Four 'C'-begin-words. Amazing!
how to patipate,can it held on webstie
gym
I hope it will be a rated event for both divisions. :D Finally I will get to code Caesar cypher(Rot13) and other cool algorithms like transposition, substitution(Monoalphabetic && Polyalphabetic) in reverse(decryption). m = D{key}(m')
It's a gym contest.None of gym contests are rated.
what are the stars near contests in gym?
Difficulty level.
CS knowledge like Counter Strike knowledge ? :D
well this will be an interesting way to get rid of my boredom(since there is a lot of time before the new contest)
the interesting picture :>
I hope the questions will be interesting too!! :)
nice,and could you put the Shahid Beheshti University ACM into the gyms too,thanks
im searching for a team is there any?
Happy Halloween :)
Перевод задач будет?
Я читал задачи — там не понадобится перевод. Начнется контест — увидишь.
very nice problem I love them !:)
ridam 2 in c0nteste2n baw....... hadeAghal nmiriDd b Sme reza...... tnks :x
please write in English you are very Rude .....!
Да-да-да! Я догнал I_love_Tanya_Romanova! Ну как догнал... Он 10 задач за полтора часа решил, а я за три... Но догнал ведь!
Я тоже так думал... :)
it was really good but the time of contest was so a lot and i resigned from coding after 2 hours
Some violet colored participant like to ask: can you give me code of N or B please ? here is code of H ;) : ...
The same :D
I_love_Hoang_Yen, kennethsnow and 135678942570 are first to get the full-score.
Congratulations!
Решил А только с помощью гугла. Скажите, неужели этот алгоритм шифрования все знают, что раз эту задачу так активно решали, или просто другие тоже гуглом пользовались? Я вот из всех задач гуглил только А, Е (ну там без этого никак), и вот сейчас пытаюсь О найти, но пожалуй там нечто иное, а я просто слеп...
A — RSA, это один из столпов современной криптографии, самый популярный алгоритм асимметричного шифрования, по крайней мере до недавнего времени (десяток лет) точно.
А я про него почему-то ничего не слышал до сего дня.
А что в O? Название задачи "0x" так и намекало на Hex, но раз в вводе 52 буквы + 10 цифр + '+', '=', '/' пытался использовать 65-ю систему счисления...
спойлер алерт.
обяснил свой подход в ←Ред.
Ну как-то так скорее: 8522285
https://en.wikipedia.org/wiki/Base64
Чтобы решать А, не обязательно было мыслить в терминах RSA. Если бы меня в этот момент спросили, как работает RSA, ответить мне было бы сложнее, чем решить эту задачу. Можно строить цепочку размышлений так, будто перед нами АСМ-задача:
Первые два числа — ключи, третий — результат. Почти наверняка это какая-то арифметическая операция; почти для всех возможных операций требуется какой-то модуль; к тому же, результат везде не больше за входные числа. Поскольку в первом примере результат больше за второе число, то если модуль и есть — то это первое число. Если есть модуль, то и делать все надо по этому модулю. Дальше, в ограничениях написано, что нужно перебрать; значит, это какая-то труднообратимая операция, иначе дали бы нормальные ограничения. Смотрим в таблицу, решают вообще все кому не лень — следовательно, операция очень-очень примитивная. Возможно что-то, что и в сторону шифрования считать сложно, но вряд ли — это ведь криптография, должно быть что-то асимметричное. Какие самые примитивные подобные действия с одним-двумя числами мы знаем? Дискретный корень/дискретный логарифм нам в помощь.
Но это уже детали — каждый решает так, как ему удобней.
What is the solution of 7th test case in task G?
zombiesaredangerous
In G, I used online anagram solver for test 5, 6, 7. Was that intended method?
Brute force + Creativity + Do a little smart was the intended method :-)
And what was the answer to test case 6?
justalittleshuffle
Problem G case 7, "use some bazinga order" we (non-native speaker) just guess it is an amazing answer. :-)
can somebody tell, how to solve N?
** spoiler alert **
If you really want to see solution, click on Rev until you see it.
Thanks, I observed it for 1 hour and didn't find it:( Then I left this contest.
I don’t understand how you can just guess the 12 unknown patterns.
Spoiler (See Revisions)
Sorry, I don’t see what you’re talking about. You’re just reciting the input data and saying “look, there’s a pattern”, which is not very helpful. There certainly is a pattern (as I describe in my answer), but you don’t even attempt to explain what it is. As for this particular thread, my very point is that finding a pattern is, you know, a bit different from guessing.
In this contest you sometimes just had to use your intuition and make educated guesses. Also see other tasks like L or G. Most of the sequence here was known and a good guess for the pattern was +1 +7 +1 +7 +1 ...
spoiller alert
from test cases, you can see a pattern going on. for instance, 0 is a, 8 is c, 16 is e, 17 is f, 25 is 5, 4 is i... and so on.
Permute the bits in each number and treat it as an alphabet index.
The first thing to notice is that the numbers are all smaller than 32 and that the task description guarantees that they all correspond to letters. It seems that the numbers are (in some way transformed) alphabet indices.
At this point, we can compare some encoded and decoded indices. We can see that that ‘a’ is zero both encoded and decoded if you take alphabet indices to start at zero (which we can now try to assume), and in other indices bits seem to move around. We should also take a look at the problem name: it seems like it has the first letter in the middle… in fact, it seems like all the letters are shuffled.
Together, this leads to the guess that perhaps the encryption just permutes the bits in the binary representation of the index. This permutation can be reconstructed from the sample data; a quick way is to start with the indices that have only a single bit set, namely, 4, 8 and 16 (because we can immediately see where the permutation moves that bit). We do indeed get a single permutation that holds for all of the sample data, and so the problem is solved.
The problem name is a shuffled “Permutation”.
used wordlist and regex
p[letters]{10}
to guess the word :D
In G, when I saw "lbciutrps", I immediately know that it is "strip club".. If my girlfriend knows, she would be mad ~~
I wonder why you immediately know it. Is it your favourite word? Does this word always appear in your mind? :P
What is test case #4 in problem H ? (Can't find mistake in my code/logic).
Testcase #4 for H was weird: My Python program failed when it assumed the input to be formatted exactly as specified. Only after I modified the read function to ignore whitespace did it pass. I saw that other people had the same problem (runtime error on test 4) and I asked a clarifying question, but no reaction from the judges. I feel like that testcase should have been fixed and the solutions rejudged...
My Perl program reads exactly formatted input too. Now, after I stripped lines from spaces + ignored empty lines, my code got AC too.
Ah, so that was the problem! I rewrote my Python solution in C.
Actually, my Python implementation should tolerate whitespace on lines… Were the lines split incorrectly? Edit: right; it seems from your comments that there were empty lines.
Thank you for the problems.
I see that some participants (including me) have problems with H's test 4. What is that specific about it?
It's completely random :D
Can't you agree that test #4 is incorrect? — has excessive input which is not defined in the section "input"? Empty lines they are. Can't you agree that there exist some test cases which has a statement's logic collision? If take first line of input twenty six zeroes, then 1) if follow "input" section — there must follow zero lines, 2) if follow upper statement — then there must follow more than zero lines. If contestant strictly follows what is written in "input" section, he knows how much lines must input include, and he can read all lines till the end of input file. If there are excessive — non declared lines — it's obvious that they can affect result of program. Others, who read not all lines of input, for example if they count from the first input line how much lines should follow, then use only them, but not use lines which follows later and which are not declared.
How to solve M?
Letters with odd ASCII -> 191 - theirnumberinalphabet
Letters with even ASCII -> 189 - theirnumberinalphabet
Spoiler on revisions and code on ideone (http://ideone.com/G14Imp)
XOR each byte with 222.
One of the common symbols used to denote XOR in mathematics is the circled plus
, which is hinted at in the problem name. (In fact, the TeX code for 
is literally
\oplus.) The value 222 is easily determined from the sample data.In many programming languages including C, C++, C#, D, Java, Python, Ruby, Perl, PHP and JavaScript, XOR is performed by the
^operator. Some others, such as Pascal and Haskell, provide anxorkeyword or function.Is any editorial-like thing available?
Interseting contest indeed. Without teammates,after solving 11 problems,I got stuck and went to bed(so sad) Will there be official/unofficial Editorial for this contest?
why we can't see others code for the problems that we didn't solve?
...i want to learn something new..
Funny contest!
Will there be Crypto Cup 2.0 in the future?
Sure !
next Halloween?!
Maybe !
theme of the contest — search (binary? ternary? Web!)
Can someone provide some hint on how to use the tree from task P to decode? I can construct the tree from the Prufer sequence but not finding how to use that information to transpose the string.
Root the tree (root is vertex 1), then sort the adjacency list of each vertex in increasing order.Then assign a character to each vertex of the tree, one by one using DFS (by starting time), ci is the character assigned to vertex i (Find the DFS order of the tree and call it b1, b2, ..., bn, so cbi = si). Then find BFS order of the tree (first all vertexes of first level, the second level,...), it is p1, p2, ..., pn. Answer is : cp1cp2...cpn .
Finally your standard round is coming!