Problem D
Insecure in Prague
—- The 2004 ACM Programming Contest World Finals —-

Prague is a dangerous city for developers of cryptographic schemes. In 2001, a pair of researchers in Prague announced a security flaw in the famous PGP encryption protocol. In Prague in 2003, a flaw was discovered in the SSL/TLS (Secure Sockets Layer and Transport Layer Security) protocols. However, Prague’s reputation for being tough on cryptographic protocols hasn’t stopped the part-time amateur cryptographer and full-time nutcase, Immanuel Kant-DeWitt (known to his friends as “I. Kant-DeWitt”), from bringing his latest encryption scheme to Prague. Here’s how it works:
 「プラハは暗号開発者にとって厄介な都市。2001年、研究者ペアがプラハで、有名なPGP暗号プロトコルにセキュリティ脆弱性のあることを公表した。2003年プラハで、SSL/TLS (セキュアソケットレイヤとトランスポートレイヤセキュリティ)の脆弱性が見つけられた。しかし、暗号プロトコルの不幸に対するプラハの評判があっても、アマチュア暗号開発者であり、奇人であるImanuel Kant-DeWitt(仲間ではI. Kant-DeWittとして知られている)が自分の開発した最新の暗号をもってプラハにやってきた。その詳細は以下の通り。」

A plain text message p of length n is to be transmitted. The sender chooses an integer m >= 2n, and integers s, t, i, and j, where 0 <= s, t, i, j < m and i < j. The scheme works as follows: m is the length of the transmitted ciphertext string, c. Initially, c contains m empty slots. The first letter of p is placed in position s of c. The kth letter, k >= 2, is placed by skipping over i empty slots in c after the (k-1)st letter, wrapping around to the beginning of c if necessary. Slots already containing letters are not counted as empty. For instance, if the message is PRAGUE, if s = 1, i = 6, and m = 15, then the letters are placed in c as follows:
 「長さnの平文テキストメッセージpを送ろうとする。送信者は整数m (m>=2n)、及び整数 s, t, i, j (0 <= s, t, i, j < m、i < j) を選ぶ。仕組みはこうは。mは送られた暗号文字列cの長さ。初期状態では、cにm個の空スロットを含む。pの最初の文字はcの位置sに置く。k (k >= 2) 番目の文字は、k-1番目の文字からi個の空スロットをスキップしたところに置く。必要であれば、cの先頭に戻ってもよい。文字の入ったスロットは空スロットとしてはカウントしない。例えば、メッセージがPRAGUEだとして、s = 1, i = 6, m = 15とすると、各文字はcに次のように置くことになる。」

Starting with the first empty slot in or after position t in string c, the plain text message is entered again, but this time skipping j empty slots between letters. For instance, if t = 0 and j = 8, the second copy of p is entered as follows (beginning in position 2, the first empty slot starting from t = 0):
 「文字列cについて、位置tのところ(そこが空スロットでなければそれ以降)の最初の空スロットから、平文テキストメッセージをもう一度入れる。ただし、今回は文字間の空スロットj個をスキップことにする。例えば、t = 0、j = 8とすると、pの2回目のコピーは以下になる(t=0からの最初の空スロットである、位置2より始まる)。」

Finally, any remaining unfilled slots in c are filled in with randomly chosen letters:

Kant-DeWitt believes that the duplication of the message, combined with the use of random letters, will confuse decryption schemes based upon letter frequencies and that, without knowledge of s and i, no one can figure out what the original message is. Your job is to try to prove him wrong. Given a number of ciphertext strings (and no additional information), you will determine the longest possible message that could have been encoded using the Kant-DeWitt method.
 「ランダムに文字が組み込まれたメッセージの2重化によって、文字の出現頻度に基づく解読や、sとiの知識がなしに元の文字列を知ることはできないとKant-DeWitt believesは信じているが、彼の間違いを証明してほしい。複数の暗号文字列に対し、追加情報なしに、Kant-DeWitt方式で暗号化された最長のありうる文字列を決めて欲しい。」

A number of ciphertext strings, one per line. Each string will consist only of upper case alphabetic letters, with no leading or trailing blanks; each will have length between 2 and 40. Input for the last test case is followed by a line consisting of the letter X.

For each input ciphertext string, print the longest string that could be encrypted in the ciphertext. If more than one string has the longest length, then print “Codeword not unique”. Follow the format of the sample output given below.
 「各暗号文字列に対し、その文字列に暗号化された最長文字列を表示すること。同じ長さの文字列が複数ある場合、”Codeword not unique”と表示すること。サンプル出力のフォーマットに従うこと。」

Sample Input

Output for the Sample Input
Code 1: PRAGUE
Code 2: Codeword not unique
Code 3: Codeword not unique

Comments are closed.

Post Navigation